Перегляд вихідного коду сторінки Булева функція

{{right|{{2-ary truth table|T=1|F=0
|0|0|0|1|[[Кон'юнкція|AND]]<br/><math>A \land B</math>|
|1|1|1|0|[[Штрих Шефера|NAND]]<br/><math>A \uparrow B</math>|thick
|0|1|1|1|[[Диз'юнкція (логіка)|OR]]<br/><math>A \lor B</math>|
|1|0|0|0|[[Стрілка Пірса|NOR]]<br/><math>A \downarrow B</math>|thick
|0|1|1|0|[[Виключна диз'юнкція|XOR]]<br/><math>A \oplus B</math>|
|1|0|0|1|[[Логічна еквівалентність|EQ]]<br/><math>A \leftrightarrow B</math>|thick
|1|1|0|1|[[Логічна імплікація|IMPLY]]<br/><math>A \to B</math>|
|0|0|1|0|<!-- [[Неімплікація |NIMPLY]] --><br/><math>A \nrightarrow B</math>|thick
|1|0|1|1|<!-- [[Обернена імплікація|Converse]] --><br/><math>A \leftarrow B</math>|
|0|1|0|0|<br/><math>A \nleftarrow B</math>|thick
}}}}

'''Бу́лева фу́нкція''' (''функція алгебри логіки'', ''логічна функція'')&nbsp;— в [[дискретна математика|дискретній математиці]] [[відображення]] ''B''<sup>''n''</sup> → ''B'', де ''B'' = {0,1}&nbsp;— [[булева множина]].

''B''<sup>''n''</sup>&nbsp;— [[множина]] всіх можливих [[послідовність|послідовностей]] з 0 та 1 довжини ''n''.

Булева функція задається у вигляді [[Табулювання функції|таблиці]], або графіка зі стандартним ([[лексикографічний порядок|лексикографічним]]) розташуванням наборів аргументів.

В стандартному розташуванні набори можна розглядати як двійкові записи цілих чисел від 0 до <math>2^n - 1</math>. Функцію, задану зі стандартним розташуванням наборів, можна ототожнити з набором довжини <math>2^n</math>.

Очевидно, що множина всіх можливих наборів довжини <math>2^n</math>, тобто множина n-арних булевих функцій, складається з <math>2^{2^n}</math> елементів. При n=0 це 2, при n=1&nbsp;— 4, при n=2&nbsp;— 16, при n=3&nbsp;— 256 тощо.

Нульарними булевими функціями є сталі 0 і 1.

Функції 0 і 1 називаються тотожними нулем і одиницею, функція x&nbsp;— тотожною, <math>\overline x</math>— запереченням. Замість виразу <math>\overline x</math> вживається ще вираз <math>\neg x</math>. Ці вирази читаються як «не x».

Подамо також деякі з 16 бінарних функцій разом із їх позначеннями: функція, позначена виразом <math>x \wedge y</math>, називається кон'юнкцією і позначається ще як x&y, <math>x\cdot y</math> або xy. Усі ці вирази читаються як «x і y».

Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f&nbsp;— відповідний [[знак]], склалися історично. Їх так само можна позначати й у вигляді f(x, y), наприклад, <math>\vee(x, y)</math>.

При роботі з булевими функціями відбувається повне абстрагування від сенсу, який мався на увазі в алгебрі висловлювань.{{sfn| Ігошин|2008|з = 94 }} Проте, між булевими функціями і формулами [[алгебра висловлювань|алгебри висловлювань]] можна встановити взаємно однозначну відповідність, якщо:{{sfn|Ігошин|2008|з = 104-105}}

* Встановити взаємно однозначну відповідність між булевими змінними і пропозіціональними змінними.
* Встановити зв'язок між булевими функціями і логічними зв'язками.
* Залишити розстановку дужок без змін.

== Основні відомості ==
Кожна булева функція [[Арність|арності]] ''n'' повністю визначається заданням своїх значень на своїй [[Область визначення|області визначення]], тобто на всіх булевих векторах довжини ''n''. Число таких векторів дорівнює 2 <sup>''n''</sup>. Оскільки на кожному векторі булева функція може приймати значення або 0, або 1, то кількість всіх ''n''&nbsp;-арних булевих функцій дорівнює 2 <sup>(2 <sup>''n''</sup>) </sup>. Тому в цьому розділі розглядаються тільки найпростіші і найважливіші булеві функції.

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

=== Таблиці істинності ===
{{Головна|Таблиця істинності}}

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

<center>
{|Class="wikitable" align ="center" style ="width:10cm"
|+
|-align="center "bgcolor = #EEEEFF
!x<sub>1</sub>||x<sub>2</sub>||…||x<sub>n-1</sub>||x<sub>n</sub>||f(x<sub>1</sub>, x<sub>2</sub>,…,x<sub>n</sub>)
|-align="center" bgcolor = #F0F0F0
|0||0||…||0||0||bgcolor = white|0
|-align="center" bgcolor = #F0F0F0
|0||0|| … ||0||1||bgcolor = white|0
|-align="center " bgcolor = #F0F0F0
|0||0|| … ||1||0||bgcolor = white|1
|-align ="center " bgcolor = #F0F0F0
|0||0|| … ||1||1||bgcolor = white|0
|-align = " center " style="height : 1.2cm " bgcolor =#F0F0F0
|<math>\vdots</math>||<math>\vdots</math>||<math>\vdots</math>||<math>\vdots</math> ||<math>\vdots</math>||bgcolor = white|<math>\vdots</math>
|-align ="center" bgcolor = #F0F0F0
|1||1||…||0||0||bgcolor = white|1
|- align ="center" bgcolor=#F0F0F0
|1||1||…||0||1||bgcolor = white|0
|-align="center" bgcolor = #F0F0F0
|1||1||…||1||0||bgcolor = white|0
|-align="center" bgcolor = #F0F0F0
|1||1||…||1||1||bgcolor = white|0
|}
</center>

=== Нульарні функції ===
При ''n''=0 кількість булевих функцій зводиться до двох 2 <sup>2<sup> 0 </sup> </sup>=2<sup>1</sup>=2, перша з них тотожно дорівнює 0, а друга 1. Їх називають булевими константами&nbsp;— тотожний нуль і тотожна одиниця. <br/>
[[Табулювання функції|Таблиця значень]] і назв нульарних булевих функцій:
{|Class="standard"
!||Значення
!Позначення
!Назва
|-
|||0||F0, 0 = 0
|тотожний нуль
|-
|||1||F0,1 =1
|тотожна одиниця, [[тавтологія (логіка)|тавтологія]]
|-
|}

=== Унарні функції ===
При ''n''=1 число булевих функцій дорівнює 2 <sup>2<sup>1</sup> </sup>=2<sup>2</sup>=4. Визначення цих функцій міститься в наступній таблиці.

Таблиця значень і назв булевих функцій від однієї змінної:
{|Class = "standard"
!x<sub>0</sub>=x||1||0
!Позначення
!Назва
|-
!0
||0||0||F1,0 =0
|тотожний нуль
|-
!1
||0||1||F1,1={{overline|''x''}}= ¬ ''x'' = ''x'' '= NOT(x)
|заперечення, логічне «НІ», «НЕ», [[інвертор]], SWAP (обмін)
|-
!2
||1||0||F1,2 =''x''
|тотожна функція, логічне «ТАК», повторювач
|-
!3
||1||1||F1,3=1
|тотожна одиниця, [[тавтологія (логіка)|тавтологія]]
|-
|}

=== Бінарні функції ===
При ''n''=2 число булевих функцій дорівнює 2<sup>2<sup>2</sup> </sup>=2<sup>4</sup>=16.

Таблиця значень і назв булевих функцій від двох [[Змінна|змінних]]:
{|Class="standard"
!x<sub>1</sub>=x||1||1||0||0
!
!
|-
!x<sub>0</sub>=y||1||0||1||0
!Позначення
!Назва
|-
!0
||0||0||0||0||F2,0=0
|тотожний нуль, детектор 0
|-
!1
||0||0||0||1||F2,1=''x''↓''y''=''x''NOR''y''=NOR(''x'',''y'')=''x''НЕ- АБО''y''= НЕ- АБО(''x'',''y'')
|[[стрілка Пірса]], НЕ-АБО, 2АБО-НЕ, антидиз'юнкція, функція Даггера, функція Вебба, детектор 1
|-
!2
||0||0||1||0||F2,2={{overline|''x''←''y''}}=''x''<''y''=''x''LT''y''=LT(''x'',''y'')
|інверсія зворотньої [[імплікація|імплікації]], менше, детектор 2
|-
!3
||0||0||1||1||F2,3={{overline|''x''}}=''x'''=¬''x''=NOT1(''x'',''y'')=не1(''x'',''y'')
|заперечення (негація, інверсія) першого операнда
|-
!4
||0||1||0||0||F2,4={{overline|''x''→''y''}}=''x''>''y''=''x''GT''y''= GT(''x'',''y'')
|інверсія прямої [[імплікація|імплікації]], більше, детектор 4
|-
!5
||0||1||0||1||F2,5={{overline|''y''}}=''y'''= ¬''y''=NOT2(''x'',''y'')=НЕ2(''x'',''y'')
|заперечення (негація, інверсія) другого операнда
|-
!6
||0||1||1||0||F2,6 =''x''⊕''y''=''x''XOR''y''=XOR(''x'',''y'')=''x''><''y''=''x''<>''y''=''x''NE''y''= NE(x, y)
|додавання по модулю 2, [[Виключна диз'юнкція|виключне «або»]], сума Жегалкіна,{{sfn|Ігошин|2008|з=96}} не дорівнює
|-
!7
||0||1||1||1||F2,7=''x''<nowiki>|</nowiki>''y''=''x''NAND''y''=NAND(''x'',''y'')=''x''НЕ-І''y''=НЕ-І(''x'',''y'')
|[[штрих Шефера]], НЕ-І, 2І-НЕ, антикон'юнкція, пунктир Чулкова
|-
!8
||1||0||0||0||F2,8=''x''∧''y''=''x''·''y''=''x''''y''=''x''&''y''=''x''AND''y''=AND(''x'',''y'')=''x''І''y''=І (''x'',''y'')=min(''x'',''y'')
|[[кон'юнкція ]], 2І, мінімум, детектор 8
|-
!9
||1||0||0||1||F2,9=(''x''≡''y'')=''x''~''y''=''x''↔''y''=''x''EQV''y''=EQV(''x'',''y'')
|[[Логічна еквівалентність|еквівалентність]], рівність
|-
!10
||1||0||1||0||F2,10=YES2(''x'',''y'')=да2(''x'',''y'')=''y''
|другий операнд
|-
!11
||1||0||1||1||F2,11 = ''x''→''y''=''x''⊃''y''=''x''≤''y''=''x''LE''y''=LE(''x'',''y'')
|пряма (матеріальна) [[імплікація]] (від першого аргументу до другого), менше або дорівнює
|-
!12
||1||1||0||0||F2,12=YES1(''x'',''y'')=ТАК1(''x'',''y'')=''x''
|перший операнд
|-
!13
||1||1||0||1||F2,13=''x''←''y''=''x''⊂''y''=''x''≥''y''=''x''GE''y''=GE(''x'',''y'')
|зворотня [[імплікація]] (від другого аргументу до першого), більше або дорівнює
|-
!14
||1||1||1||0|| F2,14 =''x''∨''y'' =''x''+''y'' =''x''OR''y'' =OR(''x'',''y'') =''x''АБО''y''=АБО(''x'',''y'')=max''x'',''y'')
|[[диз'юнкція]], 2АБО, максимум
|-
!15
||1||1||1||1||F2,15 = 1
|тотожна одиниця, [[тавтологія (логіка)|тавтологія]]
|-
|}

При двох аргументах [[Польська нотація|префіксний]], інфіксний і [[Польський інверсний запис|постфіксний]] записи, за економічністю, майже однакові.

=== Тернарні функції ===
При ''n''=3 число булевих функцій дорівнює 2<sup>(2<sup>3</sup>)</sup>=2<sup>8</sup>=256 (дужки потрібні, так як запис <math>a^{n^m}</math> не має властивість [[асоціативність|асоціативності]] і (2<sup>2</sup>)<sup>3</sup>=4<sup>3</sup>). Деякі з них визначені в наступній таблиці:<br/>
Таблиця значень і назв деяких булевих функцій від трьох змінних, що мають власну назву:

{|Class="standard"
!x<sub>0 </sub>=z||1||0||1||0||1||0||1||0||||
|-
!x <sub>1</sub>=y||1||1||0||0||1||1||0||0||||
|-
!x<sub>2</sub>=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) = Webb<sub>2</sub>(x,y,z) = NOR(x,y,z)
|[[стрілка Пірса]], НЕ-АБО, 2АБО-НЕ, антидиз'юнкція, функція Даггера, функція Вебба, детектор 1
|-
!23
||0||0||0||1||0||1||1||1
|F3,23=<math>\neg(>=2(x,y,z))</math>={{overline|≥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<nowiki>|</nowiki>y<nowiki>|</nowiki>z=<nowiki>|</nowiki>(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)=(x AND y AND z)=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⊕<sub>2</sub>y⊕<sub>2</sub>z=⊕<sub>2</sub>(x, y,z)
|Тернарне додавання [[Модульна арифметика|по модулю]] 2
|-
!216
||1||1||0||1||1||0||0||0
|F3,216=''f<sub>1</sub>''
|Розряд позики при тернарному відніманні
|-
!232
||1||1||1||0||1||0||0||0
|F3,232=''f<sub>2</sub>''=[>=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)=(x OR y OR z)=OR(x, y, z)=(x АБО y АБО z)=АБО(x, y, z)=max(x, y, z)
|АБО, максимум
|}
При трьох і більше аргументах префіксний (і постфіксний) запис економічніший ніж інфіксний запис.

== Повні системи булевих функцій ==
{{main|Замкнений клас функцій алгебри логіки}}

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

{| class="standard" align="center" style="width:8cm"
 |-align="center"
 ! <math>x_2=x</math> || <math>x_1=y</math> || <math>x_0=z</math> || <math>f(x,y,z)</math> 
 |-align="center"
 | 0 || 0 || 0 || 1
 |-align="center"
 | 0 || 0 || 1 || 1
 |-align="center"
 | 0 || 1 || 0 || 1
 |-align="center"
 | 0 || 1 || 1 || 1
 |-align="center"
 | 1 || 0 || 0 || 0
 |-align="center"
 | 1 || 0 || 1 || 0
 |-align="center"
 | 1 || 1 || 0 || 1
 |-align="center"
 | 1 || 1 || 1 || 0
|}

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

Як найпростіші приклади замкнених класів булевих функцій можна назвати множину <math>\{x\}</math>, що складається з однієї [[Тотожне відображення|тотожної функції]], або множину <math>\{0\}</math>, всі функції якої тотожно рівні нулю незалежно від своїх аргументів. Замкнені також множини функцій <math>\{x,\overline{x}\}</math> і множина всіх [[Унарна операція|унарних]] функцій. А ось [[Об'єднання множин|об'єднання]] замкнених класів може таким вже не бути. Наприклад, об'єднавши класи <math>\{0\}</math> і <math>\{x,\overline{x}\}</math>, ми за допомогою суперпозиції <math>\overline{0}</math> зможемо отримати константу 1, яка у вихідних класах була відсутня.

Зрозуміло, множина <math>P_2</math> всіх можливих булевих функцій теж є замкненою.

=== Тотожність і двоїстість ===
Дві булеві функції тотожні одна одній, якщо на будь-яких однакових наборах аргументів вони приймають рівні значення. [[Тотожність]] функцій f і g можна записати, наприклад, так:<br/>
<math>f(x_1,x_2,\dots,x_n)=g(x_1, x_2,\dots,x_n)</math>
Переглянувши таблиці істинності булевих функцій, легко отримати такі тотожності:
{| style="width:15cm"
|-
| <math>\overline{0}=1</math> || <math>\overline{1}=0</math> || <math>\overline{\overline{x}}=x</math>
|| <math>xy=yx\!</math> || <math>x\lor y=y \lor x</math>
|-
|| <math>0x=0\!</math> || <math>1x=x\!</math> || <math>0\lor x=x</math> || <math>1\lor x=1</math> || <math>xx=x\lor x=x</math>
|}
А перевірка таблиць, побудованих для деяких суперпозицій, дасть такі результати:
{| style="width:15cm"
|-
| <math>x\overline{x}=0</math> || <math>x\lor\overline{x}=1</math>
|}
{| style="width:15cm"
|-
| <math>\overline{x\cdot y}=\overline{x}\lor\overline{y}</math>
|| <math>\overline{x}\cdot\overline{y}=\overline{x\lor y}</math> || ([[закони де Моргана]])
|}
<math>x(y\lor z)=xy\lor xz</math><br/>
<math>x\lor yz=(x \lor y)(x\lor z)</math> ([[дистрибутивність]] кон'юнкції і диз'юнкції)

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

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

=== Повнота системи, критерій Поста ===
{{main|Критерій Поста}}

Система булевих функцій називається ''повною'', якщо можна побудувати їх [[Суперпозиція функцій|суперпозицію]], тотожну будь-якій заздалегідь заданій функції. Кажуть ще, що [[Замикання (математика)|замикання]] даної системи збігається з множиною <math>P_2</math>.

Американський математик [[Еміль Пост]] ввів у розгляд такі замкнені класи булевих функцій:
* Функції, що зберігають константу <math>P_0</math> і <math>P_1</math>;
* Самодвоїсті функції <math>S</math>;
* Монотонні функції <math>M</math>;
* Лінійні функції <math>L</math>.
Ним було доведено, що будь-який замкнутий клас булевих функцій, який не збігається з <math>P_2</math>, цілком утримується в одному з цих п'яти так званих ''передповних класів'', але при цьому жоден з п'яти не міститься цілком в об'єднанні чотирьох інших. Таким чином, критерій Поста для повноти системи зводиться до з'ясування, чи не міститься вся ця система цілком в одному з передповних класів. Якщо для кожного класу в системі знайдеться функція, що не входить до нього, то така система буде повною, і за допомогою вхідних у неї функцій можна буде отримати будь-яку іншу булеву функцію.
Пост довів, що множина замкнених класів булевих функцій&nbsp;— [[зліченна множина]].

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

== Подання булевих функцій ==

Теорема Поста відкриває шлях до подання булевих функцій синтаксичним способом, який у ряді випадків виявляється набагато зручнішим, ніж таблиці істинності. Відправною точкою тут служить знаходження деякої повної системи функцій <math>\Sigma=\{f_1,\ldots,f_n\}</math>. Тоді кожна булева функція може бути представлена деяким [[Терм (логіка)|термом]] в [[Сигнатура (математична логіка)|сигнатурі]] <math>\Sigma</math>, який в даному випадку називають також [[Формула|формулою]].
Щодо вибраної системи функцій корисно знати відповіді на такі питання:
* Як побудувати по даній функції формулу, що її представляє?
* Як перевірити, що дві різні формули еквівалентні, тобто задають одну і ту ж функцію?
** Зокрема: чи існує спосіб приведення довільної формули до еквівалентної їй ''канонічної'' форми такий, що дві формули еквівалентні [[Тоді й лише тоді|тоді і тільки тоді]], коли їх канонічні форми збігаються?
* Як з даної функції побудувати формулу, що її представляє, з тими чи іншими заданими властивостями (наприклад, найменшого розміру), і чи можливо це?

Позитивні відповіді на ці та інші питання суттєво збільшують прикладне значення обраної системи функцій.

=== Диз'юнктивна нормальна форма (ДНФ) ===
{{ main | Диз'юнктивна нормальна форма }}
''Простою кон'юнкцією'' або ''кон'юнктом'' називається [[кон'юнкція]] деякого кінцевого набору змінних або їх заперечень, причому кожна змінна зустрічається не більше одного разу. '' Диз'юнктивною нормальною формою '' або '' ДНФ '' називається диз'юнкція простих кон'юнкцій.
Елементарна кон'юнкція:
* '''Правильна''', якщо кожна змінна входить у неї не більше одного разу (включаючи заперечення) ;
* '''Повна''', якщо кожна змінна (або її заперечення) входить до неї рівно 1 раз;
* '''Монотонна''', якщо вона не містить заперечень змінних.

Наприклад <math>a\overline{b}c\lor bc\lor\overline{a}</math>&nbsp;— є ДНФ.

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

Легко переконатися, що кожній булевій функції відповідає деяка ДНФ, а функції, відмінної від тотожного нуля&nbsp;— навіть ДДНФ. Для цього достатньо в таблиці істинності цієї функції знайти всі булеві вектори, на яких її значення дорівнює 1, і для кожного такого вектора <math>b=(b_1,b_2,\ldots,b_n)</math> побудувати кон'юнкцію <math>x_1^{b_1}x_2^{b_2}\ldots x_n^{b_n}</math>, де <math>x_i^1=x_i</math> <math>x_i^0=\overline{x_i}</math>. Диз'юнкція цих кон'юнкцій є ДДНФ вихідної функції, оскільки на всіх булевих векторах її значення збігаються зі значеннями вихідної функції. Наприклад, для імплікації <math>x \to y</math> результатом є <math>\overline{x} y\lor \overline{x}\,     \overline   {y}\lor xy</math>, що можна спростити до <math>\overline {x} \lor y </math>.

=== Кон'юнктивна нормальна форма (КНФ) ===
{{ main | Кон'юнктивна нормальна форма }}

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

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

КНФ може бути перетворена на еквівалентну їй ДНФ шляхом розкриття дужок за правилом:
{{center|<math>a(b\lor c)\to ab\lor ac</math>}}
яке виражає [[дистрибутивність]] кон'юнкції щодо диз'юнкції. Після цього необхідно в кожній кон'юнкції видалити повторювані [[Змінна|змінні]] або їх заперечення, а також викинути з диз'юнкції всі кон'юнкції, в яких зустрічається змінна разом зі своїм запереченням. При цьому результатом не обов'язково буде СДНФ, навіть якщо вихідна КНФ була СКНФ. Так само можна завжди перейти від ДНФ до КНФ. Для цього слід використовувати правило,
{{center|<math>a\lor bc\to(a\lor b)(a\lor c)</math>}}
яке виражає [[дистрибутивність]] диз'юнкції щодо кон'юнкції. Результат потрібно перетворити описаним вище способом, замінивши слово «кон'юнкція» на «диз'юнкція» і навпаки.

=== Алгебраїчна нормальна форма (АНФ або поліном Жегалкіна) ===
{{Головна|Поліном Жегалкіна}}
 
[[Алгебраїчна нормальна форма]](загальноприйнята назва в зарубіжній літературі) або [[поліном Жегалкіна]] (назва, що використовується у вітчизняній літературі)&nbsp;— це форма подання логічної функції у вигляді [[Многочлен|поліному]] з коефіцієнтами виду 0 і 1, в якому як добуток використовується операція [[Кон'юнкція|кон'юнкції]] ("І", AND), а як додавання&nbsp;— [[Виключна диз'юнкція|додавання по модулю 2]] (що виключає «АБО», XOR).

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

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

== Класифікація булевих функцій ==

* За кількістю ''n'' вхідних операндів, від яких залежить значення на виході функції, розрізняють нульарні (''n'' = 0), унарні (''n'' = 1), бінарні (''n'' = 2), тернарні (''n'' = 3) булеві функції та функції від більшого числа операндів.

* За кількістю одиниць і нулів в таблиці істинності відрізняють вузький клас {{Не перекладено|Збалансована булева функція|збалансованих булевих функцій||Balanced boolean function}} (також званих врівноваженими або рівновірогідними, оскільки при рівноймовірно випадкових значеннях на вході або при переборі всіх комбінацій за таблицею істинності ймовірність отримання на виході значення '' '1 '' ' дорівнює 1/2) від більш широкого класу незбалансованих булевих функцій (так само званих неврівноваженими, оскільки ймовірність отримання на виході значення '' '1 ''' відмінна від 1/2). Збалансовані булеві функції в основному використовуються в [[Криптографія|криптографії]].

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

* За значенням функції на протилежних один одному наборах значень аргументів відрізняють самодвоїсті функції (значення яких інвертується при інвертуванні значення всіх входів) від інших булевих функцій, що не володіють такою властивістю. Нижня частина [[Таблиця істинності|таблиці істинності]] для самодвоїстих функцій є дзеркальним відображенням інвертованої верхньої частини (якщо розташувати вхідні комбінації в таблиці істинності в природному порядку).

* За алгебраїчним ступенем нелінійності відрізняють [[Лінійна функція|лінійні булеві функції]] ([[Алгебраїчна нормальна форма|АНФ]] яких зводиться до лінійної суми за модулем 2 вхідних значень) і нелінійні булеві функції ([[Алгебраїчна нормальна форма|АНФ]] яких містить хоча б одну нелінійну операцію кон'юнкції вхідних значень). Прикладами лінійних функцій є: [[Виключна диз'юнкція|додавання по модулю 2]] (що виключає «АБО», XOR), [[еквівалентність]], а також всі булеві функції, [[Алгебраїчна нормальна форма|АНФ]] яких містить лише лінійні операції [[Виключна диз'юнкція|додавання за модулем 2]] без кон'юнкцій. Прикладами нелінійних функцій є: [[кон'юнкція]] («І», AND), [[штрих Шефера]] («НІ-І», NAND), [[стрілка Пірса]] (« НІ-АБО», NOR), а також всі булеві функції, [[Алгебраїчна нормальна форма|АНФ]] яких містить хоча б одну нелінійну [[Кон'юнкція|операцію кон'юнкції]].

== Див. також ==
* [[Алгебра Жегалкіна]]
* [[Критерій Поста]]
* [[Бент-функція]]
* [[Булева алгебра]]
* [[Бітові операції]]
* [[Комбінаційна логіка]]
* [[Мінімізація булевих функцій]]
* [[Трійкова логіка]]
* [[Логічні елементи]]
* [[Нормальна форма формули у логіці предикатів]]

== Література ==
* {{ Книга|автор = Гаврилов Г. П.,Сапоженко А. А.|заголовок=Збірник завдань з дискретної математики|місце={{М.}}|видавництво=Наука|рік = 1969}}
* {{ Книга|автор = Марченков С. С.|заголовок=Замкнуті класи булевих функцій|місце={{М.}}|видавництво=Фізматліт|рік = 2000}}
* {{ Книга|автор = Яблонський С. В.|заголовок=Введення в дискретну математику|місце={{М.}}|видавництво = Наука|рік = 1986}}
* {{ Книга|автор = Ігошин В. І.|заголовок=Математична логіка і теорія алгоритмів| місце={{М.}}| видання = 2- е вид., Стереотип.| Видавництво = Видавничий центр « Академія»| рік = 2008|isbn = 978-5-7695-4593-1|ref=Ігошин|сторінок = 448}}
* {{ Книга |автор = Самофалов К. Г., Романкевич А. М., Валуйський В. Н., Канівський Ю. С., Пиневич М. М. |заголовок = Прикладна теорія цифрових автоматів|місце = Київ| видавництво = Вища Школа| рік = 1987|ref = Самофалов|сторінок = 375|сторінки = 183-189}}
* [https://web.archive.org/web/20070710025553/http://mathcyb.cs.msu.su/paper/books/dmcour.pdf Алексєєв В.&nbsp;Б.&nbsp;Дискретна математика (курс лекцій, II семестр). Упоряд. А.&nbsp;Д.&nbsp;Поспєлов]
* [Http://ido.tsu.ru/iop_res/bulevfunc/index.html '' Бикова С. В., Буркатовський Ю. Б. '', Булеві функції, навчально&nbsp;— методичний комплекс, Томськ, 2006]

== Посилання ==
{{примітки}}

{{Логічні операції}}
{{Математична логіка}}

[[Категорія:Булева алгебра]]
[[Категорія:Теорія дискретних функціональних систем]]
[[Категорія:Математична логіка]]