程序代写代做代考 Predicate Logic

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, n0, 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.