Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 24 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
70
Принцип двойственности. Пусть
(
)
m
x,,xf K
1
,
(
)
n
x,,xg K
11
, ,
(
)
nm
x,,xg K
1
булевы функции и пусть
(
)
(
)
(
)
(
)
nmnn
x,,xg,,x,,xgfx,,x KKKK
1111
=
Φ
суперпозиция функ-
ций
m
g,,g,f K
1
. Тогда двойственная функция от суперпозиции функций
равна суперпозиции двойственных функций:
(
)
(
)
(
)
(
)
nmnn
x,,xg,,x,,xgfx,,x KKKK
1111
∗∗
= Φ .
Из определения двойственной функции следует , что две булевы
функции равны тогда и только тогда , когда равны двойственные им
функции. Используя этот факт , а также принцип двойственности, из уже
известных равносильностей легко получить новые .
Пример. Пусть
y
x
x
f
=
,
y
x
g
=
. Доказать, что
g
f
=
.
Доказательство. Построим
f
и
g :
(
)
(
)
(
)
()
.y&xy&xyxy,xgg
;y&xyx&xyx&xyx&xyxxyxxy,xff
====
=======
Видим, что
∗∗
= gf
. Следовательно,
g
f
=
, т.е.
y
x
y
x
x
=
.
Доказывается теорема, что число всех булевых функций от
n
пе-
ременных равно
n
2
.
Действительно, любая булева функция от
n
переменных однозначно
задается столбцом своих значений, длина которого равна
n
строк, а число
различных столбцов равно числу всех размещений с повторениями из 0 и
1 длины
n
, т.е.
nn
A
22
2
2 =
, что и доказывает теорему.
Примечание. Задание булевой функции в виде функциональной
схемы будет рассмотрено далее.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Рассмотреть различные способы задания булевой функции от трех пе -
ременных, которая:
a) принимает значение 1 в том и только в том случае, когда ровно две
переменные равны нулю ;
b) принимает такое же значение, как большинство (или меньшество)
переменных .
2. Найти множество истинности
f
E для булевой функции
f
, заданной
формулой: