Solution for:

P -> Q

~Q -> ~P

P -> Q <=> ~Q -> ~P

Homework 3
Cs472/572 Artificial Intelligence
Dept of Computer Science
Iowa State University

http://www.cs.iastate.edu/~cs572/assignments/assignment3.pdf

TA ,Jie Bao
Dept of Computer Science
Iowa State University
baojie@cs.iastate.edu
http://www.cs.iastate.edu/~baojie
Dec 7, 2002

Based on the solution of Becca Wemhoff.

Index

Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6
Problem 7
Problem 8
Problem 9
Problem 10
Problem 11
Problem 12
Problem 13
Problem 14
Problem 15
Problem 16

1 (20 pts.) 6.2 Use truth tables to show that the following sentences are valid, and thus that the equivalences hold. Some of these equivalence rules have standard names, which are given in the right column.

a.	P ^ (Q ^ R)	<=>	(P ^ Q) ^ R	Associativity of conjunction
b.	P V (Q V R)	<=>	(P V Q) V R	Associativity of disjunction
c.	P ^ Q	<=>	Q ^ P	Commutativity of conjunction
d.	P V Q	<=>	Q V P	Commutativity of disjunction
e.	P ^ (Q V R)	<=>	(P ^ Q) V (P ^ R)	Distributivity of ^ over V
f.	P V (Q ^ R)	<=>	(P V Q) ^ (P V R)	Distributivity of V over ^
g.	~ (P ^ Q)	<=>	~P V ~Q	de Morgan’s Law
h.	~ (P V Q)	<=>	~P ^ ~Q	de Morgan’s Law
i.	P => Q	<=>	~Q => ~P	Contraposition
j.	~ ~P	<=>	P	Double Negation (Involution)
k.	P => Q	<=>	~P V Q
l.	P <=> Q	<=>	(P => Q) ^ (Q => P)
m.	P <=> Q	<=>	(P ^ Q) V (~P ^ ~Q)
n.	P ^ ~P	<=>	False	^ Complement
o.	P V ~P	<=>	True	V Complement

They are all valid. The turth tables:

a. Associativity of conjunction: P ^ (Q ^ R) <=> (P ^ Q) ^ R

P	Q	R	(Q ^ R)	(P ^ Q)	P ^ (Q ^ R)	(P ^ Q) ^ R	P ^ (Q ^ R) <=> (P ^ Q) ^ R
1	1	1	1	1	1	1	1
1	1	0	0	1	0	0	1
1	0	1	0	0	0	0	1
1	0	0	0	0	0	0	1
0	1	1	1	0	0	0	1
0	1	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	0	0	0	0	0	0	1

b. Associativity of disjunction: P v (Q v R) <=> (P v Q) v R

P	Q	R	(Q v R)	(P V Q)	P V (Q V R)	(P V Q) V R	P V (Q V R) <=> (P V Q) V R
1	1	1	1	1	1	1	1
1	1	0	1	1	1	1	1
1	0	1	1	1	1	1	1
1	0	0	0	1	1	1	1
0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1
0	0	1	1	0	1	1	1
0	0	0	0	0	0	0	1

c. Commutativity of conjunction: P ^ Q <=> Q ^ P

P	Q	P ^ Q	Q ^ P	P ^ Q <=> Q ^ P
1	1	1	1	1
1	0	0	0	1
0	1	0	0	1
0	0	0	0	1

d. Commutativity of disjunction: P v Q <=> Q V P

P	Q	P V Q	Q V P	P V Q <=> Q V P
1	1	1	1	1
1	0	1	1	1
0	1	1	1	1
0	0	0	0	1

e. Distributivity of ^ over V: P ^ (Q V R)<=>(P ^ Q) V (P ^ R)

P	Q	R	(Q V R)	(P ^ Q)	(P ^ R)	P ^ (Q V R)	(P ^ Q) V (P ^ R)	P ^ (Q V R) <=> (P ^ Q) V (P ^ R)
1	1	1	1	1	1	1	1	1
1	1	0	1	1	0	1	1	1
1	0	1	1	0	1	1	1	1
1	0	0	0	0	0	0	0	1
0	1	1	1	0	0	0	0	1
0	1	0	1	0	0	0	0	1
0	0	1	1	0	0	0	0	1
0	0	0	0	0	0	0	0	1

f. Distributivity of v over ^: P V (Q ^ R) <=> (P V Q) ^ (P V R)

