Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in

Exercise sheet 5

Resolution

Computing resolvents, refuting to prove a consequence, and saturating to show that a set is satisfiable. Chapter 5.

Solution
  1. On $p$: $q \lor r \lor \lnot s$. It is the only one.
  2. On $p$: $q \lor \lnot q$; on $q$: $p \lor \lnot p$. Two tautologies, useless. No $\square$: one does not resolve on two literals at once, and these two clauses are satisfiable together ($p = 1, q = 0$).
  3. None: no literal together with its opposite.
  4. $\square$.
Solution

Let $v$ be a model of the two clauses. If $v(p) = 1$, $\lnot p$ is false, so $D$ is true; if $v(p) = 0$, $p$ is false, so $C$ is true. In both cases $C \lor D$ is true in $v$.

Solution
  1. Clauses: $\lnot p \lor q$, $\lnot q \lor r$, and $\lnot(p \to r) \equiv p \land \lnot r$ gives $p$ and $\lnot r$. Then $p$ and $\lnot p \lor q$: $q$; $q$ and $\lnot q \lor r$: $r$; $r$ and $\lnot r$: $\square$.
  2. We refute the negation: $(\lnot p \lor q \lor r) \land (\lnot q \lor r) \land p \land \lnot r$. Clauses: $\lnot p \lor q \lor r$, $\lnot q \lor r$, $p$, $\lnot r$. Then $p$ with the first: $q \lor r$; with $\lnot r$: $q$; with $\lnot q \lor r$: $r$; with $\lnot r$: $\square$.
  3. Negation: $((p \to q) \to p) \land \lnot p$. Now $(p \to q) \to p \equiv \lnot(\lnot p \lor q) \lor p \equiv (p \land \lnot q) \lor p$, in CNF $p \land (p \lor \lnot q)$. Clauses: $p$, $p \lor \lnot q$, $\lnot p$. Then $p$ and $\lnot p$: $\square$.
  4. $t$: train late, $x$: there are taxis, $j$: Jean is late. Hypotheses $t \land \lnot x \to j$, $\lnot j$, $t$; conclusion $x$. Clauses: $\lnot t \lor x \lor j$, $\lnot j$, $t$, $\lnot x$. Then $\lnot j$ with the first: $\lnot t \lor x$; with $t$: $x$; with $\lnot x$: $\square$. The reasoning is correct.
Solution
  1. We add $\lnot j$. With $\lnot a \lor j$: $\lnot a$. With $p \lor j \lor a$ and $\lnot j$: $p \lor a$, then with $\lnot a$: $p$. With $\lnot p \lor j \lor a$ and $\lnot j$: $\lnot p \lor a$, then with $\lnot a$: $\lnot p$. Finally $p$ and $\lnot p$: $\square$. So the facts entail $j$.
  2. We add $p$, and we may use $j$ (proved). $j$ and $\lnot j \lor \lnot p$: $\lnot p$; with $p$: $\square$.
Solution
  1. $p \lor q$ and $\lnot p \lor q$: $q$. $p \lor q$ and $p \lor \lnot q$: $p$. $\lnot p \lor q$ and $p \lor \lnot q$: two tautologies. Then $q$ and $p \lor \lnot q$: $p$ (already there); $p$ and $\lnot p \lor q$: $q$ (already there). Nothing new any more.
  2. $\square$ has not appeared: $S$ is satisfiable. Model: $p = 1, q = 1$.
  3. We already have $p$ and $q$; with $\lnot p \lor \lnot q$ and $p$: $\lnot q$; with $q$: $\square$. $S'$ is unsatisfiable: its four clauses each rule out one of the four interpretations.