Quantifiers And Logical Operators
QUANTIFIERS AND LOGICAL OPERATORS: The transcription of mathematical statements involves predicates, quantifiers and logical operators. Assume that “Universe of discourse” is I and let
- E (x), x –even
- O (x), x–odd
- P (x), x–prime
- N (x), x non-negative.
(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.
(iv) If an integer is not odd, then its even.
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”
(ii) “If xy = x for every y, then 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:
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
which is difficult to interpret.
The equivalent form
is more tractable and can easily be shown to be true for the nonnegative integers by choosing x > y.