Булевы функции

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

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

Это функция $f(x_1, x_2, \ldots, x_n)$, аргументы которой $x_1, x_2, \ldots, x_n$, и сама функция $f$ принимают значения $0$ или $1$.

Логические функции могут быть заданы таблично, либо аналитически.

В общем случае, булеву функцию от $n$ переменных можно рассматривать как отображение $\lbrace 0, 1\rbrace^n \to \lbrace 0, 1 \rbrace$. Пространство $\lbrace 0, 1\rbrace^n$ можно интерпретировать как $n$-битное двоичное число.

Существует $2^n$ различных $n$-битных двоичных чисел. Так как каждому из них сопоставляется значение функции – 0 или 1, то общее количество различных булевых функций $n$ аргументов равно $2^{2^n}$.

От двух переменных существует 16 различных булевых функций. Особо интересными из них являются:

• Штрих Шеффера $$f(x,y) = \;\overline{a \,\&\,b}\; = a | b$$
• Стрелка Пирса $$f(x,y) = \;\overline{a \vee b}\; = a \downarrow b$$

Канонические формы логических функций

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

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

Нормальная форма

Если логическая функция выражена через дизъюнкцию, конъюнкцию и отрицание переменных, то такая форма записи называется нормальной.

Среди нормальных форм выделяют такие, в которых функции записываются единственным образом. Их называют совершенными.

Элементарная конъюнкция

Это конъюнкция одной или нескольких переменных, или их отрицаний.

Элементарная дизъюнкция

Это дизъюнкция одной или нескольких переменных, или их отрицаний.

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

Это дизъюнкция не повторяющихся элементарных конъюнкций.

Конъюнктивная нормальная форма (КНФ)

Это конъюнкция не повторяющихся элементарных дизъюнкций.

Среди дизъюнктивных или конъюнктивных нормальных форм, очевидно, существуют совершенные.

Совершенная ДНФ (СДНФ)

Это ДНФ, в которой каждая элементарная конъюнкция состоит из $k$ переменных $x_1, x_2, \ldots, x_k$, причем на $i$-том месте конъюнкции стоит переменная $x_i$ или ее отрицание $\;\overline{x_i}\;$, и все элементарные конъюнкции различны.

Совершенная КНФ (СКНФ)

Это КНФ, в которой каждая элементарная дизъюнкция состоит из $k$ переменных $x_1, x_2, \ldots, x_k$, причем на $i$-том месте дизъюнкции стоит переменная $x_i$ или ее отрицание $\;\overline{x_i}\;$, и все элементарные дизъюнкции различны.

Любую логическую функцию можно представить в виде СДНФ или СКНФ. Для обоснования этого утверждения, рассмотрим две теоремы.

Теорема о существовании СДНФ

Пусть $f(x_1, x_2, \ldots, x_n)$ – булева функция от $n$ переменных, не равная тождественно нулю. Тогда существует СДНФ, выражающая функцию $f$.

Доказательство

Для начала покажем, что переменную можно “вынести” за знак функции с помощью конъюнкции:

$$f(x_1,\ldots,x_i,\ldots,x_n) = \;\overline{x_i}\; \,\&\,f(x_1,\ldots,0,\ldots,x_n) \vee x_i \,\&\,f(x_1,\ldots,1,\ldots,x_n)$$

Действительно, если $x_i = 0$, то $$f(x_1,\ldots,x_i,\ldots,x_n) = 1 \,\&\,f(x_1,\ldots,0,\ldots,x_n) \vee 0 \,\&\,f(x_1,\ldots,1,\ldots,x_n) = f(x_1,\ldots,0,\ldots,x_n)$$

Иначе, если $x_i = 1$, $$f(x_1,\ldots,x_i,\ldots,x_n) = 0 \,\&\,f(x_1,\ldots,0,\ldots,x_n) \vee 1 \,\&\,f(x_1,\ldots,1,\ldots,x_n) = f(x_1,\ldots,1,\ldots,x_n)$$

Последовательно “вынося” переменные за знак функции, получим следующую формулу (знаки конъюнкции опущены):

