(b) ℑ ∨
⇒ ∨ ℑ
!
( , )
!
( , )
y
P x y
y P x y
x
x
xy = 0
LHS: (i) y
y
=
=
0
0
RHS: ( )
, , ,
x
x
0 0
1 2 3
=
=
K
(ii) y
y
=
=
0
0
P x y
xy
( , ) is = 0.
Ì Exam ple 8.3.5: Specify the universe of discourse for which the
following propositions are true. Try to choose the universe to be as large a
subset of integers as possible.
(a) ∨
>
x x
[
]
10
(b) ∨ =
[
]
x 3
(c) ∨ ℑ
+ =
x
y x y
[
]
436
(d) ℑ ∨
+ <
y
x x y
[
].
0
Solu tion
(a) Universe of discourse: “All Integers greater than 10”.
(b) Universe of discourse: “The Universe has 3 only”.
(c) Universe of discourse: I
(d) Universe of discourse: I
Ì Exam ple 8.3.6: Let the universe of discourse consists of the integers 0
and 1. Find finite disjunctions and conjunctions of propositions which do
not use quantifiers and which are equivalent to the following:
(a) ∨ x P x
( , )
0
(b) ∨ ∨
x
y P x y
( , )
(c) ∨ ℑ
x
y P x y
( , )
(d) ℑ ∨
x
y P x y
( , )
(e) ℑ ℑ
y x P x y
( , )
Solu tion
U = 0 1
, .
(a) ∨
=
∧
x P x P
( , )
( , ) ( , ).
0
0 0
01
(b) ∨ ∨
=
∧
∧
∧
x
y P x y P
P
P
P
( , )
( , )
( , )
( , )
( , )
0 0
0 1
1 0
1 1
(c) ∨ ℑ
=
∨
∧
∨
x
y P x y
P
P
P
P
( , ) [ ( , )
( , )] [ ( , )
( , )]
0 0
0 1
1 0
1 1
(d) ℑ ∨
=
∧
∨
∧
x
y P x y
P
P
P
P
( , ) [ ( , )
( , )] [ ( , )
( , )]
0 0
1 0
0 1
1 1
(e) ℑ ℑ
=
∨
∨
∨
y x P x y P
P
P
P
( , )
( , )
( , )
( , )
( , ).
0 0
0 1
1 0
1 1
280
Theory of Automata, Formal Languages and Computation