(g) p
q
r s
⇒ ⇔ ⇒
(
(
))
p q r
s
r s
⇒
q
r
s
⇔ ⇔
( ( ) ) p
q
r s
⇒ ⇒ ⇒
(
(
))
True
T T F F
T
T
T
Ì Exam ple 8.1.8: Construct the truth table for
(
) (
).
¬ ∨ ∧ ¬ ∨
p q
q p
Solu tion
p
q ¬ p ¬ q ¬ ∨
p q ¬ ∨
q p [(
) (
)
¬ ∨ ∧ ¬ ∨
p q
q p
T
T
F
F
T
T
T
T
F
F
T
F
T
F
F
T
T
F
T
F
F
F
F
T
T
T
T
T
Ì Exam ple 8.1.9: Determine the Truth Table for ¬ ¬ ∧ ¬
(
)
p
q .
p
q
¬ p
¬ q
¬ ∧ ¬
p
q
¬ ¬ ∧ ¬
(
)
p
q
T
T
F
F
F
T
T
F
F
T
F
T
F
T
T
F
F
T
F
F
T
T
T
F
Ì Exam ple 8.1.9: Using truth tables, show that if P
Q
⇔ is true, then
P Q
⇒ and Q P
⇒ are both true. Conversely, show that if P Q
⇒ and
Q P
⇒ are both true, then P
Q
⇔ is true.
Solu tion
P
Q
P
Q
⇔
P Q
⇒
Q P
⇒
T
T
T
T
T
—T
F
F
F
T
F
T
F
T
F
F
F
T
T
T
—254
Theory of Automata, Formal Languages and Computation