Title PredCalculusPractice 59.3 KB 7
##### Document Text Contents
Page 1

First-Order Logic Practice Questions & Answers

This exercise is not graded and you will not turn it in. These are practice questions (done and discussed in-class)
to get you used to writing in first order logic.

Convert to English
1. x IsABunny(x) IsCute(x)

All bunnies are cute

2. x IsAStudent(x) IsTakingAI(x) IsCool(x)

Everyone student who is taking AI is cool

3. x IsABunny(x) IsAStudent(x) IsTakingAI(x) IsCute(x) IsCool(x)

Every bunny who is a student taking AI is cute and cool

Everyone who eats ramen is either homeless or a graduate student

5. s h IsAStudent(s) IsTaking(s,AI) HomeworkFor(h,AI) ¬Hates(s,h)

There is at least one student who doesn’t hate (any of) the AI homework

6. a (IsACat(a) Rules(a)) (IsADog(a) Drools(a))

Cats rule and dogs drool

7. p time base isACaptain(captain) isABase(base) <(time, Now)

Owns(captain, base, time) Owns(CATS, base, Now)

All the bases that belonged to Captain now belong to CATS

8. =(2,2)

2=2

9. +(2, 2) 4

2+2=4

10. 2 + 2 4

2+2=4

Page 2

Convert to English and Predicate Calculus
11. Convert to English and FOL

for (i=0; i<numObjects; i++)
{
Object x = Objects(i);
if isMushroom(i)
if isPoisonous(x) && isPurple(x)
return false;
}
return true;

There are no mushrooms that are poisonous and purple
x Mushroom(x) ¬(Poisonous(x) Purple(x))

12. Convert to English and FOL

for (i=0; i<numObjects; i++)
{
Object x = Objects(i);
if isMushroom(i) && isPoisonous(x) && isPurple(x)
return true;
}
return false;

There is a mushroom that is purple and poisonous
x Mushroom(x) Poisonous(x) Purple(x)

Convert to First-Order Logic
13. There is a bunny who is a cute

x IsABunny(x) IsCute(x)

14. Elder gods do not like Hello Kitty

x IsAnElderGod(x) ¬Likes(x, HelloKitty)

x,y SisterInLaw(x,y) z Female(x) Spouse(y,z) Siblings(x,z)

16. There is only one Elvis (do not use !)

x IsElvis(x) y IsELvis(y) x=y

In class there was some discussion as to whether the approach i showed in class was correct. As everyone
figured, it wasn’t (i was comparing predicates, which are bools, instead of objects). Above is the correct syntax.

17. Every child who has a Chinpokomon card is cool

x,y Child(x) ChinpokomonCard(y) Owns(x,y) Cool(x)

Page 3

18. Some students took AI1 in Spring 2008 (using Take(person, course, semester))

x Student(x) Takes(x, AI1, Spring2008)

19. Every student who takes AI1 passes it

x,y Student(x) Semester(y) Takes(x, AI1, y) Passes(x, AI1, y)

The y in the above sentence (the semester the course was taken) is used because we defined our predicate to
take a time parameter in question 18. Including it with Passes wasn’t necessary but was done the same way for
consistency.

Page 4

First-Order Logic Practice Questions
Second Wave

In the sentences below, a symbol is missing. What symbol is it most likely to be?
20. x Something(x) ??? SomethingElse(x)

The general rule is, goes with , goes with . The questions in the next section show why.

21. x Something(x) ??? SomethingElse(x)

The general rule is, goes with , goes with . Questions 24-27 show why.

Is this correctly written?
22. Peter has at least two children.
x,y ParentOf(Peter, x) ParentOf(Peter, y)

No.

Consider the array of kids [Alice, Bob, Charles]. Peter is the father of Alice and no one else. Now consider the
equivalent C (pseudo)code

//--- Look for first match
for (x=0; x<numKids; x++)
if isParent(Peter, kids[x])
match1Found = true;

//--- Now look for a second match
for (y=0; y<numKids; y++)
if isParent(Peter, kids[y])
match2Found = true;

return match1Found && match2Found;

