Участник:Fad Oleg

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

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

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

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

[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] \left (x \leftarrow y \right ) [/math].

[math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/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]\triangleright[/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]\{f_0, f_1, f_s, f_m, f_l \}[/math] — полная, то [math]\left | X \right | \le 5[/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] несамодвойственная, т.е. [math] f_0 = f_s [/math]. Тогда [math]\left | X \right | \le 4[/math].

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Источники

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

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

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