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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
  
 
<tex> 0 = x \land \lnot x </tex>
 
<tex> 0 = x \land \lnot x </tex>
 +
 +
==Полнота стандартного базиса==
  
 
{{Утверждение
 
{{Утверждение
Строка 29: Строка 31:
  
 
}}
 
}}
 +
 +
==Источники==
 +
[https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Булевы функции ]]

Версия 14:51, 15 июня 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] 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]\triangleleft[/math]

Источники

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