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!
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!
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:
It is a similar intuition to the idea of universal quantification being true on the empty domain.