程序代写代做代考 Predicate Logic

Predicate Logic

1

Predicate Logic

Part 2

Fariba Sadri

2

Recall 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

3

Propositional Logic:

all the predicates are

nullary

Some useful equivalences
All propositional logic equivalences hold for

predicate logic wffs.

E.g. A  B   A  B

So

able_to_work(john)  employed(john) 

 able_to_work(john)  employed(john)

X (able_to_work(X)  employed(X)) 

X (¬ able_to_work(X)  employed(X))

4

5

Some useful equivalences cntd.

E.g. (A  B)   A   B

So

 (academic(john)  rich(john)) 

 academic(john)   rich(john)

6

Another instance of the same equivalence:

(A  B)   A   B

A

(X (able_to_work(X)  employed(X)) 

inflation(low)) 

B

 (X (able_to_work(X)  employed(X)))

  inflation(low)

7

Some other equivalences in

predicate logic

• Xp(X)  X p(X)

all true, none false

• X p(X)  X p(X)

all false – none true

• Xp(X)  X p(X)

at least one true – not all false

• X p(X)  X p(X)

at least one false – not all true

Equivalence exercises

X (cautious(X) normal(X) 

Y shelter(Y,X)) 

¬X ((cautious(X) normal(X)) 

¬Y shelter(Y,X))

X Y (aggresive(X)  sees(X, Y) 

fights(X, Y)) 

X ¬Y (aggresive(X)  sees (X, Y) 

¬fights (X, Y))

8

9

Some other equivalences in

predicate logic

Suppose W1, W2 are wffs.

If W1 can be transformed to W2 by a

consistent renaming of variables, then W1

and W2 are equivalent.

10

E.g.

X p(X)  Y p(Y)

X Y (p(X,Y)  q(Y, X)) 

Z W (p(Z,W)  q(W, Z))

11

Some other equivalences in

predicate logic

If two wffs differ only in the order of two
adjacent quantifiers of the same kind, then
they are equivalent. E.g.

X Y p(X,Y)  Y X p(X,Y)

X Y p(X,Y)  Y X p(X,Y)

But

X Y p(X,Y) is not equivalent to

Y X p(X,Y)

More Equivalences

X(A  B)  XA  XB

E.g.

X(male(X)  female(X)) 

X male(X)  X female(X)

12

More Equivalences

X (A  B)  X A X B

E.g.

X ( mscDegree(X)duration(X, 12months)

phdDegree(X)duration(X, 42months)) 

X (mscDegree(X)duration(X, 12months))

X (phdDegree(X)duration(X, 42months))

13

14

Some notes on quantifiers

1. Free and Bound variables:

An occurrence of a variable in a wff is

bound if it is within the scope of a quantifier

in that wff. It is free if it is not within the

scope of any quantifier in that wff.

15

Examples

X (p(X)  q(Y,X))

Both occurrences of X in the above wff are

bound (they are both within the scope of the

.)

The occurrence of Y is free (it is not within

the scope of any quantifier.)

16

(X p(X))  (Xq(X))

In the wff above, both occurrences of X are

bound, the first by the , the second by the

.

17

(X p(X))  (Yq(X,Y))

In the wff above, the first occurrence of X is

bound, the second is free. The occurrence of

Y is bound.

18

Definition.

If a wff contains no free occurrences of

variables it is said to be closed, otherwise it

is said to be open.

A wff with no free occurrences of variables is

also called a sentence.

E.g.

Bird(X)  has_beak(X)

is a wff but not a sentence.

X (Bird(X)  has_beak(X))

is a wff and a sentence.

19

20

Back to equivalences

2. A particular occurrence of a variable is

bound by the closest quantifier which can

bind it.

E.g.

X (p(X)  X q(X)) 

X (p(X)  Y q(Y))

21

3. Law of vacuous quantification

X W  W if W (a wff) contains no free

occurrences of X.

X (p(a)  q(a))  p(a)  q(a)

X X p(X)  X p(X)

X Y(p(X) Y q(X,Y))

which quantification can we drop?

More Equivalences

If X does not occur free in A then

X(A  B)  A  XB, and

X(A  B)  A  XB.

E.g.

X(funny(john)  loves(X, john)) 

funny(john)  X loves(X, john)

22

More Equivalences

If X doesn’t occur free in A, then

X(A  B)  A  XB, and

X(A  B)  A  XB.

E.g.

X(station(victoria)  tubeLine(X, victoria))

 station(victoria)  X tubeLine(X, victoria)

23

More Equivalences

If X does not occur free in B then

X(A  B)  XA  B, and

X(A  B)  XA  B.

Be careful:

The quantifier changes.

24

X(A  B) is equivalent to XA  B, and

X(A  B) is equivalent to XA  B

E.g.

X(loves(X, john)  happy(john)) 

(X loves(X, john))  happy(john)

25

Warning: non-equivalences

The following are NOT logically equivalent

(though always, the first |= the second):

X(A  B) and XA  XB

X(A  B) and XA  XB

XA  XB and X (A  B)

Can you find a ‘counter-example’ for each

one?

26

Counter-example for

X(p(X)  q(X)) and Xp(X)  Xq(X)

Take

p(a) p(b) ¬p(c)

q(a) ¬q(b)

Then RHS is true, but LHS is not.

27

Examples for slide 26

X(A  B) and XA  XB

Not equivalent

X(male(X)  female(X)) and

X male(X)  X female(X)

XA  XB and X (A  B)

X msc(X)  X meng(X) and

X (msc(X)  meng(X))

28