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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

+x1x2…xn-1xnf(x1, x2,…,xn)00…00000 … 01000 … 10100 … 110 11…00111…01011…10011…110

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

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

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

Бінарні функції При n=2 число булевих функцій дорівнює 222 =24=16.

Таблиця значень і назв булевих функцій від двох змінних: {|Class="standard" !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=xLTy=LT(x,y) |інверсія зворотньої імплікації, менше, детектор 2 |- !3 ||0||0||1||1||F2,3==x=¬x=NOT1(x,y)=не1(x,y) |заперечення (негація, інверсія) першого операнда |- !4 ||0||1||0||0||F2,4==x>y=xGTy= GT(x,y) |інверсія прямої імплікації, більше, детектор 4 |- !5 ||0||1||0||1||F2,5==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(23)=28=256 (дужки потрібні, так як запис не має властивість асоціативності і (22)3=43). Деякі з них визначені в наступній таблиці: Таблиця значень і назв деяких булевих функцій від трьох змінних, що мають власну назву:

x0 =z10101010x 1=y11001100x2=x11110000ПозначенняНазви 1 00000001 F3,1 = x↓y↓z = ↓(x,y,z) = Webb2(x,y,z) = NOR(x,y,z)стрілка Пірса, НЕ-АБО, 2АБО-НЕ, антидиз'юнкція, функція Даггера, функція Вебба, детектор 12300010111F3,23==Перемикач по більшості з інверсією, 3ППБ-НЕ, мажоритарний клапан з інверсією12601111110F3,126=(x≠y≠z)=[≠(x, y,z)]=NE(x, y,z)Нерівність12701111111F3,127=x|y|z=|(x, y,z)=NAND(x, y,z)3І-НЕ, штрих Шефера12810000000F3,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І, мінімум12910000001F3,129=(x=y=z)=[=(x, y,z)]=EQV(x, y, z)Рівність15010010110F3,150=x⊕y⊕z=x⊕2y⊕2z=⊕2(x, y,z)Тернарне додавання по модулю 221611011000F3,216=f1Розряд позики при тернарному відніманні23211101000F3,232=f2=[>=2(x, y, z)]=≥2(x, y, z)=(x і y) АБО (y і z) АБО (z і x)Розряд переносу при тернарному додаванні, перемикач по більшості, 3ППБ, мажоритарний клапан25411111110F3,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)АБО, максимум При трьох і більше аргументах префіксний (і постфіксний) запис економічніший ніж інфіксний запис.

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

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

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

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

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

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

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

Дві булеві функції тотожні одна одній, якщо на будь-яких однакових наборах аргументів вони приймають рівні значення. Тотожність функцій f і g можна записати, наприклад, так:

Переглянувши таблиці істинності булевих функцій, легко отримати такі тотожності:

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

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

(дистрибутивність кон'юнкції і диз'юнкції)

Функція називається двоїстою до функції , якщо . Легко показати, що в цій рівності f і g можна поміняти місцями, тобто функції f і g двоїсті одна одній. З найпростіших функцій двоїсті одна одній константи 0 і 1, а із законів де Моргана випливає двоїстість кон'юнкції і диз'юнкції. Тотожна функція, як і функція заперечення, двоїста сама до себе.

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

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

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

Американський математик Еміль Пост ввів у розгляд такі замкнені класи булевих функцій: Функції, що зберігають константу і ; Самодвоїсті функції ; Монотонні функції ; Лінійні функції . Ним було доведено, що будь-який замкнутий клас булевих функцій, який не збігається з , цілком утримується в одному з цих п'яти так званих передповних класів, але при цьому жоден з п'яти не міститься цілком в об'єднанні чотирьох інших. Таким чином, критерій Поста для повноти системи зводиться до з'ясування, чи не міститься вся ця система цілком в одному з передповних класів. Якщо для кожного класу в системі знайдеться функція, що не входить до нього, то така система буде повною, і за допомогою вхідних у неї функцій можна буде отримати будь-яку іншу булеву функцію. Пост довів, що множина замкнених класів булевих функцій — зліченна множина.

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

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

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

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

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

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

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