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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
76
Учитывая, что
(
)
(
)
aabbababa ===∨∨ 0 , получим другую
КНФ , равносильную КНФ
1
:
(
)
(
)
(
)
(
)
(
)
.КНФyxzyxzzyxzyxf
2
=
=
Неоднозначность нормальных форм очевидна.
Таким образом, применяя различные равносильные преобразования,
мы можем прийти к различным нормальным формам, реализующих одну и
ту же функцию. В связи с этим возникает возможность выбора более
предпочтительной реализации.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. По данному набору
(
)
n
α
α
,...,
1
значений переменных
n
xx ,...,
1
построить
элементарную конъюнкцию , истинную только для этого набора значе-
ний переменных.
2. По данному набору
(
)
n
α
α
,....
1
значений переменных
n
xx ,...,
1
построить
элементарную дизъюнкцию , ложную только для этого набора значений
переменных .
3. С помощью эквивалентных преобразований привести к ДНФ формулы:
1)
(
)
(
)
;zxyzx
2)
(
)
(
)
(
)
(
)
;
41431424321
xxxxxxxxxxx
3)
(
)
(
)
;~ yxzyzx →↓
4)
(
)
(
)
;|
314321
xxxxxx
5)
(
)
(
)
.~ yxyxx →∨
4. С помощью эквивалентных преобразований привести к КНФ формулы:
1)
;
y
x
2)
(
)
(
)
;xxxxx
4321
3)
(
)
(
)
;~|
41321
xxxxx
4)
(
)
(
)
(
)
;~ xyzyxyz ↓∨
5)
(
)
(
)
(
)
.~ zyxzyx →⊕→
5. Пусть
nm
UUXX ,...,,,...,
11
- произвольные формулы алгебры логики.
Доказать следующие эквивалентности: