Закон двойственности
Пример. Проверить на полноту следующую систему функций: { x ’ y, x & y ).
Для проверки составим следующую таблицу.
Таблица 1.19
|
f |
To |
T1 |
S |
M |
L |
|
’ |
– |
+ |
– |
– |
– |
|
& |
+ |
+ |
– |
+ |
– |
В данной таблице знак «+» означает, что функция принадлежит соответствующему классу, а знак «–», что не принадлежит. Из таблицы видно, что все функции данной системы принадлежат классу Т1. Следовательно, по теореме о полноте данная система функций не является полной.
Пример. Проверить на полноту следующую систему функций:
{
,
x 
y }.
Функция не сохраняет 0, не сохраняет 1 и не является монотонной. Функция х
y не является самодвойственной и нелинейная. Из
этого следует, что в данной системе функций есть хотя бы одна функция не принадлежащая
каждому из пяти замкнутых классов. Следовательно, данная система функций функционально
полная.
Замечание. Можно показать, что если функция не принадлежит
классам T
, T
и S , то она не принадлежит и
классам M и L.
Следующие системыне являются полными
{ 
,1 }, { xy, x 
y }, { x 
y, }, { xy yz xz, },
{ xy yz xz, 0, 1 }, { 0, xy,
x y z }, { 1, xy,
x y z },