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!

  • 1
    The empty set does not exist in propositional logic, so your question doesn't really make sense... – Zhen Lin Jan 3 '12 at 14:54
  • I perhaps should give some more context. I am studying satisfiability. Let F be a clause-set (a conjunction of clauses). If the empty clause belongs to F then F is unsatisfiable. If F is the empty set then F is satisfiable. I think I am confused about the scenarios where F contains only one clause; the empty clause, and when F has no clauses. Why is the first unsatisfiable (i.e. false) but the second satisfiable (true)? – Danny King Jan 3 '12 at 15:01
  • I have updated the title, thanks. – Danny King Jan 3 '12 at 15:06
  • Are your clauses supposed to be in disjunctive normal form, perhaps? Then the empty clause is false because $\bot \lor p = p$ always. Whereas $\top \land p = p$ always, so the empty set is always satisfiable. – Zhen Lin Jan 3 '12 at 15:34
  • 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! – Danny King Jan 3 '12 at 15:52
up vote 8 down vote accepted

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.

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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