P	Q	R	(Q ^ R)	(P V Q)	(P V R)	P V (Q ^ R)	(P V Q) ^ (P V R)	P V (Q ^ R) <=> (P V Q) ^ (P V R)
1	1	1	1	1	1	1	1	1
1	1	0	0	1	1	1	1	1
1	0	1	0	1	1	1	1	1
1	0	0	0	1	1	1	1	1
0	1	1	1	1	1	1	1	1
0	1	0	0	1	0	0	0	1
0	0	1	0	0	1	0	0	1
0	0	0	0	0	0	0	0	1

g. de Morgan's Law: ~(P ^ Q) <=> ~P V ~Q

P	Q	(P ^ Q)	~P	~Q	~(P ^ Q)	~P V ~Q	~(P ^ Q) <=> ~P V ~Q
1	1	1	0	0	0	0	1
1	0	0	0	1	1	1	1
0	1	0	1	0	1	1	1
0	0	0	1	1	1	1	1

h. de Morgan's Law: ~(P V Q) <=> ~P ^ ~Q

P	Q	(P V Q)	~P	~Q	~(P V Q)	~P ^ ~Q	~(P V Q) <=> ~P ^ ~Q
1	1	1	0	0	0	0	1
1	0	1	0	1	0	0	1
0	1	1	1	0	0	0	1
0	0	0	1	1	1	1	1

i: Contraposition: P -> Q <=> ~Q -> ~P

j: Double Negation: ~~P <=> P

P	~P	~(~P)	P	~~P <=> P
1	0	1	1	1
0	1	0	0	1

k P -> Q <=> ~P V Q

P	Q	~P	P -> Q	~P V Q	P -> Q <=> ~P V Q
1	1	0	1	1	1
1	0	0	0	0	1
0	1	1	1	1	1
0	0	1	1	1	1

l. P <=> Q <=> (P -> Q) ^ (Q -> P)

m. P <=> Q <=> (P ^ Q) V (~P ^ ~Q)

P	Q	P ^ Q	~P	~Q	(~P ^ ~Q)	P <=> Q	(P ^ Q) V (~P ^ ~Q)	P <=> Q <=> (P ^ Q) V (~P ^ ~Q)
1	1	1	0	0	0	1	1	1
1	0	0	0	1	0	0	0	1
0	1	0	1	0	0	0	0	1
0	0	0	1	1	1	1	1	1

n. Complement P ^ ~P <=> False

P	~P	P ^ ~P	FALSE	P ^ ~P <=> FALSE
1	0	0	0	1
0	1	0	0	1

o. Complement: P V ~P <=> True

P	~P	P V ~P	TRUE	P V ~P <=> TRUE
1	0	1	1	1
0	1	1	1	1

[Back to top]

2. (20 pts.) 6.3 Look at the following sentences and decide for each if it is valid, unsatisfiable, or neither. Verify your decision using truth tables, or by using the equivalence rules of Exercise 6.2. Were there any that initially confused you?

a.	Smoke => Smoke
b.	Smoke => Fire
c.	(Smoke => Fire) => (~Smoke => ~Fire)
d.	Smoke V Fire V ~Fire
e.	((Smoke ^ Heat) => Fire) <=> ((Smoke => Fire) V (Heat => Fire))
f.	(Smoke => Fire) =>((Smoke ^ Heat) => Fire)
g.	Big V Dumb V (Big => Dumb)
h.	(Big ^ Dumb) V ~Dumb

a. Smoke => Smoke : valid

	Smoke => Smoke
TRUE	TRUE
FALSE	TRUE

Using the equivalences from 6.2:

(Smoke => Smoke) <=> ~Smoke V Smoke (6.2 k)
<=> ~Smoke V Smoke (6.2 d)
<=> True (6.2 o)

b. Smoke => Fire

Smoke	Fire	Smoke => Fire
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	TRUE
FALSE	FALSE	TRUE

Since the last column has both TRUE and FALSE, this sentence is neither valid nor unsatisfiable; it is satisfiable, but it is not valid.

c. (Smoke => Fire) => (~Smoke => ~Fire)

Smoke	Fire	~Smoke	~Fire	Smoke => Fire	~Smoke => ~Fire	(Smoke => Fire) => (~Smoke => ~Fire)
TRUE	TRUE	FALSE	FALSE	TRUE	TRUE	TRUE
TRUE	FALSE	FALSE	TRUE	FALSE	TRUE	TRUE
FALSE	TRUE	TRUE	FALSE	TRUE	FALSE	FALSE
FALSE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE

Since the last column has both TRUE and FALSE, this sentence is neither valid nor unsatisfiable; it is satisfiable, but it is not valid.

d. Smoke V Fire V ~Fire

