26. Булева алгебра

Нехай задане деяка множина М и набір операцій Ф, виконуваних на цій множини: Ф = {₁, ₂,..., _n}, тоді двійка множин А = (М, Ф) називається алгеброю. Множина М називається основною чи несущєю множиною. Множина Ф називається сигнатурою операцій чи просто сигнатурою.

Визначення: Булєвою алгеброю В = (М,  ,  0, 1) називається множина М с двома бінарними операціями “” і “”, однією унарною операцією інверсії “” у сигнатурі і двома відзначеними елементами (універсальними границями) “0” і “1”, причому для будь-яких x₁, x₂, x₃, що належать множині M, набір операцій задовольняє наступним тотожностям:

Основні тотожності булєвої алгебри

1. x₁x₂=x₂x₁; x₁x₂=x₂x₁; комутативність

2. x₁(x₂x₃)=(x₁x₂)x₃; x₁(x₂x₃)=(x₁x₂)x₃; асоціативність

3. x₁(x₂x₃)=(x₁x₂)(x₁x₃); x₁(x₂x₃)=(x₁x₂)(x₁x₃); дистрибутивність;

4. x₁0=0; x₁0=x₁; x₁1=x₁; x₁1=1; 0=1; 1=0;

універсальні границі;

5. x₁x₁=x₁; x₁x₁=x₁; ідемпотентність;

6. x₁x₁=0; x₁x₁=1; (x)=x; доповнення і інволютивність

7. x₁(x₁x₂=x₁; x₁(x₁x₂)=x₁; поглинання;

8. (x₁x₂)(x₁x₂)=x₁; (x₁x₂)(x₁x₂)=x₁; склеювання;

9. x₁(x₁x₂)=x₁x₂; x₁(x₁x₂)=x₁x₂; (x₁x₃)(x₂x₃)= (x₁x₃)(x₂x₃)= =(x₁x₃)(x₂x₃)(x₁x₂); =(x₁x₃)(x₂x₃)(x₁x₂);

Блейка-Порецького

10. (x₁x₂)=x₁x₂; (x₁x₂)=x₁x₂; де Моргана

Крім десяти основних тотожностей необхідно визначити теореми розкладання (11, 12) і теореми підстановки(13-16), що можуть скоріше привести до мінімальної формули:

11. f(x₁, x₂,…, x_i,…, x_n)=(x_if(x₁, x₂,…,1,…, x_n))(x_i f(x₁, x₂,…, 0,…, x_n));

12. f(x₁, x₂,…, x_i,…, x_n)=(x_if(x₁, x₂,…, 0,…, x_n))(x_if(x₁, x₂,…, 1,…, x_n))

13. x_if(x₁, x₂,..., x_i,x_i,..., x_n)=x_if(x₁, x₂,..., 1, 0,..., x_n);

14. x_if(x₁, x₂,..., x_i,x_i,..., x_n)=x_if(x₁, x₂,..., 0, 1,..., x_n);

15. x_if(x₁, x₂,..., x_i,x_i,..., x_n)=x_if(x₁, x₂,..., 0, 1,..., x_n);

16. x_if(x₁, x₂,..., x_i,x_i,..., x_n)=x_if(x₁, x₂,..., 1, 0,..., x_n)

Для доказу тотожностей можна використовувати метод зіставлення таблиць істинності лівої і правої частини тотожностей – досить переконатися в однакових значеннях на відповідних наборах аргументів.

Інший метод заснований на еквівалентних перетвореннях з використанням доведених раніше тотожностей булєвої алгебри.

Приклад: а) Идемпотентность (збереження ступеня):

хх=(хх)1=(хх)(хх)=х(хх)=х0=х;

б) Поглинання:

хху=(х1)(ху)=х(1y)=x 1=х

в) Блейка-Порецького:

хху=(хх)(ху)=1(хy)=хy

Спрощення запису формул

