Участник:Fad Oleg

2021-06-18T19:39:41Z

188.170.83.10: /* Полнота стандартного базиса */

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

{{Определение
|id = def1
|definition = '''Стандартный базис''' — система булевых функций:
<tex>\{\land, \lor, \lnot \} </tex>
}}

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

<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex>

<tex> x \rightarrow y = \lnot x \lor y </tex>

<tex> 0 = x \land \lnot x </tex>

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

{{Утверждение
|statement = Стандартный базис является полной системой булевых функций
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]].
}}

Однако, по [[Множества|закону де Моргана]]:

<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>

<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>

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

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

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

==Теорема о максимальном числе функций в базисе==
{{Теорема
|statement = Максимально возможное число булевых функций в базисе — четыре
|proof = Очевидно, что число булевых функций в базисе не превышает число [[Полные системы функций. Теорема Поста о полной системе функций|классов Поста]]. Попробуем ограничить базис четырьмя булевыми функциями. В базисе обязательно найдётся функция
<tex> f(x_1, x_2, \ldots, x_n) </tex>, которая не сохраняет ноль, т.е. <tex> f(0, 0, \ldots, 0) = 1 </tex>. Тогда возможны два случая:

1. <tex> f(1, 1, \ldots, 1) = 0 </tex>, тогда функция <tex>f</tex> также не сохраняет единицу.

2. <tex> f(1, 1, \ldots, 1) = 1 </tex>, тогда функция <tex>f</tex> несамодвойственная.

В любом случае, функция <tex>f</tex> будет не принадлежать сразу двум классам Поста.
}}

==Источники==
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]

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

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

Викиконспекты - Вклад участника [ru]

Участник:Fad Oleg