Ekzamen-Дисмат

Теорема о функциональной полноте. Проверка системы функций на полноту.

Теорема. Система функций D является полной тогда и только тогда, когда она целиком не входит ни в один из основных замкнутых класов T0,T1,S,M,L

Доказательство.

Пусть система D полностью не входит ни в один из основных замкнутых классов. Тогда в D найдутся ф-и f0T0,f1T1,fsS,flL, fmM.Покажем, что конъюнкцию и отрицание можно представить в виде суперпозиции этих пяти функций. Из этого будет следовать, что это множество образует полную систему функций. Возьмём функцию f0 которая не сохраняет 0. Это означает f(0,0,...,0)=1

I f0(1,1,...,1)=0

II f0(1,1,...,1)=1

I f0(x,x,...,x)=x

fsS. Из несамодвойственной ф-иfs путём подстановки вместо переменных тождественной функции, отрицания можно получить константу. Вторую константу можно получить путём навешивания отрицания над первой.

Из flL при помощи тождественной функции, отрицания и констант строится конъюнкция.

В I случае в построении участвовали f0,fs,fl

II f(x,x,...,x)=1

Рассмотрим f1T1

Она на единичном наборе принимает нулевые значения. Тогда результат подстановки вместо переменных в функцию f1 функции f0(x,x,...x) даёт значение ноль. Из немонотонной ф-и используя 0,1 и тождественную функцию можно построить отрицание. Из нелинейной функции путем подстановки констант, отрицаний, тождественной функции можно получить конъюнкцию.

Содержание