З таблиці булєвих функцій від двох перемінних можливо побачити, що між функціями мається залежність у_і=y_15-i ,де 0  і  15. На підставі цього можна записати співвідношення:

для констант:

0=1 і 1=0

для БФ від однієї перемінної:

х= (х)

для БФ від двох перемінних:

х₁х₂=(х₁х₂); х₁х₂=(х₁+х₂); х₁х₂=(х₁х₂); х₁х₂=(х₁х₂); х₁х₂=(х₁+х₂); х₁х₂=х₁+х₂); х₁+х₂=(х₁х₂); х₁х₂=(х₁х₂); х₁х₂=(х₁х₂); х₁+х₂=(х₁х₂).

З приведених залежностей випливає, що будь-яка функція двох перемінних, включаючи і константи, виражається в аналітичному виді через сукупність із шести функцій, що містить заперечення і будь-які функції з зазначених пар {у₀, у₁₅, {y₁, y₁₄}, {y₂, y₁₃}, {y₄, y₁₁}, {y₆, y₉, y₇, y₈} і являющуюся надлишкової.

Легко довести, що

(х₁х₂)=х₁х₂;

(х₁х₂)=(х₁х₂)(х₁х₂)

Сукупність можливо скоротити до чотирьох функцій: константи 0”, заперечення х, диз'юнкції “x₁x₂” і коньюнкції х₁х₂. Ці чотири функції також можуть бути скорочені – із законів де-Моргана і інволютивності (подвійного заперечення).

Таким чином, виконуються тотожності:

х₁х₂=(х₁х₂);

х₁х₁=0;

(х₁х₁)=0;

х₁х₂=(х₁х₂).

Звідси випливає, що булєви функції виконуються через заперечення і конъюнкцию чи заперечення і диз'юнкцію.

Якщо в булєвої формулі перемінні зв'язані тільки одним типом операції (диз'юнкції чи кон'юнкції), то в силу асоциативністі дужки не проставляються.

Приклад: (х₁х₂)(х₃х₄)=х₁х₂х₃х₄

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

П риклад: (ху)z=xyz=(x y) z=x y z.

Двоїстість формул булевої алгебри

У булевій алгебрі має місце принцип двоїстості. Взаємно двоїстими операціями є диз'юнкція і кон'юнкція. Заміняючи в деякій формулі кожну операцію на двоїсту їй, одержуємо двоїсту формулу.

Приклад: Формула (х₁х₂)(х₃х₄) Двоїста формула (х₁х₂)(х₃х₄).

Визначення: Таблиця істинності двоїстої функції f виходить заміною значень перемінних і значень самої функції f у таблиці істинності вихідної функції f на протилежні, тобто 01, 10.

Приклад: х₁ х₂ f=x₁x₂ x₁ x₂ f^ =x₁x₂

0 0 0 1 1 1

0 1 1 1 0 0

1 0 1 0 1 0

1 1 1 0 0 0

Залишається тільки перевернути отриману таблицю для зростання значень аргументів зверху вниз.

X₁ x₂ f^ =x₁x₂

0 0 0

0 1 0

а1 0 0

1 1 1

Формула чи функція, рівносильна своєї двоїстої функції, називається самодвоїстою.

Приклад: у₁=х₁х₂х₁х₃х₂х₃ та y₂=(х₁х₂)(х₁х₃)(х₂х₃) – двоїсті і рівносильні функції, тобто y=у₁=у₂ – самодвоїста функція.

Теорема: Якщо формули f₁ чи f₂ рівносильні, то і двоїсті їм формули f₁^ і f₂^ також рівносильні, і навпаки.

F₁=f₂f₁^=f₂^

Приклад: х(ху)=х  х(ху)=х

х(ху)=ху  х(ху)=ху

Теорема: (принцип двоїстості): Якщо в булєвої формулі f замінити кон'юнкції на диз’юнкції, «0» на «1», «1» на «0», то одержимо формулу f^, двоїсту вихідної.

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