Smoke	Fire	~Fire	Smoke V Fire V ~Fire
TRUE	TRUE	FALSE	TRUE
TRUE	FALSE	TRUE	TRUE
FALSE	TRUE	FALSE	TRUE
FALSE	FALSE	TRUE	TRUE

Since the last column is all TRUE, this is a valid sentence.

Assume that it is parenthesized this way: (left-most pairing) (Smoke V Fire) V ~Fire , Using the equivalences from 6.2:

(Smoke V Fire) V ~Fire) <=> Smoke V (Fire V ~Fire) (6.2 b)
<=> Smoke V True (6.2 o)
<=> True (Identity: P V TºT)

e. ((Smoke ^ Heat) => Fire) <=> ((Smoke Þ Fire) V (Heat => Fire))

Smoke	Heat	Fire	Smoke ^ Heat	(Smoke ^ Heat) => Fire	Smoke => Fire	Heat => Fire	(Smoke => Fire) V (Heat => Fire)	((Smoke ^ Heat) => Fire) <=> ((Smoke => Fire) V (Heat => Fire))
TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE
TRUE	TRUE	FALSE	TRUE	FALSE	FALSE	FALSE	FALSE	TRUE
TRUE	FALSE	TRUE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE
TRUE	FALSE	FALSE	FALSE	TRUE	FALSE	TRUE	TRUE	TRUE
FALSE	TRUE	TRUE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE
FALSE	TRUE	FALSE	FALSE	TRUE	TRUE	FALSE	TRUE	TRUE
FALSE	FALSE	TRUE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE
FALSE	FALSE	FALSE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE

Since the last column is all TRUE, this is a valid sentence.

Using the equivalences from 6.2:

(Smoke ^ Heat) => Fire
<=> ~(Smoke ^ Heat) V Fire (6.2 k)
<=> (~Smoke V ~Heat) V Fire (6.2 g)
<=> ~Smoke V (~Heat V Fire) (6.2 b)
<=> ~Smoke V (~Heat V (Fire V Fire)) (Idempotent P V PºP)
<=> ~Smoke V ((~Heat V Fire) V Fire) (6.2 b)
<=> ~Smoke V (Fire V (~Heat V Fire)) (6.2 d)
<=> (~Smoke V Fire) V (~Heat V Fire)) (6.2 b)
<=> (Smoke => Fire) V (~Heat V Fire)) (6.2 k)
<=> (Smoke => Fire) V (Heat => Fire)) (6.2 k)

f. (Smoke => Fire) =>((Smoke ^ Heat) => Fire)

Smoke	Heat	Fire	Smoke => Fire	Smoke ^ Heat	(Smoke ^ Heat) => Fire	(Smoke => Fire) => ((Smoke ^ Heat) => Fire)
TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE
TRUE	TRUE	FALSE	FALSE	TRUE	FALSE	TRUE
TRUE	FALSE	TRUE	TRUE	FALSE	TRUE	TRUE
TRUE	FALSE	FALSE	FALSE	FALSE	TRUE	TRUE
FALSE	TRUE	TRUE	TRUE	FALSE	TRUE	TRUE
FALSE	TRUE	FALSE	TRUE	FALSE	TRUE	TRUE
FALSE	FALSE	TRUE	TRUE	FALSE	TRUE	TRUE
FALSE	FALSE	FALSE	TRUE	FALSE	TRUE	TRUE

Since the last column is all TRUE, this is a valid sentence.

Using the equivalences from 6.2:

(Smoke => Fire) =>((Smoke Ù Heat) => Fire)
<=> ~(Smoke => Fire) V ((Smoke Ù Heat) => Fire) (6.2 k)
<=> ~(~Smoke V Fire) V ((Smoke ^ Heat) Þ Fire) (6.2 k)
<=> (~ ~Smoke ^ ~Fire) V ((Smoke ^ Heat) Þ Fire) (6.2 h)
<=> (Smoke ^ ~Fire) V ((Smoke Ù Heat) => Fire) (6.2 j)
<=> (Smoke ^ ~Fire) V (~ (Smoke ^ Heat) Ú Fire) (6.2 k)
<=> (Smoke ^ ~Fire) V ((~Smoke V ~Heat) V Fire) (6.2 g)
<=> ((Smoke ^ ~Fire) V (~Smoke V ~Heat)) V Fire (6.2 b)
<=> ((~Fire ^ Smoke) V (ØSmoke V ~Heat)) V Fire (6.2 c)
<=> (((~Fire ^ Smoke) V ~Smoke) V ~Heat) V Fire (6.2 b)
<=> ((~Smoke V (~Fire ^ Smoke)) V ØHeat) V Fire (6.2 c)
<=> (((~Smoke V ~Fire) ^ (~Smoke V Smoke)) V ØHeat) V Fire (6.2 f)
<=> (((~Smoke V ~Fire) ^ (Smoke V ~Smoke)) V ~Heat) V Fire (6.2 d)
<=> (((~Smoke V ~Fire) ^ True) V ~Heat) V Fire (6.2 o)
<=> ((~Smoke V ~Fire) V ~Heat) V Fire (Identity P ^ TºP)
<=> (~Smoke V (~Fire V ~Heat)) V Fire (6.2 b)
<=> (~Smoke V (~Heat V ~Fire)) V Fire (6.2 d)
<=> ~Smoke V ((~Heat V ~Fire) V Fire) (6.2 b)
<=> ~Smoke V (~Heat V (~Fire V Fire)) (6.2 b)
<=> ~Smoke V (~Heat V (Fire V ~Fire)) (6.2 d)
<=> ~Smoke V (~Heat V True) (6.2 o)
<=> (~Smoke V ~Heat) V True (6.2 b)
<=> True (Identity P V TºT)

