Course:CPSC522/Predicate Calculus

Title

Predicate calculus is a formalization of logic that improves over propositional logic by allowing reasoning about elements of domains as well as their properties and relationships between them

Note to critiquers: the content here has been prepared solely by the collaborators. While constructive feedback is still welcomed, please take these circumstances into account for grading purposes.

Principal Author: Wenyi Wang
Collaborators: Jordon Johnson and Tian Qi (Ricky) Chen

Abstract

This page provides an introduction to the syntactical aspects of predicate calculus that improve upon propositional logic: domains, predicates, variables, instantiation, and quantifiers. It also discusses the idea of quantifier scope and its effects on instantiation.

Builds on

Predicate calculus builds on the logical forms of propositional logic to allow reasoning about individuals, objects, and their interactions.

More general than

Logic programming languages, such as Prolog, are based on the principles of predicate calculus.

Content

While propositional logic gives us logical connectives (conjunction, implication, etc.), it deals with statements as black boxes having truth values. For example, let $P$ represent the statement "John has a dog." There are (at least) two significant limitations with this representation:

• It would be very cumbersome to have different symbols to represent similar statements for every other person who may or may not have a dog;
• There is no way to relate $P$ to other statements as being about John or his dog.

It is desirable to be able to dig deeper and decompose the statements themselves in order to analyze them and perform more detailed reasoning about them. The syntax of predicate calculus incorporates propositional logic and introduces a number of concepts that facilitate these goals. For example, the logic programming language Prolog uses the principles of predicate calculus to perform automated reasoning from a query, given a knowledge base and set of rules.

Domains

A domain is the set of all things making up a "universe" about which we would like to reason. For example, we may wish to reason about animals, people, numbers, or data structures.

Like other kinds of sets, domains have elements, often called individuals or objects. Valid domains must not be empty, since there is no point in reasoning about something that does not exist. We can represent specific individuals using constants, which are identifiers (names, values, etc.) that uniquely identify the individual in the domain. An example of a simple domain would be the set of colours in a rainbow, which we can call $B$; it traditionally has seven elements, and we can assign constants to those elements such as Red, Yellow, and Blue. We can also represent unspecified individuals in a set using variables.

Predicates

Predicates are used to allow reasoning about either the properties of individuals in the domain(s) or the relationships between those individuals. Predicates are structured as boolean functions with individuals as their arguments. For example, to represent whether an individual is a person, we can use the predicate isPerson(x); isPerson(AlbertEinstein) is true, while isPerson(Yellow) is false. We can also reason about relationships between individuals; for example, if we use the predicate square(x, y) to represent "x is the square of y," then square(25, 5) is true, and square(4, 3) is false.

Different predicates can take different numbers of arguments, as has already been shown. The number of arguments a predicate takes is called its arity; predicates with a single argument are unary, predicates with two are binary, and so on. Note that the order of arguments is important; while square(25, 5) is true, square(5, 25) is false. While only constant arguments have been shown in the examples so far, variable arguments are also permitted. Depending on the formalism being used, it may be permitted to have multiple predicates use the same name if they have different arity values (akin to function overloading in some programming languages).

Some mathematical operators (>, =, <, etc.) can be used as predicates, but infix notation is used for them; one would write 5 > 3 rather than >(5,3).

A predicate with arguments is called an atomic formula. Atomic formulas can be combined using logical operators and quantifiers; for example,

$isWoman(x)\rightarrow isPerson(x)$

is a formula consisting of the atomic formulas isWoman(x) and isPerson(x) connected by implication. Formulas (atomic and otherwise) can be given names; we can, for example, call the above formula $A$.

Note that an atomic formula with only constants as its arguments must be either true or false. An assignment is the assignment of truth values to all possible combinations of individuals in a predicate. For example, let us take a simple domain with individuals {5, -5, 25, 3}. An assignment of the predicate square(x,y) would be

x \ y	5	-5	25	3
5	0	0	0	0
-5	0	0	0	0
25	1	1	0	0
3	0	0	0	0

where true=1 and false=0.

Note that the assignment for this binary predicate is a 2-D array; assignments in finite domains can be represented by n-dimensional arrays for predicates of arity n.

Variables

The idea of variables is intuitively related to their use in mathematics, and rightly so. Variables allow us to reason with unspecified elements of a given domain or serve as placeholders when defining predicates. As in mathematics, they are often represented by lower-case letters at the end of the alphabet (eg. x, y, z); and they are permitted in the syntax anywhere constants can be used. You will hopefully have noticed that variables have been used while defining every predicate in this page. For example, take the predicate square(x,y); the x and y are variables that allow us to reason with unspecified numbers, or to determine a truth value for any specific constant numbers, such as 25 and 5.

Variables and constants are also collectively known as terms.

Instantiation

We may (and often do) want to use a term in place of a variable, whether it be a constant or (in some cases) another variable. For example, consider the formula defined earlier and named $A$. Suppose we wanted to apply the formula to a specific individual:

$isWoman(MarieCurie)\rightarrow isPerson(MarieCurie)$

Note that all of the occurrences of the variable in the formula have been replaced. In terms of $A$, replacing the variable with the desired term results in the following notation:

$S_{MarieCurie}^{x}A$

This instantiation of $A$ indicates that all occurrences of x in $A$ have been replaced with MarieCurie; and MarieCurie is then an instance of x.

Quantifiers

We may (and often do) want to reason about things that are always true (or not), as well as things that are sometimes true (or not); in predicate calculus, quantifiers allow us to do that.

The universal quantifier, $\forall$, is used in reference to every element in a domain. For example, if we wanted to say that every person owns a ferret (using the domain $W$ of people and predicate F(x)), we could represent it in this way:

