9
правок
Изменения
Нет описания правки
== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.
== Формулировка и доказательство критерия ==
{{
Теорема|statement=
б) <tex>f_0</tex>(1) = 0, тогда <tex>f_0</tex>(x, x, x, ..., x) = ¬x'''.'''
а) <tex>f_1</tex>(0) = 0, тогда <tex>f_1</tex>(x, x, x, ..., x) = <tex>~0</tex>'''.'''
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''
}}
== Источники ==
* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]
* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]
