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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Полнота стандартного базиса)
Строка 15: Строка 15:
 
==Полнота стандартного базиса==
 
==Полнота стандартного базиса==
  
{{Утверждение
+
{{Теорема
|id = prop1
+
|id = theor1
 
|statement = Стандартный базис является полной системой булевых функций
 
|statement = Стандартный базис является полной системой булевых функций
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]]. А учитывая, что, по [[Множества|закону де Моргана]]:
+
|proof = Данное утверждение - следствие [[СДНФ|теоремы об СДНФ]].  
 +
}}
 +
 
 +
Однако, по [[Множества|закону де Моргана]]:
  
 
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
 
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
Строка 24: Строка 27:
 
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
 
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
  
полными являются даже системы:
+
Следовательно, стандартный базис не является базисом ''(забавно)'', так как базисами являются подмножества системы:
  
 
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
 
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
  
 
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
 
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
 
}}
 
  
 
==Источники==
 
==Источники==

Версия 23:16, 16 июня 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] (дизъюнктивный базис Буля)

Источники

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

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

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