37
правок
Изменения
Новая страница: «{{Определение |id = def1 |neat = 1 |definition = '''Стандартный базис''' - полная система булевых функций:…»
{{Определение
|id = def1
|neat = 1
|definition = '''Стандартный базис''' - полная система булевых функций:
<tex>\{\land, \lor, \lnot \} </tex>
}}
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что по закону де Моргана:
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
полными являются даже системы:
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и логической константы 0, т. к. все остальные операции являются их отрицаниями:
|id = def1
|neat = 1
|definition = '''Стандартный базис''' - полная система булевых функций:
<tex>\{\land, \lor, \lnot \} </tex>
}}
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде [[ДНФ]] или [[КНФ]]. А учитывая, что по закону де Моргана:
<tex> x \land y = \lnot \left (\lnot x \lor \lnot y \right ) </tex>
<tex> x \lor y = \lnot \left (\lnot x \land \lnot y \right ) </tex>
полными являются даже системы:
<tex> \{ \land , \lnot \} </tex> (конъюнктивный базис Буля)
<tex> \{ \lor , \lnot \} </tex> (дизъюнктивный базис Буля)
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и логической константы 0, т. к. все остальные операции являются их отрицаниями:
