logo search
Diskretnaya_matematika_1_semestr

Полнота и замкнутость.

Система булевых ф-ций DP2 наз. полной (ф-ционально полной), если любую бул. ф-цию можно представить в виде ф-лы над мн-вом ф-ций D. Например: Р2 {,&,}.

Теорема:

Пусть D={d1,…,dl,…} – полная система ф-ций и такая, что каждая её ф-ция представима в виде ф-лы надмножеством ф-ции системы G(G={g1,…,gk,…}), то система ф-ций G полная cистема ф-ции. D={d1,d2,…,dn…}, T={t1,t2,…,tn…}.

Док-во. Воспользуемся тем, что D-полная система ф-ции. Тогда произвольную булеву ф-цию f можно реализовать над множеством ф-ции сиситемы Д: di=Ci[g1,..,gk,…]

F=C[C1[g1,…,gk],…,C1[g1,…,gk,…]…]. Что и требовалось доказать.

На основе этой теоремы покажем, что система G, состоящая из двух ф-ций (G={-,&}) является полной.

В качестве системы Д выберем систему(Д={-,&,∪})

¬(x∪y)=¬x&¬y; x∪y=¬(¬x&¬y)

Представили дизъюнкцию в виде ф-лы G, и тем самым показали, что G-полная система ф-ции.

Покажем, что G={1} является полной системой ф-ции. В качестве Д={-,&} ¬x=x\x; x&y=¬(x\y)=(x\y)/(x\y)