PREDICATES AND QUANTIFIERS

PREDICATES AND QUANTIFIERS

INTRODUCTION TO PREDICATES

          Predicate is an open statement or sentence that contains a finite numbers of variables. Predicates become statement when specifies values are substituted for the variables by certain allowable choices of value.

Examples :

 x + y= z is written as:
Sum(x,y,z)
This stands for the predicate x + y = z
You may have a predicate like this:
M(x,y)
which could stand for x is married to y

Again, we do not have a unique value, the value will depend on the values given to the variables x and y.

In Programming we often come across statements like this:
If x > 3
then y = 5
else y = 1
x > 3 is the predicate.

When the program is executed, x will have a specific value and so we can find out if that statement becomes true or false and variable y will be set accordingly.

In general you have predicates in the form of:
P(x) – this is a unary predicate (has one variable)
P(x,y) – this is a binary predicate (has two variables)
P(x1, x2, x…….., xn) – this is an n-ary or n-place predicate – (has n individual variables in a predicate)

You have to choose the values for the variables – these can be from a set of humans -a specific human, a set of places or a place, a set of integers or an integer, a set of real numbers or a real number, negative numbers etc, etc, etc and so on.

QUANTIFIERS

Definition : A quantifier is a logical symbol which makes an assertion about the set of values which make one or more formulas true. This is an exceedingly general concept; the vast majority of mathematics is done with the two standard quantifiers,   (for all) and   (there exists).

The universal quantifier   takes a variable x and a formula, which may or may not contain x , and asserts that the formula holds for any value of x (the value as being taken from some given universe A ).

 Example:

Here is a (true) statement about real numbers:

Every real number is either rational or irrational.

I could try to translate the statement as follows: Let

P = "x is a real number"

Q = "x is rational"

R = "x is irrational"

The statement can be expressed as the implication   .

The simple statements contain a variable x, and you might find it difficult to translate these statements without using a variable (or, what is the same thing, a pronoun). The reason is that the original statement is meant to apply to every element of a set --- in this case, every element of the set of real numbers.

You can see that I'm cheating in making my translation: "x is a real number" is not a single statement about a uniquely specified object "x". It is a different kind of statement than "  is a real number", which talks about a specific real number   .

I can use quantifiers to translate statements like these so as to capture this meaning. Mathematicians use two quantifiers:

•  , the universal quantifier, which is read "for all", "for every", or "for each".

•  , the existential quantifier, which is read "there is" or "there exists".

Here are some examples which show how they're used.

Example. Let   mean "x likes pizza". Then:

 means "Everyone likes pizza".

 means "Someone likes pizza".

Note that if "Someone likes pizza" is true, it may be true that "Everyone likes pizza". On the other hand, if "Everyone likes pizza" --- and assuming that the set of people is nonempty --- it must be true that "Someone likes pizza".

 means "Not everyone likes pizza".

 means "No one likes pizza".

Again, if "Not everyone likes pizza", it may be true that "No one likes pizza". On the other hand, if "No one likes pizza", it {\it must} be true that "Not everyone likes pizza".

Note also that if `Not everyone likes pizza", it may be true that "Someone likes pizza".

Example quantifier using in reality.

  Existential Quantifier

1      “Some student in this class has visited Mexico”

This statement is an existential quantification. Namely

∃xQ(x). We use it when not every student has visited Mexico.

Universal Quantifier

1     “Every student in your class has taken a course in calculus.”

This statement is a universal quantification.  Namely,

∀xP(x). We use it because it stated that every it means all the student.


REFERENCE : 

http://jasoninclass.wordpress.com/category/predicate-logic/
www.slidesshare.net/uyar/predicates-and-sets
www.comp.uark.edu/~lanzani/2603-NOTES/2.1-website.pdf