$$\begin{array}{c} f(x_1,\ldots,x_n) & = & \;\overline{x_1}\; & \;\overline{x_2}\; & \ldots & \;\overline{x_{n-1}}\; & \;\overline{x_n}\; & f(0, 0, \ldots, 0, 0) & \vee\\ & \vee& \;\overline{x_1}\; & \;\overline{x_2}\; & \ldots & \;\overline{x_{n-1}}\; & x_n & f(0, 0, \ldots, 0, 1) & \vee\\ & \vee& \;\overline{x_1}\; & \;\overline{x_2}\; & \ldots & x_{n-1} & x_n & f(0, 0, \ldots, 1, 1) & \vee\\ & \ldots \\ & \vee& \;\overline{x_1}\; & x_2 & \ldots & x_{n-1} & x_n & f(0, 1, \ldots, 1, 1) & \vee\\ & \vee& x_1 & x_2 & \ldots & x_{n-1} & x_n & f(1, 1, \ldots, 1, 1) \end{array}$$

Теперь, зная значения функции, можно полностью исключить конъюнкции, содержащие $f=0$, по закону поглощения нуля, и опустить в остальных конъюнкциях $f=1$ по закону поглощения единицы.

Мы получили СДНФ, следовательно, она существует по построению. $\blacksquare$

Очевидна причина требования неравенства нулю: для $f=0$ СДНФ не будет иметь ни одного члена.

Теорема о существовании СКНФ

Пусть $f(x_1, x_2, \ldots, x_n)$ – булева функция от $n$ переменных, не равная тождественно единице. Тогда существует СКНФ, выражающая функцию $f$.

Доказательство

Для начала покажем, что переменную можно “вынести” за знак функции с помощью дизъюнкции:

$$f(x_1,\ldots,x_i,\ldots,x_n) = (x_i \vee f(x_1,\ldots,0,\ldots,x_n)) \,\&\,(\;\overline{x_i}\; \vee f(x_1,\ldots,1,\ldots,x_n))$$

Действительно, если $x_i = 0$, то $$f(x_1,\ldots,x_i,\ldots,x_n) = (0 \vee f(x_1,\ldots,0,\ldots,x_n)) \,\&\,(1 \vee f(x_1,\ldots,1,\ldots,x_n)) = f(x_1,\ldots,0,\ldots,x_n)$$

Иначе, если $x_i = 1$, $$f(x_1,\ldots,x_i,\ldots,x_n) = (1 \vee f(x_1,\ldots,0,\ldots,x_n)) \,\&\,(0 \vee f(x_1,\ldots,1,\ldots,x_n)) = f(x_1,\ldots,1,\ldots,x_n)$$

Последовательно “вынося” переменные за знак функции, получим следующую формулу:

$$\begin{array}{c} f(x_1,\ldots,x_n) & = & (\;\overline{x_1}\; &\vee& \;\overline{x_2}\; &\vee& \ldots &\vee& \;\overline{x_{n-1}}\; &\vee& \;\overline{x_n}\; &\vee& f(1, 1, \ldots, 1, 1)) & \,\&\,\\ & \,\&\,& (\;\overline{x_1}\; &\vee& \;\overline{x_2}\; &\vee& \ldots &\vee& \;\overline{x_{n-1}}\; &\vee& x_n &\vee& f(1, 1, \ldots, 1, 0)) & \,\&\,\\ & \,\&\,& (\;\overline{x_1}\; &\vee& \;\overline{x_2}\; &\vee& \ldots &\vee& x_{n-1} &\vee& x_n &\vee& f(1, 1, \ldots, 0, 0)) & \,\&\,\\ & \ldots \\ & \,\&\,& (\;\overline{x_1}\; &\vee& x_2 &\vee& \ldots &\vee& x_{n-1} &\vee& x_n &\vee& f(1, 0, \ldots, 0, 0)) & \,\&\,\\ & \,\&\,& (x_1 &\vee& x_2 &\vee& \ldots &\vee& x_{n-1} &\vee& x_n &\vee& f(0, 0, \ldots, 0, 0)) \end{array}$$

