Участник:Fad Oleg

Материал из Викиконспекты
Версия от 00:48, 25 июня 2021; 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 \subseteq P_2[/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]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(1, 1, \ldots, 1) = 0 [/math], тогда функция [math]f[/math] также не сохраняет единицу и немонотонная, т.е.

[math] f_0 = f_1 = f_m [/math]. Тогда [math]\left | X \right | \le 3[/math].

2. [math] f(1, 1, \ldots, 1) = 1 [/math], тогда функция [math]f[/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 \subseteq P_2[/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]

Источники

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

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

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