булевская функция это такая функция одного или нескольких булевских переменных которая принимает
Булевы функции
Содержание
1 Понятие булевой функции
Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:
| x 1 | x 2 | . | x n- 1 | x n | f |
|---|---|---|---|---|---|
| 0 | 0 | . | 0 | 0 | f(0,0. 0,0) |
| 0 | 0 | . | 0 | 1 | f(0,0. 0,1) |
| 0 | 0 | . | 1 | 0 | f(0,0. 1,0) |
| 0 | 0 | . | 1 | 1 | f(0,0. 1,1) |
| . | . | . | . | . | . |
| 1 | 1 | . | 0 | 0 | f(1,1. 0,0) |
| 1 | 1 | . | 0 | 1 | f(1,1. 0,1) |
| 1 | 1 | . | 1 | 0 | f(1,1. 1,0) |
| 1 | 1 | . | 1 | 1 | f(1,1. 1,1) |
| x | 0 | x | ¬ x | 1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Функций от двух аргументов шестнадцать. Наиболее употребимые из этих функций (только те, которые существенно зависят от обеих переменных) мы приводим в следующей таблице:
| x 1 | x 2 | x 1 & x 2 | x 1 Ъ x 2 | x 1 Й x 2 | x 1 Е x 2 | x 1 є x 2 | x 1 | x 2 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
2 Суперпозиция функций
Пример 1 (суперпозиция функций).
Суперпозицию ( x & y ) Е ( ¬x Ъ ¬y ) можно прочитать как « x и y плюс не x или не y ».
3 Двойственные функции
Пример 2 (двойственные функции).
Предложение 1 (Двойственная к двойственной функции). Функция, двойственная к двойственной функции f равна самой функции f.
Пример 3 (вектор двойственной функции).
4 Разложение функции по переменным
Разложения по всем переменным дают суперпозицию конъюнкции, дизъюнкции и отрицания.
Следствие 1 (Совершенная дизъюнктивная нормальная форма).
Любая функция f может быть представлена в следующей форме: *
Следствие 2 (Совершенная конъюнктивная нормальная форма).
Совершенная дизъюнктивная и конъюнктивная нормальная формы дают способ представления булевой функции через суперпозицию конъюнкции, дизъюнкции и отрицания если у нас есть таблица значений функции.
Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.
Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0 и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.
Пример 4 (совершенная дизъюнктивная нормальная форма).
Построим совершенную дизъюнктивную нормальную форму функции, заданной следующей таблицей.
| x | y | z | f |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Булевская функция это такая функция одного или нескольких булевских переменных которая принимает
2.1 рТЕДУФБЧМЕОЙЕ МПЗЙЮЕУЛЙИ ЖХОЛГЙК
 |
