ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 6752
Скачиваний: 28
71
закона де Моргана. Заметим также, что x
i
σ
i
= x
i
⎯
σ
i
. Следовательно,
σ=(1,...,1)
f (x
1
,х
2
,...,x
n
) =
٨
(f (
σ
1
,
σ
2
,...,
σ
n
) ٧ х
1
⎯
σ
1
٧ х
2
⎯
σ
2
٧...٧ х
n
⎯
σ
n
). ■
σ=(0,...,0)
Если f (x
1
,x
2
,...,x
n
)
≢ 1, то соотношение (6) можно переписать в
форме
f(x
1
,x
2
,...,x
n
) =
٨
(х
1
⎯
σ
1
٧ х
2
⎯
σ
2
٧...٧ х
n
⎯
σ
n
).
(7)
по всем
σ,
f(
σ)=0
Эта форма называется совершенной конъюнктивной нормальной
формой (совершенной КНФ) функции f (x
1
,x
2
,...,x
n
).
Построим совершенную КНФ функции х
1
⊕ х
2
(табл. 3.5):
х
1
⊕ х
2
= (х
1
٧ х
2
) (
⎯х
1
٧
⎯х
2
).
Вывод. Булеву функцию любого числа переменных можно по-
строить из функций одной или двух переменных. Средством такого
построения является суперпозиция булевых функций, то есть под-
становка одних булевых функций вместо переменных в другие буле-
вы функции.
3.4
Полнота
системы
булевых
функций
Система булевых функций {f
1
(x
11
,...,x
1p1
),...,f
s
(x
s1
,...,x
sps
),...} на-
зывается полной, если для любой булевой функции f (x
1
,...,x
n
) мож-
но построить равную её функцию, представляющую собой результат
суперпозиции функций {f
1
,...,f
s
,...} и x
1
,...,x
n
.
Примеры полных систем булевых функций.
1.
x
1
x
2
, x
1
٧ x
2
,
⎯x
1
. Полнота следует из того, что для каждой функ-
ции можно построить совершенные ДНФ и КНФ.
2.
x
1
x
2
,
⎯x
1
. Полнота следует из п.1 и равенства х
1
٧ х
2
=
⎯х
1
⎯х
2
.
3.
x
1
٧ x
2
,
⎯x
1
. Полнота следует из п.1 и равенства х
1
х
2
=
⎯х
1
٧
⎯х
2
.
4.
х
1
х
2
, х
1
⊕ х
2
, 1. Полна, так как
⎯х
1
= х
1
⊕ 1, а система x
1
x
2
,
⎯x
1
явля-
ется полной (п.2).
Теорема 3. Любую булеву функцию f (x
1
,...,x
n
) можно предста-
вить в виде полинома
72
f (x
1
,x
2
,...,x
n
) = a
0
⊕ a
1
x
1
⊕ a
2
x
2
⊕...⊕ a
2
n
-1
x
1
…x
n
,
где a
i
∈{0,1}, i = 0, 1,...,2
n
-1.
Доказательство. Система функций х
1
х
2
, х
1
⊕ х
2
, 1, 0 полна.
Пользуясь правилами
A
⊕ A = 0, A · A = A, A ⊕ 0 = A,
A · 0 = 0, A · 1 = A, A · B = B · A,
A
⊕ B = B ⊕ A, (A ⊕ B) · C = A · C ⊕ B · C,
которые легко проверить, получим представление функции в виде
полинома по модулю 2. ■
Легко показать, что представление функции в виде полинома
по модулю два является единственным.
Как обнаружить полноту или неполноту булевых функций? Для
решения этого вопроса познакомимся с пятью классами булевых
функций.
Класс функций, сохраняющих ноль
Функция f (x
1
,...,x
n
) называется сохраняющей ноль, если она
на наборе из нулей принимает значение 0, т.е. f (0,...,0) = 0.
Так, функции x
1
x
2
, x
1
٧ x
2
, х, 0 – сохраняют ноль, функции
x
1
→ х
2
,
⎯х, 1 – не сохраняют.
Лемма 1. Из функций, сохраняющих ноль, суперпозицией
можно получить только функции, сохраняющие ноль.
Доказательство. Поскольку функции, равные переменным,
сохраняют ноль, достаточно показать, что функция
Φ (х
1
,...,х
n
) = f (f
1
(x
1
,...,x
n
),..., f
m
(x
1
,...,x
n
))
сохраняет ноль, если функции f, f
1
,...,f
m
сохраняют ноль. Последнее
следует из
f (f
1
(0,...,0),... f
m
(0,...,0)) = f (0,...,0) = 0. ■
Следствие. Полная система булевых функций должна содер-
жать хотя бы одну функцию, не сохраняющую ноль.
Класс функций, сохраняющих единицу
Функция f (x
1
,...,x
n
) называется сохраняющей единицу, если
она на наборе из единиц принимает значение 1, то есть f (1,..,1) = 1.
Так, функции x
1
x
2
, x
1
٧ x
2
, х, 1 – сохраняют единицу, функции
x
1
⊕ х
2
,
⎯х, 0 – не сохраняют.
73
Лемма 2. Из функций, сохраняющих единицу, суперпозицией
можно получить только функции, сохраняющие единицу.
Доказательство очевидно.
Следствие. Полная система булевых функций должна содер-
жать хотя бы одну функцию, не сохраняющую единицу.
Класс самодвойственных функций
Функция f (x
1
, ... ,x
n
) называется самодвойственной, если
f (x
1
, ... ,x
n
) =
⎯f (⎯x
1
,…,
⎯x
n
). Например, x ,
⎯x – самодвойствен-
ные функции, x
1
x
2
, x
1
٧ x
2
- несамодвойственные.
Лемма 3. Из самодвойственных функций путём суперпозиции
можно получить только самодвойственные функции.
Доказательство. Пусть f (y
1
, ... ,y
m
), f
1
(x
1
, ... ,x
n
),...,f
m
(x
1
, ...
,x
n
)
− самодвойственные функции. Надо показать, что
Φ (x
1
,...,x
n
) = f (f
1
(x
1
,...,x
n
),..., f
m
(x
1
,...,x
n
))
− самодвойственная.
Из цепочки равенств
⎯Φ (⎯x
1
,…,
⎯x
n
) =
⎯f (f
1
(
⎯x
1
,…,
⎯x
n
),…,f
m
(
⎯x
1
,…,
⎯x
n
)) =
=
⎯f (⎯f
1
(x
1
,…,x
n
),…,
⎯f
m
(x
1
,…,x
n
)) = f (f
1
(x
1
,…,x
n
),…,f
m
(x
1
,…,x
n
)) =
= Φ (x
1
,...,x
n
) следует, что Φ (x
1
,...,x
n
) – самодвойственна. ■
Следствие. Полная система функций должна содержать хотя
бы одну несамодвойственную функцию.
Лемма 4. Из несамодвойственной функции подстановкой x
и
⎯x можно получить константу.
Доказательство. Функция f (x
1
, ... ,x
n
) несамодвойственная,
поэтому найдется набор
α = (α
1
,...,
α
n
) такой, что f (
α
1
,...,
α
n
) =
=f (
⎯α
1
,...,
⎯α
n
). По набору
α = (α
1
,...,
α
n
) определяются вспомогатель-
ные функции
ϕ
i
(x) (i = 1,2...,n),
x, если
α
i
= 0,
ϕ
i
(x) =
⎯x, если α
i
= 1.
Функция
ϕ
i
(x) обладает свойством
ϕ
i
(0) =
α
i,
ϕ
i
(1) =
⎯α
i
.
Рассмотрим функцию
ϕ (x) = f (ϕ
1
(x), ... ,
ϕ
n
(x)). Она получена
из функции f (x
1
, ... ,x
n
) подстановкой x и
⎯x. Функция ϕ (x) – кон-
станта, так как
ϕ (0) = f (ϕ
1
(0),...,
ϕ
n
(0)) = f (
α
1
,...,
α
n
) = f (
⎯α
1
,...,
⎯α
n
) =
= f (
ϕ
1
(1),...,
ϕ
n
(1)) =
ϕ(1). ■
74
Класс монотонных функций
Набор
α = (α
1
,...,
α
n
) предшествует набору
β = (β
1
,...,
β
n
), если
α
i
≤ β
i
(i=1,2,...,n). Этот факт обозначаем как
α
≼ β. Наборы, кото-
рые находятся в отношении
≼ , называются сравнимыми.
Функция f (x
1
,...,x
n
) называется монотонной, если для любой
пары наборов
α = (α
1
,...,
α
n
) и
β = (β
1
,...,
β
n
) таких, что
α
≼ β,
f (
α) ≤ f(β).
Например, функции x
1
x
2
, x
1
٧ x
2
, x – монотонные, а
⎯x − немо-
нотонная.
Лемма 5. Из монотонных функций с помощью суперпозиции
можно получить только монотонные функции.
Доказательство. Пусть функции f (y
1
,...,y
m
), f
1
(x
1
,...,x
n
),...,
f
m
(x
1
,...,x
n
)
−монотонные. Надо показать, что
Φ(x
1
,...,x
n
) = f (f
1
(x
1
,...,x
n
),...,f
m
(x
1
,...,x
n
))
− монотонная функция.
Пусть
α
≼ β, тогда f
i
(
α) ≤ f
i
(
β) (i=1,...,m). Отсюда
Φ(
α) = f (f
1
(
α),...,f
m
(
α)) ≤ f (f
1
(
β),...,f
m
(
β)) = Φ(β). ■
Следствие. Полная система функций должна содержать хотя
бы одну немонотонную функцию.
Лемма 6. Из немонотонной функции путём подстановки кон-
стант 0, 1 и функции x можно получить
⎯x.
Доказательство. Пусть дана немонотонная функция
f (x
1
,...,x
n
), т.е. для неё существуют наборы
α = (α
1
,...,
α
n
) и
β = (β
1
,...,
β
n
) такие, что
α
≼ β, а f (α) > f (β). Рассмотрим функцию
ψ(x), которая получается из функции f (x
1
,...,x
n
) подстановкой кон-
стант 0, 1 и функции x. Подстановку определим следующим обра-
зом: вместо x
i
будем подставлять
α
i
, если
α
i =
β
i
, и x, если
α
i
≠
β
i
.
Рассмотрим функцию
ψ(x).
ψ (0) = f (α
1
,...,
α
n
) > f (
β
1
,...,
β
n
) =
ψ(1).
Следовательно,
ψ(x) =⎯x.
■
Класс линейных функций
Функция f (x
1
,...,x
n
) называется линейной, если полином этой
функции имеет вид
f (x
1
,...,x
n
) = a
0
⊕ a
1
x
1
⊕...⊕a
n
x
n
, где a
i
∈
{0,1} (i=0,1,...,n).
75
Например: x,
⎯x – линейны, x
1
x
2
− нелинейна.
Лемма 7. Из линейных функций суперпозицией можно полу-
чить только линейные функции.
Доказательство очевидно.
Следствие. Полная система функций должна содержать хотя
бы одну нелинейную функцию.
Лемма 8. Из нелинейной функции f (x
1
,...,x
n
), констант 0, 1 и
функций x,
⎯x, y суперпозицией можно получить конъюнкцию двух
переменных xy.
Доказательство. Так как функция f (x
1
,...,x
n
) нелинейна, её по-
лином по модулю 2 содержит хотя бы один член с конъюнкцией
двух переменных x
i
и x
j
. Члены полинома, представляющего функ-
цию f (x
1
,...,x
n
) можно перегруппировать следующим образом:
f (x
1
,...,x
n
) = x
i
x
j
f
1
(x
1
,...,x
i-1
,x
i+1
,...,x
j-1
, x
j+1
,..., x
n
)
⊕
⊕ x
i
f
2
(x
1
,...,x
i-1
, x
i+1
,...,x
j-1
, x
j+1
,..., x
n
)
⊕
⊕ x
j
f
3
(x
1
,...,x
i-1
, x
i+1
,...,x
j-1
, x
j+1
,..., x
n
)
⊕
⊕ f
4
(x
1
,..., x
i-1
,x
i+1
,..., x
j-1
, x
j+1
,..., x
n
),
где функция f
1
(x
1
,..., x
i-1
,x
i+1
,..., x
j-1
, x
j+1
,..., x
n
)
≢ 0, т.е. существует
набор (
α
1
,...,
α
i-1
,
α
i+1
,...,
α
j-1
,
α
j+1
,...,
α
n
) такой, что
f (
α
1
,...,
α
i-1
,
α
i+1
,...,
α
j-1
,
α
j+1
,...,
α
n
) = 1.
Подставляя этот набор в f (x
1
,...,x
n
), получим функцию
χ(x
i
, x
j
):
χ (x
i
, x
j
) = f (
α
1
,...,
α
i-1
, x
i
,
α
i+1
,...,
α
j-1
, x
j
,
α
j+1
,...,
α
n
) = x
i
x
j
⊕ αx
i
⊕ βx
j
где
α = f
2
(
α
1
,...,
α
i-1
,
α
i+1
,...,
α
j-1
,
α
j+1
,...,
α
n
),
β = f
3
(
α
1
,...,
α
i-1
,
α
i+1
,...,
α
j-1
,
α
j+1
,...,
α
n
),
γ = f
4
(
α
1
,...,
α
i-1
,
α
i+1
,...,
α
j-1
,
α
j+1
,...,
α
n
).
Рассмотрим функцию F (x, y) =
χ (x ⊕β, y ⊕α) = xy ⊕ αβ ⊕ γ.
Она получена суперпозицией
χ (x
i
, x
j
), x, y и
⎯x (⎯x = x ⊕ 1).
Если
αβ ⊕ γ = 0, то F (x, y) = xy,
а если
αβ ⊕ γ = 1, то⎯F (x, y) = xy. ■
Критерий полноты системы булевых функций дает теорема 4
(приведем ее без доказательства).
Теорема 4 (о полноте). Для того чтобы система булевых
функций {f
1
(x
11
,..., x
1p1
),..., f
s
(x
s1
,..., x
sps
),…} была полна, необходимо
и достаточно, чтобы она содержала функцию, не сохраняющую 0;
функцию, не сохраняющую 1; несамодвойственную функцию; немо-
нотонную функцию; нелинейную функцию.
⊕ γ,