Участник:Fad Oleg

Материал из Викиконспекты
Версия от 00:57, 15 июня 2021; Fad Oleg (обсуждение | вклад) (Новая страница: «{{Определение |id = def1 |neat = 1 |definition = '''Стандартный базис''' - полная система булевых функций:…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Стандартный базис - полная система булевых функций: [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] (дизъюнктивный базис Буля)

Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и логической константы 0, т. к. все остальные операции являются их отрицаниями: