Assignment  #3
CSE P573 Autumn 2004 - Applications of Artificial Intelligence
Due: October 25

Readings for Week 3 (Logic & Prolog):

If you have time & interest, you can read Chapters 7 to 9 straight through. But following are the sections we will actually be using, so at least skim them:

• Sec 7.3
• Sec 7.4, up to page 207
• Part of Sec 7.5, from page 213 to top of 217
• Sec 8.2 
• Sec 9.1
• Sec 9.2 up to page 277
• Sec 9.4
• Sec 9.5 up to page 300

Exercises:

Turn in hardcopy in class.  Written exercises should be typed or neatly handwritten.  R&N = Russell & Norvig, Artificial Intelligence, A Modern Approach, 2nd Ed.

1.  Finish and turn in the Prolog exercise begun in class, with the following extra features:

Imagine that you have just been hired by snacks.com, an Internet startup that provides snacking recommendations. Your first assignment is to create an expert system that will recommend snacks according to the following rules: Every snack should contain one beverage and one munchie. Sweet beverages are good with salty munchies. Bitter beverages are good with sweet munchies or salty munchies. Define a predicate snack(X,Y).  Show all the recommendations it makes from the following database of ground facts:

sweet(coke).
sweet(shake).
sweet(marshmellows).
sweet(chocolate).
salty(pretzels).
salty(fries).
bitter(beer).
bitter(coffee).
beverage(coke).
beverage(shake).
beverage(beer).
beverage(coffee).
munchie(marshmellows).
munchie(chocolate).
munchie(pretzels).
munchie(fries).

Your boss is delighted, but tells you to modify the program to take into account the following constraints:

• Because of a lawsuit from the American Heart Association, every recommended snack must contain at least one low fat food. Low fat foods include marshmellows, pretzels, beer, coffee, and Coke.
• Premium subscribers to snack.com should be able to access a special list of convenient snacks. A convenient snack is one where both the beverage and the munchie can be purchased at the same store. For example,
• Dicks sells Coke, shakes, and fries.
• Starbucks sells coffee and chocolate.
• The Hub sells Coke, pretzels, and chocolate.
• The Blue Moon sells beer and pretzels.

Show the modified program and its new recommendations. You should cleanly separate assertions about the properties of particular food items from general rules about snacks.

2. R&N 7.11, parts a, b, and c.  "DPPL" refers to the Davis-Putnam procedure briefly described in the first lecture, which tests whether or not a set of clauses in satisfiable.  But nothing in your answer needs to make use of the details of Davis-Putnam: you should just consider it to be a "black box" which which determines satisfiability.

3. R&N 9.11, by doing a resolution proof by hand.

4. Extra Credit:  In 1901, the philosopher Bertrand Russell set the world of mathematics on its ear by pointing out that earlier attempts to write down a logic for set theory were inconsistent.  Recreate his paradox by translating the following into logic using the predicate "member" and the constant term "S", and then deriving a contradiction by resolution.  (The proof is extremely short but surprisingly tricky to get right.)

• If something is not a member of itself, then it is a member of S.
• If something is a member of S, then it is not a member of itself.
• Either S is a member of S, or S is not a member of S.

Readings for Week 4 (Natural Language Processing)

Read R&N Chapter 22.  Read the first two sections 22.1 and 22.2 carefully.  Test your understanding by asking yourself what each of the following means: formal language; grammar; phrase structure; lexicon; parse tree; open/closed class words.  Skim the following sections through 22.7.  In class we will concentrate on material related to section 22.4 and a bit of 22.5.  You can skip 22.7 and 22.8 entirely.