Лекция: Функциональная полнота

Совокупность логических операций функциолнально полна, когда какие-либо из операпций совокупности обладают нижеперечисленными свойствами:

1. Несохранение 0 ( f(0, 0, ..., 0) = 1)

2. Несохранение 1 ( а(1, 1, ..., 1) = 0)

3. Не самодвойственность.

f(X1,X2,...,Xn) ¹ f(X1,X2,...,Xn)

4. Немонотонность.

a1×a2×...×an ³b1×b2×...×bn

f(a1,a2,...,an)<f(b1,b2,...,bn)

5. Нелинейность.

Функция называется нелинейной, если она не может быть представлена в виде :

a0 Å a1x1 Å a2x2 Å...,

где ai = 1 или 0

Примеры линейных функций:

1 Å X = X

a0 = 1

a1 = 1

a2..¥ = 0

X Å Y — неравнозначность.

a0 = 0

a1 = 1

a2 = 1

a3..¥ = 0

Функционально полные наборы создают, например:

Ø и &; Ø и Ú; Ø и ®. Операции штрих Шеффера½ и стрелка Пира ¯ каждая в отдельности образуют функционально полный набор.