Solu tion
(i) ∨
⇔ ¬ ¬ ∨
⇔ ¬ ℑ ¬
⇔ ¬ ℑ ¬
x
x
x
x
P x
P x
P x
P x
( )
(
( ))
(
( ))
( ).
(ii) ℑ
⇔ ¬ ¬ ℑ
⇔ ¬ ∨ ¬
⇔ ¬ ∨ ¬
x
x
x
x
P x
P x
P x
P x
( )
(
( ))
(
( ))
( ).
Ì Exam ple 8.4.5: Find an assertion which is logically equivalent to
ℑ! ( )
xP x but which uses only the quantifiers ∨ and ℑ together with the
predicate for equality and logical operators.
Solu tion
ℑ
⇔ ℑ
∧ ∨
⇒ =
! ( )
[ ( )
[ ( )
]
xP x
P x
P y
y x
x
y
Ì Exam ple 8.4.6: Find whether the assertion
∨
⇒
⇒ ∨
⇒ ∨
x
x
x
P x
Q x
P x
Q x
[ ( )
( )] [
( )
( )]
is true or not.
Solu tion:
P(x)
Q(x)
∨
⇒
x P x
Q x
( )
( )
∨
⇒ ∨
x
x
P x
Q x
( )
( )
T
T
T
T
T
T
T
T
T
F
F
F
T
F
F
F
F
T
T
T
F
T
T
T
F
F
T
T
F
F
T
T
The assertion is “TRUE”.
Ì Exam ple 8.4.7: For a universe containing only the elements 0 and 1,
expand ℑ
∧
x P x Q x
[ ( )
( )] and [
( )
( )]
ℑ
∧ ℑ
x
x
P x
Q x into propositions
involving P
P
( ), ( ),
0
1 K etc., and without quantifiers. Rearrange the
terms of the expansion to show that
286
Theory of Automata, Formal Languages and Computation