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

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

Бу́лева фу́нкція (функція алгебри логіки, логічна функція) — в дискретній математиці відображення 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=Натуральна ступінь.Властивість6]</ref >).Деякі з них визначені в наступній таблиці:
Таблиця значень і назв деяких булевих функцій від трьох змінних, що мають власну назву:

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 .

Кон'юнктивна нормальна форма ( КНФ )[ред.ред. код]

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

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

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

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



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

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

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