(a) (
)
P Q
P
∧ ∧ ¬
(b) [
(
)]
P
Q
R
P Q
⇒ ∨ ¬
∧ ¬ ∧ .
Solu tion
(a) (
)
[ (
)
]
[
]
P Q
P
P Q P
P
Q P
∧ ∧ ¬ ⇔ ¬ ¬ ∧ ∨
⇔ ¬ ¬ ∨ ¬ ∨
(b) [
(
)]
[
(
)] (
)
(
)
P
Q
R
P Q
P Q
R
P Q
P Q
R
P
⇒
∨ ¬
∧ ¬ ∧
⇔ ¬ ∨ ∨ ¬
∧ ¬ ∧
⇔ ¬ ∨ ∨ ¬ ∧ ¬ ∧
⇔ ¬ ∧ ¬ ∧ ∨ ∧ ¬ ∧
∨ ¬ ∧ ¬ ∧
⇔ ¬ ∧ ∨ ∧ ¬ ∨
Q
P
P Q
Q
P Q
R
P Q
P Q
Q
P
(
) (
(
)) (
(
))
(
) (
) (
)
[(
)(
)]
(
).
¬ ∧ ∧ ¬ ∨
∧ ¬
∧ ¬
⇔ ¬ ∨ ¬
P Q
R
Q
P
R
P
Q
1
Ì Exam ple 8.1.18: Establish the following tautologies by simplifying the
left side to the form of the right side:
(a) [(
)
)
]
P Q
P
∧
⇒
⇔1
(b) ¬ ¬ ∨
⇒ ¬
⇔
( (
)
)
P Q
P
0
(c) [(
) (
)]
P
P
P
P
⇒ ¬ ∧ ¬ ⇒
⇔ 0
Solu tion
(a) [(
)
]
(
)
(
)
P Q
P
P Q P
P
Q P
P
P
Q
Q
∧
⇒ ⇔ ¬ ∧ ∨
⇔ ¬ ∨ ¬ ∨
⇔
∨ ¬ ∨ ¬
⇔ ∨ ¬
⇔
1
1
(b) ¬ ¬ ∨
⇒ ¬
⇔ ¬
∨ ∨ ¬
⇔ ¬ ∨ ¬ ∨
⇔ ¬ ∨
⇔ ¬
⇔
( (
)
[(
)
]
[
)
]
[
]
[ ]
P Q
P
P Q
P
P
P Q
Q
1
1
0
(c) [(
) (
)]
[(
) (
)]
P
P
P
P
P
P
P P
P P
⇒ ¬ ∧ ¬ ⇒
⇔ ¬ ∨ ¬ ∧ ∨
⇔ ¬ ∧
⇔ 0
Ì Exam ple 8.1.19: Using the truth table of ⇒, relate the following
assertion to the logical operator ⇒: “If you start with a false assumption,
you can prove anything you like”.
Prop o si tions and Pred i cates
261