Участник:Fad Oleg

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

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

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

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

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

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

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

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

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

Рассмотрим произвольный базис, в котором число булевых функций равно числу классов Поста. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция $f(x_1, x_2, \ldots, x_n)$, которая не сохраняет ноль, т.е. $f(0, 0, \ldots, 0) = 1$. Тогда возможны два случая: 1. $f(1, 1, \ldots, 1) = 0$, тогда функция $f$ также не сохраняет единицу. 2. $f(1, 1, \ldots, 1) = 1$, тогда функция $f$ несамодвойственная. В любом случае, функция $f$ будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций.

$\triangleleft$

Источники

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

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

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