Assignment 3 - CSE 473 - Autumn 2003

Work should be turned in at the start of class on the indicated dates.

1.  Due Friday, Oct 17: Read & Summarize: R&N section 7.6 (Effective Propositional Inference).

2. Due Monday, Oct 20: Written Exercises:

(2.1) Translate the following sentences into propositional logic. Specify a single set of simple propositions that are used by the sentences, and indicate the intended meaning of each. After translating each directly into logic convert the formulas into conjunctive normal form.

(2.1.1) It will snow tomorrow, and if the kumquats are in blossom the crop will be ruined.

(2.1.2.) If it snows tomorrow and the kumquats are in blossom, then the crop will be ruined.

(2.1.2) If it snows or freezes tomorrow, then if the kumquats are in blossom and are unprotected, then the crop will be ruined unless a miracle occurs.

(2.2) For each of the following pairs of formulas shade the area of the Venn diagram that contains truth-assignments that make formula “A” true with horizontal lines, and shade the area that makes formula “B” true with vertical lines. Then indicate whether or not formula A entails formula B.

Example: [A] [B] Does [A] entail [B]? YES

(2.2.1) [A] [B] Does [A] entail [B]?

(2.2.2) [A] [B] Does [A] entail [B]?

(2.2.3) [A] [B] Does [A] entail [B]?

(2.2.4) [A] [B] Does [A] entail [B]?

(2.3) A Latin Square of Order N is an N by N grid where each cell is filled with an integer between 1 and N such that no integer is repeated in any row or any column. Show how the problem of finding a Latin Square can be encoded as a propositional satisfiability problem. Use propositional schemas to describe the large set of formulas required. It is okay to use inequality in the schema quantifier, for example:

would instantiate to the set of formulas P(i,j) where i and j take on all pairs of values from 1 to n except for the cases where i=j. Similarly it is okay to use < or > in the schema quantifiers.

When the schemas are instantiated, how many different propositions appear? What is the total size of the instantiated problem, counting all the propositions that appear in all the formulas?

3. Due Wednesday, Oct 22: Read & Summarize the follow three sections. (This is the order in which we will discuss the material.)

· R&N page 211 (Reasoning Patterns in Propositional Logic) up to page 217 (stop before Completeness of Resolution).

· R&N page 9.2 (Unification and Lifting) up to page 278 (stop before Storage and Retrieval).

· R&N 8.4 (Knowledge Engineering in First Order Logic).

Looking ahead

Topics to be discussed in class this week and next:

· Wednesday Oct 15 - Introduction to Propositional Logic

· Friday Oct 17 - Algorithms for Reasoning with Propositional Logic

· Monday Oct 20 - First feedback on planning project, and discussion of the written exercises due that day. Jeffrey Bigham will run the class. I will be in upstate New York running a workshop on “Mixed Initiative Decision Making Systems” for the Air Force.

· My Tuesday Oct 21 office hours are changed to 11:00-12:00 on Thursday Oct 23, again due to the workshop.

· Wednesday Oct 22 - Applications of satisfiability testing to hardware and software verification and diagnosis of complex systems.

· Friday Oct 24 - Games!

Following games we will cover probabilistic reasoning and machine learning. The final programming project will be to build a spam e-mail filter using machine learning. This will require you to collect a sample of your own e-mail for training, the larger the better. Therefore you should start saving a copy of all the email you receive, one set of “good” email, and one set of spam. Because you may be receiving very little spam due to the effectiveness of the spam filters already in place in the university e-mail system, we will provide additional examples of spam for the project.