Теорема 2.3. О разложении функции по переменным

 

Пусть f(x₁,..., x_n) Î P₂. Тогда для любого m: 1 ≤ m ≤ n допустимо представление

f(x₁,..., x_m, x_m+1,..., x_n) = ,

где дизъюнкция берется по всем наборам из 0 и 1, которое называется разложением функции f по переменным x ₁,..., x_n.

Прежде чем доказать утверждение, рассмотрим примеры.

 

Пример 2.12. m = 1, запишем разложение по переменным х:

f (x ₁,..., x_n)= = f (0, x ₂ , …, x_n)Ú x ₁ f (1, x ₂,..., x_n). (2.1)

 

Пример 2.13. m =2, запишем разложение по переменным х и :

f (x ₁, x ₂,… x _n) = =

=

= .

Если f (x ₁, x ₂) = x ₁ Å x ₂, то последняя формула дает x ₁ Å x ₂ = x ₂Ú x ₁ .

 

Доказательство. Для доказательства возьмем произвольный набор (a ₁,..., a _n) и покажем, что левая и правая части формулы (2.1) принимают на этом наборе одинаковые значения. Слева имеем f (a ₁,..., a_n). Cправа: .

Дизъюнкция берется по всевозможным наборам (s ₁,..., s_m). Если в этих наборах хотя бы одно s_i ¹ a_i (1≤ i ≤ m), то = 0 и , следовательно, ненулевой член будет только на наборе (s ₁,..., s_m) = (a ₁,..., a_m), тогда = f (a ₁,..., a_n).

 

Следствие 2.1. Любую функцию f(x₁,..., x_n), не равную тождественно нулю, можно представить в виде: , причём единственным образом. Этот вид называется совершенной дизъюнктивной нормальной формой функции f(x₁,..., x_n) и записывается СДНФ.

 

Доказательство. Существование СДНФ для функции, не равной тождественно нулю, вытекает из предыдущей теоремы.

Замечание. – элементарная конъюнкция ранга n по числу входящих переменных; предполагается, что при i ¹ j, х_i ¹ х_j. СДНФ для f (x₁,..., x_n) – дизъюнкция элементарных конъюнкций ранга n. Если функция представлена в виде дизъюнкций элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше n, то такая форма называется дизъюнктивной нормальной формой (ДНФ).

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

а) Если f ≡ 0, то f (x ₁,..., x_n) = & .

б) Если f (x ₁,..., x_n) ¹ 0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки , &, Ú. СДНФ дает алгоритм представления функции в виде формулы через &, Ú, .

 

Пример 2.14. Пусть функция f (x ₁, x ₂, x ₃) задана таблицей истинности (2.19). Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому

f (x ₁, x ₂, x ₃) = x ₁⁰ & x ₂¹ & x ₃⁰ Ú x ₁¹ & x ₂⁰ & x ₃⁰ Ú x ₁¹& x ₂¹ & x ₃¹ = = & x ₂& Ú x ₁& & Ú x ₁& x ₂& x _3.

Таблица 2.19

x 1	x 2	x 3	f

Следствие 2.3. Мы умеем представлять функцию в виде . Нельзя ли представить ее в виде ? Пусть функция f (x₁,..., x_n) ¹ 1 тождественно. Тогда функция f * ¹ 0 тождественно, и ее можно представить в виде

По принципу двойственности заменим & на Ú и наоборот; получим (2.2)

называется элементарной дизъюнкцией ранга n. Представление функции в виде (2.2) называется совершенной конъюнктивной нормальной формой или в краткой записи – СКНФ. СКНФ для f (x ₁,..., x_n) – конъюнкция элементарных дизъюнкций ранга n. КНФ для f (x ₁,..., x_n) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньше n.

Пример 2.15. Пусть f (x ₁, x ₂, x ₃) = x ₁ (x ₂ (x ₃ ~ x ₁)). Представим ее в виде СКНФ, для этого получим таблицу истинности (табл.2.20).

Функция равна нулю только на наборе (1, 1, 0), поэтому

f (x ₁ x ₂ x ₃)= x ₁ Ú x ₂ Ú x ₃ = x ₁⁰Ú x ₂⁰Ú x ₃¹= Ú Ú x ₃.

 

Таблица 2.20

x 1	x 2	x 3	x 3~ x 1	x 2 (x 3~ x 1)	f
1	1	1	1 1	1	1

 

2.5. Полнота, примеры полных систем

Определение 2.9. Система функций { f ₁, f ₂,..., f _s,...}Ì P ₂ называется полной в Р ₂, если любая функция f (x ₁,..., x_n) Î P ₂ может быть записана в виде формулы через функции этой системы.

 

Полные системы

1. P ₂ – полная система.

2. Система M ={ x ₁& x ₂, x ₁Ú x ₂, } – полная система, так как любая функция алгебры логики может быть записана в виде формулы через эти функции.

 

Пример 2.16. Неполные системы: { }, {0,1}.

Лемма (достаточное условие полноты)

Пусть система U = { f ₁, f ₂,..., f_s,...} полна в Р ₂. Пусть B = { g ₁, g ₂,..., g_k,...} – некоторая система из Р ₂, причем любая функция f_i Î U может быть выражена формулой над B, тогда система B полна в Р ₂.

Доказательство. Пусть h(x₁,..., x_n) Î P₂; так как U полна в Р₂, то h(x₁,..., x_n) =N[f₁,..., f_s,...] = N[L₁[g₁,..., g_k],..., L_s[g₁,..., g_k],...] = U[g₁,..., g_k]. Здесь мы воспользовались тем, что для любого i n f_i может быть выражена формулой над B, поэтому f_i=L_i[g_i,..., g_k].

3. Система { x ₁Ú x ₂, } полна в P ₂.

Возьмем в качестве полной в Р ₂ системы U ={ x ₁Ú x ₂, , x ₁& x ₂}, B ={ x ₁Ú x ₂, }. Надо показать, что x ₁& x ₂ представляется формулой над B. Действительно, по правилу Де Моргана получим x ₁& x ₂= .

С помощью этой леммы докажем полноту еще ряда систем.

4. Система { x ₁& x ₂, } – полна в Р ₂.

5. Система { x ₁| x ₂} полна в Р ₂. Для доказательства возьмем в качестве полной в Р ₂ системы U = { x ₁& x ₂, } и выразим х ₁& х ₂ и через х ₁| x ₂ :

= x ₁ | x ₁, x ₁ & x ₂ = = (x ₁| x ₂)|(x ₁| x ₂).

6. Система { x ₁ x ₂} полна в Р ₂. U = { x ₁Ú x ₂, }, = x ₁ x ₁, x ₁Ú x ₂ = = = (x ₁ x ₂) (x ₁ x ₂).

7. Система { x ₁& x ₂, x ₁Å x ₂, 0, 1}, U = { x ₁& x ₂, }, = x ₁Å1.

Следствие 2.4. Полином Жегалкина.

f (x ₁,..., x_n) Î P ₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как { x ₁& x ₂, x ₁Å x ₂, 0, 1} полна в Р ₂. В силу свойства x &

& (y Å z)= xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ... х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина

где , s = 0, 1,..., n, причем при s = 0 получаем свободный член а ₀.