| тЙУХОПЛ 1 |
ѓX = 1\и ; и 
Y = и × Y = min(X,Y);
уХННБ РП НПДХМА 2 ЛБЛ ВЙОБТОБС ПРЕТБГЙС ПВМБДБЕФ УЧПКУФЧБНЙ ЛПННХФБФЙЧОПУФЙ Й БУУПГЙБФЙЧОПУФЙ
(Б 
b) У = Б (b У), Й РПЬФПНХ ЕЕ НПЦОП ЪБРЙУЩЧБФШ ВЕЪ УЛПВПЛ Б b У Й РЕТЕУФБЧМСФШ УМБЗБЕНЩЕ.
чБЦОЩК РТЙНЕТ РТЙНЕОЕОЙС ВХМЕЧЩИ ЖХОЛГЙК ДБАФ БТЙЖНЕФЙЮЕУЛЙЕ ДЕКУФЧЙС ОБД ДЧПЙЮОЩНЙ ЮЙУМБНЙ: РПУЛПМШЛХ ЧПЪНПЦОЩЕ ЪОБЛЙ Ч ДЧПЙЮОПК УЙУФЕНЕ УХФШ 0 Й 1, ФП ЪБЧЙУЙНПУФЙ ЪОБЛПЧ ТЕЪХМШФБФБ ПФ ЪОБЛПЧ УМБЗБЕНЩИ/УПНОПЦЙФЕМЕК ЧЩТБЦБАФУС ВХМЕЧЩНЙ ЖХОЛГЙСНЙ. рТЙ УМПЦЕОЙЙ ДЧХИ ПДОПЪОБЮОЩИ ДЧПЙЮОЩИ ЮЙУЕМ б Й ч ЪОБЛ УХННЩ Ч НМБДЫЕН ТБЪТСДЕ ТБЧЕО (AB), Б ЪОБЛ РЕТЕОПУБσ ЧПЪОЙЛБЕФ ФПМШЛП ЕУМЙ ПВБ УМБЗБЕНЩИ ТБЧОЩ 1, Ф.Е. σ= бч. хНОПЦЕОЙЕ ПДОПЪОБЮОЩИ ДЧПЙЮОЩИ ЮЙУЕМ ФПЦДЕУФЧЕООП ЛПОЯАОЛГЙЙ, ЮФП ЖБЛФЙЮЕУЛЙ ПФНЕЮЕОП ЧЩЫЕ.
| X | 0 | X | ѓX | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| X | Y | XY | X Y | X Y | X Y | XY | X | Y |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| X | Y | Z | m3 | g1 | g2 |
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 |
нОПЦЕУФЧП ЧУЕИ МПЗЙЮЕУЛЙИ ЖХОЛГЙК, ПФ МАВПЗП ЛПОЕЮОПЗП ЮЙУМБ РЕТЕНЕООЩИ ПВПЪОБЮБЕФУС т2.
чЩУЛБЪЩЧБОЙС Й РТЕДЙЛБФЩ
пУОПЧОЩН РПОСФЙЕН НБФЕНБФЙЮЕУЛПК МПЗЙЛЙ СЧМСЕФУС РПОСФЙЕ ЧЩУЛБЪЩЧБОЙС.
чЩУЛБЪЩЧБОЙЕН ОБЪЩЧБЕФУС РПЧЕУФЧПЧБФЕМШОПЕ РТЕДМПЦЕОЙЕ, ЛПФПТПЕ НПЦЕФ ВЩФШ МЙВП ЙУФЙООЩН, МЙВП МПЦОЩН.
рТЙНЕТ
рТЕДМПЦЕОЙС, Ч ЛПФПТЩЕ ЧИПДСФ РЕТЕНЕООЩЕ Й ЛПФПТЩЕ РТЙ ЪБНЕОЕ ЬФЙИ РЕТЕНЕООЩИ ЙИ ЪОБЮЕОЙСНЙ УФБОПЧСФУС ЧЩУЛБЪЩЧБОЙСНЙ, ОБЪЩЧБАФ ЧЩУЛБЪЩЧБФЕМШОЩНЙ ЖПТНБНЙ ЙМЙ РТЕДЙЛБФБНЙ. рТЙ ЬФПН ДПМЦОП ВЩФШ ЪБДБОП НОПЦЕУФЧП X, ЛПФПТПЕ НПЦЕФ РТЙОЙНБФШ РЕТЕНЕООБС И, ЕУМЙ РТЕДЙЛБФ У ПДОПК РЕТЕНЕООПК (ПДОПНЕУФОЩК РТЕДЙЛБФ).
нОПЦЕУФЧП ф ЪОБЮЕОЙК РЕТЕНЕООПК РТЙ РПДУФБОПЧЛЕ ЛПФПТЩИ Ч РТЕДЙЛБФ РПМХЮБЕФУС ЙУФЙООПЕ ЧЩУЛБЪЩЧБОЙЕ, ОБЪЩЧБАФ НОПЦЕУФЧПН ЙУФЙООПУФЙ РТЕДЙЛБФБ.
еУМЙ РТЕДЙЛБФ ДЧХНЕУФОЩК ( У ДЧХНС РЕТЕНЕООЩНЙ), ФТЕИНЕУФОЩК Й Ф.Д., ФП ДМС ЛБЦДПЗП РЕТЕНЕООПЗП ДПМЦОП ВЩФШ ХЛБЪБОП НОПЦЕУФЧП ЕЗП ЪОБЮЕОЙК.
лЧБОФПТЩ
ч ЖПТНХМЙТПЧЛБИ ТБЪМЙЮОЩИ НБФЕНБФЙЮЕУЛЙИ РТЕДМПЦЕОЙК ЮБУФП ЧУФТЕЮБАФУС УМПЧБ «ОЕЛПФПТЩЕ», «ЧУЕ», «ЛБЦДЩК» Й ЙИ УЙОПОЙНЩ.
тБУУНПФТЕООЩЕ РТЙНЕТЩ РПМХЮЕОЙС ЧЩУЛБЪЩЧБОЙК У РПНПЭША ЛЧБОФПТПЧ ПФОПУЙМЙУШ Л ПДОПНЕУФОЩН ЧЩУЛБЪЩЧБФЕМШОЩН ЖПТНБН (ПДОПНЕУФОЩН РТЕДЙЛБФБН). чУЕ УЛБЪБООПЕ ПУФБЕФУС УРТБЧЕДМЙЧЩН Й ДМС НОПЗПНЕУФОЩИ ЧЩУЛБЪЩЧБФЕМШОЩИ ЖПТН, ОП РТЙ ЬФЙН ОБДП ЙНЕФШ Ч ЧЙДХ, ЮФП Ч РПДПВОЩИ УМХЮБСИ ДМС РПМХЮЕОЙС ЧЩУЛБЪЩЧБОЙК ОБДП УЧСЪБФШ ЛЧБОФПТПН ЛБЦДХА РЕТЕНЕООХА.
рТЙНЕТ
хЦЕ ЗПЧПТЙМПУШ, ЮФП Ч НБФЕНБФЙЛЕ ПДОПК ЙЪ ЧБЦОЕКЫЙИ ЪБДБЮ СЧМСЕФУС ХУФБОПЧМЕОЙЕ ЪОБЮЕОЙС ЙУФЙООПУФЙ ЧЩУЛБЪЩЧБОЙК. чЩСУОЙН, ЛБЛ ХУФБОБЧМЙЧБАФ ЪОБЮЕОЙС ЙУФЙООПУФЙ ЧЩУЛБЪЩЧБОЙК У ЛЧБОФПТБНЙ.
ч ЧЩУЛБЪЩЧБОЙЙ (
И
и) F(x) ХФЧЕТЦДБЕФУС, ЮФП ДМС МАВПЗП И ЙЪ НОПЦЕУФЧБ и ЙУФЙООП F(x), РПЬФПНХ ЮФПВЩ ХВЕДЙФШУС Ч ЙУФЙООПУФЙ ЬФПЗП ЧЩУЛБЪЩЧБОЙС, ОБДП РПЛБЪБФШ, ЮФП НОПЦЕУФЧП ф ЙУФЙООПУФЙ ЧЩУЛБЪЩЧБФЕМШОПК ЖПТНЩ F(x) УПЧРБДБЕФ У НОПЦЕУФЧПН X. юФПВЩ ХВЕДЙФШУС Ч МПЦОПУФЙ ЧЩУЛБЪЩЧБОЙС (Ии) F(x) ДПУФБФПЮОП РПЛБЪБФШ, ЮФП ф
и, ФП ЕУФШ ДПЛБЪБФШ, ЮФП УХЭЕУФЧХЕФ ФБЛПЕ ЪОБЮЕОЙЕ И, РТЙ ЛПФПТПН ЧЩУЛБЪЩЧБФЕМШОБС ЖПТНБ ПВТБЭБЕФУС Ч ЦЕМБЕНПЕ ЧЩУЛБЪЩЧБОЙЕ.
чППВЭЕ, ЙУФЙООПУФШ ЧЩУЛБЪЩЧБОЙС У ЛЧБОФПТПН ПВЭОПУФЙ ХУФБОБЧМЙЧБЕФУС РХФЕН ДПЛБЪБФЕМШУФЧБ. рПЛБЪБФШ МПЦОПУФШ ФБЛЙИ ЧЩУЛБЪЩЧБОЙК НПЦОП, РТЙЧЕДС ЛПОФТРТЙНЕТ.
чЩСУОЙН, ЛБЛ ХУФБОБЧМЙЧБЕФУС ЪОБЮЕОЙЕ ЙУФЙООПУФЙ ЧЩУЛБЪЩЧБОЙК У ЛЧБОФПТПН УХЭЕУФЧПЧБОЙС.
ч ЧЩУЛБЪЩЧБОЙЙ (
И) F(x) ХФЧЕТЦДБЕФУС, ЮФП Ч НОПЦЕУФЧЕ и ЕУФШ ФБЛПК ЬМЕНЕОФ И, ЛПФПТЩК ПВМБДБЕФ УЧПКУФЧПН F. рПЬФПНХ ПОП ВХДЕФ ЙУФЙООП, ЕУМЙ НОПЦЕУФЧП ЙУФЙООПУФЙ ЧЩУЛБЪЩЧБФЕМШОПК ЖПТНЩ F(x) ОЕ РХУФП. дМС ФПЗП ЮФПВЩ РПЛБЪБФШ ЬФП, ДПУФБФПЮОП ОБКФЙ ФБЛПЕ ЪОБЮЕОЙЕ РЕТЕНЕООПК И, РТЙ ЛПФПТПН ЧЩУЛБЪЩЧБФЕМШОБС ЖПТНБ F(x) ПВТБЭБЕФУС Ч ЙУФЙООПЕ ЧЩУЛБЪЩЧБОЙЕ, ФП ЕУФШ РТЙЧЕУФЙ РТЙНЕТ. фБЛ, ЧЩУЛБЪЩЧБОЙЕ «ОЕЛПФПТЩЕ ОБФХТБМШОЩЕ ЮЙУМБ ДЧХЪОБЮОЩЕ» НПЦОП УЮЙФБФШ ЙУФЙООЩН, ФБЛ ЛБЛ 36 ДЕКУФЧЙФЕМШОП ДЧХЪОБЮОПЕ ЮЙУМП.
чЩУЛБЪЩЧБОЙЕ (И) F(x) МПЦОП Ч ФПН УМХЮБЕ, ЛПЗДБ ф=ø ХВЕДЙФШУС Ч ЬФПН НПЦОП МЙЫШ РХФЕН ДПЛБЪБФЕМШУФЧБ.
фБЛЙН ПВТБЪПН, ЙУФЙООПУФШ ЧЩУЛБЪЩЧБОЙС У ЛЧБОФПТПН УХЭЕУФЧПЧБОЙС ХУФБОБЧМЙЧБЕФУС РТЙ РПНПЭЙ ЛПОЛТЕФОПЗП РТЙЕНБ. юФПВЩ ХВЕДЙФШУС Ч МПЦОПУФЙ ФБЛПЗП ЧЩУЛБЪЩЧБОЙС, ОЕПВИПДЙНП РТПЧЕУФЙ ДПЛБЪБФЕМШУФЧП.
Булева функция
Содержание
Основные сведения
Таблицы истинности
Булева функция задаётся конечным набором значений, что позволяет представить её в виде таблицы истинности, например [4] :
| 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 |
 | | | | | |
