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.

Fermat

## 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

- All letters, upper- and lowercase.
- All digits from 0 to 9.
- 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

`aunt(emma)`

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: logic, predicate calculus