Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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

1 Answer 1

up vote 6 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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