2.4 Разложение булевой функции по переменным

Обозначим XS=

Посмотрим, чему равно XS при разных значениях X и S.

X\S	0	1
0	1	0
1	0	1

Из таблицы следует: XS=1 тогда и только тогда, когда X=S.

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

Пусть F(X1, ..., Xn) Î P2. Тогда для любого M: 1 ≤ M ≤ N допустимо представление:

F(X1, ..., Xm, Xm+1, ..., Xn) = ,

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

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

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

F(X1, ..., Xn) = = F(0, X2 , …,Xn)ÚX1F(1, X2, ..., Xn). (1)

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

F(X1,X2,…XN) = =

.

Если F(X1, X2) = X1 Å X2, то последняя формула дает X1 Å X2 = X2Ú X1 .

Доказательство. Для доказательства возьмем произвольный набор (A1, ..., A N) и покажем, что левая и правая части формулы (1) принимают на этом наборе одинаковые значения. Слева имеем F(A1, ..., AN). Cправа : .

Дизъюнкция берется по всевозможным наборам (S1, ..., SM). Если в этих наборах хотя бы одно SI ¹ AI (1≤I≤M), то = 0 и , следовательно, ненулевой член будет только на наборе (S1, ..., SM) = (A1, ..., AM), тогда F(A1, ..., AN).

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

Доказательство. Существование СДНФ для функции не равной тождественно нулю вытекает из предыдущей теоремы. Покажем, что эта СДНФ единственная. В самом деле, имеется N-местных функций, не равных нулю тождественно. Подсчитаем число различных СДНФ от N переменных. Путь означает число сочетаний из N элементов по K. Тогда число одночленных СДНФ равно . Число K-членных СДНФ равно . Число N-членных СДНФ равно . Число всех различных СДНФ

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

Замечание. – элементарная конъюнкция ранга n по числу входящих переменных, предполагается, что при I ¹ J , ХI ¹ ХJ. СДНФ для F(X1, ..., xN) –Дизъюнкция элементарных конъюнкций ранга N. Если функция представлена в виде дизъюнкций элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше N, то такая форма называется Дизъюнктивной нормальной формой (ДНФ).

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

А) Если F ≡ 0, то F(X1, ..., Xn) = & .

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

Пример 3. Пусть функция F(X1, X2, X3) задана таблицей истинности. Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и

(1, 1, 1), поэтому F(X1, X2, X3) = X10 & X21 & X30 ÚX11 & X20 & X30 ÚX11&X21 & X31=

= &X2& ÚX1& & ÚX1&X2&X3.

X1

X2

X3

F

0

0

0

0

1

1

1

1

0

1

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

1

0

1

0

0

1

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

.

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

(2)

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

Пример 4. Пусть F(X1, X2, X3) = X1 (X2 (X3 ~ X1)). Представим ее в виде СКНФ, для этого получим таблицу истинности.

X1

X2

X3

X3~X1

X2 (X3~X1)

F

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

1

0

1

0

0

1

0

1

1

1

1

0

1

1

0

1

1

1

1

1

1

1

0

1

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

F(X1 X2 X3)=X1 ÚX2 ÚX3 =X10ÚX20ÚX31= Ú Ú X3.

< Предыдущая Следующая >