Predicate Logic: Introduction

Predicate Logic upgrades Propositional Logic by adding the ability to talk about the relationships between things, and whether they are true for all things or for some things.

Slides for the videos (PDF).

Introduction

In the first video, we look at the syntax of Predicate Logic and how Predicate Logic formulas are constructed.

Enter any notes to yourself here.

Formal Syntax and Vocabularies

Predicate Logic formulas are built from predicate symbols and function symbols, collectively known as a vocabulary. In the second video this week, we look at some example vocabularies and the formal syntax of Predicate Logic. The key concept to understand when looking at the syntax is the ideas of free and bound variables, and the fact that we can rename bound variables without changing the meaning of a formula.

Enter any notes to yourself here.

Saying what you mean

Predicate Logic is a very expressive language for making complex statements. In video 3.3, we go through a collection of sample statements showing how to express various forms of relationship in Predicate Logic, and point out some common pitfalls.

Enter any notes to yourself here.

Exercises

Writing formulas

Write the following English-language statements as Predicate Logic formulas. Invent whatever vocabulary (function and relation symbols) you feel is necessary to write the statement as a formula.

How to enter formulas

Predicate symbols are any sequence of letters and numbers, where the first character is a letter, followed by their arguments in parentheses. This is similar to the rules for variable names in Java.

Connectives and Quantifiers are represented by ASCII versions:

And (“∧”) is represented by “/\” (forward slash, backwardslash).
Or (“∨”) is represented by “\/” (backward slash, forward slash).
Implies (“→”) is represented by “->” (dash, greater than).
Not “¬” is represented by “¬” (top left of your keyboard). Alternatively, you can use “~” (tilde) or “!” (exclamation mark).
For all “∀x.” is represented by “all x.”.
Exists “∃x.” is represented by “ex x.”.
Use parentheses “(” and “)” to disambiguate mixtures of connectives.

As an example of the use of ASCII for entering formulas, the formula

∀d.  Sunny(d) ∨ Rainy(d)

is entered as all d. Sunny(d) \/ Rainy(d).

Use equality “x = y” and disequality “x != y” (or “¬ (x = y)”) to state when two things are the same or different.

The rules for mixing connectives and parentheses were described Lecture 1.

“Every tree is green”.
Answer...
The formula I would write is:
```
∀t.  tree(t) → green(t)
```
or
```
∀t.  tree(t) → colour(t, green())
```
both of which say "for all t, if t is a tree, then t is green."
It is also sort of correct to write:
```
∀t.  green(t)
```
But only if we are assuming that everything in the universe is a tree. Remember that ∀x. means "for all entities in the universe". It is up to us as modellers to decide what the limits of the universe we are talking about, but when communicating with others we need to be clear about it.
Note that changing the variable name doesn't affect whether it is a tree or not. The formulas
```
∀tree.  green(tree)
```
and
```
∀dog.  green(dog)
```
both mean exactly the same thing. As far as Predicate Logic is concerned, variables are given meaning by how they are used, not by how they are named.
I'm happy with this one.
“Every tree is bare and dead”.
Answer...
This rather bleak sentence can be expressed as:
```
∀t.  tree(t) → (bare(t) ∧ dead(t))
```
or, in words: "every thing t that is a tree is both bare and dead".
When writing on paper, it is common mistake to mix up the final part and write the even bleaker sentence:
```
∀t.  (tree(t) → bare(t)) ∧ dead(t)
```
which says for all things “t”, if “t” is a tree then it is bare, and, separately, “t” is dead. As we shall see later in the course, this sentence will imply that everything is dead:
```
∀t.  dead(t)
```
I'm happy with this one.
“There exists a tree that is green”.
Answer...
I would write:
```
∃t.  tree(t) ∧ green(t)
```
This says "there exists a t, such that t is a tree and t is green".
As above, if you are assuming that every thing in the universe is a tree, then the following also makes sense:
```
∃t.  green(t)
```
It is tempting to write the following wrong thing:
```
∃t.  tree(t) → green(t)
```
but this says "there exists a t, such that if t is a tree, then t is green". This statement is true of, for example, a red ball: there is a red ball, and if it were a tree it would be green, but it isn't a tree, so it doesn't matter (for the purposes of this formula) what colour it is. Another example: “if your granny had wheels, she'd be a car”.
I'm happy with this one.
“All the leaves are brown, and the sky is grey”.
Answer...
One way to write this lyric is:
```
(∀l.  leaf(t) → brown(t)) ∧ grey(sky())
```
Note here I have used a 0-argument function sky() to talk about “the” sky, instead of saying “there exists a thing which is the sky, and it is grey”. When we talk about fixed objects (e.g., “socrates()”), we can use 0-argument function symbols.
I'm happy with this one.
“For every ‘x’ there is a ‘y’ that is greater than ‘x’”. (You might want to use a predicate symbol like “greaterthan” for this.)
Answer...
```
∀x. ∃y.  greaterthan(y, x)
```
where we are implicitly assuming that it makes sense to compare things. You could also be explicit about the fact that we are comparing numbers (for instance):
```
∀x. 
  number(x) → (∃y.  number(y) ∧ greaterthan(y, x))
```
I'm happy with this one.
“For every tree that is green, there is a tree that is blue”.
Answer...
```
∀t. 
  (tree(t) ∧ green(t)) → (∃u.  tree(u) ∧ blue(u))
```
In words: "for all t, if t is a tree and t is green, then there exists a u such that u is a tree and is blue.". It is also possible to replace the ∧ to the left of the → with another →:
```
∀t.  tree(t) → green(t) → (∃u.  tree(u) ∧ blue(u))
```
Optionally, depending on how you want to interpret the English statement, you could also state that the blue tree is different to the green tree:
```
∀t. 
  (tree(t) ∧ green(t)) →
  (∃u.  tree(u) ∧ blue(u) ∧ t != u)
```
I'm happy with this one.
“There is a bird that has sat in every tree”.
Answer...
```
∃b.  bird(b) ∧ (∀t.  tree(t) → satIn(b, t))
```
In words: "there exists a bird b, such that for all trees t, b has sat in t".
The following expresses something different:
```
∀t.  tree(t) → (∃b.  bird(b) ∧ satIn(b, t))
```
Which says "Every tree has a bird that sits in it". Note that in this sentence there could be a different bird in every tree. The original sentence asks for one bird that has sat in every tree.
Another faulty formula is:
```
∀t. ∃b.  tree(t) ∧ bird(b) ∧ satIn(b, t)
```
which says "for all t, (a) t is a tree, and (b) there exists a bird b that has sat in t". Taking just the (a) part, this formula implies the formula:
```
∀t.  tree(t)
```
which says that everything is a tree. Indeed, if we assume that there is at least one thing in the universe, we can use the following chain of reasoning:
1. If there is at least one thing in the univese, call it “Sylvester”
2. Then using the faulty formula, setting t to be “Sylvester”, we learn that
  1. There exists something, call it “Tweety”
  2. “Sylvester” is a tree
  3. “Tweety” is a bird
  4. “Tweety” has sat in “Sylvester”
