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

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

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

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

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

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

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

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

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

.

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

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

Доказательство.Существование СДНФ для функции не равной тождественно нулю вытекает из предыдущей теоремы. Покажем, что эта СДНФ единственная. В самом деле, имеется n-местных функций, не равных нулю тождественно. Подсчитаем число различных СДНФ от n переменных. Путь означает число сочетаний из n элементов по k. Тогда число одночленных СДНФ равно . Число k-членных СДНФ равно . Число 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 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки , &, Ú. СДНФ дает алгоритм представления функции в виде формулы через &, Ú, .

Пример 3. Пусть функция f(x₁, x₂, x₃) задана таблицей истинности. Запишем ее в виде СДНФ. Наборов, на которых функция равна 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.

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

.

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

(2)

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

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

x1	x2	x3	x3~x1	x2 (x3~x1)	f
1	1	1	1 1	1	1

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

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