g. Big V Dumb V (Big => Dumb)

Big	Dumb	Big => Dumb	Big V Dumb V (Big => Dumb)
TRUE	TRUE	FALSE	TRUE
TRUE	FALSE	FALSE	TRUE
FALSE	TRUE	TRUE	TRUE
FALSE	FALSE	TRUE	TRUE

Since the last column is all TRUE, this is a validsentence.

Using the equivalences from 6.2:

(Big V Dumb) V (Big Þ Dumb)
<=> (Big V Dumb) V (~Big V Dumb) (6.2 k)
<=> ((Big V Dumb) V ~Big) V Dumb (6.2 b)
<=> ((Dumb V Big) V ~Big) V Dumb (6.2 d)
<=> (Dumb V (Big V ~Big)) V Dumb (6.2 b)
<=> (Dumb V True) V Dumb (6.2 o)
<=> True V Dumb (Identity P V TºT)
<=> Dumb V True (6.2 d)
<=> True (Identity P V TºT)

h. (Big ^ Dumb) V ~Dumb

Big	Dumb	Big ^ Dumb	~Dumb	(Big ^ Dumb) V ~Dumb
TRUE	TRUE	TRUE	FALSE	TRUE
TRUE	FALSE	FALSE	TRUE	TRUE
FALSE	TRUE	FALSE	FALSE	FALSE
FALSE	FALSE	FALSE	TRUE	TRUE

Since the last column has both TRUE and FALSE, this sentence is neither valid nor unsatisfiable; it is satisfiable.

[Back to top]

3. (20 pts.) 6.8 We have defined four different binary logical connectives.

a. Are there any others that might be useful?
b. How many binary connectives can there possibly be?
c. Why are some of them not very useful?

Since each input to a binary connector is assigned to one of two possible logical values, True and False, there are 2 ² = 4 possible configurations of inputs. To calculate the total number of binary connectors, we note that the result of any input configuration may be True or False. Thus there are 4 ² = 16 different combinations of inputs and results.

The resulting combinations are below. The shaded meanings are the four binary logical connectives already defined.

P	T	T	F	F
Q	T	F	T	F	Meaning of Arg₁ a_k Arg₂
P a₁ Q	T	T	T	T	True	Tautology
P a₂ Q	T	T	T	F	Arg₁ Ú Arg₂	Disjunction
P a₃ Q	T	T	F	T	Arg₂ Þ Arg₁	Converse (can also express Inverse)
P a₄ Q	T	T	F	F	Arg₁
P a₅ Q	T	F	T	T	Arg₁ Þ Arg₂	Implication
P a₆ Q	T	F	T	F	Arg₂
P a₇ Q	T	F	F	T	Arg₁ Û Arg₂	Double Implication
P a₈ Q	T	F	F	F	Arg₁ Ù Arg₂	Conjunction
P a₉ Q	F	T	T	T	~(Arg₁ ^ Arg₂)	NAND
P a₁₀ Q	F	T	T	F	~(Arg₁ <=> Arg₂)
P a₁₁ Q	F	T	F	T	~(Arg₂)
P a₁₂ Q	F	T	F	F	~(Arg₁ => Arg₂)
P a₁₃ Q	F	F	T	T	~(Arg₁)
P a₁₄ Q	F	F	T	F	~(Arg₂ => Arg₁)
P a₁₅ Q	F	F	F	T	~(Arg₁ V Arg₂)	NOR
P a₁₆ Q	F	F	F	F	~(True) = False	Contradiction

