2015-05-20
1145
Пусть f(x1,..., xn) Î P2. Тогда для любого m: 1 ≤ m ≤ n допустимо представление
f(x1,..., xm, xm+1,...,xn) = 
,
где 
, и дизъюнкция берется по всем 
наборам из 0 и 1, которое называется разложением функции f по переменным x 1,..., 
.
Прежде чем доказать утверждение, рассмотрим примеры.
Пример 12. m = 1, запишем разложение по переменной 
:
f (x 1,..., xn)= 
= 
f (0, x 2 , …, xn) Ú x 1 f (1, x 2,..., xn).
Пример 13. Рассмотрим функцию 
и запишем разложение по переменным 
:
.
Если f (x 1, x 2) = x 1 Å x 2, то последняя формула дает
x 1 Å x 2 = 
x 2Ú x 1 
, так как 
и 
, 
и 
.
Доказательство теоремы. Для доказательства возьмем произвольный набор (a 1,..., a n) и покажем, что левая и правая части разложения по переменным принимают на этом наборе одинаковые значения. Слева имеем f (a 1,..., an).
Cправа: 
.
Дизъюнкция берется по всевозможным наборам (s 1,..., sm).
Если в этих наборах хотя бы одно si ¹ ai (1≤ i ≤ m), то 
= 0 и 
, следовательно, ненулевой член будет только на наборе (s 1,..., sm) = (a 1,..., am), тогда 
= f (a 1,..., an).
Следствие 1. Любую функцию f (x1,..., xn), не равную тождественному нулю, можно представить в виде: 
. Этот вид называется совершенной дизъюнктивной нормальной формой функции f (x1,..., xn) и записывается СДНФ.
|
|
|
Замечание. 
– элементарная конъюнкция ранга n по числу входящих переменных; предполагается, что при i ¹ j, хi ¹ хj. СДНФ для f (x1,..., xn) – дизъюнкции элементарных конъюнкций ранга n. Если функция представлена в виде дизъюнкции элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше n, то такая форма называется дизъюнктивной нормальной формой (ДНФ).
Cледствие 2. Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и Ú.
а) Если f ≡ 0, то f (x 1,..., xn) = 
& 
. 
б) Если f (x 1,..., xn) ¹ 0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки 
, &, Ú. СДНФ дает алгоритм представления функции в виде формулы через &, Ú, .
Пример 14. Пусть функция f (x 1, x 2, x 3) задана таблицей истинности (18). Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому
f (x 1, x 2, x 3) = x 10 & x 21 & x 30 Ú x 11 & x 20 & x 30 Ú x 11& x 21 & x 31 =
.
Таблица 18
| x 1 | x 2 | x 3 | f | ||||
Следствие 3. Мы умеем представлять функцию в виде 
. Нельзя ли представить ее в виде 
? Пусть функция f (x1,..., xn) ¹ 1 тождественно. Тогда функция f * ¹ 0 тождественно, и ее можно представить в виде СДНФ.
По принципу двойственности заменим & на Ú и наоборот; получим
называется элементарной дизъюнкцией ранга n. Это представление функции называется совершенной конъюнктивной нормальной формой или в краткой записи – СКНФ. СКНФ для
|
|
|
f (x 1,..., xn) – конъюнкция элементарных дизъюнкций ранга n. КНФ для f (x 1,..., xn) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньше n.
Пример 15. Пусть f (x 1, x 2, x 3) = x 1 
(x 2 (x 3 ~ x 1)). Представим ее в виде СКНФ, для этого получим таблицу истинности (табл. 19).
Функция равна нулю только на наборе (1, 1, 0), поэтому
f (x 1 x 2 x 3)= x 1 
Ú x 2 Ú x 3 
= x 10Ú x 20Ú x 31= Ú Ú x 3.
Таблица 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 |
