Изменения

Перейти к: навигация, поиск

Участник:Fad Oleg

113 байт убрано, 15 июнь
Нет описания правки
}}
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы <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 = Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что , по закону де Моргана:
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
<tex> \{ \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>
 
{{Утверждение
|id = prop1
|statement = Стандартный базис является полной системой булевых функций
|proof = Данное утверждение является следствием существования [[СДНФ]]
}}
37
правок

Навигация