Дистрибутивні структури

Визначення 6.11. Структура називається дистрибутивною, якщо вона задовольняє властивості дистрибутивності, тобто якщо для будь-яких трьох її елементів виконані тотожності:

, . (6.4)

Критерій дистрибутивності структури: структура дистрибутивна тоді й тільки тоді, коли вона дедекиндова й не містить підструктури виду (або ізоморфної їй структури), що містить три ланцюги довжини 2 та складаються з одного елемента нульової висоти, трьох елементів одиничної висоти, одного елемента висоти 2 (рис. 6.4), тобто дистрибутивна .

Рисунок 6.4 – Структура із критерію дистрибутивності

У структурі існують елементи, для яких властивість дистрибутивності не виконується :

6.4 Ізоморфізм множин

Визначення 6.12. Множини й ізоморфні, якщо існує взаємо-однозначна відповідність і зворотна відповідність такі, що

;

.

Визначення 6.13. Упорядковані множини й ізоморфні, якщо між ними існує ізоморфізм, що зберігає порядок, тобто

,

;

інакше, ізоморфізм двох упорядкованих множин і спостерігається при взаємо-однозначній відповідності між і , коли з порівнянності прообразів випливає порівнянність їхніх образів і навпаки: із треба .

Приклад 6.4. Будь-які дві алгебри, утворені множинами й однакової потужності, ізоморфні (операції однакові, а відображення – взаємо-однозначна відповідність множин-носіїв).

Поняття ізоморфізму є одним з важливих у математиці. Його сутність можна виразити так: якщо алгебри й ізоморфні, то елементи й операції в алгебрі можна перейменувати так, що співпадає з .

Будь-яке еквівалентне співвідношення в довільній алгебрі зберігається й у будь-якій ізоморфній їй алгебрі, що дозволяє автоматично поширювати такі співвідношення у вихідній алгебрі на всі ізоморфні їй алгебри. Це дає можливість розглядати об'єкти з точністю до ізоморфізму, тобто розглядати тільки ті властивості об'єктів, які зберігаються при ізоморфізмі. Зокрема, ізоморфізм зберігає такі властивості операцій як асоціативність, комутативність, дистрибутивність.

6.5 Контрольні запитання

1. Як визначається структура?

2. Які закони визначають структуру як булеву алгебру?

3. Як формулюється властивість дедекиндовості структури?

4. Як формулюється критерій дедекиндовості структури?

5. Як визначається структура, на якій заснований критерій дедекиндовості?

6. Як визначається властивість дистрибутивності структури?

7. Як формулюється критерій дистрибутивності структури?

8. Які структури використовуються в критерії дистрибутивності?

9. Що називається інтервалом?

10. Які елементи є додатковими в структурі?

11. Які елементи є структурними нулем і одиницею?

12. Які елементи називаються зв'язаними в структурі?

13. Що таке собою структура як алгебраїчна система?

14. Як визначаються супремум та інфімум для пари порівнянних елементів?

15. Що називається ізоморфізмом множин?

16. Чим характеризується ізоморфізм упорядкованих множин?

17. Чим визначається ізоморфізм алгебр?

7 Висновки до розділу «Теорія множин»

За допомогою поняття ізоморфізму множин, а потім і алгебр, можна показати, що існує взаємо-однозначна відповідність, при якому алгебра множин Кантора ізоморфна алгебрі Буля. Це означає, що в булевій алгебрі існують аналогічні операції й об'єкти, властивості яких зберігаються при ізоморфізмі. Зокрема, ізоморфізм зберігає асоціативність, комутативність, дистрибутивність.

Таким чином, теорія множин дозволила чітко сформулювати поняття ізоморфізму систем об'єктів, заданих разом з об’єднувальними їхніми відношеннями, і призвела до розуміння тієї обставини, що кожна математична теорія в її чистій абстрактній формі вивчає ту чи іншу систему об'єктів
“з точністю до ізоморфізму”, тобто може бути без змін перенесена на будь-яку систему об'єктів, ізоморфну тій, для вивчення якої вона була спочатку створена.

8 Позначення до розділу «Теорія множин»

Символ	Розшифровка
	Відношення приналежності. Приналежність об'єкта множині позначається за допомогою символу
	Не належить:
	Нестроге включення
	Строге включення
	Булеан (множина всіх підмножин) множини М
U	Універсальна множина (універсум)
	Порожня множина
	Потужність множини М
	Алгебра, де – носій, – сигнатура (набір операцій)
	Алгебра множин Кантора, де носій – сукупність множин, сигнатура – набір теоретико-множинних операцій
– (або )	Операція теоретико-множинного доповнення
	Операція теоретико-множинного перетинання
	Операція теоретико-множинного об'єднання
	Операція теоретико-множинної різниці
	Операція симетричної різниці множин
	За визначенням (від англ. definition – визначення)
	Сукупність елементів таких, що
	Наслідок (символ наслідку)
	Рівносильно (тоді й тільки тоді)
	Квантор спільності (для кожного, для всіх)
	Квантор існування (існує)
	Не існує
	Існує і єдиний
	-мірний вектор (кортеж), де – координати або компоненти вектора.
	Упорядкована пара або вектор розмірності два
	Проекція вектора на i-у вісь (i-а координата)
	Проекція множини векторів на -у вісь
	Операція декартова (прямого) добутку множин; операція розширеного декартова добутку відношень
	Декартова ступінь множини
	Ін’єктивність (властивість ін’єктивності)
	Сур’єктивність (властивість сур’єктивності)
	Бієкція (властивість бієктивної або взаємо-однозначної відповідності)
	Відповідність із множини до множини
	Зворотна до відповідність
	Композиція функцій і
	Відношення ступеня n (n-арне або n-місцеве відношення), задане на множині
	Бінарне відношення на множині
	Тернарне відношення на множині
	Реляційна алгебра (алгебра відношень), де носій – сукупність відношень, сигнатура – набір операцій над відношеннями
	Проекція бінарного відношення на множину (домен)
	Проекція n-арного відношення на множини (домени)
	Елементи та перебувають у відношенні :
	Граф бінарного відношення, де – носій графа (множина вершин), – сигнатура графа (множина дуг) ;
	Окіл одиничного радіуса елемента