| 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 1 = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.
Таблица значений и названий нульарных булевых функций:
| Значение | Обозначение | Название |
|---|---|---|
| 0 | F0,0 = 0 | тождественный ноль |
| 1 | F0,1 = 1 | тождественная единица, тавтология |
Унарные функции
При n = 1 число булевых функций равно 2 2 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 2 = 2 4 = 16.
Таблица значений и названий булевых функций от двух переменных:
y = x ↔ y = x EQV y = EQV(x,y)
Аналогичная таблица в английской Википедии.
При двух аргументах префиксная, инфиксная и постфиксная записи, по экономичности, почти одинаковы.
Тернарные функции
При n = 3 число булевых функций равно 2 (2 3 ) = 2 8 = 256 (скобки нужны, так как запись 
не обладает свойством ассоциативности (сочетательности) и (2 2 ) 3 = 4 3 = 64 [6] ). Некоторые из них определены в следующей таблице:
Таблица значений и названий некоторых булевых функций от трех переменных, имеющих собственное название:
| x0=z | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ||
|---|---|---|---|---|---|---|---|---|---|---|
| x1=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) | 3ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса |
| 23 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | F3,23 =  = 2(x,y,z))» border=»0″ /> = ≥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) | 3ИЛИ, максимум |
При трёх и более аргументах префиксная (и постфиксная) запись экономичнее инфиксной записи.
Полные системы булевых функций
Суперпозиция и замкнутые классы функций
Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции 
(суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:
 |  |  |  |
|---|---|---|---|
| 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 |
Говорят, что множество функций замкнуто относительно операции суперпозиции, если любая суперпозиция функций из данного множества тоже входит в это же множество. Замкнутые множества функций называют также замкнутыми классами.
В качестве простейших примеров замкнутых классов булевых функций можно назвать множество 
, состоящее из одной тождественной функции, или множество 
, все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций 
и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы и , мы с помощью суперпозиции 
сможем получить константу 1, которая в исходных классах отсутствовала.
Разумеется, множество 
всех возможных булевых функций тоже является замкнутым.
Тождественность и двойственность
Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так: 
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
 |  |  |  |  |
 |  |  |  |  |
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
 |  |
 |  | (законы де Моргана) |
(дистрибутивность конъюнкции и дизъюнкции)
Функция 
называется двойственной функции 
, если 
. Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Полнота системы, критерий Поста
Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством .
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с , целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом, критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию. Пост доказал, что множество замкнутых классов булевых функций — счётное множество.
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее, чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций 
. Тогда каждая булева функция может быть представлена некоторым термом в сигнатуре 
, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция
Например 
— является ДНФ.
Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: 
.
Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции, отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора 
построить конъюнкцию 
, где 
. Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации 
результатом является 
, что можно упростить до 
.
Конъюнктивная нормальная форма (КНФ)
Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.
Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».
КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:
которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило
выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.
Алгебраическая нормальная форма (АНФ или полином Жегалкина)
Алгебраическая нормальная форма (общепринятое название в зарубежной литературе) или полином Жегалкина (название, используемое в отечественной литературе) — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции («И», AND), а в качестве сложения — сложение по модулю 2 (исключающее «ИЛИ», XOR). Для получения полинома Жегалкина следует выполнить следующие действия: