Функциональный набор логических функций - это такой набор функций, который позволяет любую функцию математической логики описать с помощью функций данного набора.
Теорема Поста. Для того чтобы набор функций {f1,f2,……fn} был функционально полный необходимо и достаточно, чтобы для всего набора функций в целом не выполнялись свойства сохранения нуля, сохранения единицы, линейности, монотонности и самодвойственности.
Полноту набора удобно определять по таблице Поста, в клетках которой ставится знак «+» или «-» в зависимости от того, обладает функция из этого набора тем или иным свойством. В силу теоремы Поста для полноты системы необходимо и достаточно, чтобы в каждом столбце был хотя бы один минус.
{ }
T0
T1
L
M
S
F1
+
+
+
+
-
F2
-
-
-
-
+
ПРИМЕР
Доказать, что набор функций6 дизъюнкция и отрицание является функционально полным.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление