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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
72
3)
(
)
(
)
.xyxf
=
7. Построить двойственные функции для всех элементарных булевых
функций.
8. Доказать или опровергнуть равенство двух функций, используя прин-
цип двойственности:
1)
(
)
,zyxf
=
(
)
(
)
;yxyx
=
ϕ
2)
(
)
;zyxf
=
(
)
(
)
;yxyx
=
ϕ
3)
(
)
;zyxf
=
xz
xy
=
ϕ
4)
(
)
;zyxf
=
xz
xy
=
ϕ
5)
(
)
;zyxf
=
(
)
(
)
.zxyx
=
ϕ
9. Доказать, что
(
)
1
yxf , , если:
1)
(
)
(
)
;xyyxf
=
2)
(
)
(
)
;yxyxf ⊕=
3)
(
)
;| yxxyf ↔=
4)
(
)
.yxyxf ∨= .
5.2 Дизъюнктивные и конъюнктивные нормальные формы
Пусть
x
- булева переменная.
Введем обозначение:
σ
σ
σ
=
xxx , где параметр
{
}
., 10
σ
Оче-
видно, что ,
если,x
если,x
x
=
=
=
0
1
σ
σ
σ
т.е. .xx,xx ==
01
Легко видеть, что
1
=
σ
x тогда и только тогда, когда
σ
=
x
.
Пусть
n
x,...,x,x
21
- булевы переменные .
Определение. Формулы алгебры логики вида:
n
n
iii
x&...&x&x
σ
σσ
2
2
1
1
и
n
n
iii
x...xx
σ
σσ
∨∨
2
2
1
1
,
где
{
}
n...,,,i
k
21
,
{
}
10 ,
k
σ
, называются соответственно элементарной
конъюнкцией (э.к.) и элементарной дизъюнкцией (э.д.) на множестве
булевых переменных
{
}
n
x,...,x,x
21
.