( або )	Фактор-множина множини за бінарним відношенням R
	Бінарне відношення еквівалентності
	Елемент еквівалентний елементу при заданому бінарному відношенні еквівалентності
	Клас еквівалентності елемента
	– розбивка множини
	Відношення нестрогого порядку
	Відношення строгого порядку
	Множина із бінарним відношенням порядку (упорядкованості)
	Порівнянність елементів в упорядкованій множині ( порівняний з )
	Супремум
	Інфімум
(або )	Зворотне відношення до бінарного відношення
	Висота елемента впорядкованої множини
	Довжина впорядкованої множини

9 Основні поняття булевої алгебри

9.1 Логічні операції й логічні функції

Визначення 9.1. Логічна (булева) змінна – така величина , що може приймати тільки два значення (нуль або одиниця / неправда або істина): .

Визначення 9.2. Логічна (булева або функція алгебри логіки – ФАЛ) є функція від булевих змінних, що приймає значення 0 або 1:

.

Змінні булевої функції утворюють набори з нулів і одиниць. Такі набори називаються двійковими й розглядаються як кінцеві впорядковані послідовності, на яких задана булева функція.

Булева функція від n змінних визначена на двійкових наборах.

Перехід від десяткової до двійкової системи числення здійснюється відомим способом шляхом розподілу числа з десяткової системи на два. Наприклад, числу 6 у десятковій системі відповідає (1, 1, 0) у двійковій: .

Кожному двійковому набору відповідає його десятковий еквівалент або порядковий номер (табл. 9.1 – 9.3).

Таблиця 9.1 – Двійкові набори для

булевої функції від двох змінних

Таблиця 9.2 – Двійкові набори для булевої функції від трьох змінних

Таблиця 9.3 – Двійкові набори для булевої функції від чотирьох змінних

У булевій алгебрі мають місце основні логічні операції – інверсія, кон’юнкція, диз’юнкція, а також імплікація, еквівалентність, сума за модулем два (табл. 9.4).

Таблиця 9.4 – Логічні операції

Назва	Позначення	Читання
Диз’юнкція (логічне додавання)	(+)	x АБО y
Кон’юнкція (логічне множення)	(&, •)	x И y
Інверсія (заперечення)	– ()	НЕ x
Імплікація		x ТЯГНЕ y
Еквівалентність	~	x еквівалентно y
Сума за модулем 2 (виключне АБО чи XOR)		x сума за модулем 2 y

Як і в арифметичному множенні, символ кон’юнкції часто опускається: або .

Кожній логічній операції відповідає логічна функція з однойменною назвою. Оскільки логічні операції є бінарними, крім інверсії, яка є унарною, для їхнього завдання необхідні дві змінні, тобто кожна функція має бути визначена на 4-х двійкових наборах. Логічні функції задаються за допомогою таблиць істинності, які є правилами їхнього обчислення (табл. 9.5).

Таблиця 9.5 – Таблиці істинності для елементарних булевих функцій

З табл. 9.5 видно, що:

1. Кон’юнкція приймає нульове значення, якщо серед співмножників є хоча б один нуль, і єдине одиничне значення – на наборі з одиниць. Цей підхід можна поширити на добуток змінних:

(9.1)

2. Диз’юнкція приймає єдине нульове значення, якщо всі доданки дорівнюють нулю, і одиничне значення, якщо серед доданків є хоча б одна одиниця, тобто для функції від змінних є правильним:

(9.2)

3. Два однакових компоненти еквіваленти, а два різних – ні.

4. Сума за модулем два обертається на нуль, якщо доданки – два однакових компоненти, і дорівнює одиниці – при додаванні двох різних компонентів.

5. Функція імплікація приймає єдине нульове значення, коли 1 тягне (спричиняє) 0.

6. Сума за модулем два та еквівалентність – взаємно зворотні один одному, тобто , .

Функції можуть бути представлені через операції за допомогою формул переходу:

, (9.3)

, (9.4)

. (9.5)

Пріоритет виконання операцій визначається дужками в логічному виразі, яким представлена функція. Якщо не зазначено інакше, операції виконуються в такому порядку: 1) інверсія, 2) кон’юнкція, 3) диз’юнкція.

За допомогою таблиць істинності можна знаходити значення булевих функцій. При цьому треба логічний вираз, яким задана функція, розбити на елементарні операції (унарну та бінарні), і потім обчислити їх послідовно відповідно до порядку їхнього виконання.

Приклад 9.1. Скласти таблицю істинності для функції

.

Розв’язок. Потрібно скласти таблицю істинності для функції від трьох змінних. Вона визначена на стандартних двійкових наборах (див. табл. 9.2). Порядок обчислення функції встановлений дужками й буде таким: (табл. 9.6).

Таблиця 9.6 – Обчислення функції