4
$\begingroup$

The empty clause is a clause containing no literals and by definition is false.

c = {} = F

What then is the empty set, and why does it evaluate to true?

Thanks!

  • 0
    That makes perfect sense, thank you! Would you like to convert your comment into an answer so that I can accept it? If not, I'll type it up and give you credit. Thanks!2012-01-03

2 Answers 2

9

Remember, we take the disjunction over the elements of a clause, then the conjunction over the entire clause set. So if the clause set is empty, then we have an empty conjunction. If the clause itself is empty, then we have an empty disjunction.

What does it mean to take an empty conjunction or empty disjunction? Let's consider a similar situation. Over the real numbers, what is an empty sum, or an empty product? I claim that an empty sum should be 0; an empty product should be 1. Why is this? Clearly, we have:

sum(2,3,4)+sum(5,6,7) = sum(2,3,4,5,6,7)

sum(2,3,4)+sum(5,6) = sum(2,3,4,5,6)

sum(2,3,4)+sum(5) = sum(2,3,4,5)

Now make the second sum empty:

sum(2,3,4)+sum() = sum(2,3,4)

So sum() should be 0. In the same way, product() must be 1. (Replace "sum" by "product" and "+" by "*" in the lines above.)

In general, a commutative, associative binary operation applied on an empty set should be the identity element for that operation.

Now back to your original example. Since the identity for conjunction is "true", and the identity for disjunction is "false", that is why an empty clause set is true, but empty clause is false.

0

You can get an intuition why this is so by observing that:

  1. A disjunction is true iff there exists a member which is true. In an empty disjunction (empty clause) there is no such member, so it is always false.
  2. A conjunction is true iff no member which is false exists. An empty conjunction (empty set in cnf problems) has no member (and a fortiori no member which is false) so it is always true.

It is a similar intuition to the idea of universal quantification being true on the empty domain.