Вторая теорема о функциональной полноте.

Система функций будет полной если она содержит хотя бы одну из функций :

- несамодвойственную

- несохраняющую 0

- несохраняющую 1

- немонотонную

- нелинейную

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

Доказательство теоремы сводится к доказательству утверждения : имеет несамодвойственную, несохраняющую 0 и 1 функции можно получить конст-ты 0 или 1. Если тезис будет доказан, то теорема сводится к первой теореме о функциональной полноте.

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

f (d₁, d₂, …, d_n) = ( ₁, ₂, …, _n)

Определим функцию f ( x )

f ( x ) = f ( x^d1, x^d2, …, x^dn), где

x, d_i = 1

x^di =

, d_i = 0, при этом

0^di = _i , 1^di = _i , тогда

f ( 0 ) = f ( 0^d1, 0^d2, …, 0^dn) = f ( ₁,…, _n) = f (d₁, …, d_n) = f ( 1^d1, …, 1^dn) = f ( 1 )

т.е. f ( x ) = const.

Рассмотрим 2 случая для функции несохраняющей 0 :

1. Имеем функцию несохраняющую 0 следующего вида :

f₀ ( x₁, …, x_n )

d₀ ( 0 ) = f₀ ( 0, …, 0 ) = 1

d₀ ( 1 ) = f₀ ( 1, …, 1 ) = 0 Þ d₀ ( x ) =

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

2. Имеем функцию несохраняющую 0 вида :

f₀ ( x₁, …, x_n )

d₀ ( 0 ) = f₀ ( 0, …, 0 ) = 1

d₀ ( 1 ) = f₀ ( 1, …, 1 ) = 1 Þ d₀ ( x ) = 1

Имеем конст-ту 1.

Для получения конст-ты 0 используем функцию несохраняющую 1 вида :

f₁ ( x₁, …, x_n )

d₁ ( 1 ) = f₁ ( 1, …, 1 ) = Æ Þ d₁ ( d₀ ( x )) = Æ

т.е. получена конст-та 0.

Таким образом доказана достаточность теоремы.

Доказательство необходимости теоремы следует из замкнутости классов самодвойственных, сохраняющих 0 и 1 функций.

Таким образом теорема доказана.

На основании 2^-й теоремы о функциональной полноте, построим расширенную таблицу Поста:

yi	Kн	Кл	K0	K1	Kc
f1						a
f2						b
f6						c
f7						d
f8						e
f9						f
F12						g
F13						h
F14						k

х1	х2	F1	F2	F6	F7	F8	F9	F12	F13	F14

F1 = х1*х2

F2 = х1* 2 = х1х2 Å x1

F6 = 1*х2 + х1* 2 = х1Åх2

F7 = х1 + х2 = х1х2 Å x1 Å х2

F8 = 1* 2 = х1х2 Å x1 Å х2 Å 1

F9 = 1 2 + х1х2 = х1Åх2 Å 1

F12 = 1 = х1 Å 1

F13 = 1 + х2 = х1х2 Å x1 Å 1

F14 = 1 + 2 = х1х2 Å 1

1 - не принадлежит классу.

С помощью метода Квайна найдем мин. покрытие табл., т. е. Получим все базисы в узком смысле в пр-ве Р_a

P = ( b + c + e + f + g + h + k )( a + b + d + e + h + k )( e + f + g + h + k ) &

& ( b + c + g + k )( a + b + c + d + e + f + h + k ) = e + k + ( b + c + f + g + h )

( a + b + d + h )( f + g + h )( b + c + g )( a + b + c + d + f + h ) =

= e + k ( h + b + ( c + f + g )( a + d ) (a + c + d + f))( f + g + h )( b + c + g ) =

= e + k + (h + ac + b + a + af + ag + dc + df + dg )( g + bf + bh +c + ch) =

= e + k + hg + hb + hc + bg + bf + acf + ag + dcf + dg.

П₁ = {f₈} П₆ = { f₂ ,f₁₂}

П₂ = {f₁₄} П₇ = { f₂ ,f₉}

П₃ = {f₁₂ ,f₁₃} П₈ = { f₁ ,f₆ ,f₉}

П₄ = { f₂ ,f₁₃} П₉ = { f₁ ,f₁₂}

П₅ = { f₆ ,f₁₃} П₁₀ = { f₆ ,f₇ ,f₉}

П₁₁ = {f₇ ,f₁₂}

Если результаты исследования базисов в узком смысле объед., то можно сделать вывод, что общее число всех возможных различных базисов равно 17.

Если сравнить базисы в узком смысле с базисами в широком смысле, то можно выявить следующие соответствия :

П₁ ¾ В₂

П₂ ¾ В₄

П₉ ¾ В₁₀

П₁₁ ¾ В₉

На основани базисов в узком смысле можно реализовать любую Булеву функцию.

Приведем Р⁵, его сост-т следующие функции :

{y₂, y₉} = П₇

y₂(x₁, x₂) = x_{1 2}

y₉(x₁, x₂) = x₁ Å x₂

_{x1 x1}

_x2 ^{& f 2} _x2 ^{f 9}

Через имеющиеся функции выразим функцию отрицания, для этого с помощью у₉ получим константу 1.

y₉(x , x ) = 1, тогда y₂( у₉ (x , x ) =

Используя функцию отрицания и y₂ получим конъюкцию :

y₂( x₁ , y₂ (у₉ (x₂ , x₂), x₂ )) = x₁x₂

_x1

_x2

_{& x2} ^& _x1x2

Имея функцию отрицания и конъюкцию, можно реализовать произвольную булеву функцию.

Если рассматривать базисы в узком и широком смысле с практической точки зрения, то следует отметить, что базисы в узком смысле не имеют никаких преимуществ, так как на практике всегда имеются константы 0 и 1.