⇔ ∧ ¬ ∨ ∧ ∨ ∧
⇔
∨ ∨ ∧
⇔
∧ ∨ ∨ ¬
(
) (
) (
)
(
)
(
)
T
Q
P T
P R
Q P P R
P R P
Q
7
(Answer)
Ì Exam ple 8.5.5: Obtain a Disjunctive Normal Form of
P
P Q
Q
P
→
→
∧ ¬ ¬ ∨ ¬
((
)
(
))
Solu tion
P
P Q
Q
P
P
P Q
Q P
P
P Q
Q
→
→
∧ ¬ ¬ ∨ ¬
⇔ → ¬ ∨ ∧ ∧
⇔ ¬ ∨ ¬ ∨ ∧
((
)
(
))
[(
) (
)]
[(
) ( ∧
⇔ ¬ ∨ ¬ ∨
∧ ¬ ∨ ∧
⇔ ¬ ∨ ¬ ∨
∧ ¬ ∨ ∧
P
P
P Q
P Q P
P
P Q
P Q
F
)]
[
(
)] [
(
)]
[
(
)] [(
) ( )]
[(
) (
)] [(
)]
[
(
)] (
)
[(
⇔ ¬ ∨ ¬ ∨ ¬ ∨
∧ ¬ ∨
⇔ ¬ ∨ ¬ ∨
∧ ¬ ∨
⇔
P
P
P Q
P Q
P
P Q
P Q
¬ ∨ ¬ ∨ ¬ ∨
∧ ¬ ∨
⇔ ¬ ∨ ∧ ¬ ∨
⇔ ¬ ∨
P
P
P Q
P Q
P Q
P Q
P Q
) (
)] (
)
[
] [
]
(Answer)
Ì Exam ple 8.5.6: Obtain the Conjungtive Normal Form of
¬ ∨
↔ ( ∧
(
)
)
P Q
P Q
Solu tion
¬ ∨
↔ ( ∧
⇔ ¬ ∨ ∧ ∧
∨ ¬ ¬ ∨
∧ ¬ ∧
⇔ ¬
(
)
)
[ (
) (
)] [ ( (
))
(
)]
[(
P Q
P Q
P Q
P Q
P Q
P Q
P
Q
P Q
P Q
P
Q
P
P Q
Q
P Q
∧ ¬ ∧ ∧
∨
∨ ∧ ¬ ∨ ¬
⇔
∧ ¬ ∧ ∧ ¬ ∨ ∨ ∧ ¬
) (
)] [(
) (
)]
[(
) (
) ( P
Q
P Q
P
Q
∨ ¬
⇔
∨ ∧ ¬ ∨ ¬
)]
(
) (
)
(Answer)
GLOSSARY
Logic: Discipline which deals with methods of reasoning.
Proposition (statement): Any declarative sentence which is true (T) or false
(F).
Truth Value: T or F are the truth values of a statement.
Liar’s Paradox: This statement is false.
Connectives: AND, NOT, OR, ......
Negation: ~ P or ¬ P (NOT P)
Conjunction: AND (
)
p q
∧
Disjunction: OR (
)
p q
∨
292
Theory of Automata, Formal Languages and Computation