42. Prove that the statements
¬ ℑ ∨
x
y P x y
( , ) and ∨ ℑ ¬
x
y
P x y
( , )
have the same truth table.
43. State the truth values of the following:
(a) ℑ
→ ℑ
! ( )
( )
xP x
P x
x
(b) ∨
→ ℑ
x P x
x P x
( )
! ( )
(c) ℑ ¬
→ ¬ ∨
!
( )
( )
P x
P x
x
44. Show that ∨
∨ ∨
x
x
P x
Q x
( )
( ) and ∨
∨
x P x Q x
( ( )
( )) are not logically
equivalent.
45. Show that ∨
∨ ℑ
x
x
P x
Q x
( )
( ) and ∨ ℑ
∨
x
y P x Q y
( ( )
( )) are equivalent.
46. Obtain the principal disjunctive normal form and principal conjunctive
normal form of
P
Q
↔ .
47. Obtain the PDNF of the following
(a) ¬ ∨
P Q
(b) (
) (
) (
).
P Q
P Q
Q R
∧ ∨ ¬ ∧ ∨ ∧
48. Obtain the disjunctive normal form of
P
P
Q
Q R
∨ ¬ →
∨ ¬ →
(
(
(
)))
49. Derive the disjunctive normal form of
P
P Q
Q R
→
→
∧ ¬ →
((
) (
)))
50. Obtain the conjunctive normal form of
(
) (
)
¬ →
∧
↔
P
R
Q
R
51. State whether the following argument is valid or not. Give proof if it is
valid. Otherwise give counter example.
Babies are illogical.
Nobody is despised, who can manage crocodiles.
Illogical people are despised.
Therefore babies cannot manage crocodiles.
52. If the colonel was out of the room when the murder was committed, then
he could not have been right about the weapon used. Either the butler is
lying or he knows who the murderer was. If Lady Sharon was not the
murderer, then either colonel was in the room at the time or the butler is
lying. Either the butler knows who the murdered was or the colonel was
out of the room of the time of the murder. The policeman deduced that if
the colonel was right about the weapon, they Lady Sharon was the
murderer. Was he right?
298
Theory of Automata, Formal Languages and Computation