Solu tion
(
) (
)
(
) (
)
(
)
(
)
(
)
P Q
R Q
P Q
R Q
P
R Q
P R Q
P R
→
∧ →
⇔ ¬ ∨ ∧ ¬ ∨
⇔ ¬ ∧ ¬ ∨
⇔ ¬ ∨ ∨
⇔
∨ → Q
Hence proved.
Ì Exam ple 8.1.24: Prove that
¬
∧ → ¬ ∨ ¬ ∨
⇒ ¬ ∨
(
) (
(
)) (
).
P Q
P
P Q
P Q
¬ ∨ → ¬ ∨ ¬ ∨
⇒
∧ ∨ ¬ ∨ ¬ ∨
⇒
∧ ∨ ¬ ∨
⇒
(
)
(
(
))
(
) [
(
)]
(
) (
)
P Q
P
P Q
P Q
P
P Q
P Q
P Q
(
)
((
)
)
((
) (
)
(
(
)
P Q
P Q
P Q
P Q
P
P
Q
P Q
T Q
P
∧ ∨ ¬ ∨
⇒
∧ ∨ ¬ ∨
⇒
∨ ¬ ∧ ∨ ¬ ∨
⇒ ∧ ∨ ¬ )
(
)
∨
⇒
∨ ¬ ∨
⇒ ∨ ¬
⇒ ¬ ∨
Q
Q
P Q
Q
P
P Q
Hence proved.
Ì Exam ple 8.1.25: Show that S R
∨
is tautologically implied by
(
) (
) (
).
P Q
P
R
Q S
∨ ∧ →
∧ →
Solu tion
Assume that (
) (
) (
)
P Q
P
R
Q S
∨ ∧ →
∧ → has the truth value T.
(
), (
)
P Q P
R
∨
→ and (
)
Q S
→ all have truth value T. As the truth value of
P Q
∨ is T, either P has Truth value T or Q have truth value T.
Suppose P has the value T. As P
R
→ has truth value T, R should have
truth value T. On the other hand suppose Q has the truth value T. As Q S
→ has
truth value T, S should have truth value T. Thus either R has truth value T or S
has truth value T, i.e., R ∨ S has truth value T.
Therefore (
) (
) (
)
P Q
P
R
Q S
∨ ∧ →
∧ →
is tautologically implied by
S R
∨ .
8.2 LOGICAL INFERENCE
Rule P : A premise may be introduced at any point in the derivation.
Rule T : A formula S may be introduced in a derivation if S is tautologically
implied by any one or more of the preceding formula in the
derivation.
Prop o si tions and Pred i cates
265