Участник:Fad Oleg — различия между версиями
Fad Oleg (обсуждение | вклад) |
Fad Oleg (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|id = def1 | |id = def1 | ||
− | |definition = '''Стандартный базис''' | + | |definition = '''Стандартный базис''' — система булевых функций: |
<tex>\{\land, \lor, \lnot \} </tex> | <tex>\{\land, \lor, \lnot \} </tex> | ||
}} | }} | ||
Строка 12: | Строка 12: | ||
<tex> 0 = x \land \lnot x </tex> | <tex> 0 = x \land \lnot x </tex> | ||
+ | |||
+ | ==Полнота стандартного базиса== | ||
{{Утверждение | {{Утверждение | ||
Строка 29: | Строка 31: | ||
}} | }} | ||
+ | |||
+ | ==Источники== | ||
+ | [https://ru.wikipedia.org/wiki/Булева_функция#Полные_системы_булевых_функций Полные системы булевых функций — Википедия] | ||
+ | |||
+ | Категория: Дискретная математика и алгоритмы | ||
+ | |||
+ | Категория: Булевы функции |
Версия 14:53, 15 июня 2021
Определение: |
Стандартный базис — система булевых функций: |
Для перехода к стандартному базису достаточно показать тождественные формулы для операций эквиваленции, импликации и константы , т. к. все остальные операции являются их отрицаниями:
Полнота стандартного базиса
Утверждение: |
Стандартный базис является полной системой булевых функций |
Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде ДНФ или КНФ. А учитывая, что, по закону де Моргана:
полными являются даже системы: (конъюнктивный базис Буля) (дизъюнктивный базис Буля) |
Источники
Полные системы булевых функций — Википедия
Категория: Дискретная математика и алгоритмы
Категория: Булевы функции