Закон двойственности
x 
y = 1 
x
x
y .
Для проверки функции на линейность полезна следующая теорема.
Теорема.Если в таблице задания функции количество значений функции, равных 1, не равно количеству значений функции, равных 0, то функция не является линейной. Если равно, то надо проверять функцию на линейность.
L– класс всех линейных логических функций.
Этот класс так же замкнут, т.к. выражение, составленное из линейных выражений, является линейным.
Определение. Функционально замкнутый класс называется предполным, если он не содержится ни в каком функционально замкнутом классе, отличном от самого себя и от класса всех функций алгебры логики.
Предполными классами будут классы Т
, T
, S, M и L. Других предполных классов нет.
Теорема (Теорема Поста). Для того чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов To, T1, S, M и L.
Из данной теоремы следует, что при проверке системы на полноту надо все функции системы проверить на принадлежность одному классу, затем другому и т.д. При этом, достаточно найти хотя бы одну функцию, не принадлежащую данному классу. Тогда остальные функции системы на принадлежность этому классу можно не проверять. Если при проверке окажется, что все функции системы принадлежат данному классу, то проверку надо закончить, т.к. по теореме о полноте такая система не будет полной.
предыдущаяследующая