0.3 Discrete structures logic  (Page 12/23)

Thus we need more powerful logic to deal with these and other problems. The predicate logic is one of such logic and it addresses these issues among others.

Well formed formula (wff) of predicate logic

Predicate

To cope with deficiencies of propositional logic we introduce two new features: predicates and quantifiers.

A predicate is a verb phrase template that describes a property of objects, or a relationship among objects represented by the variables.

For example, the sentences "The car Tom is driving is blue", "The sky is blue", and "The cover of this book is blue" come from the template "is blue" by placing an appropriate noun/noun phrase in front of it. The phrase "is blue" is a predicate and it describes the property of being blue. Predicates are often given a name. For example any of "is_blue", "Blue" or "B" can be used to represent the predicate "is blue" among others. If we adopt B as the name for the predicate "is_blue", sentences that assert an object is blue can be represented as "B(x)", where x represents an arbitrary object. B(x) reads as "x is blue".

Similarly the sentences "John gives the book to Mary", "Jim gives a loaf of bread to Tom", and "Jane gives a lecture to Mary" are obtained by substituting an appropriate object for variables x, y, and z in the sentence "x gives y to z". The template "... gives ... to ..." is a predicate and it describes a relationship among three objects. This predicate can be represented by Give( x, y, z ) or G( x, y, z ), for example.

Note: The sentence "John gives the book to Mary" can also be represented by another predicate such as "gives a book to". Thus if we use B( x, y ) to denote this predicate, "John gives the book to Mary" becomes B( John, Mary ). In that case, the other sentences, "Jim gives a loaf of bread to Tom", and "Jane gives a lecture to Mary", must be expressed with other predicates.

Quantification --- forming propositions from predicates

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) can be made a proposition by applying one of the following two operations to each of its variables:

1. assign a value to the variable

2. 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 P(x), by using quantifiers on variables. There are two types of quantifiers: universal quantifier and existential quantifier.

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.