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

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

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

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

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

f(X₁,X₂,...,X_n) ¹ f(X₁,X₂,...,X_n)

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

a₁×a₂×...×a_n ³b₁×b₂×...×b_n

f(a₁,a₂,...,a_n)<f(b₁,b₂,...,b_n)

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

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

a₀ Å a₁x₁ Å a₂x₂ Å...,

где a_i = 1 или 0

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

1 Å X = X

a₀ = 1

a₁ = 1

a_2..¥ = 0

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

a₀ = 0

a₁ = 1

a₂ = 1

a_3..¥ = 0

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

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