Ì Exam ple 8.1.15: State the converse and contrapositive of the following
statements:
(a) If it rains, I am not going.
(b) I will stay only if you go.
(c) If you get 8 pounds, you can bake the cake.
(d) I can’t complete the task if I don’t get more help.
Solu tion
(a) Converse: If I don’t go, then it rains.
Contrapositive: If I go, then it does not rain.
(b) Converse: If you go then I will stay
Contrapositive: If you go I will not stay
(c) Converse: If you can bake the cake you get 8 pounds.
Contrapositive: If you cannot bake the cake you don’t get 8
pounds.
(d) Converse: I don’t get more help if I can’t complete the task.
Contrapositive: I can complete the the task if I get more help.
Ì Exam ple 8.1.16: For each of the following expressions, use identities
to find equivalent expressions which use only ∧ and ¬ and are as simple as
possible.
(a) P Q
R
∨ ∨ ¬
(b) P
Q R
P
∨ ¬ ∧
⇒
[(
)
]
(c) P
Q P
⇒
⇒
(
)
Solu tion
(a) P Q
R
P
Q
R
P
Q R
P
Q R
∨ ∨ ¬ ⇔ ¬ ¬ ∧ ¬ ∨ ¬
⇔ ¬ ¬ ∧ ¬ ∧
⇔ ¬ ¬ ∧ ¬ ∧
(
)
((
)
)
(
)
(b) P
Q R
P
Q R
P
P
Q R P
∨ ¬ ∧
⇒ ⇔ ¬ ¬ ∧ ¬ ¬ ∧
⇒
⇔ ¬ ¬ ∧ ¬ ¬ ¬ ∧ ∨
⇔ ¬
[(
) ]
(
[(
)
])
(
( (
)
)]
(
((
)
)]
¬ ∧ ¬ ∧ ∧ ¬
P
Q R
P
(c) P
Q P
P
Q P
P
Q P
P P
Q
Q
⇒
⇒
⇔ ⇒ ¬ ∨
⇔ ¬ ∨ ¬ ∨
⇔ ¬ ∨ ∨ ¬
⇔ ∨ ¬
⇔
(
)
(
)
(
)
(
)
1
1
Ì Exam ple 8.1.17: For each of the following expressions, use identities
to find equivalent expressions which use only ∨ and ¬ and are as simple as
possible.
260
Theory of Automata, Formal Languages and Computation