Теперь, зная значения функции, можно полностью исключить дизъюнкции, содержащие $f=1$, по закону поглощения единицы, и опустить в остальных дизъюнкциях $f=0$ по закону поглощения нуля.

Мы получили СКНФ, следовательно, она существует по построению. $\blacksquare$

Очевидна причина требования неравенства единице: для $f=1$ СКНФ не будет иметь ни одного члена.

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

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

это система булевых функций $\lbrace f_1, \ldots, f_n \rbrace$, которая позволяет выразить произвольную логическую функцию.

По теоремам о существовании СДНФ и СКНФ, система функций $\lbrace \,\&\,, \vee, \neg \rbrace$ является полной.

Полноту других систем можно обосновать при помощи следующего очевидного утверждения:

Если система $\lbrace f_1, \ldots, f_n \rbrace$ является полной, и каждая из функций $f_1, \ldots, f_n$ может быть выражена через функции $g_1, \ldots, g_n$, то система $\lbrace g_1, \ldots, g_n \rbrace$ так же является полной.

Так, несложно доказать, что системы $\lbrace \vee, \neg \rbrace$ и $\lbrace \,\&\,, \neg \rbrace$ так же являются полными.

Из всех булевых функций двух переменных, штрих Шеффера и стрелка Пирса образуют полные системы булевых функций сами по себе.

Штрих Шеффера $x|y$ определяется как

Можно видеть так же, что $x|y = \;\overline{x\,\&\,y}\;$, что объясняет другое название этой функции: “И-НЕ”.

Через штрих Шеффера легко выражаются конъюнкция, дизъюнкция и инверсия:

$$x|x = \;\overline{x\,\&\,x}\; = \;\overline{x}\;$$

$$x|y = \;\overline{x\,\&\,y}\; = \;\overline{x}\; \vee\;\overline{y}\;$$

Следовательно,

$$x \vee y = \;\overline{\;\overline{x\vee y}\;}\; = \;\overline{\;\overline{x}\; \,\&\,\;\overline{y}\;}\; = \;\overline{x}\; | \;\overline{y}\; = (x|x)|(y|y)$$

$$x \,\&\,y = \;\overline{\;\overline{x\,\&\,y}\;}\; = \;\overline{x | y}\; = (x|y)|(x|y)$$

Стрелка Пирса $x\downarrow y$ определяется как

Можно видеть так же, что $x\downarrow y = \;\overline{x\vee y}\;$, что объясняет другое название этой функции: “ИЛИ-НЕ”.

Через стрелку Пирса легко выражаются конъюнкция, дизъюнкция и инверсия:

$$x\downarrow x = \;\overline{x\vee x}\; = \;\overline{x}\;$$

$$x\downarrow y = \;\overline{x\vee y}\; = \;\overline{x}\; \,\&\,\;\overline{y}\;$$

Следовательно,

$$x \vee y = \;\overline{\;\overline{x\vee y}\;}\; = \;\overline{x\downarrow y}\; = (x\downarrow y)\downarrow(x \downarrow y)$$

$$x \,\&\,y = \;\overline{\;\overline{x\,\&\,y}\;}\; = \;\overline{\;\overline{x}\; \vee\;\overline{y}\;}\; = \;\overline{x}\; \downarrow\;\overline{y}\; = (x\downarrow x)\downarrow(y\downarrow y)$$

Возможность выражения любой булевой функции через одну имеет большое значение при разработке элементной базы для реализации алгебры логики в вычислительных машинах. В частности, возможность на одинаковых логических элементах собрать схему произвольной сложности значительно упрощает задачу производства логических схем.

Особенно интересным является тот факт, что СДНФ может быть непосредственно выражена через элементы И-НЕ со многими входами, а СКНФ – через элементы ИЛИ-НЕ со многими входами. Для этого все элементарные конъюнкции/дизъюнкции заменяются на И-НЕ/ИЛИ-НЕ, и их дизъюнкция/конъюнкция так же заменяется на И-НЕ/ИЛИ-НЕ