Assignment 4 – CSE 473 Introduction to AI – Fall 2003

  1. Read & Summarize: R&N 9.4 (pages 287-295).  Due Monday, October 27th.  This material is the basis for Prolog, a programming language based on logic.  R&N separate the discussion of backward-chaining from the discussion of resolution, but we will see in class how backward-chaining is simply a special case of resolution.

 

  1. Read & summarize R&N Chapter 6 (Adversarial Search), (at least) up to the end of section 6.4.  Due Wednesday, October 29th.  We will be covering this entire chapter, so if you would like to get a head start on the next assignment you can go ahead and summarize the entire chapter. 

  2. Written exercise: Due Wednesday, October 29th.  Encode the problem of determining if the following two circuits compute the same function by writing a formula in propositional logic that is satisfiable if and only if the circuits are not equivalent.  Follow the approach used in the lecture slides from October 22nd.

    The left circuit is a 1-bit adder implemented using XOR and AND gates.  The right circuit is an adder implemented using only NAND gates.  Note that each circuit has two outputs, the low order bit and the high order bit.  Think carefully about how to assert that the circuits are not equivalent.



  3. Written exercise: Due Wednesday, October 29th.  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:
    1. Every snack should contain one beverage and one munchie.
    2. Sweet beverages are good with salty munchies.
    3. Bitter beverages are good with sweet munchies or salty munchies.

Fortunately you know Prolog.  Ten minutes after getting the assignment you have implemented the following Prolog program:

 

snack(B,M) :- beverage(B),munchie(M),goeswith(B,M).

goeswith(B,M) :- sweet(B),salty(M).

goeswith(B,M) :- bitter(B),sweet(M).

goeswith(B,M) :- bitter(B),salty(M).

 

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:

 

c.  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.

 

d. 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.  You should cleanly separate assertions about the properties of particular food items from general rules about snacks.