Математическая логика. Типовые расчеты. Лоскутова Е.С - 15 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

)10)(3)(18()12(
))(())(())(())(( ≡∧∨∨∨∨≡∧→→→→ XYXXYXXYXXYX
)9)(16()3)(5(
)()()()())(( ≡∧∨∨∧∨∧≡∧∨∨∧∨≡ XYXXYXXXYXXYX
YXEXYXXXYXXY →≡∧∨≡∨∧∨≡∨∧∨∅≡
)12)(7()17()6)(8(
)()()()( .
Преобразуйте данную формулу равносильным образом так, чтобы она содержала только операции отрицания и
конъюнкции.
YXYYX →→∧↔ ))()((
.
Решение. Сначала упростим формулу:
)18)(11)(10()13)(12(
))()()(())()(( ≡∨∨∧∨∧∨≡→→∧↔ YXYXYYXYXYYX
)17()6()15(
)()()()()()( ≡∨∧∨≡∨∧≡∨∧∨∧∨∧≡ YYYXYYXYXYXYYX
YXEYX ∨≡∧∨≡
)7(
)( .
Затем, с помощью закона де Моргана, поменяем дизъюнкцию на конъюнкцию:
Y
X
Y
X
∧
≡
∨
)11(
.
6. Приведите равносильными преобразованиями следующую формулу к ДНФ:
))(()( YXZYX
∧
→
∧
→ .
Решение. Сначала все логические связки выразим через
∧
и ∨ :
))(()())(()(
)12(
YXZYXYXZYX ∧∨∧∨≡∧→∧→ .
Затем, на основании закона дистрибутивности, сделаем так, чтобы конъюнкции выполнялись раньше дизъюнкций:
()
4
)5(
))(()())(()())(()( ≡∧∧∨∧∨∧∧∨∧≡∧∨∧∨ YXYZYYXXZXYXZYX
)()()()(
)4(
YXYZYYXXZX ∧∧∨∧∨∧∧∨∧≡ .
Данная формула уже является ДНФ, но её ещё можно упростить:
()() ()
8916
)9)(16(
)()()()(
)()()()(
≡∧∨∧∨∧∅∨∧≡
≡∧∧∨∧∨∧∧∨∧
XYZYYZX
YXYZYYXXZX
)()()()()()(
)8()8(
XYZYZXXYZYZX ∧∨∧∨∧≡∧∨∧∨∅∨∧≡ .
Это и есть искомая дизъюнктивная нормальная форма.
7. Приведите равносильными преобразованиями следующую формулу к КНФ:
)()( TZYX →∨∧ .
Решение. Выразим все логические связки через
∧
и ∨ :
)()()()(
)10()11)(12(
TZYXTZYXTZYX ∧∨∨≡∨∨∨≡→∨∧ .
Далее, на основании закона дистрибутивности, сделаем так, чтобы дизъюнкции выполнялись раньше конъюнкций:
)()()(
)6(
TYXZYXTZYX ∨∨∧∨∨≡∧∨∨
.
8. Применяя равносильные преобразования, найдите СДНФ и СКНФ для данной формулы. Проверьте полученные
формы с помощью таблицы истинности.
.))(( YXZY ↔→∧
Решение. Чтобы найти СДНФ и СКНФ формулы, сначала построим её ДНФ и КНФ:
()() ()
1445
)4)(5()13)(12(
))()(()(
))()((())((
≡∨∧∨∧∨∧≡
≡∨∧∨∨∧≡↔→∧
XYYXYZY
XYYXZYYXZY
)16()3)(5()14(
)()()())(()( ≡∧∨∧∨∧≡∨∧∨∧≡ YYXYZYYXYZY
()
)()()()(
)8(
16
XYZYXYZY ∧∨∧≡∅∨∧∨∧≡ .
Это дизъюнктивная форма; преобразуя её, найдем конъюнктивную форму:

Страницы