Дискретная математика. Элементы теории задачи и упражнения. Часть 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
- произвольные формулы алгебры логики.
Доказать следующие эквивалентности:

Страницы