37
правок
Изменения
Нет описания правки
{{Определение
|id = def1
<tex>\{\land, \lor, \lnot \} </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 = Данное утверждение является следствием существования [[СДНФ]]}}
