程序代写代做代考 algorithm finance PowerPoint Presentation

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

XY (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.