Полные системы. Примеры полных систем (с доказательством полноты)

Определение. Множество функций алгебры логики A называется полной системой (в P2), если любую функцию алгебры логики можно выразить формулой над A.

Система функций A={ f₁, f₁,…, f_m }, являющаяся полной, называется базисом.

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f₁, образующей этот базис, превращает систему функций (f₁, f₁,…, f_m) в неполную.

Теорема. Система A = {∨, &, ¬} является полной.

Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x & ¬x. Теорема доказана.

Лемма. Если система A — полная, и любая функция системы A может быть выражена формулой над некоторой другой системой B, то B — также полная система.

Доказательство. Рассмотрим произвольную функцию алгебры логики f (x₁, …, x_n) и две системы функций: A = {g₁, g₂, …} и B = {h₁, h₂, …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней:

f (x₁, …, x_n) = ℑ[g1, g2,…]

где g_i= ℜ_i[h1,h2,…]

то есть функция f представляется в виде

f (x₁, …, x_n)=ℑ[ℜ1,ℜ2,...]

иначе говоря, может быть представлена формулой над B. Перебирая таким образом все функции алгебры логики, получим, что система B также полна. Лемма доказана.

Теорема. Следующие системы являются полными в P₂:

1) {V, ¬};

2) {&, ¬};

3) { | };

4) {&, ⊕, 1}базис Жегалкина.

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

1) Известно (теорема 3), что система A = {&, V, ¬} полна. Покажем, что полна система B = { V, ¬. Действительно, из закона де Моргана ¬(x& y) = (¬x ∨ ¬y) получаем, что x & y =¬ (¬x ∨ ¬y), то есть конъюнкция выражается через дизъюнкцию и отрицание, и все функции системы A выражаются формулами над системой B. Согласно лемме система B полна.

2) Аналогично пункту 1: ¬(x ∨ y) = x & y ⇔ x ∨ y =¬(¬x & ¬y) и из леммы 2 следует истинность утверждения пункта 2.

3) x | y=¬(x&y), x | x = ¬x; x & y = ¬(x | y) = (x | y) | (x | y) и согласно лемме 2 система полна.

4) ¬x = x ⊕1 и согласно лемме 2 система полна.

Теорема доказана.

Дата добавления: 2014-01-03