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, n0, 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