QUESTIONS FOR WRITTEN ASSIGNMENTS

$2\mathrm{.}1$ Assessment $2$

Question $1(20)$

Use the method of analytic tableaux to show that the following formulas have the corresponding

properties:

$($i$)($p $$ q$)($p $$ q$)$ satisfiable

$($ii$)(($p $->$ q$)($q $->$ r$))->($p $->$ r$)$ valid

Do not apply the formal algorithm $($Alg$.3\mathrm{.}15),$ just use the method of analytic tableaux described at

the beginning of $3\mathrm{.}3$ of the prescribed book.

Question $2(10)$

Convert the formula $($p $->$q$)($p $->$ q$)$ to clausal form. Show all the steps.

Question $3(10)$

Use resolution to show that the set of clauses $\{\{$p$,$ q$,$ r$\},\{$p$,$q$\},\{$p$,$ q$,$r$\},\{$p$,$q$,$ r$\}\}$ is satisfiable.

Show all the steps, including the numbers of clauses to which the resolution rule is applied.

Question $4(10)$

Prove the following proposition $($a rephrasing of Prp$.3\mathrm{.}38)$:

An interpretation I is a model of a set of formulas U iff I satisfies the set of clauses

comprising the union of the clausal forms of the formulas in U $.$

$3$

Question $5(10)$

Use resolution to show that the entailment $\{$p $->($q $->$ r$),($s $->($s $->$ r$))->$ p$\}|=($p $->$ q$)->$ r

holds.

Show the steps to convert the formulas to their necessary clausal forms, as well as the application

of resolution.

Question $6(20)$

Use the DPLL procedure to show that the following sets of clauses have the corresponding properties:

$($i$)\{\{$p$,$ q$,$s$\},\{$q$\},\{$r$\},\{$p$,$ q$,$r$,$ s$\}\}$ satisfiable

$($ii$)\{\{$p$\},\{$p$,$ r$,$ s$\},\{$q$,$r$\},\{$p$,$ q$,$r$\},\{$r$,$s$\}\}$ unsatisfiable

Explain each step, showing the set of clauses after each propagation, and explain why the output

indicates the required property.

Question $7(10)$

Consider the discussion of the complexity of the DPLL algorithm given in $3\mathrm{.}6\mathrm{.}4.$

$1.$ Check the time complexity analysis by showing how the DPLL algorithm will deal with a set

of clauses involving $3$ propositional symbols, as specified for the worst case. Execute the DPLL

algorithm. Count and state the number of clauses, the number of choice points and the number

of inspections to verify the given formulas.

$2.$ Devise a way to mark the clauses and literals in a set of clauses to allow the DPLL algorithm

to attain a space complexity of O$($n$).$

$3.$ Count the number of inspections involved in a single branch, that the non$-$deterministic analysis

would require as described in the final section of the $3\mathrm{.}6\mathrm{.}4.$