This is an old revision of the document!
Homework 04 -DRAFT
Problem 1
Consider the definitions of interpolants in Interpolation for Propositional Logic from lecture06. Prove properties 1,2,3,4 for and
.
Problem 2
Build a DPLL SAT solver that accepts input in the CNF version of the DIMACS format. (The input file is a formula in conjunctive normal form, where each clause is given on a separate line as a list of indices denoting propositional variables, a negative index indicates a negated propositional variable.)
If a given formula is satisfiable, the SAT solver should produce an assignment to all variables such that the formula evaluates to true under this assignment.
If a given formula is unsatisfiable, the SAT solver can simply say “false”.
The expected level of sophistication is a DPLL solver with unit propagation, additional techniques will be part of the next homework.