0

I have following task in my study materials:

Have formulas $\varphi = (a \implies b) \iff c, \psi = \lnot a \lor (b \implies c)$. Determine whether the formulas $\varphi$ and $\psi$ are tautologically equivalent using the resolution method.

What I did so far is that I have converted formulas into DNF:

$$\varphi \vDash (a \wedge \lnot c) \lor (a \wedge b) \lor (\lnot b \wedge \lnot c) \lor (\lnot b \wedge \lnot a) \lor (c \wedge \lnot a) \lor (c \wedge b)$$ $$\psi \vDash \lnot a \lor \lnot b \lor c$$

I checked that it's correct. But now what?

1 Answers1

0

First, your DNF is actually not equivalent to $\varphi$: if $a=T$, $b=T$, and $c=F$, then $(a \Rightarrow b) \Leftrightarrow c = (T \Rightarrow T) \Leftrightarrow F = T \Leftrightarrow F = F$, but your DNF would be $T$, since term $(a \land b)$ would be $T$.

Second, to do Resolution, you typically put statements into CNF, not DNF. For example, putting $\varphi$ into CNF:

$$(a \Rightarrow b) \Leftrightarrow c =$$

$$((a \Rightarrow b) \Rightarrow c) \land (c \Rightarrow(a \Rightarrow b)) = $$

$$(\neg (\neg a \lor b) \lor c) \land (\neg c \lor (\neg a \lor b)) = $$

$$( a \land \neg b) \lor c) \land (\neg c \lor \neg a \lor b) = $$

$$( a \lor c) \land (\neg b \lor c) \land (\neg c \lor \neg a \lor b)$$

Third, if you want to use Resolution to check whether two statements $\varphi$ and $\psi$ are equivalent, first do Resolution on $\varphi$ and $\neg \psi$, and see if you get a contradiction (i.e. see if you can resolve that to the empty clause). If so, then $\varphi$ implies $\psi$, and if not, then $\varphi$ does not imply $\psi$, and hence they are not equivalent. But if $\varphi$ does imply $\psi$, then do another Resolution, but this time on $\psi$ and $\neg \varphi$. If you get a contradiction there, then $\psi$ implies $\varphi$, and given that you already had that $\varphi$ implies $\psi$, they are equivalent, but if you can't get a contradiction, then $\psi$ does not imply $\varphi$, and hence they are not equivalent.

Alternatively, you can do Resolution on $\neg( \varphi \Leftrightarrow \psi)$ .. if you get a contradiction (empty clause), then they are equivalent, but if not, then they are not equivalent.

Finally: you know that you cannot get a contradiction (empty clause) when you find that you cannot apply the resolution rule to obtain any clauses different from the ones you already have.

Bram28
  • 100,612
  • 6
  • 70
  • 118