Assignment 4 – CSE 473 Introduction
to AI – Fall 2003
- 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.
- 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.
- 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.
- 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:
- 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.
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.