1
$\begingroup$

I have 2 clauses of cardinality 3

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

or, in set notation

$$\{a, b, c\}, \{a, \lnot b, \lnot c\}$$

I applied resolution incorrectly and got clause

$$\{a\}$$

Now, someone told me that if we apply resolution on these 2 clauses we get a tautology, but I don't understand why/how.
Can someone please explain? Thank you.

$\endgroup$
0
$\begingroup$

You only resolve on one literal. This was your mistake: you resolved on both $b$ and $c$, but you can only resolve on one of them.

Now, if you resolve on $b$, the result is $\{a,c,\neg c\}$, which is indeed a tautology, since whether $c$ is true or false, this clause will always be satisfied: it is a tautologous clause.

Likewise, if you resolve on $c$, the result is $\{a , b , \neg b\}$, which is a tautologous clause as well.

$\endgroup$
  • $\begingroup$ I'm confused on how you get a tautology here. If $a$ is false and either $b$ and $c$ are true or $b$ and $c$ are both false, won't the statement be false: $(F \vee T \vee T) \wedge (F \vee F \vee F)$? It would seem to me that this simplifies to $a \vee (b \oplus c)$. $\endgroup$ – Jared Feb 9 at 2:53
  • $\begingroup$ But then I may be confused on what is meant by "applying resolution". $\endgroup$ – Jared Feb 9 at 2:58
  • 1
    $\begingroup$ @Jared You are right that the original statement is not a tautology ... all that is being shown here is that, through the resolution rule, you can derive a tautology from this statement. But of course, any statement implies a tautology! So, the fact that a tautology can be derived from some statement means absolutely nothing ... it certainly does not mean that the original statement is a tautology itself, if that's what you're thinking. $\endgroup$ – Bram28 Feb 9 at 3:54
  • $\begingroup$ @Bram28 Oooh, so clear... Thanks a lot 👍 $\endgroup$ – Grasta Feb 9 at 12:57
  • $\begingroup$ @Grasta You're welcome! :) $\endgroup$ – Bram28 Feb 9 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.