As you can see, each connective can be defined in terms of primitives already in the language and the connectives that we already know. Some are useful, such as NAND and NOR. However, some are not very useful at all. For instance, instead of using connectors a₁, a₄, a₆, a₁₁, a₁₃, or a₁₆, I would use the simpler form, True, Arg1, Arg2, ~Arg₁, ØArg₂, or False, respectively.

[Back to top]

4. (20 pts.) 7.2 Represent the following sentences in first-order logic, using a consistent vocabulary (which you must define):

a. Not all students take both History and Biology
b. Only one student failed History.
c. Only one student failed both History and Biology.
d. The best score in History was better than the best score in Biology.
e. Every person who dislikes all vegetarians is smart.
f. No person likes a smart vegetarian.
g. There is a woman who likes all men who are not vegetarians.
h. There is a barber who shaves all men in town who do not shave themselves.
i. No person likes a professor unless the professor is smart.
j. Politicians can fool some of the people all of the time, and they can fool all of the people some of the time, but they can’t fool all of the people all of the time.

(for questions a–d):

Constants:

Biology: a specific course
History: a specific course

Predicates: (returns true or false)

Better(g ₁, g ₂): grade g ₁ is a “better” grade than grade g ₂.
Enrolled(s, c): student s is taking course c
Failing(g): grade g is a failing grade.
Student(s): s is a student

Functions:

Grade(s, c): the grade that student s earned for course c

(a.) Not all students take both History and Biology

Ø"s Student(s) => ( Enrolled(s, History) ^ Enrolled(s, Biology) )

$s Student(s) ^ (~Enrolled(s, History) V ~Enrolled(s, Biology) )

(b.) Only one student failed History.

$s₁ Student(s₁) ^ Enrolled(s₁, History) ^ Failing(Grade(s₁, History)) ^
("x (Student(x) ^ Enrolled(x, History) Ù Failing(Grade(x, History))) => s₁=x )

(c.) Only one student failed both History and Biology.

$s₁ Student(s₁) ^ Enrolled(s₁, History) ^ Failing(Grade(s₁, History)) ^
Enrolled(s₁, Biology) ^ Failing(Grade(s₁, Biology)) ^
("x (Student(x) ^ Enrolled(x, History) ^ Failing(Grade(x, History)) ^
Enrolled(x, Biology) ^ Failing(Grade(x, Biology))) => s₁=x )

(d.) The best score in History was better than the best score in Biology.

$s_h Student(s_h) ^ Enrolled(s_h, History) ^ "s_b (Student(s_b) ^ Enrolled(s_b, History))
=> Better(Grade(s_h, History), Grade(s_b, Biology))

(note that since we’re using ", we can’t just say Better(Grade(s_h,History),Grade(s_b,Biology)) since Grade(s_b,Biology) isn’t defined for non-students nor students who are not taking Biology. We could extend our definitions to include some kind of error for these undefined results(e.g. #N/A like in Excel), but we would also have to specify what Better(#N/A,anotherGrade) means and how that is handled in a ".)

(for questions e–g):

Constants: (no constants are necessary for the statement of the given sentences)

Predicates: (returns true or false)

Likes(x, y): x “likes” y. (“Dislikes” is ~Likes). x and y are not necessarily persons.
Man(x): the gender of x is male. Assume also that Person(x) is True. (Note that English generally acknowledges that “man” applies to humans; “male” would be the generic term.)
Person(x): x is a person
Smart(x): x is acknowledged as being smart. x is not necessarily a person. Smart(PussInBoots) is true where PussInBoots is a cat (and taking into account your answer to Russell & Norvig 1.10…)
Vegetarian(x): x is a vegetarian. x is not necessarily a person. Vegetarian(Trigger) is true where Trigger is a horse.
Woman(x): the gender of x is female. Assume also that Person(x) is True. (Note that English generally acknowledges that “woman” applies to humans; “female” would be the generic term.)

Functions: (no functions are necessary for the statement of the given sentences)

(e.) Every person who dislikes all vegetarians is smart.

"p ( Person(p) ^ ("v Person(v) ^ Vegetarian(v) => ~Likes(p, v) ) ) => Smart(p)

or, if this person dislikes anything that is a vegetarian (like horses and rabbits), then

"p ( Person(p) ^ "v Vegetarian(v) => ~Likes(p, v) ) => Smart(p)

(f.) No person likes a smart vegetarian.

Ø$p Person(p) ^ "v Person(v) ^ Vegetarian(v) ^ Smart(v) ^ Likes(p, v)

"p "v (Person(p) ^ Person(v) ^ Vegetarian(v) ^ Smart(v) ) => ~Likes(p, v)

