ВУЗ:
Составители:
Рубрика:
Так как Q(X, Y, Z) принимает значение истины на всяком наборе пропозиционных переменных, на котором значение
истины принимает формула Р(X, Y, Z), то по определению логического следования Р
−
Q. ■
2 способ.
□ Рассмотрим следующую формулу:
))(())(( ZYXZYX ∨→→→∨ ,
с помощью равносильных преобразований докажем, что она тождественно истинна.
∨≡∨∨∨∨∨≡∨→→→∨ XZYXZYXZYXZYX (())(())(())((
)10)(18()3)(12(
∨∨∧≡∨∨∨∧∨∧≡∨∨∨∧∨ XZXZYXZYZXZYXZY )()()())
)15()5(
∨∨≡∨∨∨∧≡≡∨∨∨∧∨≡∨∨ XZZYXZEZYXZXXZY
)7()17()6(
))(())()((
.
)7()17(
EEYXZY ≡∨∨≡∨∨
Итак, формула P→Q является тавтологией, следовательно, по теореме 1 (п. 1.8) Р
−
Q. ■
3 способ.
□ Предположим противное, т.е., что Q не является логическим следствием P, тогда 1))((
=
→∨λ ZYX , а
0))(( =∨→λ ZYX .
Так как
.0)(,0)(,0)(,1)(,0))(( =
λ
=
λ
⇒
=
∨
λ
=
λ
⇒=∨→λ ZYZYXZYX
Но если ,0)(,0)(,1)( =λ=λ=λ ZYX то 0))((
=
→∨λ ZYX . Получено противоречие, следовательно, наше предпо-
ложение неверно и Р
−
Q. ■
4 способ.
□ Рассмотрим следующую формулу:
))(())(( ZYXZYX ∨→→→∨ ,
преобразуем её:
∧≡∨∨∨∨∨≡∨→→→∨ XZYXZYXZYXZYX (())(())(())((
)10)(18()12)(3(
.)())(())
)8(
YXZZYXZYXZY ∧∧∨∅∧∨∧≡∧∧∧∨∧
Затем воспользуемся формулой метода резолюций
)()( QRQP ∨∧∨
−
R
P
∨ ,
где в качестве Q выступает Z.
)4)(8(
))(())())((( ≡∧∧∅∨∧−∧∧∨∅∧∨∧ YXYXYXZZYX
(
)
(
)
.
)16(
48
∅≡∧∧∧≡ YXYX
Тогда EZYXZYX =∨→→→∨ ))(())(( и по теореме 1 (п. 1.8) Р
−
Q. ■
10. Выясните, верны ли следующие следования из группы формул:
)(),,( TXTZTYZYX ∧−→∧∨∨ .
Решение. Допустим, что данное следование неверно, т.е. существуют такие значения переменных, для которых
,1)(,1)(,1)( =→λ=∧λ=∨∨λ TZTYZYX
а .0)(
=
∧
λ
TX
Тогда из
1)( =∧λ TY
следует, что 1)( =λ T и
1)( =λ Y
, а значит 0)(
=
λ
Y . Если 1)( =
λ
T , следовательно,
0)( =λ T
и
одновременно
⇒=→λ ,1)( TZ 0)( =
λ
Z . Так как 1)(
=
λ
T и 0)(
=
∧
λ
TX , то 0)(
=
λ
X .
Но если
0)( =λ Y , 0)( =λ Z , 0)( =λ X , то 1)(
≠
∨∨
λ
ZYX . Получено противоречие; следовательно, наше предпо-
ложение неверно и логическое следование имеет место.
11. Найдите все неравносильные между собой и не тождественно истинные следствия из данных посылок:
ZYYX →→ , .
Решение. Составляем конъюнкцию посылок и приводим её равносильными преобразованиями к СКНФ:
