(a) For every x and y, there is a z such that x + y = z.
(b) No x is less than 0.
(c) For all x, x + 0 = x.
(d) For all x, x – y = y for all y.
(e) There is an x such that x y y
⋅ = for all y.
Solu tion:
S x y z x y z
P x y z x y z
L x y x y
( , , ) :
( , , ) :
( , ) :
+ =
− =
<
Universe of Discourse : N.
(a) ∨ ∨ ℑ
+ =
x
y
z x y z
(
) i.e. ∨ ∨ ℑ ≤
x
y
z
x y z
( , , )
(b) ∨ ¬
¬ ℑ
x
x
L x
L x
(
( , ))
[ ( , )]
0
0
or
(c) ∨ x S x x
( , , )
0
(d) ∨ ∨
x
y P x y x
( , , )
(e) ℑ ∨
x
y P x y y
( , , )
Ì Exam ple 8.3.2: Show that ℑ ℑ
x y P x y
( , ) and ℑ ℑ
y x P x y
( , ) are
equivalent by expanding the expressions into infinite disjunctions.
Proof: To prove: ℑ ℑ
= ℑ ℑ
x y
y x
P x y
P x y
( , )
( , ).
ℑ ℑ
= ℑ
∨ ℑ
∨ ℑ
=
x y
y
y
y
P x y
P y
P y
P y
P
( , ) [
( , )] [
( , )] [
( , )]
[ (
0
1
2
0
KK
, )
( , )
( , )
]
[ ( , )
( , )
( , )
]
[ (
0
0 1
0 2
10
1 1
12
2
∨
∨
∨
∨
∨
∨
P
P
P
P
P
P
KK
KK
, )
( , )
( , )
]
[ ( , )
( , )
( , )
]
0
2 1
2 2
0 0
1 0
2 0
∨
∨
∨
=
∨
∨
∨
∨
P
P
P
P
P
KK
KK
KK
[ ( , )
( , )
( , )
]
[ ( , )
( , )
( , )
P
P
P
P
P
P
0 1
1 1
2 1
0 2
1 2
2 2
∨
∨
∨
∨
∨
∨
∨
KK
KK ]
[
( , )] [
( , )] [
( , )]
( ,
∨
= ℑ
∨ ℑ
∨ ℑ
∨
= ℑ ℑ
KK
KK
x
x
x
y x
P x
P x
P x
P x y
0
1
2
).
Hence Proved.
¨
Ì Exam ple 8.3.3: Determine which of the following propositions are true
if the universe is the set of integers I and ⋅ denotes the operation of
multiplication.
(a) ∨ ℑ
⋅ =
x
y x y
[
]
0
(b) ∨ ℑ
⋅ =
x
y x y
! [
]
1
278
Theory of Automata, Formal Languages and Computation