Булева функція

Булева функція задається кінцевим набором значень, що дозволяє представити її у вигляді таблиці істинності, наприклад:[2]

x1	x2	…	xn-1	xn	f(x1, x2,…,xn)
0	0	…	0	0	0
0	0	…	0	1	0
0	0	…	1	0	1
0	0	…	1	1	0
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$
1	1	…	0	0	1
1	1	…	0	1	0
1	1	…	1	0	0
1	1	…	1	1	0

При n=0 кількість булевих функцій зводиться до двох 2 ^{2 0} =2¹=2, перша з них тотожно дорівнює 0, а друга 1. Їх називають булевими константами — тотожний нуль і тотожна одиниця.
Таблиця значень і назв нульарних булевих функцій:

При n=1 число булевих функцій дорівнює 2 ²¹ =2²=4. Визначення цих функцій міститься в наступній таблиці.

Таблиця значень і назв булевих функцій від однієї змінної:

При n=2 число булевих функцій дорівнює 2²² =2⁴=16.

Таблиця значень і назв булевих функцій від двох змінних:

При двох аргументах префіксний, інфіксний і постфіксний записи, за економічністю, майже однакові.

При n=3 число булевих функцій дорівнює 2⁽²³⁾=2⁸=256 (дужки потрібні, так як запис ${\displaystyle a^{n^{m}}}$ не має властивість асоціативності і (2²)³=4³). Деякі з них визначені в наступній таблиці:
Таблиця значень і назв деяких булевих функцій від трьох змінних, що мають власну назву:

