Обозначим xs= 
Посмотрим, чему равно xs при разных значениях x и s (табл. 3.17).
Таблица 3.17
| x\s | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
Из табл. 3.17 следует: 
тогда и только тогда, когда x= s.
Теорема о разложении функции по переменным. 
Пусть f(x1, ..., x n) ÎP2. Тогда для любого m: 1 ≤ m ≤ n допустимо представление f(x1, ... , x m, x m+1, ..., x n) =
= 
,
где 
, и дизъюнкция берется по всем 
наборам из 0 и 1, которое называется разложением функции f по переменным x1, ..., 
.
Прежде чем доказать утверждение, рассмотрим примеры.
Пример 12. m = 1, запишем разложение по переменной 
:
f (x1, ..., x n)= 
= 
f (0, x2 , …, x n) Úx1f (1, x2, ..., x n).
Пример 13. Рассмотрим функцию 
и запишем разложение по переменным 
:
.
Если f(x1, x2) = x1 Å x2, то последняя формула дает x1 Å x2 = = 
x2Ú x1 
, так как 
и 
, 
и 
.
Доказательство теоремы. Для доказательства возьмем произвольный набор (a1, ..., a n) и покажем, что левая и правая части разложения по переменным принимают на этом наборе одинаковые значения. Cлева имеем f(a1, ..., an).
Cправа: 
.
Дизъюнкция берется по всевозможным наборам (s1, ..., sm). Если в этих наборах хотя бы одно si¹ai(1≤i≤m), то 
и 
, следовательно, ненулевой член будет только на наборе (s1, ... ,sm) = (a1, ... ,am), тогда 
= f (a1, ..., an).
Следствие 1. Любую функцию f (x1, ..., x n), не равную тождественному нулю, можно представить в виде: 
. Этот вид называется совершенной дизъюнктивной нормальной формой функции f (x1, ..., x n) и записывается CДНФ.
Замечание. 
– элементарная конъюнкция ранга n по числу входящих переменных; предполагается, что при i ¹ j, х i ¹ х j. СДНФ для f (x1, ..., x n) – дизъюнкции элементарных конъюнкций ранга n. Если функция представлена в виде дизъюнкции элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше n, то такая форма называется дизъюнктивной нормальной формой (ДНФ).
C ледствие 2. Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и Ú.
а) Если f ≡ 0, то f(x1, ..., x n) = 
& 
. 
б) Если f(x1, ..., x n) ¹ 0 тождественно, тогда ее можно представить в виде CДНФ, где используются только связки 
, &, Ú. CДНФ дает алгоритм представления функции в виде формулы через &, Ú, 
.
Пример 14. Пусть функция f (x1, x2, x3) задана таблицей истинности (3.18). Запишем ее в виде CДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f(x1, x2, x3) = = x10 &x21 &x30 Ú x11 &x20 &x30 Úx11&x21 &x31 
.
Таблица 3.18
| 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, ..., x n) ¹ 1 тождественно. Тогда функция f* ¹ 0 тождественно, и ее можно представить в виде СДНФ.
По принципу двойственности заменим & на Ú и наоборот; получим
называется элементарной дизъюнкцией ранга n. Это представление функции называется совершенной конъюнктивной нормальной формой или в краткой записи – CКНФ. CКНФ для
f(x1, ..., x n) – конъюнкция элементарных дизъюнкций ранга n. КНФ для f(x1, ..., x n) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньше n.
Пример 15. Пусть f(x1, x2, x3) = x1 
(x2 (x3 ~ x1)). Представим ее в виде CКНФ, для этого получим таблицу истинности (табл. 3.19).
Функция равна нулю только на наборе (1, 1, 0), поэтому f(x1, x2, x3)=x1 
Úx2 
Úx3 
=x10Úx20Úx31= 
Ú Úx3.
Таблица 3.19
| 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 |
3.5. Полнота, примеры полных систем
Определение. Cистема функций {f1, f2, ..., f s , ...} 
P2 называется полной в Р 2 , если любая функция f(x1, ..., x n )ÎP2 может быть записана в виде формулы через функции этой системы.
Полными системами, например, являются само 
или множество 
, так как каждая функция может быть представлена в виде CДНФ или CКНФ, где используются только эти связки. Примерами неполных систем являются 
или 
.
Лемма (достаточное условие полноты).
Пусть система U = {f1, f2, ..., f s, ...} полна в Р2, 
–диагностическая система. Пусть B = {g1, g2, ..., g k, ...} – некоторая система из Р2, причем любая функция f iÎ U может быть выражена формулой над B, тогда система B полна в Р2.
Доказательство. Пусть h(x1, ..., x n)ÎP2; так как U полна в Р2, то
h(x1, ..., x n) = N[f1, ..., f s, ...] = N[L1 [g1, ..., g k, ...], ..., L s[g1,..., g k, ...], ...] = = 
[g1, ..., g k]. Здесь мы воспользовались тем, что для любого i 
nf i может быть выражена формулой над B, поэтому f i = L i[g i, ..., g k, ...].
C помощью леммы докажем полноту некоторых важных систем.
1. Cистема 
полна в 
.
Возьмем в качестве полной в Р2 системы U = {x1Úx2, 
, x1&x2}, B={x1Úx2, }. Надо показать, что x1&x2 представляется формулой над B. Действительно, по правилу Де Моргана получим x1&x2= 
.
2. Cистема {x1&x2, } полна в Р2.
3. Cистема {x1|x2} полна в Р2. Для доказательства возьмем в качестве полной в Р2 системы U = {x1&x2, 
} и выразим х1&х2 и 
через х1|x2: = x1 | x1, x1 &x2 = 
= (x1|x2)|(x1|x2).
4. Cистема {x1 
x2} полна в Р2. U = {x1Úx2, }, = x1 x1, x1Úx2 =
= 
= (x1 
x2) (x1 x2).
5. Cистема {x1&x2, x1Åx2, 0, 1}, U = {x1&x2, }, = x1Å1.
Дата: 2019-04-23, просмотров: 247.
