Участник:Fad Oleg

Представление булевых функций

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций $\Sigma = \{f_1,\ldots,f_n\}$. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре $\Sigma$, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

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

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

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

Определение:

Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов.

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

Примеры ДНФ:

$f(x,y,z) = (x \land y) \lor (y \land \neg {z})$.

$f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg{t}) \lor (x \land \neg {m})$.

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

Определение:

Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.

Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.

Пример КНФ:

$f(x,y,z) = (x \lor y) \land (y \lor \neg{z})$

$f(x,y,z,t) = (x \lor t) \land (y \lor \neg{t}) \land (\neg{t} \lor \neg{z}) \land (\neg{x} \lor \neg{y} \lor z)$

$f(x,y,z,t,m) = (x \lor m \lor \neg{y}) \land (y \lor \neg{t}) \land (y \lor t \lor \neg{x})$

Полином Жегалкина

Определение:

Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида $0$ и $1$, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или.

Полином Жегалкина имеет следующий вид:

$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_{n-1} x_n \oplus \ldots \oplus a_{11\ldots1} x_1 x_2 \ldots x_n$

С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: $\bigl\langle \wedge, \oplus, 1 \bigr\rangle$, который, в свою очередь, по теореме Поста является полным.

Примеры:

$f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2$

$f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3$

$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$

Тождественные функции. Выражение функций друг через друга

Определение:

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

Приведение тождественной функции есть выражение булевой функции через другие.

Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.

Пример:

Выразим следующие функции через систему функций $\{\land, \lor, \lnot \}$. $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 )$ $x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y$ $\langle x, y, z \rangle = \left ( x \land y \right ) \lor \left ( y \land z \right ) \lor \left ( x \land z \right ) = \left ( x \lor y \right ) \land \left ( y \lor z \right ) \land \left ( x \lor z \right )$

Подстановка одной функции в другую

Определение:

Подстановкой (англ. substitution) функции $g$ в функцию $f$ называется замена $i$-того аргумента функции $f$ значением функции $g$: $h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})$

Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.

При подстановке функции $g$ вместо $i$-того аргумента функции $f$, результирующая функция $h$ будет принимать аргументы, которые можно разделить на следующие блоки:

1. $x_{1}, \ldots, x_{i-1}$	— аргументы функции $f$ до подставленного значения функции $g$
2. $x_{i}, \ldots, x_{i+m-1}$	— используются как аргументы для вычисления значения функции $g(y_{1}, \ldots, y_{m})$
3. $x_{i+m}, \ldots, x_{n+m-1}$	— аргументы функции $f$ после подставленного значения функции $g$

Пример:

Исходные функции: $f(a,b) = a \vee b$ $g(a) = \neg a$ $h(a,b) = f(a,g(b)) = a \vee \neg b$ — подстановка функции $g$ вместо второго аргумента функции $f$. В данном примере при помощи подстановки мы получили функцию $h(a,b)=a \leftarrow b$.

Отождествление переменных

Определение:

Отождествлением переменных (англ. identification of variables) называется подстановка $i$-того аргумента функции $f$ вместо $j$-того аргумента: $h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{i}, x_{j+1}, \ldots, x_{n})$

Таким образом, при отождествлении $c$ переменных мы получаем функцию $h$ с количеством аргументов $n-c+1$.

Пример:

$f(a,b) = a \vee b$ — исходная функция $h(a) = a \vee a$ — функция с отождествленными первым и вторым аргументами Очевидно, в данном примере мы получили функцию $P_{1}$ — проектор единственного аргумента.

Схемы из функциональных элементов

Определение:

Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе $B$, в котором: 1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные); 2. в каждую из остальных вершин входит одно или более ребер (зависит от выбранного базиса $B$). Такие вершины называются функциональными элементами и реализуют какую-либо булеву функцию из базиса $B$.

Отождествление переменных осуществляется при помощи ветвления проводников.

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

Некоторые логические элементы:

И	ИЛИ	НЕ	Штрих Шеффера	Стрелка Пирса

Стандартный базис

Определение:

Стандартный базис — система булевых функций: $\{\land, \lor, \lnot \}$

Если рассматривать множество бинарных булевых функций $P_2(2)$, то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы $0$ с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:

$x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right )$

$x \rightarrow y = \lnot x \lor y$

$0 = x \land \lnot x$

Функции $\mid \ и \downarrow$ являются отрицаниями функций $\land \ и \ \lor$ соответственно.

$x \mid y = \lnot \left ( x \land y \right )$

$x \downarrow y = \lnot \left ( x \lor y \right )$

Тождественность функций можно доказать с помощью таблицы истинности.

Пример:

Выразим через стандартный базис обратную импликацию $\left (x \leftarrow y \right )$.

$x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y$

Полнота стандартного базиса

Утверждение:

Стандартный базис является полной системой булевых функций

$\triangleright$

Данное утверждение - следствие теоремы об СДНФ. Если рассмотреть функцию, не равную тождественному нулю, то она представима в виде СДНФ, в которой используются функции стандартного базиса. Способ выражения тождественного нуля через функции стандартного базиса уже был описан выше.

$\triangleleft$

Замечание:

По закону де Моргана:

$x \land y = \lnot \left (\lnot x \lor \lnot y \right )$

$x \lor y = \lnot \left (\lnot x \land \lnot y \right )$

Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:

$\{ \land , \lnot \}$ (конъюнктивный базис Буля)

$\{ \lor , \lnot \}$ (дизъюнктивный базис Буля)

Теоремы о числе функций в базисе

Теорема:

Максимально возможное число булевых функций в безызбыточном базисе — четыре.

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

$\triangleright$

Рассмотрим произвольный безызбыточный базис $X$. Тогда по теореме Поста $X$ содержит следующие функции (не обязательно различные): $f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L$, где $T_0, T_1, S, M, L$ — классы Поста. Значит, так как $X$ — безызбыточный базис, а система $\{f_0, f_1, f_s, f_m, f_l \}$ — полная, то $\left | X \right | \le 5$ Рассмотрим $f_0$. Возможны два случая: 1. $f_0(1, 1, \ldots, 1) = 0$, тогда $f_0$ также не сохраняет единицу и немонотонная, т.е. $f_0 = f_1 = f_m$. Значит, $\left | X \right | \le 3$. 2. $f_0(1, 1, \ldots, 1) = 1$, тогда $f_0$ несамодвойственная, т.е. $f_0 = f_s$. Значит, $\left | X \right | \le 4$.

$\triangleleft$

Теорема:

Для любого числа $k, 1 \le k \le 4$ найдётся базис $X$, что $\left | X \right | = k$.

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

$\triangleright$

Приведём примеры базисов для каждого $k$: $k = 1 \Rightarrow X = \{ \downarrow \}$; $k = 2 \Rightarrow X = \{ \lnot, \land \}$; $k = 3 \Rightarrow X = \{ \land, \oplus, 1\}$; $k = 4 \Rightarrow X = \{ 0, 1, x\land y, x\oplus y\oplus z\}$; Докажем, что последняя система является базисом: $0 \notin T_1$; $1 \notin T_0$; $x\land y \notin L\ и\ S$; $x\oplus y\oplus z \notin M$ (доказывается с помощью таблицы истинности).

$\triangleleft$

Источники

Полные системы булевых функций — Википедия

Категория: Дискретная математика и алгоритмы

Категория: Булевы функции