Predicate Calculus: Its Simple Syntax, and Semantics

In my previous post I talked about propositional calculus. Today we will talk about predicate calculus and its syntax and semantics. Predicate calculus builds on this concept by allowing us to describe the relationships in our logical assertions. We could have a statement like “it snowed on Saturday” (it did… it sucks), and represent that as

weather(saturday, snow)

We can now add variables and start to generalize. For example if we use the X as a variable for the day of the week, we can say

weather(X, snow) is true

to say that it snows every day of the week (I hope not!). As usual, we first need to define the words in our language, that is the syntax.

The essential quality of a proof is to compel belief.


Predicate Calculus Syntax and Semantics

In predicate calculus we use improper symbols to describe objects and their relationship in the world. These are parentheses “( )”, commas “,”, and periods “.”.

We define the symbols as strings of characters and digits. No spaces or special characters can be used, although the “_” can be used for readability. That is the valid characters used are

  1. All letters, upper- and lowercase.
  2. All digits from 0 to 9.
  3. The underscore, “_”.

And all symbols must start with a letter. Some correct examples are

Name   coffee3   stan_and_kyle   emma   XYZ   likes   partner_of

And some invalid examples are

7John   stan and kyle   ta%ble   ###123   lookout!!!

These symbols can represent variables, constants, functions, or predicates.

Variables are used for the abstract concept of classes. Any symbol beginning with a capital is a variable.

X   Name   Location

Constants are specific objects in the world, and start with a lowercase.

emma   small   pink     
note: true and false are reserved as truth symbols

Functions also start with a lowercase, and are used the map elements in a set. In this writers world, the function


evaluates to nancy. Functions also have an arity associated with them. In the previous example the arity would be 1. An example of an arity of 2 could be

loves(nancy, emma)

Another simple example would be

subtract(nine, two)

which evaluates to seven.

A predicate term is a constant, variable, or function expression of a specific arity. We use these terms to describe the problem domain. This leads to another definition, the atomic sentence. It is simply a predicate of N arity followed by N terms in parentheses separated by commas. It is the the most primitive unit of a predicate term. An example of an atomic sentence is

loves(aunt(emma), partner_of(nancy))

Now that we have our basic unit, we can build predicate sentences. First some definitions of symbols

  • ∧ : logical and
  • ∨ : logical or
  • ¬ : logical not
  • → : logical implies
  • ≡ : logical equivalent to
  • ∀ : universal quantifier (reads “sentence is true for all values”)
  • ∃ : existential quantifier (reads “sentence is true for at least one value”)

To end our discussion on syntax I’ll show another example[efn_note](Luger, George F.; Stubblefield, William A, Artificial intelligence: structures and strategies for complex problem solving 1998)[/efn_note].

mother(eve, abel)
mother(eve, cain)
father(adam, abel)
father(adam, cain)

∀ X ∀ Y father(X, Y) ∨ mother(X, Y) → parent(X, Y)
∀ X ∀ Y ∀ Z parent(X, Y) ∧ parent(X, Z) → sibling(Y, Z)

The first 4 lines describe the world. The second two sentences define rules of the world. The first states that for all X’s and all Y’s, if the X is the father of Y or mother of Y, than X is implied to be a parent of Y. The second states that for all X’s, Y’s, and Z’s if a parent of Y is X, and a parent of Z is X, then it is implied that the sibling of Y is Z. If this still confuses you, I encourage you to plug in the variables and see how that looks on paper.

If you want more check out the MIT OpenCourseWare video here!

Tags: ,

Leave a Reply