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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Bn — множина всіх можливих послідовностей з 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).


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

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

Основні відомості[ред.ред. код]

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

Таблиці істинності[ред.ред. код]

Булева функція задається кінцевим набором значень, що дозволяє представити її у вигляді таблиці істинності , наприклад [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
\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 =21=2, перша з них тотожно дорівнює 0, а друга 1. Їх називають булевими константами — тотожний нуль і тотожна одиниця.
Таблиця значень і назв нульарна булевих функцій:

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

Унарні функції[ред.ред. код]

При n = 1 число булевих функцій дорівнює 2 21 =22=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 число булевих функцій дорівнює 222 =24=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=xy=xNORy=NOR(x,y)=xНЕ- АБОy= НЕ- АБО(x,y) стрілка Пірса, НЕ-АБО, 2АБО-НЕ, антідіз'юнкція, функція Даггера, функція Вебба, детектор 1
2 0 0 1 0 F2,2=xy=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=xy=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 =xy=xXORy=XOR(x,y)=x><y=x<>y=xNEy= NE(x, y) додавання по модулю 2, виключне «або», сума Жегалкіна[1], не дорівнює
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=xy=x·y=xy=x&y=xANDy=AND(x,y)=xІy=І (x,y)=min(x,y) кон'юнкція , 2І, мінімум, детектор 8
9 1 0 0 1 F2,9=(xy)=x~y=xy=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 = xy=xy=xy=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=xy=xy=xy=xGEy=GE(x,y) зворотня імплікація (від другого аргументу до першого), більше або дорівнює
14 1 1 1 0 F2,14 =xy =x+y =xORy =OR(x,y) =xАБОy=АБО(x,y)=maxx,y) диз'юнкція, 2АБО, максимум
15 1 1 1 1 F2,15 = 1 тотожна одиниця, тавтологія

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

Тернарні функції[ред.ред. код]

При n=3 число булевих функцій дорівнює 2(23)=28=256 (дужки потрібні, так як запис a^{n^m} не має властивість асоціативності і (22)3=43). Деякі з них визначені в наступній таблиці:
Таблиця значень і назв деяких булевих функцій від трьох змінних, що мають власну назву:

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 = xyz = ↓(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)=(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) 3ІЛІ, максимум

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

Повні системи булевих функцій[ред.ред. код]

Суперпозиція і замкнуті класи функцій[ред.ред. код]

Результат обчислення булевої функції може бути використаний в якості одного з аргументів іншої функції. Результат такої операції суперпозиції можна розглядати як нову булеву функцію зі своєю таблицею істинності. Наприклад, функції 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 0
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). Збалансовані булеві функції в основному використовуються в криптографії .
  • За залежності значення функції від перестановки її вхідних бітів розрізняють симетричні булеві функції (значення яких залежить тільки від кількості одиниць на вході) і несиметричні булеві функції (значення яких так само залежить від перестановки її вхідних біт).
  • За значенням функції на протилежних один одному наборах значень аргументів відрізняють самодвоїстої функції (значення яких інвертується при інвертуванні значення всіх входів) від інших булевих функцій, що не володіють такою властивістю . Нижня частина таблиці істинності для самодвоїстих функцій є дзеркальним відображенням інвертованою верхньої частини (якщо розташувати вхідні комбінації в таблиці істинності в природному порядку) .



Див. також[ред.ред. код]

Література[ред.ред. код]

Посилання[ред.ред. код]