Quantification --- Forming Propositions from Predicates

- universe
- universal quantifier
- existential quantifier
- free variable
- bound variable
- scope of quantifier
- order of quantifiers

A predicate with variables is not a proposition. For example,
the statement *x > 1* with variable *x* over the universe of real numbers
is neither true nor false since we don't know what *x* is. It can be true
or false depending on the value of *x*.

For *x > 1* to be a proposition either we substitute a specific number for *x*
or change it to something like "There is a number *x* for which *x > 1* holds",
or "For every number *x*, *x > 1* holds".

More generally, a predicate with variables
(called an
**atomic formula****proposition** by applying one of the following two operations to each of its variables:

- assign a value to the variable
- quantify the variable using a
**quantifier**(see below).

For example, *x > 1* becomes *3 > 1* if *3* is assigned to *x*,
and it becomes a true statement, hence a proposition.

In general, a quantification is performed on formulas of predicate logic
(called
wff
),
such as ** x > 1** or

The **universal quantifier** turns, for example, the statement *x > 1*
to "for every object *x*
in the universe, *x > 1*", which is expressed as
"*x* * x > 1*".
This new statement is true or false in the universe of discourse. Hence it is a proposition once the universe is specified.

Similarly the **existential quantifier** turns, for example, the statement *x > 1*
to "for some
object *x* in the universe, *x > 1*", which is expressed as "
*x x > 1*." Again, it is true or false in the universe of discourse, and hence
it is a proposition once the universe is specified.

The Universal Quantifier

The expression:*P(x)*is the predicate denoting:, and*x*has wheels- the universe of discourse is only populated by cars.

If all the elements in the universe of discourse can be listed then the universal quantification

For example, in the above example of

The Existential Quantifier

The expression:-
*P(x)*is the predicate meaning:,*x*loves you - The universe of discourse contains (but is not limited to) all living creatures.

**Existential Quantifier** and **Connective OR**

If all the elements in the universe of discourse can be listed, then the existential quantification
*xP(x)* is equivalent to the disjunction:
** P(x_{1}) P(x_{2})
P(x_{3})
... P(x_{n})**.

For example, in the above example of

An appearance of a variable in a

For example, in

How to read quantified formulas

When reading quantified formulas in English,For example, let the universe be the set of airplanes and let

Order of Application of Quantifiers

When more than one variables are quantified in a wff such asThe positions of the same type of quantifiers can be switched without affecting the truth value as long as there are no quantifiers of the other type between the ones to be interchanged.

For example

However, the positions of different types of quantifiers can
**not** be switched.

For example
** x y
P( x, y )** is

Click Yes or No , then Submit. There are two sets of questions.