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

Булева функція
Названо на честь	Джордж Буль
Досліджується в	булева алгебра
Кодомен	булева множина
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика

Бу́лева фу́нкція (функція алгебри логіки, логічна функція) — в дискретній математиці відображення Bⁿ → B, де B = {0,1} — булева множина.

Bⁿ — множина всіх можливих послідовностей з 0 та 1 довжини n.

Булева функція задається у вигляді таблиці, або графіка зі стандартним (лексикографічним) розташуванням наборів аргументів.

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

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

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

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

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

Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f — відповідний знак, склалися історично. Їх так само можна позначати й у вигляді f(x, y), наприклад, $\vee (x,y)$.

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

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

Основні відомості

Кожна булева функція арності n повністю визначається заданням своїх значень на своїй області визначення, тобто на всіх булевих векторах довжини n. Число таких векторів дорівнює 2 ⁿ. Оскільки на кожному векторі булева функція може приймати значення або 0, або 1, то кількість всіх n -арних булевих функцій дорівнює 2 ^{(2 n)} . Тому в цьому розділі розглядаються тільки найпростіші і найважливіші булеві функції.

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

Таблиці істинності

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

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
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\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. Їх називають булевими константами — тотожний нуль і тотожна одиниця.
Таблиця значень і назв нульарних булевих функцій:

	Значення	Позначення	Назва
	0	F0, 0 = 0	тотожний нуль
	1	F0,1 =1	тотожна одиниця, тавтологія

Унарні функції

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

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

x0=x	1	0	Позначення	Назва
0	0	0	F1,0 =0	тотожний нуль
1	0	1	F1,1=x= ¬ x = x '= NOT(x)	заперечення, логічне «НІ», «НЕ», інвертор, SWAP (обмін)
2	1	0	F1,2 =x	тотожна функція, логічне «ТАК», повторювач
3	1	1	F1,3=1	тотожна одиниця, тавтологія

Бінарні функції

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

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

x1=x	1	1	0	0
x0=y	1	0	1	0	Позначення	Назва
0	0	0	0	0	F2,0=0	тотожний нуль, детектор 0
1	0	0	0	1	F2,1=x↓y=xNORy=NOR(x,y)=xНЕ- АБОy= НЕ- АБО(x,y)	стрілка Пірса, НЕ-АБО, 2АБО-НЕ, антидиз'юнкція, функція Даггера, функція Вебба, детектор 1
2	0	0	1	0	F2,2=x←y=x<y=xLTy=LT(x,y)	інверсія зворотньої імплікації, менше, детектор 2
3	0	0	1	1	F2,3=x=x'=¬x=NOT1(x,y)=не1(x,y)	заперечення (негація, інверсія) першого операнда
4	0	1	0	0	F2,4=x→y=x>y=xGTy= GT(x,y)	інверсія прямої імплікації, більше, детектор 4
5	0	1	0	1	F2,5=y=y'= ¬y=NOT2(x,y)=НЕ2(x,y)	заперечення (негація, інверсія) другого операнда
6	0	1	1	0	F2,6 =x⊕y=xXORy=XOR(x,y)=x><y=x<>y=xNEy= NE(x, y)	додавання по модулю 2, виключне «або», сума Жегалкіна, не дорівнює
7	0	1	1	1	F2,7=x|y=xNANDy=NAND(x,y)=xНЕ-Іy=НЕ-І(x,y)	штрих Шефера, НЕ-І, 2І-НЕ, антикон'юнкція, пунктир Чулкова
8	1	0	0	0	F2,8=x∧y=x·y=x'y=x&y=xANDy=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=xEQVy=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=xLEy=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=xGEy=GE(x,y)	зворотня імплікація (від другого аргументу до першого), більше або дорівнює
14	1	1	1	0	F2,14 =x∨y =x+y =xORy =OR(x,y) =xАБОy=АБО(x,y)=maxx,y)	диз'юнкція, 2АБО, максимум
15	1	1	1	1	F2,15 = 1	тотожна одиниця, тавтологія

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

Тернарні функції

При n=3 число булевих функцій дорівнює 2⁽²³⁾=2⁸=256 (дужки потрібні, так як запис $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=$\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)=(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⊕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)=(x OR y OR z)=OR(x, y, z)=(x АБО y АБО z)=АБО(x, y, z)=max(x, y, z)	АБО, максимум

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

Повні системи булевих функцій

Суперпозиція і замкнені класи функцій

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

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$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

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

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

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

Тотожність і двоїстість

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

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

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

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

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

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

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

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

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

Функція $g(x_{1},x_{2},\dots ,x_{n})$ називається двоїстою до функції $f(x_{1},x_{2},\dots ,x_{n})$, якщо $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, а із законів де Моргана випливає двоїстість кон'юнкції і диз'юнкції. Тотожна функція, як і функція заперечення, двоїста сама до себе.

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

Повнота системи, критерій Поста

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

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

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

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

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

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

Теорема Поста відкриває шлях до подання булевих функцій синтаксичним способом, який у ряді випадків виявляється набагато зручнішим, ніж таблиці істинності. Відправною точкою тут служить знаходження деякої повної системи функцій $\Sigma =\{f_{1},\ldots ,f_{n}\}$. Тоді кожна булева функція може бути представлена ​​деяким термом в сигнатурі $\Sigma$, який в даному випадку називають також формулою. Щодо вибраної системи функцій корисно знати відповіді на такі питання:

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

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

Диз'юнктивна нормальна форма (ДНФ)

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

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

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

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

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

Кон'юнктивна нормальна форма (КНФ)

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

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

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

$a(b\lor c)\to ab\lor ac$

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

$a\lor bc\to (a\lor b)(a\lor c)$

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

Алгебраїчна нормальна форма (АНФ або поліном Жегалкіна)

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• Гаврилов Г. П.,Сапоженко А. А. Збірник завдань з дискретної математики. — М. : Наука, 1969.
• Марченков С. С. Замкнуті класи булевих функцій. — М. : Фізматліт, 2000.
• Яблонський С. В. Введення в дискретну математику. — М. : Наука, 1986.
• Ігошин В. І. Математична логіка і теорія алгоритмів. — 2- е вид., Стереотип. — М., 2008. — 448 с. — ISBN 978-5-7695-4593-1.
• Самофалов К. Г., Романкевич А. М., Валуйський В. Н., Канівський Ю. С., Пиневич М. М. Прикладна теорія цифрових автоматів. — Київ : Вища Школа, 1987. — С. 183-189.
• Алексєєв В. Б. Дискретна математика (курс лекцій, II семестр). Упоряд. А. Д. Поспєлов
• Бикова С. В., Буркатовський Ю. Б. , Булеві функції, навчально — методичний комплекс, Томськ, 2006