(g.) There is a woman who likes all men who are not vegetarians.

$w Woman(w) ^ "m (Man(m) ^ ~Vegetarian(m)) => Likes(w, m)

(for question h):

Constants: (no functions are necessary for the statement of the given sentence)

Predicates: (returns true or false)

Barber(b): b is a barber. Assume that Person(b) is True. Note that the gender of b is unspecified.
LivesIn(x, t): x’s abode is in the town t. Person(x) is True.
Man(x): the gender of x is male. Assume also that Person(x) is True. (Note that English generally acknowledges that “man” applies to humans; “male” would be the generic term.)
Shaves(x, y): person x shaves person y. Person(x) and Person(y) are True.

Functions: (no functions are necessary for the statement of the given sentence)

(h.) There is a barber who shaves all men in town who do not shave themselves.

$b $t Barber(b) ^ LivesIn(b, t) ^
"x (Man(x) ^ LivesIn(x, t) ^ ~Shaves(x, x)) => Shaves(b, x)

An interesting exercise would be to make a FOPL sentence for the following:

“There is a barber who shaves only the men who do not shave themselves.”

$ b Barber(b) ^ " (m) Man(m) => (~Shaves(m,m) <=> Shaves(b,m))

Ah, but what if (m=b)? How can we have (~Shaves(b,b) <=> Shaves(b,b)) be true? We can’t. Which means that Man(b) is false – the barber is a Woman!

(for question i):

Constants: (no constants are necessary for the statement of the given sentence)

Predicates: (returns true or false)

Likes(x, y): x “likes” y. (“Dislikes” is ~Likes). x and y are not necessarily persons.
Person(x): x is a person
Professor(x): x is a professor. Person(x) is True.
Smart(x): x is acknowledged as being smart. x is not necessarily a person. Smart(PussInBoots) is true where PussInBoots is a cat (and taking into account your answer to Russell & Norvig 1.10…)

Functions: (no functions are necessary for the statement of the given sentence)

(i.) No person likes a professor unless the professor is smart.

"x "y (Person(x) ^ Professor(y) ^ ~Smart(y)) => ~Likes(x, y)

~ $x $y Person(x) ^ Professor(y) ^ ~Smart(y) ^ Likes(x, y)

(for question j):

Constants: (no constants are necessary for the statement of the given sentence)

Predicates: (returns true or false)

Fools(x, y, t): x fools y at time t. x and y are not necessarily people.
Person(x): x is a person
Politician(p): p is a politician. Note that Person(p) is True (although there are some that would disagree…)

Functions: (no functions are necessary for the statement of the given sentence)

(j.) Politicians can fool some of the people all of the time, and they can fool all of the people some of the time, but they can’t fool all of the people all of the time.

