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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
69
(
)
(
)
(
)
(
)
(
)
()()()()
.xxxxxxxxxxxx
fxxxfxxxfxxxfxxx
fxxxfxxxfxxxfxxxx,x,xf
321321321321
1
3
1
2
1
1
0
3
1
2
1
1
1
3
0
2
1
1
0
3
0
2
1
1
1
3
1
2
0
1
0
3
1
2
0
1
1
3
0
2
0
1
0
3
0
2
0
1321
111011101001
110010100000
∨∨∨=
=∨∨
∨=
Такое представление называется нормальной формой, речь о которой
пойдет в следующих двух параграфах.
Всякая формула алгебры логики есть булева функция. Тождественно
истинная и тождественно ложная формулы есть постоянные функции. Их
множества значений соответственно состоят только из единиц или только
из нулей.
Булевы функции вида
,xf =
1
,y&xf
=
4
xf
=
7
,
y
,xf =
2
,yxf
=
5
,yxf ↓=
8
yxf
=
3
, ,yxf
=
6
yxf
=
9
называются элементарными.
Булевы функции от
n
переменных называются равными, если они
принимают одинаковые значения на соответствующих одинаковых набо -
рах переменных , в них входящих. Равные функции реализуются равно-
сильными формулами. Например,
(
)
.xxxxxxxx,xf 1
121212121
=
=
=
Равносильность формул доказывается:
1. С помощью таблиц истинности;
2. Методом эквивалентных (равносильных ) преобразований.
Существует еще один способ доказательства равносильности фор-
мул, основанный на применении так называемого принципа двойственно-
сти.
Булева функция
(
)
n
x,,xf K
1
называется двойственной к функции
(
)
n
x,,xf K
1
, если
(
)
(
)
nn
x,,xfx,,xf KK
11
=
. Так, функция
(
)
yxyxf &, =
, двойственна к
(
)
yxyxf
=
,
:
(
)
y&xy&xyxy,xf ==∨=
.