$\forall x\in W,F(x)$

or, since our reasoning is all about a single domain,

$\forall xF(x)$

The universal quantifier is often associated with the English phrase "for all", and so the above notation reads as follows: "For all x, x owns a ferret."

The existential quantifier, $\exists$, is often associated with the phrase "there exists", and is used in reference to some subset of the domain. When the existential quantifier is used, no claim is made on how many elements of the domain are referenced; the only restriction placed on the number of elements in the subset is that it is non-zero. For example, suppose we wanted to state that there are people who own ferrets:

$\exists x\in W,F(x)$

or

$\exists xF(x)$

since we're only dealing with a single domain. This can read as follows: "There exists some x such that x owns a ferret." There is no claim made as to how many there are; only that at least one exists.

In both cases, every occurrence of x used within the scope of the quantifier is bound to it. The scope of a quantifier can be thought of as including the logical "unit" immediately to its right. To clarify, consider the following formula:

$\forall xP(x)\rightarrow Q(x)$

Since quantifiers have a higher operational precedence than logical connectives, the scope of the universal quantifier is simply $P(x)$, and the $x$ in $Q(x)$ can be thought of as a separate variable with the same name. In order to make the scope include the entire implication, we can use parentheses:

$\forall x(P(x)\rightarrow Q(x))$

Quantifiers can be nested within the same statement. For example, let us continue with the domain of people and make the statement "everybody likes somebody":

$\forall x\exists yL(x,y)$

where $L(x,y)$ represents "x likes y". Note that, when nesting different quantifiers as was done here, the order is important:

$\exists x\forall yL(x,y)$

is the representation of "there is someone that everyone likes," which has a different meaning from the previous statement.

Also note that the two quantifiers are related through negation. Consider the following statement:

$\neg \exists xP(x)$

This can read as "There does not exist an x such that P(x) is true." That being the case, then P(x) must be false for all x, and so an equivalent statement is

$\forall x\neg P(x)$

Bound vs Free Variables

A variable associated with a quantifier and within its scope is bound to that quantifier. Variables that are not bound are free. #Instantiation as described so far can only be performed on free variables. For example, let us use the formula $A$ that we defined earlier and apply a universal quantifier:

$\forall x(isWoman(x)\rightarrow isPerson(x))$

which can be read as "for all x, if x is a woman then x is a person" or "all women are people". All occurrences of x are bound. If we instantiate using MarieCurie as before, we get

$\forall MarieCurie(isWoman(MarieCurie)\rightarrow isPerson(MarieCurie))$

which is senseless, since quantifiers are applied to variables, not constants. If we leave the quantifier out of the instantiation, we get

$\forall x(isWoman(MarieCurie)\rightarrow isPerson(MarieCurie))$

which, rather than making our original statement apply to a specific individual, has changed the meaning of our original statement.

Instantiation over universal and existential quantifiers is possible, but the quantifier is removed from the new statement in the process.

Universal Instantiation

Consider the following statement about individuals in the domain of animals:

$\forall x(isDog(x)\rightarrow hasTail(x))$

Assume that the statement is true. The universal quantifier means that the formula $isDog(x)\rightarrow hasTail(x)$ applies to every individual in the domain; and if it is true for all of the individuals in the domain, then it must be true for any specified individual. Universal instantiation allows us to take all occurrences of a variable bound to a quantifier, drop the quantifier, and instantiate that variable using another variable or constant in the domain; for example:

$isDog(FidoTheDog)\rightarrow hasTail(FidoTheDog)$ (instantiated using a constant representing a dog named Fido)

$isDog(MufasaTheLion)\rightarrow hasTail(MufasaTheLion)$ (instantiated using a constant representing Mufasa from The Lion King)

$isDog(y)\rightarrow hasTail(y)$ (instantiated using a variable representing an unspecified animal)

Universal instantiation allows us to perform universal modus ponens

$\forall x(P(x)\rightarrow Q(x))$

$P(y)$

$\therefore Q(y)$

and universal modus tollens

$\forall x(P(x)\rightarrow Q(x))$

$\neg Q(y)$

$\therefore \neg P(y)$

Existential Instantiation and Generalization

Similar to universal instantiation, existential instantiation allows us to derive statements about individuals from statements using quantifiers. For example, suppose we had the statement "some people wear glasses" (in the domain of people, using G(x) to represent "x wears glasses"):

$\exists xG(x)$

Assuming the statement is true, there is at least one individual who wears glasses; thus we can instantiate the statement using a new variable (i.e. not yet used in our reasoning), such as c:

$G(c)$

We can reason in the other direction as well. If we know that there is a specific individual (let's use the constant StephenHawking) who wears glasses, then there must be at least one person who wears glasses; thus existential generalization allows us to do the following:

$G(StephenHawking)$

$\therefore \exists xG(x)$

Resolution

Resolutions are a specific type of implication that results from the conjunction of two complementary predicates. Two predicates are complements if one is the negation of the other. For example, a simple contradiction is a resolution of the form

$F(x),\neg F(x)\rightarrow False$

Where "," is used to denote a logical "and". That is, for any variable $x$, $F(x)$ and $\neg F(x)$ cannot be both true at the same time. More generally, a resolution may involve other predicates in a disjunction ("or").

$F(x)\lor G(x),\neg F(x)\lor H(x)\rightarrow G(x)\lor H(x)$

Where "$\lor$" is used to denote a logical "or". That is, if the left-hand-side is true, then either $G(x)$ or $H(x)$ must be true.

Annotated Bibliography

Kari, Lila. Predicate Calculus. <http://www.csd.uwo.ca/~lila/logic14.pdf>

To Add

Knowledge Bases

Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.