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

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

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

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

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

21. Понятие графа.

???

Клика

Клика - максимально большой полный подграф данного графа.

a

f b

e c

d

	a	b	c	d	e	f
a
b
c
d
e
f

	a	b	c	d	e	f
a
b
c
d
e
f

Построение Клики.

1. Строим дополнительный граф исходного графа.

G̅ a

f b

e c

d

2. Найдем множество внутренней устойчивости для графа G̅.

(a Ú d)(a Ú e)(a Ú f)(b Ú c)(c Ú d)

(a Ú de)(a Ú f)(c Ú bd)

(a Ú def)(cÚ bd)

ac Ú cdef Ú bdef Ú abd

{b, d, e, f}, {c, e, f}, {a, b}, {a, c}

3. Множества полученных вершин дают всевозможные полные подграфы исходного графа G̅. Причем, максимальный из подграфов дает клику.