The first loop will find Alice ( x ParentOf(Peter, x)) at x=0 and the second loop will also find Alice
( x ParentOf(Peter, y)) at y=0. You’ve basically double-counted someone. The universal and
existential quantifiers loop through all objects to match a variable and do so independently of any other
quantifier or variable. If you don’t want to double count something, you have to check for it yourself. So the
correct version of the above is

x,y ParentOf(Peter, x) ParentOf(Peter, y) ¬(x=y)

23. Someone at Stanford is smart
x At(x, Stanford) isSmart(x)

Yes, this one is fine.

Page 5

Convert to English
24. x At(x, Berkeley) isSmart(x)

Everyone at Berkeley is smart.

If you’re wondering why i used Berkeley it’s because this is one of the rare occasions that i used someone else’s
example, in this case Russel and Norvig. You can guess what school one of the authors is from.

25. x At(x, Berkeley) isSmart(x)

Everyone is at Berkeley. Everyone is smart.

This is probably not what you wanted to write. It’s also a very common mistake. Remember – use with ,
not .

26. x At(x, Stanford) isSmart(x)

Contrary to what many people think, this statement does not say that there is a person at Stanford who is smart.
It says that if there is at least one person who, if he is at Stanford, is also smart. And if he isn’t, who knows.
While it’s possible the author meant this, in most cases this is an error. Remember – use with , not .

Applying implication elimination, you could also write:

x ¬At(x, Stanford) isSmart(x)
which means there exists at least one person who either doesn’t go to Stanford or who is smart (whether he’s at
Stanford or not).

If you build a truth table for this statement you’ll find that it is false when someone attends Stanford and none
of them are smart and is true all other times - if there is someone at Stanford who is smart and if nobody attends
Stanford. Implicative rules are always true if the antecedent – the if part – is false, with the reasoning that you
can’t test the rule and as a result can’t violate it.

27. x At(x, Stanford) isSmart(x)

There is someone who goes to Stanford and is smart.

Presumably this was Maria. But she’s here now so we can no longer verify that the above sentence is true.

28. x,y Loves(x, y)

Everybody loves everybody

29. x y Loves(x, y)

Everyone loves at least one person.

Page 6

30. x y Loves(x, y)

There is at least one person who loves everyone

Hopefully you’ve noticed that the above three sentences are identical other than the quantifiers.

Are these valid? (remember, valid = always true)
31. x y Loves(x, y) x y Loves(x, y)

The question is asking, is “everyone loves someone” the same as “there is at least one person who loves
everybody”. While this is satisfiable, it is not valid.

32. x Loves(x, Snoopy) ¬ x ¬Loves(x, Snoopy)

This question is asking, is “everyone loves Snoopy” the same as “there is not a single person who doesn’t love
Snoopy”. These are exactly the same thing.

In general, x P(x) and ¬ x ¬P(x) are equivalent. But one is shorter to write.

33. x Loves(x, AmericanIdol) ¬ x ¬Loves(x, AmericanIdol)

This question is asking, is “there is at least one person who loves American Idol” the same as “not everybody
hates American Idol” (assuming you consider not loves and hate to be the same thing; it sounds better than “not
everyone doesn’t love American Idol”). These are exactly the same thing.

In general, x P(x) and ¬ x ¬P(x) are equivalent. But one is shorter to write.

34. x,y P(x, y) P(y, x)

This question is asking, are all predicates P(x,y) the same as P(y,x) (the same statement with arguments
reversed). This is not valid (i.e., always true). For example, reversing the arguments isn’t important in
Sibling(Meg, Chris) and Sibling(Meg, Chris) but is it for Parent(Peter, Meg) and
Parent(Meg, Peter).

35. x,y x=y

Yes, this is valid (always true).

Is there at least one value for x that is the same as the value for y? As mentioned in question 22, x and y could
represent the exact same variable. If our set of objects is [apple, orange], looping through all of the objects will
make x=apple once and y=apple once.

36. x,y x=y

Is every single object the exact same as every other object? Normally, no. If you have only one object in the
world, this would be true but otherwise this is unsatisfiable.