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

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

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

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

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

Пример 12. m = 1, запишем разложение по переменной :

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

Пример 13. Рассмотрим функцию и запишем разложение по переменным :

.

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

x ₁ Å x ₂ = x ₂Ú x ₁ , так как и , и .

Доказательство теоремы. Для доказательства возьмем произвольный набор (a ₁,..., a _n) и покажем, что левая и правая части разложения по переменным принимают на этом наборе одинаковые значения. Слева имеем 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).

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

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

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

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

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

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

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

_.

Таблица 18

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

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

называется элементарной дизъюнкцией ранга n. Это представление функции называется совершенной конъюнктивной нормальной формой или в краткой записи – СКНФ. СКНФ для

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

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

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

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

Таблица 19

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