The first two formulas above avoid the problem of everything being a tree.
If you wanted to get way more complicated, then you could attempt to encode the precise meaning of “has” in terms of “there exists a point in time before the current time when the bird sat in the tree”. Whether you do this or just use a predicate like “satIn” depends on what you want to model.
I'm happy with this one.
“There is exactly one tree that is red”.
Answer...
```
∃t. 
  tree(t)
  ∧
  red(t)
  ∧
  (∀u.  (tree(u) ∧ red(u)) → t = u)
```
In words “there exists a t, which is a tree and is red, and every u that is a red tree is equal to t”. You can read the parts after the the ∃ as a list of requirements: t must be (i) a tree; (ii) red; and (iii) the only one.
I'm happy with this one.
“There is at most one red tree”.
Answer...
```
∀t1. ∀t2. 
  (tree(t1) ∧ red(t1) ∧ tree(t2) ∧ red(t2)) →
  t1 = t2
```
In words "for all t1 and t2, if they are both trees and both red, then they are equal". Note that this formula does not specify that a red tree actually exists, only that if we can find any red trees they are all equal.
I'm happy with this one.
“There exist at least two different green trees”.
<formula>
Answer...
```
∃t1. ∃t2. 
  tree(t1)
  ∧
  green(t1)
  ∧
  tree(t2)
  ∧
  green(t2)
  ∧
  t1 != t2
```
In words "there exist a t1 and a t2 that are both trees, are both green, and are not equal". Without the extra “t1 != t2”, this formula would still be true when there was only one tree.
I'm happy with this one.

Same Formulas?

Are these two formulas the same up to renaming of their bound variables?
```
∀x.  P(x)
```
and
```
∀y.  P(y)
```
(config (options (True False)))
Answer...
True: the bound variable “x” in the first one has been consistently renamed to “y” in the second.
Are these two formulas the same up to renaming of their bound variables?
```
∀x.  P(x)
```
and
```
∀y.  P(x)
```
(config (options (True False)))
Answer...
False: in the first one, “x” appears bound, but it is free in the second one.
Are these two formulas the same up to renaming of their bound variables?
```
∀x.  P(x) → (∃y.  Q(x, y))
```
and
```
∀y.  P(y) → (∃x.  Q(y, x))
```
(config (options (True False)))
Answer...
True: the bound variable “x” in the first one has been consistently renamed to “y” in the second, and the bound variable “y” has been consistently renamed to “x”.
Are these two formulas the same up to renaming of their bound variables?
```
∀x.  P(x) → (∃y.  Q(x, y))
```
and
```
∀y.  P(y) → (∃y.  Q(x, y))
```
(config (options (True False)))
Answer...
False: we can match up “x” in the first with “y” in the second, and “y” in the first with “x” in the second, but this pairing does not make “Q(x,y)” in the first and “Q(x,y)” in the second equal.
Are these two formulas the same up to renaming of their bound variables?
```
∀x.  P(x) → Q(x)
```
and
```
∀y.  Q(y) → P(y)
```
(config (options (True False)))
Answer...
False: the two formulas have different structure, because the predicate symbols “P” and “Q” are swapped.
Are these two formulas the same up to renaming of their bound variables?
```
(∀x.  P(x)) ∧ (∀x.  Q(x))
```
and
```
(∀y.  P(y)) ∧ (∀z.  Q(z))
```
(config (options (True False)))
Answer...
True: the two bound “x”s in the first formula are independent and can be renamed separately.