Solu tion
(a) P
P
∨ ¬ .
P
¬ P
P
P
∨ ¬
T
F
T
F
T
T
All truth values are True.
Therefore, it is a “Tautology”.
(b) P
P
∧ ¬
P
¬ P
P
P
∧ ¬
T
F
F
F
T
F
All truth values are False.
Therefore, it is a “contradiction”.
(c) P
P
⇒ ¬ ¬
(
)
P
¬ P
¬ ¬
(
)
P
P
P
⇒ ¬ ¬
(
)
T
F
T
T
F
T
F
T
All truth values are “True”.
Therefore, it is a “Tautology”.
(d) ¬ ∧
⇔ ¬ ∨ ¬
(
)
(
)
P Q
P
Q
P Q P Q
∧
¬ ∧
(
)
P Q ¬ P ¬ Q ¬ ∨ ¬
P
Q ¬ ∧
⇔
¬ ∨ ¬
(
)
(
)
P Q
P
Q
T T
T
F
F
F
F
T
T F
F
T
F
T
T
T
F T
F
T
T
F
T
T
F F
F
T
T
T
T
T
All truth values are “True”.
Therefore, it is a “Tautology”.
Ì Exam ple 8.1.12: Establish whether the following propositions are
tautologies, contingencies or contradictions.
256
Theory of Automata, Formal Languages and Computation