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!
Logic – Difference Between Empty Clause and Empty Clause Set in Satisfiability
logicpropositional-calculussatisfiability
Related Solutions
A formula $A$ is a tautology if it is true with every assignment.
A formula $A$ is satisfiable if there is at least an assignemnt $v$ such that $A$ is true for $v$.
If $A$ is true for the assignment $v$, then its negation, $¬A$, is false for that assignment.
A formula $A$ is a tautology iff its negation, $¬A$, is not satisfiable.
The complement of a decision problem :
is the decision problem resulting from reversing the yes and no answers.
Thus, in a nutshell, if the answer to the problem "is $A$ in TAUT ?" is NO, then $¬A$ is in SAT.
More precisely, the problem of determining if some formula $A$ is not a tautology is thus equivalent to the problem of determining if the negation of the formula, $¬A$, is satisfiable.
It seems to me that it is only a terminological issue. Compare with :
- Sanjeev Arora & Boaz Barak, Computational complexity : A Modern Approach (2009), page 55:
Now we define some additional complexity classes related to $\text {P}$ and $\text {NP}$.
If $L ⊆ \{ 0, 1 \}^∗$ is a language, then we denote by $\overline L$ the complement of $L$.
We make the following definition: $\text {coNP} = \{ L \mid \overline L ∈ \text {NP} \}$.
$\text {coNP}$ is not the complement of the class $\text {NP}$. The following is an example of a $\text {coNP}$ language: $\overline {\text {SAT} } = \{ \varphi \mid \varphi \text { is not satisfiable} \}$.
The decision problems (or languages) are complementary : not the corresponding classes of formulae.
This is an instance of the principle of explosion (a.k.a. ex falso sequitur quodlibet). The expression $\forall x \in X~\varphi(x)$ is simply shorthand for $$\forall x~(x \in X \Rightarrow \varphi(x))$$ so if $X$ is empty, then $x \in X$ is false for all $x$, and hence $x \in X \Rightarrow \varphi(x)$ is true by the principle of explosion.
Likewise, $\exists x \in X~\varphi(x)$ is shorthand for $\exists x~(x \in X \wedge \varphi(x))$, meaning that if $X$ is empty then every sentence of the form $\exists x \in X~\varphi(x)$ is false.
Why (or whether) you should accept the principle of explosion is a whole different bag of worms: some logics (including classical logic and intuitionistic logic) accept it as an axiom, whereas some (including minimal logic) do not. This matter has been discussed a lot on this website—if you're interested, you might want to have a look around.
Best Answer
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.