(i) Every integer is even or odd.
∨
∨
x E x O x
[ ( )
( )]
(ii) The only even prime is two
∨
∧
⇒ =
x E x P x
x
[ ( )
( )
]
2
(iii) Not all primes are odd.
¬ ∨
⇒
ℑ
∧ ¬
x
x
P x
O x
P x
O x
[ ( )
( )], [ ( )
( )].
(iv) If an integer is not odd, then its even.
∨ ¬
⇒
x
O x
E x
[
( )
( )]
The quantifiers may go anywhere in the transcription of mathematical
statements.
Let P x y z
( , , ) denote “xy z
= ” for the universe of integers. Informal
statements of propositions frequently omit the universal quantification of
individual variables.
(i) “If x = 0, then xy = x for all vlaues of y”
∨
= ⇒ ∨
x
y
x
P x y x
[
( , , )]
0
(ii) “If xy = x for every y, then x = 0”.
∨ ∨
⇒ =
x
y P x y x
x
[
( , , )
]
0
Propagation of negations through quantifier sequences is useful in
constructing proofs and counterexamples.
As an example, consider there exists a z such that x + z = y, for every pair of
integers x and y. This is stated as:
∨ ∨ ℑ
+ =
x
y
z x z y
[
]
This is true for universe of integers I, but not true for the natural numbers
N. We establish the falsity for the universe N by showing that its negation is
true.
The negation has the form
¬ ∨ ∨ ℑ
+ =
x
y
z x z y
[
]
which is difficult to interpret.
The equivalent form
ℑ ℑ ∨ ¬ + =
ℑ ℑ ∨
+ ≠
x y
y
x y
z
x z y
x z y
[
],
[
]
or
is more tractable and can easily be shown to be true for the nonnegative
integers by choosing x > y.
282
Theory of Automata, Formal Languages and Computation