Predicate Logic
1
Predicate Logic
Fariba Sadri
Example: MSc regulations
Passing the exams and the project implies
passing the MSc.
You do not pass the MSc and you do not get
a certificate if you do not pass the exams or
you do not pass the project.
2
3
Let us take the following propositions for
formulating the MSc regulations:
pe: pass exams
pp: pass project
pm: pass MSc
gc: get certificate
4
In propositional logic:
pe pp pm
pe ¬ pp pm gc
Not expressive enough if we want to consider
individual students, to check who has
passed the MSc, and who has not, for
example.
5
Example
John:
passes the project
but not the exams
Mary:
passes the exams
passes the project
Who passes the MSc?
6
Example
For all individuals X:
(pe(X) pp(X) pm(X) )
For all individuals X:
(pe(X) ¬pp(X)
pm(X) gc(X) )
7
Increase the expressive power of the
Propositional Logic language by adding:
• Predicates: that take arguments (extending
propositions)
• Parameters: as arguments of the predicates
• Variables: as arguments of the predicates
• Quantification
8
More formal expression of the
MSc regulations
X (pe(X) pp(X) pm(X))
X(¬pe(X) ¬pp(X)
pm(X) gc(X))
: Universal Quantifier
9
Now given:
pe(mary)
pp(mary)
Using X (pe(X) pp(X) pm(X))
With instance X=mary, i.e.
pe(mary) pp(mary) pm(mary)
We can conclude:
pm(mary)
Also given:
pp(john)
¬pe(john)
Using
X(¬pe(X) ¬pp(X) pm(X) gc(X))
With instance X=john, i.e.
¬pe(john) ¬pp(john)
pm(john) gc(john)
We can conclude:
pm(john) gc(john)
10
11
Another example
Every student has a tutor.
for all X
(if X is a student then
there is a Y such that Y is tutor of X)
X (student(X) Y tutor(Y,X))
: Existential Quantifier
12
The Predicate Logic Language
Alphabet:
• Logical connectives (same as propositional
logic): , , , ,
• Predicate symbols (as opposed to propositional
symbols):a set of symbols each with an
associated arity>=0.
• A set of constant symbols.
E.g. mary, john, 101, 10a, peter_jones
• Quantifiers ,
• A set of variable symbols. E.g. X, Y, X1, YZ.
13
Arity
In the previous examples:
Predicate Symbol Arity
student 1
tutor 2
pm 1
pp 1
14
A predicate symbol with
arity = 0 is called a nullary predicate (it is
a proposition),
arity = 1 is called a unary predicate,
arity = 2 is called a binary predicate.
A predicate symbol with arity=n (usually n>2)
is called an n-ary predicate.
15
Definition:
A Term is any constant or variable symbol.
16
Syntax of a grammatically correct
sentence (wff) in predicate logic
• p(t1,…, tn) is a wff if p is an n-ary predicate
symbol and the ti are terms.
• If W, W1, and W2 are wffs then so are the
following:
W W1 W2 W1 W2
W1 W2 W1 W2
X(W) X(W)
where X is a variable symbol.
• There are no other wffs.
From the description above you can see that
propositional logic is a special case of
predicate logic.
Predicate Logic: the predicates are
n-ary, n0, and we have terms and
quantifiers
17
Propositional Logic:
all the predicates are
nullary
18
Convention used in most places in these notes:
• Predicate and constant symbols start with lower
case letters.
• Variable symbols start with upper case letters.
19
Examples
The following are wffs:
1. married(john)
2. X(alive(X) adult_human(X)
married(X)
single(X) divorced(X) widowed(X))
3. X (bird(X) fly(X))
20
The following are not wffs:
4. X
5. single(X) Y
6. X (bird(X) feathered(X))
21
Exercise
which of the following are wffs?
1. X p(X)
2. X p(Y)
3. X Y p(Y)
4. q(X,Y,Z)
5. p(a) q(a,X,b)
6. p(a) p(a,b)
22
7. X r(X)
8. X Y p(X,Y)
9. X,Y p(X,Y)
10. X (Y)
11. x (Y p(x,Y))
23
Exercise
Formalise the following in predicate logic
using the following predicates (with their
more or less obvious meaning):
lecTheatre/1, office/1, contains/2, lecturer/1,
has/2, same/2, phd/1, supervises/2, happy/1,
completePhd/1.
1. 311 is a lecture theatre and 447 is an
office.
2. Every lecture theatre contains a projector.
3. Every office contains a telephone and
either a desktop or a laptop computer.
4. Every lecturer has at least one office.
5. No lecturer has more than one office.
24
6. No lecturers share offices with anyone.
7. Some lecturers supervise PhD students and
some do not.
8. Each PhD student has an office, but all
PhD students share their office with at
least one other PhD student.
25
9. A lecturer is happy if the PhD students
he/she supervises successfully complete
their PhD.
10. Not all PhD students complete their PhD.
26
27
Note:
X p(X) states that there is at least one X
such that p is true of X.
E.g. X father(X, john)
says John has at least one father (assuming
father(X,Y) is to be read as X is father of Y).
28
Exercise
Assuming a predicate same(X,Y) that
expresses that X and Y are the same
individual, express the statement that John
has exactly one father. You may also
assume a binary predicate “father” as above.