"w Politician(w) =>
($x "t₁ Person(x) ^ Fool(w, x, t₁)) ^
($t₂ "y Person(y) Þ Fool(w, y, t₂)) ^
~ ("z "t₃ Person(z) => Fool(w, z, t₃)) )

[Back to top]

5. (20 pts.) Consider a First-order logical system which uses two 1-place predicates; namely, Big and Small . The set of object constants is given by a , b . Enumerate all possible models in this case. For each of the following sentences, identify the models in which the given sentence is true.

Big(a) ^ Big(b)
Big(a) V Big(b)
"x Big(x)
"x ~Big(x)
$x Big(x)
$x ØBig(x)
"x Big(x) ^ Small(x)
"x Big(x) V Small(x)
"x Big(x) => ~Small(x)

All possible models: (Since there are 4 atomic predicates, there will be 2 ⁴ = 16 models.)

M ₀ = { }
M ₁ = { Big(a) }
M ₂ = { Big(b) }
M ₃ = { Small(a) }
M ₄ = { Small(b) }
M ₅ = { Big(a), Big(b) }
M ₆ = { Big(a), Small(a) }
M ₇ = { Big(a), Small(b) }
M ₈ = { Big(b), Small(a) }
M ₉ = { Big(b), Small(b) }
M ₁₀ = { Small(a), Small(b) }
M ₁₁ = { Big(a), Big(b), Small(a) }
M ₁₂ = { Big(a), Big(b), Small(b) }
M ₁₃ = { Big(a), Small(a), Small(b) }
M ₁₄ = { Big(b), Small(a), Small(b) }
M ₁₅ = { Big(a), Big(b), Small(a), Small(b) }

Models in which the given sentences are true:

M₀

M₁

M₂

M₃

M₄

M₅

M₆

M₇

M₈

M₉

M₁₀

M₁₁

M₁₂

M₁₃

M₁₄

M₁₅

Big(a) ^ Big(b)

Big(a) V Big(b)

"x Big(x)

"x ~Big(x)

$x Big(x)

$x ~Big(x)

"x Big(x) ^ Small(x)

"x Big(x) V Small(x)

"x Big(x) => ~Small(x)

[Back to top]

6. (20 pts.) Determine whether the expressions p and q unify with each other in each of the following cases. If so, give the most general unifier; if not, give a brief explanation. (Assume that the upper-case letters are (object, predicate, or function) constants and that the lower-case letters are variables.)

a. p = F(G(v), H(u, v)); q = F(w, J(x, y))
b. p = F(x, F(u, x)); q = F(F(y, A), F(z, F(B, z)))
c. p = F(x ₁, G(x ₂, x ₃), x ₂, B); q = F(G(H(A, x ₅), x ₂), x ₁, H(A, x ₄), x ₄)

a. Unify:

p = F(G(v), H(u, v)) and q = F(w, J(x, y))

Can’t be unified since the second arguments, H and J, are different constants.

b. Unify:

p = F(x, F(u, x)) and q = F(F(y, A), F(z, F(B, z)))

s = { F(y, A) | x } -> p = F(F(y, A), F(u, F(y, A))) q = F(F(y, A), F(z, F(B, z)))

{ B | y } -> p = F(F(B, A), F(u, F(B, A))) q = F(F(B, A), F(z, F(B, z)))

{ A | z } -> p = F(F(B, A), F(u, F(B, A))) q = F(F(B, A), F(A, F(B, A)))

{ A | u } -> p = F(F(B, A), F(A, F(B, A))) q = F(F(B, A), F(A, F(B, A)))

s = { F(y, A)|x , B|y , A|z, A|u } -> { F(B, A)|x , B|y , A|z, A|u }

c. Unify:

p = F(x ₁, G(x ₂, x ₃), x ₂, B) and q = F(G(H(A, x ₅), x ₂), x ₁, H(A, x ₄), x ₄)

s = { G(H(A, x ₅), x ₂) | x ₁ } -> p = F(G(H(A, x ₅), x ₂), G(x ₂, x ₃), x ₂, B) , q = F(G(H(A, x ₅), x ₂), G(H(A, x ₅), x ₂), H(A, x ₄), x ₄)

{ H(A, x ₅) | x ₂ } -> p = F(G(H(A, x ₅), H(A, x ₅)), G(H(A, x ₅), x ₃), H(A, x ₅), B) , q = F(G(H(A, x ₅), H(A, x ₅)), G(H(A, x ₅), H(A, x ₅)), H(A, x ₄), x ₄)

{ H(A, x ₅) | x ₃ } -> p = F(G(H(A, x ₅), H(A, x ₅)), G(H(A, x ₅), H(A, x ₅)), H(A, x ₅), B) , q = F(G(H(A, x ₅), H(A, x ₅)), G(H(A, x ₅), H(A, x ₅)), H(A, x ₄), x ₄)

{ x ₅ | x ₄ } -> p = F(G(H(A, x ₅), H(A, x ₅)), G(H(A, x ₅), H(A, x ₅)), H(A, x ₅), B) , q = F(G(H(A, x ₅), H(A, x ₅)), G(H(A, x ₅), H(A, x ₅)), H(A, x ₅), x ₅)

{ B | x ₅ } -> p = F(G(H(A, B), H(A, B)), G(H(A, B), H(A, B)), H(A, B), B) , q = F(G(H(A, B), H(A, B)), G(H(A, B), H(A, B)), H(A, B), B)

s = { G(H(A, x ₅), x ₂)|x _{1 ,} H(A, x ₅)|x ₂ , H(A, x ₅)|x ₃ , x ₅|x ₄ , B|x ₅ } ->{ G(H(A, B), H(A, B))|x _{1 ,} H(A, B)|x ₂ , H(A, B)|x ₃ , B|x ₄ , B|x ₅ }

[Back to top]

7. (20 pts.) Put the following FOPL formulas into clause form (CNF).

a. "x "y ( (P(x) ^ Q(y)) Þ $z R(x, y, z) )

b. $x "y $z (P(x) => (Q(y) => R(z)) )

Strategy Steps:

0. Original sentence
1. Remove implication: P => Q º ~P V Q
2. Push ~ to atomic level using de Morgan’s Laws:
    Ø(P ^ Q) º ~P V ~Q
    ~(P V Q) º ~P ^ ~Q
    Ø" x f(x) º $ x ~f(x)
    Ø$ x f(x) º " x ~f(x)
3. Remove double negation:~ ~P º P
4. Standardize quantified variables so unique names: "x f(x) º "y f(y)
5. Since now unique variable names, can move quantifiers to start of expression.
6. Eliminate $ quantifiers using Skolemization. Note that Skolem function is over variables corresponding to " quantifiers that are to the left of the $ quantifier.
7. Drop the " quantifiers, keeping in mind that all variables are now universally quantified.
8. Distribute V over ^ P V (Q ^ R) º (P V Q) ^ (P V R)
9. Write each conjunct as a separate clause, renaming variables.
10. Convert to imperative normal form (INF)
   a. Group negated terms to left (disjunction is commutative and associative).
   b. Convert disjunction of negated terms to a negation of a group of conjuncts.
   c. Add implication.

a. "x "y ( (P(x) ^ Q(y)) => $z R(x, y, z) ) (Step 0)
º "x "y ( ~(P(x) ^ Q(y)) V $z R(x, y, z) ) (Step 1)
º "x "y ( (~P(x) V ~Q(y)) V $z R(x, y, z) ) (Step 2)
º "x "y $z ( (~P(x) V ~Q(y)) V R(x, y, z) ) (Step 5)
º "x "y ( (~P(x) V ~Q(y)) V R(x, y, Skf(x,y)) ) (Step 6–$z is in scope of "x and "y)
º (~P(x) V ~Q(y)) V R(x, y, Skf(x,y)) (Step 7)
º ~(P(x) ^ Q(y)) V R(x, y, Skf(x,y)) (Step 10b)
º (P(x) ^ Q(y)) => R(x, y, Skf(x,y)) (Step 10c)

b. $x "y $z (P(x) Þ (Q(y) => R(z)) ) (Step 0)
º $x "y $z (~P(x) V (Q(y) => R(z)) ) (Step 1)
º $x "y $z (~P(x) V (~Q(y) V R(z)) ) (Step 1)
º "y $z (~P(A) V (~Q(y) V R(z)) ) (Step 6–$x is not in scope of any ")
º "y (~P(A) V (~Q(y) V R(Skf(y))) ) (Step 6–$z is in scope of "y)
º ~P(A) V (~Q(y) V R(Skf(y))) (Step 7)
º (~P(A) V ~Q(y)) V R(Skf(y)) (Step 10a)
º ~(P(A) ^ Q(y)) V R(Skf(y)) (Step 10b)
º (P(A) ^ Q(y)) => R(Skf(y)) (Step 10c)

