(b) ¬ ⇒
⇒
(
)
P Q
P
P
Q
P Q
⇒
¬ ⇒
(
)
P Q
¬ ⇒
⇒
(
)
P Q
P
T
T
T
F
T
T
F
F
T
T
F
T
T
F
T
F
F
T
F
T
∴ It is a tautology.
Hence proved.
(c) ¬ ∧
⇒
⇒ ¬
Q P Q
P
(
)
P Q ¬ Q P Q
⇒
¬ P
¬ ∧
⇒
Q P Q
(
) ¬ ∧
⇒
⇒ ¬
Q P
Q
P
(
)
T T
F
T
F
F
T
T F
T
F
F
F
T
F T
F
T
T
F
T
F F
T
T
T
T
T
∴ It is a tautology.
Hence proved.
Ì Exam ple 8.1.22: Show that
((
)
(
(
))) (
) (
)
P Q
P
Q
R
P
Q
P
R
∨ ∧ ¬ ¬ ∧ ¬ ∨ ¬
∨ ¬ ∧ ¬ ∨ ¬ ∧ ¬
is a tautology.
Solu tion
((
)
(
(
))) (
) (
)
((
)
(
P Q
P
Q
R
P
Q
P
R
P Q
P
∨ ∧ ¬ ∧ ¬ ∨ ¬
∨ ¬ ∧ ¬ ∨ ¬ ∧ ¬
⇔
∨ ∧ ¬ ¬ ∧ ¬ (
))
(
) ( (
))
((
) (
(
))
(
)
(
Q R
P Q
P R
P Q
P Q R
P Q
P
∧
∨ ¬ ∨ ∨ ¬ ∨
⇔
∨ ∧ ∨ ∧
∨ ¬ ∨ ∨ ¬ ∨
⇔
∨ ∧
∨ ∨ ¬
∨ ∧ ∨
⇔
∨ ∧ ∨
∨ ¬
R
P Q
P Q
P Q
P R
P Q
P R
P
)
[(
) ((
)
[(
) (
)]
[(
) (
)]
( ∨ ∧
⇔ ∨ ∧
∨ ¬ ∨ ∧
⇔
(
))
[
(
)]
[
(
)]
Q R
P Q R
P Q R
T
Hence the given formula is a tautology.
Ì Exam ple 8.1.23: Show that (
) (
)
P Q
R Q
→
∧ →
and (
)
P R
Q
∨ → are
equivalent formulae.
264
Theory of Automata, Formal Languages and Computation