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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |id = def1 |neat = 1 |definition = '''Стандартный базис''' - полная система булевых функций:…»)
 
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id = def1
 
|id = def1
|neat = 1
+
|definition = '''Стандартный базис''' - система булевых функций:  
|definition = '''Стандартный базис''' - полная система булевых функций:  
 
 
<tex>\{\land, \lor, \lnot \} </tex>
 
<tex>\{\land, \lor, \lnot \} </tex>
 
}}
 
}}
 +
 
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что по закону де Моргана:
 
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что по закону де Моргана:
  
Строка 17: Строка 17:
 
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
 
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
  
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и логической константы 0, т. к. все остальные операции являются их отрицаниями:
+
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <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>
 +
 
 +
{{Утверждение
 +
|id = prop1
 +
|statement = Стандартный базис является полной системой булевых функций
 +
|proof = Данное утверждение является следствием существования [[СДНФ]]
 +
}}

Версия 01:21, 15 июня 2021

Определение:
Стандартный базис - система булевых функций: [math]\{\land, \lor, \lnot \} [/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] 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]