Участник:Fad Oleg — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Полнота стандартного базиса)
(Стандартный базис)
Строка 7: Строка 7:
 
}}
 
}}
  
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <tex> 0 </tex>, т. к. все остальные операции являются их отрицаниями:
+
Для выражения любой булевой функции через стандартный базис достаточно выразить тождественные функции (функции, которые при любых одинаковых аргументах принимают равные значения) для эквиваленции, импликации и константы <tex> 0 </tex> с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции являются их отрицаниями:
  
 
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex>
 
<tex> x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) </tex>
Строка 14: Строка 14:
  
 
<tex> 0 = x \land \lnot x </tex>
 
<tex> 0 = x \land \lnot x </tex>
 +
 +
Тождественность функций можно доказать с помощью таблицы истинности.
  
 
==Полнота стандартного базиса==
 
==Полнота стандартного базиса==

Версия 16:38, 20 июня 2021

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

Определение:
Стандартный базис — система булевых функций: [math]\{\land, \lor, \lnot \} [/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]\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] f(x_1, x_2, \ldots, x_n) [/math], которая не сохраняет ноль, т.е. [math] f(0, 0, \ldots, 0) = 1 [/math]. Тогда возможны два случая:

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

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

В любом случае, функция [math]f[/math] будет не принадлежать сразу двум классам Поста. Тогда исходный базис - избыточный, и его можно сократить до четырёх функций.
[math]\triangleleft[/math]

Источники

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

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

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