Grading scheme (out of 100%)
Choose either Exercise 7.4 (choose any five from the list of twelve) or Exercise 6.10 (50%) 7.4 Which of the following are correct?
False |= True.
True |= False.
(A∧B) |=(A ⇔ B).
A⇔B|=A∨B.
A ⇔ B |=¬A∨B.
(A∧B) ⇒ C |= (A ⇒ C)∨(B ⇒ C).
(C∨(¬A∧¬B)) ≡ ((A ⇒ C)∧(B ⇒ C)).
(A∨B)∧(¬C∨¬D∨E) |=(A∨B).
(A∨B)∧(¬C∨¬D∨E) |=(A∨B)∧(¬D∨E).
(A∨B)∧¬(A ⇒ B) is satisfiable.
(A ⇔ B)∧(¬A∨B) is satisfiable.
(A ⇔ B) ⇔ C has the same number of models as (A ⇔ B) for any fixed set of proposition symbols that includes A, B, C.
6.10 Generate random instances of map‐coloring problems as follows: scatter n points on the unit square; select a point X at random, connect X by a straight line to the nearest point Y such that X is not already connected to Y and the line crosses no other line; repeat the previous step until no more connections are possible. The points represent regions on the map and the lines connect neighbors. Now try to find k‐colorings of each map, for both k = 3 and k = 4, using min‐conflicts, backtracking, backtracking with forward checking, and backtracking with MAC. Construct a table of average run times for each algorithm for values of n up to the largest you can manage. Comment on your results.
Choose either Exercise 6.1 or Exercise 7.10 (35%)
6.1 How many solutions are there for the map‐coloring problem in Figure 6.1? How many solutions if four colors are allowed? Two colors?
7.10 Decide whether each of the following sentences is valid, unsatisfiable, or neither. Verify your decisions using truth tables or the equivalence rules of Figure 7.11 (page 249).
Smoke ⇒ Smoke
Smoke ⇒ Fire
(Smoke ⇒ Fire) ⇒ (¬Smoke ⇒ ¬Fire)
Smoke ∨ Fire ∨ ¬Fire
((Smoke ∧ Heat) ⇒ Fire) ⇔ ((Smoke ⇒ Fire) ∨ (Heat ⇒ Fire))
(Smoke ⇒ Fire) ⇒ ((Smoke ∧ Heat) ⇒ Fire)
Big ∨ Dumb ∨ (Big ⇒ Dumb)
Exercise 7.25 (15%)
Write a successor‐state axiom for the Locked predicate, which applies to doors, assuming the only actions available are Lock and Unlock .
