Х1×х2=ù(`х1Ú`х2).

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

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

Приклад. (х₁Úх₂)Ú(х₃Úх₄)=х₁Úх₂Úх₃Úх₄

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

Приклад. ù (хÚу)×z=xÚy×z=(`x `y) z=`x `y z.

24.3. Подвійність формул булевої алгебри

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

Приклад. Формула (х₁Úх₂)×(х₃Úх₄)
Подвійна формула (х₁×х₂)Ú(х₃Úх₄).

Визначення. Таблиця істинності подвійної функції 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 0 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^Ú, подвійну вихідної.

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

24.4. Булева алгебра множин

Поняття булевої алгебри носить більш загальний характер, ніж тільки булева алгебра на множини функцій. Алгебра із сигнатурою типу (2, 2, 1), де тип задає арність операцій над булевими функціями, називається булевою алгеброю, якщо її операції задовольняють тотожностям 1 - 10.

Нехай задана деяка множина М.

Визначення. Алгебра А=(В(М), {È, Ç ,ù} називається булевою алгеброю множин над множиною М, тип булевої алгебри множин - (2, 2, 1).

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

Нехай визначена взаємно однозначна відповідність між множиною В(М), де М={m₁, m₂,..., m_n} і множиною двійкових векторів Вn
розмірності n: G: В(М)ÛВn

Підмножині М¢ÍМ відповідає двійковий вектор b=(b₁,b₂,.., b_n), де b_i=1, якщо m_iÎM¢, і b_i = 0, якщо m_iÏM¢ для деякого m_iÎM.

Нехай на множини двійкових векторів Вn визначена булева алгебра вигляду: А¢=(Вn,{Ú, Ù, ù}, при цьому операції для будь-яких векторів s=<s₁, s₂,..., s_n> і t=<t₁, t₂,..., t_n> визначаються в такий спосіб:

1. sÚt=<s₁Út₁, s₂Út₂,..., s_nÚt_n>

2. sÙt=<s₁Ùt₁, s₂Ùt₂,..., s_n Ùt_n>

3. `s=<`s₁,`s<sub>2</sub>,..., `s_n>.

Операції над векторами s і t називаються порозрядними логічними операціями над двійковими векторами.

Приклад. s=10110; t=00101;

sÚt=10111; `s=01001;

sÙt=00100; `t=11010.

Порозрядні операції входять до складу системи команд будь-якої ЕОМ, що спрощує реалізацію даної алгебри на ЕОМ.

Ця алгебра ізоморфна булевій алгебрі множин, це дозволяє замінити теоретико-множинні операції об'єднання, перетинання, доповнення над системами множин порозрядними логічними операціями над двійковими векторами, реалізованими на ЕОМ: G: АÞA¢, G^-1: А¢ÞA.

Приклад. М={m₁, m₂, m₃, m₄}; M₁={m₁, m₂, m₃}; M₂={m₂, m₃, m₄};

ù M₁={m₄}; ù M₂={m₁}; M₁ÇM₂={m₂, m₃}; M₁ÈM₂=
={m₁, m₂; m₃, m₄};

AÞA¢:

M₁Þb₁=<1, 1, 1, 0>; M₂Þb₂=<0, 1, 1, 1>;

ù M₁Þù b₁=<0, 0, 0, 1>; ù M₂Þù b₂=<1, 0, 0, 0>;

M₁ÇM₂Þb₁Ùb₂=<0, 1, 1, 0>; M₁ÈM₂Þb₁Úb₂=<1, 1, 1, 1>.