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