Полнота системы булевых функций

Система булевых функций {f₁ (x₁₁,...,x_1p1),...,f_s (x_s1,...,x_sps),...} называется полной, если для любой булевой функции f (x₁,...,x_n) можно построить равную её функцию, представляющую собой результат суперпозиции функций {f₁,...,f_s,...} и x₁,...,x_n .

Примеры полных систем булевых функций.

1. x₁x₂, x₁ ٧ x₂,`x₁. Полнота следует из того, что для каждой функции можно построить совершенные ДНФ и КНФ.

2. x₁x₂,`x<sub>1</sub>. Полнота следует из п.1 и равенства х<sub>1</sub> ٧ х<sub>2</sub> = `х₁`х₂ .

3. x₁ ٧ x₂, `x<sub>1</sub>. Полнота следует из п.1 и равенства х<sub>1</sub>х<sub>2</sub> =`х₁ ٧`х₂ .

4. х₁х₂, х₁ Å х₂, 1. Полна, так как`х<sub>1</sub> = х<sub>1</sub> Å 1, а система x<sub>1</sub>x<sub>2</sub>,`x₁ является полной (п.2).

Теорема 3. Любую булеву функцию f (x₁,...,x_n) можно представить в виде полинома

f (x₁,x₂,...,x_n) = a₀ Å a₁x₁ Å a₂x₂ Å...Å a₂ⁿ_-1x₁…x_n,

где a_i Î{0,1}, i = 0, 1,...,2ⁿ-1.

Доказательство. Система функций х₁х₂, х₁ Å х₂, 1, 0 полна. Пользуясь правилами

A Å A = 0, A ∙ A = A, A Å 0 = A,

A ∙ 0 = 0, A ∙ 1 = A, A ∙ B = B ∙ A,

A Å B = B Å A, (A Å B) ∙ C = A ∙ C Å B ∙ C,

которые легко проверить, получим представление функции в виде полинома по модулю 2.

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

Как обнаружить полноту или неполноту булевых функций? Для решения этого вопроса познакомимся с пятью классами булевых функций.