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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

)9()6(
)()()()()()( ≡∨∧∨∧∨∧∨≡∧∨∧ XZYZXYYYXYZY
(
)
)()()(
9
XZYZXYY ∨∧∨∧∨∧≡
.
Получившиеся нормальные формы не содержат одинаковых конъюнктов или дизъюнктов, и все элементарные
конъюнкции и дизъюнкции правильны, т.е. не содержат одинаковых переменных.
Осталось пополнить каждый конъюнкт и дизъюнкт относительно набора {X, Y, Z}, чтобы получить соответственно СДНФ
и СКНФ нашей формулы.
СДНФ:
)17()7()2(
))(())(()()()()( ≡∧∧∨∧∧≡∧∨∧≡∧∨∧ EYXEZYYXZYXYZY
()
)5(
17
))()(())()(( ≡∨∧∧∨∨∧∧≡ ZZYXXXZY ∨∧∧∨∧∧ )()( ZYXZYX
)()( ZYXZYX ∧∧∨∧∧∨
)()()(
)9(
ZYXZYXZYX ∧∧∨∧∧∨∧∧≡ .
СКНФ:
∧∅∨∨∧∅∨∨∧∅∨≡∨∧∨∧∨∧ ))(())(()()()()(
)8)(1(
ZYYXYXZYZXYY
∧∧∨∨∧∧∨∨∧∧∨≡∅∨∨∧ ))()(())()(())(())((
)16(
XXYZZZXYXXYZX
∨∧∨∨∧∨∨∧∨∧∨≡∧∨∨∧ XZYXZYXXYXYYYZX ()()()()())()((
)6(
∨∧∅∨∨≡∨∨∧∨∨∧∨∨∧∨∨ XYXZYXZYXZYXZY (())(()()()()
)9)(8(
∨≡∨∨∧∨∨∧∨∨∧∨∨∧∅∨∨ XZYXZYXZYXZYXY (()()()()())
)16(
∨∨∧∨∨∧∨∨∧∧∨∨∧∧∨∨ YXZYXZYXZZYXZZY ()()())()(())()
∧∨∨∧∨∨∧∨∨∧∨∨≡∨∨∧∨ )()()()()()
)6(
ZYXZYXZYXZYXZYXZ
∨∧∨∨≡∨∨∧∨∨∧∨∨∧∨∨∧ XZYXZYXZYXZYXZYX ()()()()()(
)9(
)()()() ZYXZYXZYXZY ∨∨∧∨∨∧∨∨∧∨∨ .
Для проверки построим таблицу истинности исходной формулы:
)((
234
1
YXZY ↔→∧ .
Действие
λ(X) λ(Y) λ(Z)
1 2 3 4
СДНФ СКНФ
1 1 1 0 1 1 0
)( ZYX ∨∨
1 1 0 0 1 1 0
)( ZYX ∨∨
1 0 1 1 0 0 0
)( ZYX ∨∨
1 0 0 1 0 1 1
)( ZYX ∧∧
0 1 1 0 0 0 0
)( ZYX ∨∨
0 1 0 0 0 1 0
)( ZYX ∨∨
0 0 1 1 1 1 1
)( ZYX ∧∧
0 0 0 1 1 1 1
)( ZYX ∧∧
9. Докажите следующее логическое следование 2-мя различными способами.
))(())(( ZYXZYX ∨→−→∨ .
Решение. Приведем 4 способа решения; читатель выберет 2 наиболее для него приемлемых.
1 способ.
□ Для доказательства построим таблицы истинности обеих формул.
))((),,(
21
ZYXZYXP →∨= ))((),,(
12
ZYXZYXQ ∨→=
Действия Действия
λ(X) λ(Y) λ(Z)
1 2 1 2
1 1 1 1
1
1
1
1 1 0 1 0
1 1
1 0 1 1
1
1
1
1 0 0 1 0 0 0
0 1 1 1
1
1
1
0 1 0 1 0 1 1
0 0 1 0
1
1
1
0 0 0 0
1
0
1

Страницы