x0 =z	1	0	1	0	1	0	1	0
x 1=y	1	1	0	0	1	1	0	0
x2=x	1	1	1	1	0	0	0	0	Позначення	Назви
1	0	0	0	0	0	0	0	1	F3,1 = x↓y↓z = ↓(x,y,z) = Webb2(x,y,z) = NOR(x,y,z	стрілка Пірса, НЕ-АБО, 2АБО-НЕ, антидиз'юнкція, функція Даггера, функція Вебба, детектор 1
23	0	0	0	1	0	1	1	1	F3,23=${\displaystyle \neg (>=2(x,y,z))}$=≥2(x,y,z)	Перемикач по більшості з інверсією, 3ППБ-НЕ, мажоритарний клапан з інверсією
126	0	1	1	1	1	1	1	0	F3,126=(x≠y≠z)=[≠(x, y,z)]=NE(x, y,z)	Нерівність
127	0	1	1	1	1	1	1	1	F3,127=x|y|z=|(x, y,z)=NAND(x, y,z)	3І-НЕ, штрих Шефера
128	1	0	0	0	0	0	0	0	F3,128 =x&y&z=&(x, y,z)=(xANDyANDz)=AND(x, y,z)=(xІyІz)=І(x, y,z)=min(x, y,z)	3І, мінімум
129	1	0	0	0	0	0	0	1	F3,129=(x=y=z)=[=(x, y,z)]=EQV(x, y,z)	Рівність
150	1	0	0	1	0	1	1	0	F3,150=x⊕y⊕z=x⊕2y⊕2z=⊕2(x, y,z)	Тернарне додавання по модулю 2
216	1	1	0	1	1	0	0	0	F3,216=f1	Розряд позики при тернарному відніманні
232	1	1	1	0	1	0	0	0	F3,232=f2=[>=2(x, y,z)]=≥2(x, y,z)=(xІy)АБО(yІz)АБО(zІx)	Розряд переносу при тернарному додаванні, перемикач по більшості, 3ППБ, мажоритарний клапан
254	1	1	1	1	1	1	1	0	F3,254=(x+y+z)=+(x, y,z)=(xORyORz)=OR(x, y,z)=(xАБОyАБОz)=АБО(x, y,z)=max(x, y,z)	АБО, максимум

При трьох і більше аргументах префіксний (і постфіксний) запис економічніший ніж інфіксний запис.

Результат обчислення булевої функції може бути використаний як один з аргументів іншої функції. Результат такої операції суперпозиції можна розглядати як нову булеву функцію зі своєю таблицею істинності. Наприклад, функції ${\displaystyle f(x,y,z)={\overline {x({\overline {y}}\lor z)}}}$ (суперпозиція кон'юнкції, диз'юнкції і двох заперечень) відповідатиме наступна таблиця:

${\displaystyle x_{2}=x}$	${\displaystyle x_{1}=y}$	${\displaystyle x_{0}=z}$	${\displaystyle f(x,y,z)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

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

Як найпростіші приклади замкнених класів булевих функцій можна назвати множину ${\displaystyle \{x\}}$, що складається з однієї тотожної функції, або множину ${\displaystyle \{0\}}$, всі функції якої тотожно рівні нулю незалежно від своїх аргументів. Замкнені також множини функцій ${\displaystyle \{x,{\overline {x}}\}}$ і множина всіх унарних функцій. А ось об'єднання замкнених класів може таким вже не бути. Наприклад, об'єднавши класи ${\displaystyle \{0\}}$ і ${\displaystyle \{x,{\overline {x}}\}}$, ми за допомогою суперпозиції ${\displaystyle {\overline {0}}}$ зможемо отримати константу 1, яка у вихідних класах була відсутня.

Зрозуміло, множина ${\displaystyle P_{2}}$ всіх можливих булевих функцій теж є замкненою.

Дві булеві функції тотожні одна одній, якщо на будь-яких однакових наборах аргументів вони приймають рівні значення. Тотожність функцій f і g можна записати, наприклад, так:
${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=g(x_{1},x_{2},\dots ,x_{n})}$ Переглянувши таблиці істинності булевих функцій, легко отримати такі тотожності:

${\displaystyle {\overline {0}}=1}$	${\displaystyle {\overline {1}}=0}$	${\displaystyle {\overline {\overline {x}}}=x}$	${\displaystyle xy=yx\!}$	${\displaystyle x\lor y=y\lor x}$
${\displaystyle 0x=0\!}$	${\displaystyle 1x=x\!}$	${\displaystyle 0\lor x=x}$	${\displaystyle 1\lor x=1}$	${\displaystyle xx=x\lor x=x}$

А перевірка таблиць, побудованих для деяких суперпозицій, дасть такі результати:

${\displaystyle x{\overline {x}}=0}$

${\displaystyle x\lor {\overline {x}}=1}$

${\displaystyle {\overline {x\cdot y}}={\overline {x}}\lor {\overline {y}}}$

${\displaystyle {\overline {x}}\cdot {\overline {y}}={\overline {x\lor y}}}$

(закони де Моргана)

${\displaystyle x(y\lor z)=xy\lor xz}$
${\displaystyle x\lor yz=(x\lor y)(x\lor z)}$ (дистрибутивність кон'юнкції і диз'юнкції)

Функція ${\displaystyle g(x_{1},x_{2},\dots ,x_{n})}$ називається двоїстою до функції ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$, якщо ${\displaystyle f({\overline {x_{1}}},{\overline {x_{2}}},\dots ,{\overline {x_{n}}})={\overline {g(x_{1},x_{2},\dots ,x_{n})}}}$. Легко показати, що в цій рівності f і g можна поміняти місцями, тобто функції f і g двоїсті одна одній. З найпростіших функцій двоїсті одна одній константи 0 і 1, а із законів де Моргана випливає двоїстість кон'юнкції і диз'юнкції. Тотожна функція, як і функція заперечення, двоїста сама до себе.

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

Система булевих функцій називається повною, якщо можна побудувати їх суперпозицію, тотожну будь-якій заздалегідь заданій функції. Кажуть ще, що замикання даної системи збігається з множиною ${\displaystyle P_{2}}$.

Американський математик Еміль Пост ввів у розгляд такі замкнені класи булевих функцій:

• Функції, що зберігають константу ${\displaystyle P_{0}}$ і ${\displaystyle P_{1}}$;
• Самодвоїсті функції ${\displaystyle S}$;
• Монотонні функції ${\displaystyle M}$;
• Лінійні функції ${\displaystyle L}$.

Ним було доведено, що будь-який замкнутий клас булевих функцій, який не збігається з ${\displaystyle P_{2}}$, цілком утримується в одному з цих п'яти так званих передповних класів, але при цьому жоден з п'яти не міститься цілком в об'єднанні чотирьох інших. Таким чином, критерій Поста для повноти системи зводиться до з'ясування, чи не міститься вся ця система цілком в одному з передповних класів. Якщо для кожного класу в системі знайдеться функція, що не входить до нього, то така система буде повною, і за допомогою вхідних у неї функцій можна буде отримати будь-яку іншу булеву функцію. Пост довів, що множина замкнених класів булевих функцій — зліченна множина.

Зауважимо, що існують функції, що не входять ні в один з класів Посту. Будь така функція сама по собі утворює повну систему. Як приклади можна назвати штрих Шефера або стрілку Пірса.

Простою кон'юнкцією або кон'юнктом називається кон'юнкція деякого кінцевого набору змінних або їх заперечень, причому кожна змінна зустрічається не більше одного разу. Диз'юнктивною нормальною формою або ДНФ називається диз'юнкція простих кон'юнкцій. Елементарна кон'юнкція:

• Правильна, якщо кожна змінна входить у неї не більше одного разу (включаючи заперечення) ;
• Повна, якщо кожна змінна (або її заперечення) входить до неї рівно 1 раз;
• Монотонна, якщо вона не містить заперечень змінних.

Наприклад ${\displaystyle a{\overline {b}}c\lor bc\lor {\overline {a}}}$ — є ДНФ.

Досконалою диз'юнктивною нормальною формою або ДДНФ щодо деякого заданого кінцевого набору змінних називається така ДНФ, у якої в кожну кон'юнкцію входять всі змінні даного набору, причому в одному і тому ж порядку. Наприклад: ${\displaystyle a{\overline {b}}c\lor abc\lor {\overline {a}}b{\overline {c}}}$.

Легко переконатися, що кожній булевій функції відповідає деяка ДНФ, а функції, відмінної від тотожного нуля — навіть ДДНФ. Для цього достатньо в таблиці істинності цієї функції знайти всі булеві вектори, на яких її значення дорівнює 1, і для кожного такого вектора ${\displaystyle b=(b_{1},b_{2},\ldots ,b_{n})}$ побудувати кон'юнкцію ${\displaystyle x_{1}^{b_{1}}x_{2}^{b_{2}}\ldots x_{n}^{b_{n}}}$, де ${\displaystyle x_{i}^{1}=x_{i}}$ ${\displaystyle x_{i}^{0}={\overline {x_{i}}}}$. Диз'юнкція цих кон'юнкцій є ДДНФ вихідної функції, оскільки на всіх булевих векторах її значення збігаються зі значеннями вихідної функції. Наприклад, для імплікації ${\displaystyle x\to y}$ результатом є ${\displaystyle {\overline {x}}y\lor {\overline {x}}\,{\overline {y}}\lor xy}$, що можна спростити до ${\displaystyle {\overline {x}}\lor y}$.

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

Досконалою кон'юнктивною нормальною формою (ДКНФ), щодо деякого заданого кінцевого набору змінних, називається така КНФ, у якої в кожну диз'юнкцію входять всі змінні даного набору, причому в одному і тому ж порядку. Оскільки (Д)КНФ і (Д)ДНФ взаємнодвоїсті, властивості (Д)КНФ повторюють всі властивості (Д)ДНФ «з точністю до навпаки».

КНФ може бути перетворена на еквівалентну їй ДНФ шляхом розкриття дужок за правилом:

${\displaystyle a(b\lor c)\to ab\lor ac}$

яке виражає дистрибутивність кон'юнкції щодо диз'юнкції. Після цього необхідно в кожній кон'юнкції видалити повторювані змінні або їх заперечення, а також викинути з диз'юнкції всі кон'юнкції, в яких зустрічається змінна разом зі своїм запереченням. При цьому результатом не обов'язково буде СДНФ, навіть якщо вихідна КНФ була СКНФ. Так само можна завжди перейти від ДНФ до КНФ. Для цього слід використовувати правило,

${\displaystyle a\lor bc\to (a\lor b)(a\lor c)}$

яке виражає дистрибутивність диз'юнкції щодо кон'юнкції. Результат потрібно перетворити описаним вище способом, замінивши слово «кон'юнкція» на «диз'юнкція» і навпаки.

Алгебраїчна нормальна форма(загальноприйнята назва в зарубіжній літературі) або поліном Жегалкіна (назва, що використовується у вітчизняній літературі) — це форма подання логічної функції у вигляді поліному з коефіцієнтами виду 0 і 1, в якому як добуток використовується операція кон'юнкції ("І", AND), а як додавання — додавання по модулю 2 (що виключає «АБО», XOR).

Для отримання полінома Жегалкіна треба виконати такі дії:

1. Отримати ДДНФ функції
2. Усі «АБО» замінити на «Виключне АБО»
3. У всіх термах замінити елементи з запереченням на конструкцію: («елемент» «виключне АБО» 1)
4. Розкрити дужки за правилами алгебри Жегалкіна і привести попарно однакові терми