PowerPoint Presentation
Predicate Logic Cntd.
Fariba Sadri
2
Rules of Inference
Natural Deduction
All inference rules for propositional logic +
4 new rules to deal with the quantifiers.
1. -elimination (E)
X p(X)
p(a)
where a is any constant.
The constant a must replace every free
occurrence of X in P(X).
3
E.g.
From X beautiful(X) we can conclude
beautiful(quasimodo).
From
X (lion(X) Y(lioness(Y)provides_food(Y,X)))
We can infer
lion(shere_khan)
Y(lioness(Y) provides_food(Y,shere_khan))
Exercise
Formalise the argument below and show that
it is valid.
MSc Generalist and MSc Software
Engineering students do group projects.
Martin is either an MSc Generalist or an MSc
Software Engineering student.
So Martin does a group project.
4
5
2. -Introduction (I)
(Universal generalisation)
If we know all the ground terms and there are a small
number of them, e.g. a1, …, an,
then to show
X p(X)
we show p(a1), …, p(an) .
Suppose we wanted to show
X (student(X)
undergrad(X) postgrad(X))
then this approach would mean checking
every student.
6
This approach is not practical in general.
But maybe we know some properties of being
a student, e.g.
All students are enrolled on a degree
programme.
Our only degree programmes are UG and PG.
Then we can show that if you pick any student
they will be UG or PG.
7
In general to show
X p(X)
we show p(a)
for an arbitrary constant a on which there are
no constraints.
8
9
-Introduction (I)
p(a)___
X p(X)
provided the following conditions are met:
i. a is an arbitrary constant.
ii. There are no assumptions involving a, left
undischarged, used to obtain p(a).
iii. Substitution of X for a in p(X) is uniform, i.e. X
is substituted for every occurrence of a.
10
E.g.
From
Y (q(a,Y) Z (r(Z) t(Z,Y,a)))
we can infer
XY (q(X,Y) Z (r(Z) t(Z,Y,X)))
provided a is an arbitrary constant.
11
Note:
To be on the safe side:
Make sure there is no variable clash when
applying the rule.
The safest is to introduce a new variable, i.e.
one that does not occur in the original wff.
12
Exercise
All messages are encrypted.
Anything that is encrypted is secure.
So all messages are secure.
13
Exercise
Given
1. X (p(X) Y q(X,Y))
2. Z (X q(Z,X) r(a) s(Z,a))
3. r(a)
show
X (p(X) s(X,a))
14
3. -Introduction (I)
p(t)____
X p(X)
where t is any term, and X does not clash with
any occurrence of X in p(t).
X is substituted for one or more occurrences
of t in p(t).
15
Example: Given
logician(charles_dodgson)
writer(charles_dodgson)
Abbreviated as l(cd) w(cd)
we can derive each of the following by an
application of the I rule.
X (l(X) w(X)) X (l(X) w(cd))
X (l(cd) w(X))
16
Beware clash of variables:
Example:
There is a course that Mary likes.
X (course(X) likes(mary,X))
We can derive:
Y X(course(X) likes(Y,X))
but not
X X(course(X) likes(X,X))
(There is a course that likes itself!)
17
4. -Elimination (E)
p(a) assume
..
..
Xp(X), W
W
where W is any wff, provided the following
conditions are met:
18
i. a is an arbitrary constant.
ii. In proving W from p(a) the only
assumption left undischarged in which a
occurs is p(a).
iii. a does not occur in W or in X p(X).
Note:
p(a) is an assumption, which is discharged by
the application of E rule, above.
19
Example:
Aliens is an exciting film.
All exciting films make a lot of money.
So there is a film that makes a lot of money.
20
1. film(als) exciting(als) given
2. X(film(X)exciting(X)makes_money(X)) given
3. film(als)exciting(als)makes_money(als) 2,E
4. makes_money(als) 3,1, E
5. film(als) 1, E
6. film(als) makes_money(als) 5,4, I
7. X (film(X) makes_money(X)) 6, I
21
Compare with:
There is an exciting film.
All exciting films make a lot of money.
So there is a film that makes a lot of money.
22
1. X (film(X) exciting(X)) given
2. X(film(X)exciting(X)makes_money(X))
given
3. film(a) exciting(a) assume
4. film(a)exciting(a)makes_money(a) 2, E
5. makes_money(a) 3,4, E
6. film(a) 3, E
7. film(a) makes_money(a) 5,6, I
8. X (film(X) makes_money(X)) 7, I
9. X (film(X) makes_money(X)) 1,3,8, E
Example:
X (manager(X) promoted(X)) ⊢
X promoted(X)
More generally, the following are useful
derivations:
X (p(X) q(X)) ⊢ X p(X)
X (p(X) q(X)) ⊢ X q(X)
23
1. X (p(X) q(X)) given
2. p(a) q(a) assume
3. q(a) 2, E
4. X q(X) 3, I
5. X q(X) 1, 2, 4, E
24
25
Exercise
Formalise the following argument and show
that it is valid.
Someone hacked into secure file f (‘finance’).
Anyone who hacks into a secure file either
has stolen its password or has had insider
help.
So there is someone who has stolen f’s
password or has had insider help.
26
Be careful!
When applying the inference rules identify
the dominant connective/quantifier
correctly.
Apply the inference rule applicable to that
connective.
Example:
From X (p(X) q(X))
we can derive p(a) q(a) by E.
But
From X (p(X) q(X))
we cannot derive (p(a) q(a)) by E.
The following derivation is wrong:
X (business(X) avoidsTax(X))
(business(amazon) avoidsTax(amazon))
27
28
Be careful!
From p(a)
we can derive X p(X) by I.
But from p(a)
we cannot derive X p(X) by I.
From ¬ happy(tom) we can derive
X happy(X) but not X happy(X).
29
Soundness and Completeness
Predicate logic is sound and complete.
Decidability
Definition:
A logical system is decidable iff it is possible to
have an effective method (an algorithm) that is
guaranteed to recognise correctly whether a wff is
a theorem of the system or not. In other words, a
logical system is decidable if it satisfies conditions
1 and 2 below.
30
1) If |= W then there is an algorithm that recognises
that W is a theorem.
2) If it is not the case that |=W then there is an
algorithm that recognises that W is not a theorem.
Propositional logic is decidable.
Predicate logic is not – it is semi-decidable, that is,
it satisfies condition 1, above, but not condition 2.