Consider the statement: "If Paul is a frenchman, then Paul is rich". Very common a statement in plain english which explains many prejudices that some minorities ,for example, suffer from (not this one of course). This statement is different from previous logical sentences we learned so far. Indeed, this sentence may be true or false depending on Paul. Therefore, one may ask the following natural question:
- Is there any frenchman under the name Paul?
So this statement will not make sense if the answer to this question is: NO. This suggests to rewrite the above sentence as: " If P(x), then Q(x)", where
-
- x represents "frenchman"
-
- P(x) states that x's name is Paul
-
- Q(x) is the sentence "x is rich".
Therefore, the above sentence has a variable, namely x. We call it open sentence or predicate. In general, we will write an open sentence as 
, where 
are the associated variables. For example, 
, is an open sentence with two variables. It is therefore natural to associate to an open sentence a domain (also called universe) which is the set where the variables live. For the above example, the universe is the set of all frenchmen. For the open sentence , the universe is the set of pairs (x,y), where x and y are real numbers. Let us go back to Paul's example. Consider the universe 
, which is the set of all frenchmen. We have three cases,
- 1.
- no frenchman under the name Paul is rich;
- 2.
- there exists a least one frenchman under the name Paul who is rich;
- 3.
- any frenchman under the name Paul is rich.
The above cases have more to do with the truthfulness of the open sentence "If P(x) then Q(x)". They also suggest the introduction of two new logical objects which we call Quantifiers,
-
-
means "for all" or "for every";
-
-
means "there exists".
is called the universal quantifier while is called the existential quantifier.
Definition. Consider the open sentence P(x), where x belongs to some universe, then the set of all the x which makes P(x) true is called the truth set. The sentence " 
" is true precisely when the truth set for P(x) is the entire universe. The sentence " 
" is true precisely when the truth set for P(x) is nonempty.
Example. Let the universe be all real numbers.
-
-
is true because the truth set of 
contains 
for example.
-
-
is false because the truth set of 
is empty.
-
-
is false. The truth set of (|x| > 0) contains allmost all real numbers but does not contain 0.
A sentence involving quantifiers is called a quantified sentence. Another exercise is to rewrite a statement using quantifiers and logical terms.
Example. The sentence:
"For every odd number x less than 6, 
is prime"
means:
"if x is odd, and less than 5, then is prime"
We can rewrite the above sentence as:
Example. Let N denote the set of natural numbers and R denote the set of real numbers. Consider the statement:
"For every natural number, there is a real number greater than the given natural number"
may be rewritten symbolically as:
Two logical forms of quantified sentences are said to be equivalent if the truth of one implies the truth of the other, and conversely, for every possible meaning of the open sentences in every universe.
Theorem. If P(x) is an open sentence with variable x, then
-
-
is equivalent to 
;
-
-
is equivalent to 
.
Example. Find the negation of the quantified sentence: "All primes are odd", where the universe is the set of natural numbers.
Answer. The sentence: "All primes are odd", may rewritten symbolically as
First we use the previous sections, to rewrite this sentence in the equivalent form
The negation is
This is equivalent (using the above Theorem)
Thus, its negation is:
"There exists a number that is prime and not odd (is even)"
Section
Mohamed Khamsi
Wed Aug 27 17:17:43 MDT 1997