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

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

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

- несохраняющую 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.