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

UptoLike

Составители: 

18
( )
(
)
( )
î
í
ì
Ï
Î
=
.,...,,,0
,...,,,1
,...,,
21
21
21
jaaa
jaaa
aaa
n
n
n
если
если
f
И наоборот, булева функция )x,...,x,x(f
n21
однозначно определяет
множество истинности
(
)
(
)
{
}
1
2121
==
nnf
,...,,f,...,,fE
aaaaaa
.
В случае описанного выше примера
(
)
(
)
(
)
(
)
{
}
.,,,E
f
001010100000
=
Имеет место
Теорема. Всякая булева функция представима в виде формулы алгебры ло-
гики через операции
&
,
и ù, и это представление таково:
(
)
( )
(
)
(
)
nmmm
,...,
n
x...,,x,,...,,f&x&...&x&xx...,,xf
m
m
121211
21
1
+
Ú
=
sss
s
ss
ss
,
где
(
)
m
,...,,
s
s
s
21
различные двоичные наборы значений пе-
ременных
iin
xx,nm,x...,,x
i
=££
s
1
1
, если 1
=
i
s
,
ii
xx
i
=
s
, если 0
=
i
s
,
m
...,
,
i
1
=
.
Приведенная выше в примере функция
(
)
321
x,x,xf представима
формулой:
(
)
(
)
(
)
(
)
(
)
( ) ( ) ( ) ( )
.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
переменных называются равными, если они
принимают одинаковые значения на соответствующих одинаковых набо-
рах переменных, в них входящих. Равные функции реализуются равно-
сильными формулами. Например,