Алгебра логики
Функции тождественны, если $f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)$ на всех наборах аргументов (таблицы истинности совпадают).
$f(\overline
Важно: Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Нормальные и совершенные нормальные формы: КНФ, ДНФ, СДНФ, СКНФ
Простая конъюнкция или конъюнкт = конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) = дизъюнкция простых конъюнкций. Пример: $a \overline c\lor b c\lor\overline$.
Совершенная ДНФ (СДНФ) относительно некоторого набора переменных = ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Пример: $a \overline c\lor a b c\lor\overline b\overline
СДНФ и СКНФ можно построить по таблице истинности.
Булева Алгебра (Алгебра Буля)
Формально: непустое множество $A$ с двумя бинарными операциями $\land$ (конъюнкция), $\lor$ (дизъюнкция), унарной операцией $\lnot$ (отрицание) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех »a», »b» и »c» из множества $A$ верны следующие аксиомы:
Проблема разрешимости
Все формулы алгебры логики делятся на тождественно истинные (всегда 1), тождественно ложные (всегда 0) и выполнимые (иногда 0, иногда 1).
Проблема разрешимости: к какому классу (из вышеперечисленных) относится данная формула?
Для каждой формулы может быть составлена таблица истинности, которая и даст ответ на поставленный вопрос, но при большом количестве переменных практическое использование таблиц истинности затруднительно.
Нетабличный способ определения формулы к данному классу
Способ состоит в приведении формулы к нормальной форме (ДНФ или КНФ) и использовании правил, которые позволяют определить, какой является формула (тождественно истинной, тождественно ложной, выполнимой).
- Критерии тождественной истинности: необходимо и достаточно, чтобы любая дизъюнкция, входящая в КНФ, содержала переменную и её отрицание.
- Критерии тождественной ложности: необходимо и достаточно, чтобы любая конъюнкция, входящая в ДНФ, содержала переменную и её отрицание.
Замкнутые классы. Монотонные функции
Замкнутый класс — такое множество булевых функций, замыкание которого относительно операции суперпозиции совпадает с ним самим: $[P]=P$. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества $P$, снова входит в это же множество.
В 1941 году Эмиль Пост представил полное описание системы замкнутых классов (решетку Поста).
Примеры замкнутых классов:
Множество $P_2$ всех возможных булевых функций замкнуто.
Особо важны для теории булевых функций следующие замкнутые классы, называемые предполными классами:
- Класс $T_0$ функций, сохраняющих 0: $T_0=\left\
- Класс $T_1$ сохраняющих 1: $T_1=\left\
- $S$ самодвойственных функций: $S=\left\
)=\overline - $M$ монотонных функций: $M=\left\
- $L$ линейных функций: $L=\left\
Ни один из предполных классов не содержится целиком в объединении четырёх остальных; любой замкнутый класс булевых функций, отличный от $P_2$, целиком содержится хотя бы в одном из пяти предполных классов.
Другими важными замкнутыми классами являются:
- Класс конъюнкций K, являющийся замыканием множества $\<\land,0,1\>$. Он представляет собой множество функций вида $c_0\land(c_1\lor x_1)\land\ldots\land(c_n\lor x_n)$.
- Класс дизъюнкций D, являющийся замыканием множества $\<\lor,0,1\>$. Он представляет собой множество функций вида $c_0\lor(c_1\land x_1)\lor\ldots\lor(c_n\land x_n)$.
- Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений).
- Класс $O^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах.
- Класс $O^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\ge x_i$, где $x_i$ — одна из переменных функции.
- Класс $I^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах.
- Класс $I^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\le x_i$, где $x_i$ — одна из переменных функции.
В 1941 году Эмиль Пост показал, что любой замкнутый класс булевых функций является пересечением конечного числа описанных выше классов, приведя полное описание структуры замкнутых классов двузначной логики. Также Пост установил, что любой замкнутый класс может быть порожден конечным базисом.
Полные системы функций. Базисы + Пост — основная теорема о функциональной полноте
Множество функций $A$ — полная система, если замыкание $A$ совпадает с множеством всех булевых функций $[A]=P_2$ (т.е. любую логическую функцию можно выразить формулой с использованием только функций множества $A$).
Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов $T_0$, $T_1$, $S$, $M$, $L$. В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера (отрицание конъюнкции).
Широко известны такие полные системы булевых функций:
- $\left\<\land,\lor,\neg\right\>$ (конъюнкция, дизъюнкция, отрицание) — ДНФ.
- $\left\<\land,\oplus,1\right\>$ (конъюнкция, сложение по модулю 2, константа 1) — полином Жегалкина.
Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента. Первая из упоминавшихся выше полных систем базисом не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является базисом — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему $\left\<\oplus,1\right\>$ можно назвать базисом класса линейных функций.
Алгебра Жегалкина
Полином Жегалкина — полином над $Z_2$ (коэффициенты только 0 и 1), в качестве произведения — конъюнкция, а в качестве сложения — исключающее или (xor, не равно, сложение по модулю 2). Общий вид:
$P = a \oplus \bigoplus_< \begin
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина.
Переключательные схемы
Функции проводимости $F$ некоторых переключательных схем:
a)
Схема не содержит переключателей и проводит ток всегда, следовательно $F=1$;
б) Схема содержит один постоянно разомкнутый контакт, следовательно $F=0$;
в) Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, $F(x) = x$;
г) — Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда $х$ замкнут, следовательно, $F(x) = \bar x$;
д) Схема проводит ток, когда оба переключателя замкнуты, следовательно, $F(x) = x \land y$;
е) Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, $F(x)=x \lor y$;
ж) Схема состоит из двух параллельных ветвей и описывается функцией .
Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).
Из двух равносильных схем более простой считается та схема, функция проводимости которой содержит меньшее число логических операций или переключателей.
Способы доказательства тавтологии и следствия
Тавтологией называется тождественно истинное высказывание, верное при любых значениях своих компонентов. Формула в исчислении высказываний является тавтологией или тождественно истинной, если её значение для любых значений аргументов истинно.
Примеры тавтологий:
- $ A \to A $ («Из »A» следует »A»»)
- $(A) \lor (\lnot A)$ («»A» или не-»A»»)
- $\overline
$.
- $(P \land (P \to Q)) \to Q$
- $A \to (B \to A)$
Формула F называется тавтологией, или тождественно истинной формулой, если F истинно при любой интерпретации.
Понятие тавтологии "двойственно"’ понятию выполнимой формулы: $F$ – тавтология тогда и только тогда, когда $\lnot F$ не выполнима. Определение эквивалентных формул, данное выше, может быть переформулировано следующим образом: F эквивалентна G, если F є G – тавтология.
Формула является »тождественно истинной», если она истинна при любых значениях входящих в неё переменных. Вот несколько широко известных примеров тождественно истинных формул логики высказываний:
Законы де Моргана:
1) $ \neg (p \lor q) \leftrightarrow (\neg p \land \neg q)$;
2) $ \neg (p \land q) \leftrightarrow (\neg p \lor \neg q)$;
Закон контрапозиции:
$(p\to q)\leftrightarrow(\neg q\to \neg p)$;
1) $p\lor(p\land q)\leftrightarrow p$;
2) $p\land(p\lor q)\leftrightarrow p$;
1) $p\land(q\lor r)\leftrightarrow(p\land q)\lor(p \land r)$;
2) $p\lor(q\land r)\leftrightarrow(p\lor q)\land(p \lor r)$.
Общие свойства символа тавтология
Правило введения и удаления логических знаков
Метод Резолюции. Теорема о замене. Теорема о резолюциях. Доказательство тавтологии с помощью метода резолюции
Правило резолюций – это правило вывода, восходящее к методу доказательства теорем через поиск противоречий; используется в логике высказываний и логике предикатов первого порядка. Правило резолюций, применяемое последовательно для списка резольвент, позволяет ответить на вопрос, существует ли в исходном множестве логических выражений противоречие
Пусть $C_1$ и $C_2$ — два предложения в исчислении высказываний, и пусть $C_1 = P \lor C’_1$, а $C_2 = \lnot P \lor C’_2$, где $P$ — пропозициональная переменная, а $C’_1$ и $C’_2$ — любые предложения (в частности, может быть, пустые или состоящие только из одного литерала). Правило вывода
называется правилом резолюции. Предложения C1 и C2 называются »резольвируемыми» (или »родительскими»), предложение $C’_1 \lor C’_2$ — »резольвентой», а формулы $P$ и $\lnot P$ — »контрарными» литералами.
Алгоритм:
- Составляем список дизъюнктов.
- Находим среди них какую-либо пару, в которой один дизъюнкт содержит переменную, а другой — ее отрицание. На основе этих двух дизънктов получаем один новый, которы заносим в список. И начинаем поиск подходящей пары снова.
- Все это продолжается до тех пор, пока на некотором шаге в списке не окажется пара $a$ и $\lnot a$.
Исчисление высказываний
Составное высказывание
Сокращенные таблицы истинности
Выбираем значение переменной, подставляем в логическое выражение, упрощаем выражение, заполняем строки в таблице истинности. Повторяем этот шаг пока таблица истинности не будет заполнена.
Формальные теории (исчисление)
Формальная теория — результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.
Формальная теория – это совокупность абстрактных объектов, не связанных с реальным миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета их смыслового содержания, т.е. семантики.
Формальная теория считается определенной, если:
- Задано конечное или счётное множество произвольных символов. Конечные последовательности символов называются выражениями теории.
- Имеется подмножество выражений, называемых формулами.
- Выделено подмножество формул, называемых аксиомами.
- Имеется конечное множество отношений между формулами, называемых правилами вывода.
Аксиоматичное построение исчисления высказываний, правило вывода (правило заключения)
- алфавит есть множество символов:
- $а, b, . а_1, b_1. $ — (пропозициональные) переменные, значением которой может быть логическое высказывание;
- $\neg, \land, \lor, \to$ (отрицание, конъюнкция, дизъюнкция и импликация) — пропозициональные связк;
- (,) — скобки, служебные символы;
- Если $P$ — пропозициональная переменная, то $P$ — формула.
- Если $A$ — формула, то $\neg A$ — формула.
- Если $A$ и $B$ — формулы, то $A \to B$, $A \land B$ и $A \lor B$ — формулы.
- Других соглашений нет.
- $A \to (B \to A)$;
- $((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$;
- $A \land B \to A$;
- $A \land B \to B$;
- $A \to (B \to (A \land B))$;
- $A \to (A \lor B)$;
- $B \to (A \lor B)$;
- $(A \to C) \to ((B \to C) \to ((A \lor B) \to C))$;
- $\neg A \to (A \to B)$;
- $(A \to B) \to ((A \to \neg B)\to \neg A)$;
- $A\lor\neg A$.
вместе с единственным правилом вывода:
Сравнение результатов аксиоматической теории исчисления с результатами, относящимися к тавтологии
Предикаты. n-местный предикат. Кванторы
Предикат (»n»-местный, или »n»-арный) — функция с множеством значений $\< 0,1 \>$ (или «ложь» и «истина»), определённая на множестве $M=<
_<1>>\times < _<2>>\times \ldots \times < _ >$. Таким образом, каждый набор элементов множества »M» он характеризует либо как «истинный», либо как «ложный». Тождественно-истинный предикат: $P\left ( x_1, . x_n \right) \equiv 1$ (на любом наборе аргументов равен 1).
Тождественно-ложный предикат: $P\left ( x_1, . x_n \right) \equiv 0$ (на любом наборе аргументов равен 0).
Предикат выполнимый, если хотя бы на одном наборе аргументов он равен 1.
Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего используются:
- Квантор всеобщности $\forall$ — «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
- Квантор существования $\exists$, читается: «существует…» или «найдётся…».
В математической логике приписывание квантора к формуле называется связыванием или навешиванием квантора.
Связанные переменные
Переменная $v$ связана в формуле $F$, если $F$ содержит $Kv$, где $K$ — квантор.
Предикаты на конечных областях. Логика одноместных предикатов
Значений $x$ конечное число, их можно перебрать.
Конъюнкция — пересечение областей определения, дизъюнкция — объединение областей определения, отрицание — дополнение области определения.
Кванторы по предикатным переменным
Правило отрицания кванторов: применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:
Определение булевой функции
Элементы булева множества [math]1[/math] и [math]0[/math] обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения [math]B^n[/math] называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается [math]P_2[/math] , а от n переменных — [math]P_2(n)[/math] . Булевы функции названы так по фамилии математика Джорджа Буля.
Содержание
Основные сведения
Определение: А́рность (англ. arity) функции — количество ее аргументов. Каждая булева функция арности [math]n[/math] полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины [math]n[/math] . Число таких векторов равно [math]2^n[/math] . Поскольку на каждом векторе булева функция может принимать значение либо [math]0[/math] , либо [math]1[/math] , то количество всех n-арных булевых функций равно [math]<2^2>^n[/math] . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
Таблица истинности [math]x_1[/math] [math]x_2[/math] [math]\ldots[/math] [math]x_n[/math] [math]f(x_1,x_2,\ldots,x_n)[/math] [math]0[/math] [math]0[/math] [math]\ldots[/math] [math]0[/math] [math]f(0,0,\ldots,0)[/math] [math]1[/math] [math]0[/math] [math]\ldots[/math] [math]0[/math] [math]f(1,0,\ldots,0)[/math] [math]0[/math] [math]1[/math] [math]\ldots[/math] [math]0[/math] [math]f(0,1,\ldots,0)[/math] [math]1[/math] [math]1[/math] [math]\ldots[/math] [math]0[/math] [math]f(1,1,\ldots,0)[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]0[/math] [math]1[/math] [math]\ldots[/math] [math]1[/math] [math]f(0,1,\ldots,1)[/math] [math]1[/math] [math]1[/math] [math]\ldots[/math] [math]1[/math] [math]f(1,1,\ldots,1)[/math] Практически все булевы функции малых арностей ( [math]0, 1, 2[/math] и [math]3[/math] ) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной (англ. dummy variable).
Нульарные функции
При [math]n = 0[/math] количество булевых функций равно [math]<2^2>^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.
Унарные функции
При [math]n = 1[/math] число булевых функций равно [math]<2^2>^1 = 2^2 = 4[/math] .
Таблица значений булевых функций от одной переменной:
Функции от одной переменной [math]0[/math] [math]x[/math] [math]\neg x[/math] [math]1[/math] 0 [math]0[/math] [math]0[/math] [math]1[/math] [math]1[/math] 1 [math]0[/math] [math]1[/math] [math]0[/math] [math]1[/math] Сохраняет 0 ✓ ✓ Сохраняет 1 ✓ ✓ Самодвойственная ✓ ✓ Монотонная ✓ ✓ ✓ Линейная ✓ ✓ ✓ ✓ Названия булевых функций от одной переменной:
Обозначение Название [math]0[/math] тождественный ноль, тождественная ложь, тождественное «НЕТ» [math]x[/math] тождественная функция, логическое «ДА», «YES»(англ.) [math]\bar x,\ \neg x,\ x'[/math] отрицание, логическое «НЕТ», «НЕ», «НИ», «NOT»(англ.), «NO»(англ.) [math]1[/math] тождественная единица, тождественная истина, тождественное «ДА», тавтология Бинарные функции
При [math]n = 2[/math] число булевых функций равно [math]<2^2>^2 = 2^4 = 16[/math] .
Таблица значений булевых функций от двух переменных:
Функции от двух переменных: x y [math]0[/math] [math]x \land y[/math] [math]x \nrightarrow y[/math] [math]x[/math] [math]x \nleftarrow y[/math] [math]y[/math] [math]x \oplus y[/math] [math]x \lor y[/math] [math]x \downarrow y[/math] [math]x = y[/math] [math]\neg y[/math] [math]x \leftarrow y[/math] [math]\neg x[/math] [math]x \rightarrow y[/math] [math]x \triangledown y[/math] [math]1[/math] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Сохраняет 0 ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Сохраняет 1 ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Самодвойственная ✓ ✓ ✓ ✓ Монотонная ✓ ✓ ✓ ✓ ✓ ✓ Линейная ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Названия булевых функций от двух переменных:
Обозначение Другие обозначения Название [math]0[/math] тождественный ноль, тождественная ложь, тождественное «НЕТ» [math]x \land y[/math] [math]x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y), x [/math] И [math]y,[/math] И [math](x, y)[/math] 2И, конъюнкция [math]x \nrightarrow y[/math] [math]x \gt y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)[/math] больше, инверсия прямой импликации [math]x[/math] [math]YES1(x,y),[/math] ДА1 [math](x, y)[/math] первый операнд [math]x \nleftarrow y[/math] [math]x \lt y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)[/math] меньше, инверсия обратной импликации [math]y[/math] [math]YES2(x, y),[/math] ДА2 [math](x, y)[/math] второй операнд [math]x \oplus y[/math] [math]x + _2 y,\ x \not = y,\ x \gt \lt y,\ x \lt \gt y,\ x\ XOR\ y,\ XOR(x,y)[/math] сложение по модулю 2, не равно, ксор, исключающее «или» [math]x \lor y[/math] [math]x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),[/math] [math]x [/math] ИЛИ [math]y,[/math] ИЛИ [math](x, y)[/math] 2ИЛИ, дизъюнкция [math]x \downarrow y[/math] [math]x\ NOR\ y,\ NOR(x,y)[/math] [math]x [/math] ИЛИ-НЕ [math]y,[/math] ИЛИ-НЕ [math](x, y)[/math] НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса [math]x = y[/math] [math]x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y[/math] равенство, эквивалентность [math]\neg y[/math] [math]NOT2(x, y),\ y’,\ \bar ,[/math] НЕ2 [math](x, y)[/math] отрицание (негация, инверсия) второго операнда [math]x \leftarrow y[/math] [math]x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)[/math] больше или равно, обратная импликация (от второго аргумента к первому) [math]\neg x[/math] [math]NOT1(x,y),\ x’,\ \bar ,[/math] НЕ1 [math](x, y)[/math] отрицание (негация, инверсия) первого операнда [math]x \rightarrow y[/math] [math]x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)[/math] меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму) [math]x \triangledown y[/math] [math]x \mid y,\ x\ NAND\ y,\ NAND(x,y),[/math] [math]x [/math] И-НЕ [math]y,[/math] И-НЕ [math](x, y)[/math] НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера [math]1[/math] тождественная единица, тождественная истина, тождественное «ДА», тавтология Тернарные функции
При [math]n = 3[/math] число булевых функций равно [math]<2^2>^3 = 2^8 = 256[/math] . Некоторые из них определены в следующей таблице:
Таблица истинности некоторых тернарных функций [math]x[/math] [math]y[/math] [math]z[/math] [math]x \downarrow y \downarrow z[/math] [math]\neg (\geq 2(x,y,z))[/math] [math]x \not = y \not = z[/math] [math]x \mid y \mid z[/math] [math]min(x,y,z)[/math] [math]x=y=z[/math] [math]x \oplus y \oplus z[/math] [math]\geq 2(x,y,z)[/math] [math]f_1[/math] [math]f_2[/math] [math]max(x,y,z)[/math] 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 Названия булевых функций трех переменных:
Обозначения Другие обозначения Названия [math]x \downarrow y \downarrow z[/math] [math]\downarrow (x,y,z) = Webb_2 (x,y,z)[/math] 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса [math]\neg (\geq 2(x,y,z))[/math] Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией [math]x \not = y \not = z[/math] [math][\not =(x,y,z)] = NE(x,y,z)[/math] Неравенство [math]x \mid y \mid z[/math] [math]\mid(x,y,z)[/math] 3-И-НЕ, штрих Шеффера [math]x \land y \land z[/math] [math]\land (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z) = \lt br/\gt (x[/math] И [math] y[/math] И [math] z) = [/math] И [math](x,y,z)[/math] 3-И, минимум [math]x=y=z[/math] [math][=(x,y,z)] = EQV(x,y,z)[/math] Равенство [math]x \oplus y \oplus z[/math] [math]x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)[/math] Тернарное сложение по модулю 2 [math]\geq 2(x,y,z)[/math] [math](x [/math] И [math]y) [/math] ИЛИ [math](y[/math] И [math] z)[/math] ИЛИ [math](z [/math] И [math] x)[/math] переключатель по большинству, 3-ППБ, мажоритарный клапан [math]f_1[/math] Разряд займа при тернарном вычитании [math]f_2[/math] Разряд переноса при тернарном сложении [math]x+y+z[/math] [math]+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) = (x [/math] ИЛИ [math] y [/math] ИЛИ [math] z) = [/math] ИЛИ [math](x,y,z)[/math] 3-ИЛИ, максимум Представление функции формулой
Определение: Если выбрать некоторый набор булевых функций [math]A[/math] , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula). Например, если [math]A = \left\<\land,\neg\right\>[/math] , то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]
Тождественность и двойственность
Определение: Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
[math]f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)[/math]Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
[math]\overline<0>=1[/math] [math]\overline<1>=0[/math] [math]\overline<\overline >=x[/math] [math]x \land y=y \land x\![/math] [math]x\lor y=y \lor x[/math] [math]0 \land x=0\![/math] [math]1 \land x=x\![/math] [math]0 \lor x=x[/math] [math]1\lor x=1[/math] [math]x \land x=x \lor x=x[/math] А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
[math]x \land \overline =0[/math] [math]x \lor \overline =1[/math] [math]\overline =\overline \lor\overline [/math] [math]\overline \land\overline =\overline (законы де Моргана) [math]x \land (y\lor z)=(x \land y)\lor (x \land z)[/math]
[math]x \lor (y \land z)=(x\lor y) \land (x\lor z)[/math] (дистрибутивность конъюнкции и дизъюнкции)Определение: Функция [math]g(x_1,x_2,\dots,x_n)[/math] называется двойственной (англ. duality) функции [math]f(x_1,x_2,\dots,x_n)[/math] , если [math]f(\overline ,\overline ,\dots,\overline )=\overline Легко показать, что в этом равенстве [math]f[/math] и [math]g[/math] можно поменять местами, то есть функции [math]f[/math] и [math]g[/math] двойственны друг другу. Из простейших функций двойственны друг другу константы [math]0[/math] и [math]1[/math] , а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Суперпозиции
Определение: Суперпозиция функций, композиция функций (англ. function composition) — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Пусть нам дан некоторый набор булевых функций [math]K[/math] . Получить новую функцию, являющеюся композицией функций из [math]K[/math] , мы можем следующими способами:
- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Полнота системы, критерий Поста
Определение: Замыкание множества функций (англ. сlosure) — подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества. Определение: Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций. Американский математик Эмиль Пост [1] сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
- самодвойственныые функции [math]S[/math] ,
- монотонные функции [math]M[/math] ,
- линейные функции [math]L[/math] .
Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math] , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций [math]\Sigma = \
- Как построить по данной функции представляющую её формулу?
- Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
- В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.
Дизъюнктивная нормальная форма (ДНФ)
Определение: Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов. Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.
Примеры ДНФ:
[math]f(x,y,z) = (x \land y) \lor (y \land \neg
)[/math] . [math]f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg
) \lor (x \land \neg ) [/math] . Конъюнктивная нормальная форма (КНФ)
Определение: Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.
[math]f(x,y,z) = (x \lor y) \land (y \lor \neg
)[/math] [math]f(x,y,z,t) = (x \lor t) \land (y \lor \neg
) \land (\neg \lor \neg ) \land (\neg \lor \neg \lor z)[/math] [math]f(x,y,z,t,m) = (x \lor m \lor \neg
) \land (y \lor \neg ) \land (y \lor t \lor \neg )[/math] Полином Жегалкина
Определение: Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида [math]0[/math] и [math]1[/math] , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином Жегалкина имеет следующий вид:
[math]P = a_ <000\ldots000>\oplus a_ <100\ldots0>x_1 \oplus a_ <010\ldots0>x_2 \oplus \ldots \oplus a_ <00\ldots01>x_n \oplus a_ <110\ldots0>x_1 x_2 \oplus \ldots \oplus a_ <00\ldots011>x_
x_n \oplus \ldots \oplus a_ <11\ldots1>x_1 x_2 \ldots x_n [/math] С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] , который, в свою очередь, по теореме Поста является полным.
[math]f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 [/math]
[math]f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 [/math]
[math]f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 [/math]
Тождественные функции. Выражение функций друг через друга
Определение: Тождественные функции — функции, которые при любых одинаковых аргументах принимают равные значения. Приведение тождественной функции есть выражение булевой функции через другие.
Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.
[math] x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )[/math]
[math] x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y[/math]
Подстановка одной функции в другую
Определение: Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_<1>, \ldots, x_ , g(x_, \ldots, x_ Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:
- [math] f(a,b) = a \vee b [/math]
- [math] g(a) = \neg a [/math]
Отождествление переменных
Определение: Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_<1>, \ldots, x_ , x_ ) = f(x_<1>, \ldots, x_, \ldots, x_ , x_, x_ )[/math] Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math] .
[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами
Схемы из функциональных элементов
Определение: Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе [math]B[/math] , в котором: 1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
Отождествление переменных осуществляется при помощи ветвления проводников.
Чтобы осуществить подстановку одной функции в другую нужно выход логического элемента, который реализует первую функцию, направить на вход логического элемента, который реализует вторую функцию.
Некоторые логические элементы:
И ИЛИ НЕ Штрих Шеффера Стрелка Пирса 
Стандартный базис
Определение: Стандартный базис — система булевых функций: [math]\ <\land, \lor, \lnot \>[/math] Если рассматривать множество бинарных булевых функций [math]P_2(2)[/math] , то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы [math] 0 [/math] с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:
[math] x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) [/math]
[math] x \rightarrow y = \lnot x \lor y [/math]
[math] 0 = x \land \lnot x [/math]
Функции [math] \mid \ и \downarrow[/math] являются отрицаниями функций [math] \land \ и \ \lor[/math] соответственно.
[math] x \mid y = \lnot \left ( x \land y \right )[/math]
[math] x \downarrow y = \lnot \left ( x \lor y \right )[/math]
Тождественность функций можно доказать с помощью таблицы истинности.
Выразим через стандартный базис обратную импликацию [math] \left (x \leftarrow y \right ) [/math] .
[math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]
Полнота стандартного базиса
[math] x \land y = \lnot \left (\lnot x \lor \lnot y \right ) [/math]
[math] x \lor y = \lnot \left (\lnot x \land \lnot y \right ) [/math]
Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:
[math] \ < \land , \lnot \>[/math] (конъюнктивный базис Буля)
[math] \ < \lor , \lnot \>[/math] (дизъюнктивный базис Буля)
Теоремы о числе функций в базисе
Рассмотрим произвольный безызбыточный базис [math] X[/math] . Тогда по теореме Поста [math]X[/math] содержит следующие функции (не обязательно различные):
[math]f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L[/math] , где [math] T_0, T_1, S, M, L[/math] — классы Поста.
Значит, так как [math]X[/math] — безызбыточный базис, а система [math]\
Рассмотрим [math]f_0[/math] . Возможны два случая:
1. [math] f_0(1, 1, \ldots, 1) = 0 [/math] , тогда [math]f_0[/math] также не сохраняет единицу и немонотонная, т.е.
[math] f_0 = f_1 = f_m [/math] . Значит, [math]\left | X \right | \le 3[/math] .
2. [math] f_0(1, 1, \ldots, 1) = 1 [/math] , тогда [math]f_0[/math] несамодвойственная, т.е.
5.3. Булевы функции от одной и двух переменных
<0,1>. В следующей таблице приведены все четыре булевы функции от одной переменной.
x g 0 ( x ) g 1 ( x ) g 2 ( x ) g 3 ( x )
g 0 ( x )=0 – функция, тождественно равная 0 (тождественный ноль);
g 1 ( x )= x – тождественная функция;
g 2 ( x )=1– x – эта функция соответствует отрицанию и носит то же название; в теории булевых функций отрицание принято обозначать через x ’, поэтому мы будем писать g 2 ( x )= x ’;
g 3 ( x )=1 – функция, тождественно равная 1 (тождественная единица).
Булевы функции от двух переменных можно рассматривать как бинарные операции на множестве <0,1>. В следующей таблице приведены все шестнадцать булевых функции от двух переменных (значения аргументов и функций выписаны в строках, функции перечисляются в столбце). Для некоторых функций указаны используемые обозначения и названия.
0 – тождественный ноль
– сложение по модулю 2
1 – тождественная единица
перечисленные функции (с помощью
суперпозиций), можно строить более сложные булевы функции,
в том числе и большего числа переменных, например, xy → zt и т.п. Булевы отрицание, конъюнкция (умножение), дизъюнкция, импликация обладают свойствами, подобными тем, которыми обладают соответствующие логические операции (с естественной заменой равносильности формул на равенство функций). Например, законы де Моргана принимают следующий вид (знак умножения, как это часто делается, опущен):
( xy )’= x ’ y ’; ( x y )’= x ’ y ’.
Кроме того, имеем:
Приведем некоторые уравнения, в которых одни булевы функции выражены через другие:
x ’ = x → 0 = x | x = x ↓ x = 1 x ;
xy = ( x ’ y ’)’ = x ’ ↓ y ’ = ( x ↓ x ) ↓ ( y ↓ y );
x y = ( x ’ y ’)’ = x ’ → y = =( x → y ) → y = x ’| y ’ = ( x | x )|( y | y ); x → y = x ’ y ;
x ↔ y = ( x → y ) ( y → x ) = xy x ’ y ’; x y = xy ’ x ’ y .
Все эти равенства легко проверяются с помощью таблиц.
Принцип двойственности естественным образом переносится на булевы функции. Приведем необходимые формулировки. Двойственной к булевой функции f ( x , y ,…, z ) называется функция
f * ( x , y ,…, z )= f ’( x ’, y ’,…, z ’).
Если f ( x , y ,…, z ) представлена формулой, содержащей только конъюнкции, дизъюнкции и отрицания, то двойственная функция получается заменой в этой формуле конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции.
Существует простой способ дать аналитическое представление функции в виде формулы, содержащей конъюнкции, дизъюнкции и отрицания, используя ее табличное задание. Например, пусть функция от трех переменных задана следующей таблицей:
x y z f ( x , y , z )
f ( x , y , z ) = x ’ y ’ z ’ xy ’ z ’ xyz .
Каждый из трех дизъюнктивных членов (слагаемых) записанной формулы соответствует набору значений аргументов, для которого функция принимает значение 1. Каждое слагаемое содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 0 в соответствующем наборе. Так, набору (0,0,0) соответствует слагаемое x ’ y ’ z ’, набору (1,0,0) – слагаемое xy ’ z ’, набору (1,1,1)
– слагаемое xyz . Каждый из дизъюнктивных членов принимает значение 1 на своем наборе значений переменных и значение 0
– на всех остальных. Дизъюнкция этих трех слагаемых принимает значение 1 лишь тогда, когда значение 1 принимает хотя бы одно из слагаемых. Таким образом, функция в правой части записанного равенства принимает значение 1 на тех же трех наборах значений аргументов, что и функция f (на остальных наборах обе эти функции принимают значение 0). Тем самым справедливость равенства установлена.
Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Получаемые при этом формулы называются совершенными дизъюнктивными нормальными формами , сокращенно СДНФ. Считается, что СДНФ тождественного нуля – это «пустая» дизъюнкция, не содержащая ни одного дизъюнктивного слагаемого.
Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме , сокращенно СКНФ. СКНФ рассмотренной ранее функции имеет следующий вид:
f ( x , y , z ) = ( x y z ’)( x y ’ z )( x y ’ z ’)( x ’ y z ’)( x ’ y ’ z ).
Каждый из пяти конъюнктивных членов (множителей) соответствует набору значений аргументов, для которого функция принимает значение 0. Каждый множитель содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 1 в соответствующем наборе. Так, набору (0,0,1) соответствует множитель xyz ’, набору (0,1,0) –
множитель xy ’ z , и т. д. Каждый из конъюнктивных членов принимает значение 0 на своем наборе значений переменных и значение 1 – на всех остальных. Конъюнкция этих трех множителей принимает значение 0 лишь тогда, когда значение 0 принимает хотя бы один из множителей. Таким образом, функция в правой части записанного равенства принимает значение 0 на тех же трех наборах значений аргументов, что и функция f .
Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной.
Теорема. Пусть f ( x 1 , x 2 ,…, x n ) – произвольная булева функция. Тогда
f ( x 1 , x 2 ,…, x n ) = x 1 f (1, x 2 ,…, x n ) x 1 ’ f (0, x 2 ,…, x n );
f ( x 1 , x 2 ,…, x n ) = ( x 1 f (0, x 2 ,…, x n ))( x 1 ’ f (1, x 2 ,…, x n )).
Доказательство. Докажем первую формулу. Чтобы не загромождать выкладки индексами и многоточиями, ограничимся случаем функции от двух переменных. Доказываемая формула принимает следующий вид:
f ( x , y ) = x f (1, y ) x ’ f (0, y ).
При любом y подстановка в правую часть x =1 и x =0 дает соответственно
1 f (1, y ) 1’ f (0, y ) = f (1, y ) 0 f (0, y ) = f (1, y ) 0 = f (1, y );
0 f (1, y ) 0’ f (0, y ) = 0 1 f (0, y ) = 1 f (0, y ) = f (0, y ).
Таким образом, левая и правая части доказываемого равенства совпадают на любом наборе значений аргументов. Следовательно, функции слева и справа от знака равенства равны. На общий случай доказательство распространяется практически без изменений. Достаточно считать, что y обозначает не одну переменную, а набор переменных. Второе равенство из формулировки теоремы доказывается аналогично (впрочем, его справедливость следует из принципа двойственности).
Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно получить СДНФ булевой функции. Например,
f ( x , y ) = x f (1, y ) x ’ f (0, y ) =
= x ( y f (1,1) y ’ f (1,0)) x ’ ( y f (1,1) y ’ f (1,0)) =
= x y f (1,1) x y ’ f (1,0) x ’ y f (1,1) x ’ y ’ f (1,0).
Функция f ( x , y ) представлена в виде дизъюнкции четырех
дизъюнктивных членов. Те из них, для которых коэффициент f ( α , β ) равен нулю, можно отбросить. В результате получится СДНФ. Например, для функции f ( x , y )= x y имеем f (0,0)= f (1,1)=0
и f (0,1)= f (1,0)=1, поэтому
Элементарной конъюнкцией ( конъюнктом ) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза.
Булевы функции от n аргументов
В предыдущей лекции мы уже говорили о булевых функциях от одного и от двух аргументов. Введем понятие булевой функции от произвольного конечного числа аргументов.
Определение 10.1. Булевой функцией от n аргументов называется функция , заданная на множестве и принимающая значения в двухэлементном множестве . Другими словами, булева функция от от аргументов обозначается так: .
Две булевы функции от и называются равными, если любым одинаковым наборам значений аргументов обе эти функции сопоставляют одинаковые элементы из множества , т.е. для любых элементов .
Ранее уже встречались булевы функции от трех аргументов, например
В частности, было показано, что и . Перечисленные функции построены с помощью суперпозиций (или последовательного применения) более простых функций.
Суперпозиция булевых функций
Определение 10.2. Суперпозицией булевых функций в булеву функцию называется новая булева функция, получающаяся из функции подстановкой вместо (всех или некоторых) аргументов функций соответственно . Полученная функция зависит от аргументов.
Например, если и , то
Или если и , то имеем
Опишем еще одну процедуру, которую можно проделывать с булевыми функциями. Зафиксировав один из аргументов булевой функции от ), получим функцию от k-й аргумент , можем получить две новые булевы функции от и .
Например, из функции от трех аргументов фиксированием первого аргумента получаем следующие функции от двух аргументов:
Предлагаем посмотреть самостоятельно, какие получатся функции из функции при последовательном фиксировании остальных ее аргументов .
Число булевых функций
Перечислив ранее все булевы функции от одного аргумента и от двух аргументов, мы видели, что первых имеется всего четыре, а вторых — шестнадцать. Возникает вопрос, сколько будет разных булевых функций от трех аргументов, от четырех аргументов и т.д. Нельзя ли указать формулу, по которой вычислялось бы число булевых функций от Теорема 10.3 (о числе булевых функций от Число различных булевых функций от Доказательство. Чтобы задать булеву функцию от из нулей и единиц значений, которые могут принимать ее аргументы , и для каждого такого набора указать значение функции , которое она принимает на этом наборе.
Выясним сначала, сколько существует различных наборов , составленных из нулей и единиц, значений для . Покажем, что это число равно . Это 0 и 1. Так что для аргументов имеется точно , составленных из 0 и 1, значений для к аргументов. Тогда среди всевозможных различных наборов значений для и точно . Следовательно, всего будет от
Разных наборов длины разных булевых функций от
Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание
У нас уже возникали вопросы относительно выражения одних булевых функций через другие, и на некоторые из них мы уже дали ответ. Как будет показано ниже, существуют такие булевы функции (уже хорошо известные нам), через которые выражаются все (вообще все, от любого числа аргументов!) булевы функции. Этим замечательным свойством обладают взятые вместе конъюнкция, дизъюнкция и отрицание. Прежде чем сформулировать и доказать основную теорему этого пункта, обратимся к следующей важной лемме.
Лемма 10.4 (о разложении функции по переменной). Для произвольной булевой функции справедливы следующие формулы, называемые формулами разложения этой функции по переменной
Доказательство. Докажем справедливость первой формулы. Нужно проверить, что функции, стоящие в обеих частях равенства, при одинаковых значениях их аргументов принимают равные значения. Рассмотрим сначала всевозможные наборы значений аргументов следующего вида , т.е. будем придавать аргументам значения: . При этом безразлично, каковы именно значения . Вычислив, какое значение принимает на наборах такого вида функция, стоящая в правой части доказываемого равенства, убедимся, что оно совпадает со значением, принимаемым функцией, стоящей в левой части этого равенства, на том же наборе значений аргументов. В самом деле,
Теперь рассмотрим всевозможные наборы значений аргументов вида , т.е. будем придавать аргументам значения: . Аналогично вычисляем значение, принимаемое функцией, стоящей в правой части доказываемого равенства, на наборах такого вида:
Итак, функции из обеих частей равенства принимают одинаковые значения при одинаковых значениях их аргументов. Следовательно, эти функции равны и доказываемая формула справедлива.
Совершенно аналогично доказывается вторая формула.
Заметим, что подобным образом могут быть записаны формулы разложения булевой функции по любой ее переменной. Запишите, например, такие разложения по последней переменной.
Представление булевых функций через конъюнкцию, дизъюнкцию и отрицание
Теорема 10.5 (о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание). Всякая булева функция может быть представлена в виде суперпозиции конъюнкции, дизъюнкции и отрицания; причем знак отрицания стоит только непосредственно около переменной и не стоит ни перед одной из внутренних скобок.
Доказательство будем вести методом математической индукции по числу .
В предыдущем параграфе перечислены все булевы функции от одного аргумента. Их всего четыре. Напомним их (используя равенства теоремы 9.3, пункт и):
Отсюда видно, что все функции от одного аргумента выражаются через конъюнкцию, дизъюнкцию и отрицание; причем знак отрицания стоит только непосредственно около переменных. Это означает, что утверждение теоремы справедливо при аргументов. Докажем ее для функций от — произвольная булева функция от
Как отмечалось в начале настоящего параграфа, фиксирование в булевой функции одного аргумента приводит к булевой функции с числом аргументов на единицу меньшим, нежели число аргументов исходной функции. Так что каждая из функций и есть булева функция от аргументов. Но согласно предположению индукции, все такие функции выражаются через конъюнкцию, дизъюнкцию и отрицание, причем знак отрицания стоит только непосредственно около переменных и не стоит ни перед одной из внутренних скобок. Принимая это во внимание, видим, что правая часть последнего равенства представляет собой суперпозицию лишь трех функций — конъюнкции, дизъюнкции и отрицания. Причем отрицание стоит около переменной . Это и доказывает окончательно теорему.
Булевы функции и формулы алгебры высказываний
Установим сначала соответствие между формулами алгебры высказываний и булевыми функциями. Это делается следующим образом. Во-первых, определяется взаимно-однозначное соответствие между пропозициональными переменными и булевыми переменными, при котором прописная буква, обозначающая пропозициональную переменную, соответствует той же самой строчной букве, обозначающей булеву переменную:
Во-вторых, устанавливается соответствие между знаками логических связок и одноименных булевых функций:
Наконец скобкам ставятся в соответствие те же скобки. Тогда каждой формуле алгебры высказываний соответствует единственная булева функция, а каждой булевой функции соответствует формула алгебры высказываний. Чтобы найти для данной формулы алгебры высказываний соответствующую ей булеву функцию, достаточно каждую прописную букву формулы заменить на такую же строчную букву, а каждый символ логической операции — на символ одноименной булевой функции.
Например, формуле соответствует булева функция .
Если булева функция задана с помощью формулы, то для того чтобы найти соответствующую этой функции формулу алгебры высказываний, нужно в выражении для булевой функции заменить строчные буквы такими же прописными буквами, а каждый символ булевой функции заменить соответственно символом одноименной логической операции . Здесь возникает неоднозначность такого обратного соответствия, поскольку булева функция может иметь множество различных формульных выражений. Например, функция, рассмотренная в предыдущем абзаце, имеет также следующие формульные выражения:
Этим выражениям сопоставляются соответственно следующие формулы алгебры высказываний:
Следовательно, все перечисленные формулы соответствуют одной и той же булевой функции.
Возникает вопрос, всякой ли булевой функции соответствует некоторая формула алгебры высказываний. Другими словами, всякая ли булева функция может быть выражена (представлена) некоторой формулой алгебры высказываний. Если булева функция задана с помощью формулы, то соответствующая этой функции формула алгебры высказываний отыскивается так, как описано в предыдущем абзаце. Если же булева функция задана не в виде формулы, то, в силу теоремы 10.5, формульное выражение для нее тем не менее существует, и, следовательно, представляющая ее формула алгебры высказываний может быть найдена по правилу, описанному выше.
Итак, отметим еще раз, что каждой формуле алгебры высказываний соответствует единственная определяемая этой формулой булева функция, что будет для нас важным в дальнейшем.
Нормальные формы булевых функций
На основе теоремы 10.5 всякая булева функция может быть представлена некоторой формулой алгебры высказываний. Нетрудно понять, что всякая формула алгебры высказываний, равносильная формуле, представляющей некоторую булеву функцию ; будет представлять функцию, равную . В частности, одной из таких представляющих формул будет совершенная дизъюнктивная нормальная форма (если данная булева функция не равна тождественно 0, т.е. представляющая формула не тождественно ложна) или совершенная конъюнктивная нормальная форма (если данная булева функция не равна тождественно 1, т.е. представляющая формула не является тавтологией). Отыскав совершенную нормальную форму для формулы алгебры высказываний, представляющей данную булеву функцию (применяя правила, полученные в теоремах 5.2 и 5.4), можно перейти от этой формы к формульному выражению для данной булевой функции. Его будем называть совершенной (дизъюнктивной или конъюнктивной) нормальной формой булевой функции , сокращенно СДН-формой или соответственно СКН-формой. Каждая из них для данной булевой функции, если она существует, единственна.
Приобретя опыт работы с булевыми функциями, можно отыскивать их нормальные формы, не переходя к символике алгебры высказываний. При этом, если функция задана каким-то формульным выражением, то для его тождественного преобразования следует пользоваться свойствами булевых функций, установленными в теоремах 9.3–9.5, а если функция задана своими значениями на всех наборах значений аргументов (т.е. если она задана таблично), то следует применять правила, полученные в теоремах 5.2 и 5.4, переведя их предварительно на язык булевых функций.