[Back to top]

8 .(20 pts.) Consider the following information:

Animals can outrun any animals that they eat.
Carnivores eat other animals.
Outrunning is transitive; i.e. if x can outrun y and y can outrun z , then x can outrun z .
Lions eat zebras.
Zebras can outrun dogs.
Dogs are carnivores.

a. Translate each of the above sentences into FOPL.
b. Translate the resulting set of FOPL sentences into clause form (CNF).
c. Use resolution theorem proving using the set of support strategy and Green’s trick for answer extraction to find two animals that lions can outrun.

Constants:

Dog: a specific class of animal. This implies that Animal(Dog) is true.
Lion: a specific class of animal. This implies that Animal(Lion) is true.
Zebra: a specific class of animal. This implies that Animal(Zebra) is true.

Predicates: (returns true or false)

Animal(x): x is classified as an animal.
Carnivore(x): x is a carnivore. A carnivore is a “flesh-eating animal,” so Animal(x) must also be true.
Eat(x, y): x eats y. x and y do not necessarily have to be animals (although in this question, all of the base cases are animals.
OutRun(x, y): x can outrun y. x and y do not necessarily have to be animals (although in this question, all of the base cases are animals.

(a) FOPL statements

0. (from the constant and predicate definitions)

0.1. Animal(Dog)

0.2. Animal(Lion)

0.3. Animal(Zebra)

0.4. "x Carnivore(x) => Animal(x)

1. Animals can outrun any animals that they eat.
"x Animal(x) => "y (Animal(y) ^ Eat(x, y) ) => OutRun(x, y)

2. Carnivores eat other animals.
"x Carnivore(x) => $y Animal(y) ^ Eat(x, y)

3. Outrunning is transitive; i.e. if x can outrun y and y can outrun z, then x can outrun z.
"x "y "z OutRun(x, y) ^ OutRun(y, z) => OutRun(x, z)

4. Lions eat zebras.
Eat(Lion, Zebra).

5. Zebras can outrun dogs.
OutRun(Zebra, Dog)

6. Dogs are carnivores.
Carnivore(Dog)

(b) CNF statements

0. (from the constant and predicate d