Homework Assignment 4
CSE 512
Problem 1: Use resolution refutation in order to prove the propositional sentence
¬Light5 => (¬ (Light7 & Light2))
from the given set of premises:
¬Light2 => Light1
Light4 => Light3
Light5 => (Light1 & Light4)
¬Light6 => ¬Light2
Light7 => ¬Light6
Show all details of CNF conversion followed by resolution refutation (also with all details).
For resolution refutation, each step of resolution should be displayed in a manner similar to the
following hypothetical step.
5. <come clause> with 17. <some other clause>
→ <new running #> <the resolvent clause>
Remember that each clause can participate in any number of resolution steps. Each new
resolvent is simply added with a new number for reference in future resolution steps.
Repeat this exercise for the same set of given premises, but this time, prove that
¬Light3 => (¬Light4 & ¬Light5)
Problem 2. Apply the inductive learning algorithm from the Week 9 and 10 lectures in order to
learn the rules which cover the data in the given table. Instances are described in terms of
attributes A, B, C, and C. The decision variable is ‘ok’; positive instances have ok=1 and negative
instances have ok=0.
Show all details of inductive learning, in particular, the steps of successive rule refinement and
the ratios that drive it. Explicitly state, when a new rule has been learned, and when or whether
additional rules are needed to cover the training instances.
id A B C D ok
1 1 0 1 1 0
2 1 1 0 1 1
3 1 1 0 0 0
4 1 1 0 1 1
5 1 0 0 0 0
6 0 1 1 1 1
7 0 1 0 1 1
8 0 1 0 0 0
9 0 1 0 1 1
10 0 0 0 0 0
This assignment is due on Thursday, March 14, 2019, at the very beginning of the lecture. We
will go over the solutions in class.
