Can a CNF formula contain no clause or contain empty clause?

246 Views Asked by At

The definition of CNF formula that i found at internet is that CNF formula is a conjunction of clause, and clause is a disjunction of literal. But i haven't found anywhere the answer of whether a CNF formula can not contain any clause and whether cnf formula can contain empty clause, i have googled a lot but still did not find the answer. Sorry for the low quality question but even on this site i did not found the answer to the question so i thought it is not a bad idea to ask here, any help is appreciated.

2

There are 2 best solutions below

0
On

The null clause $\phi$ is a clause with zero literals. In a CNF formula, the semantics of $\phi \land y = y$.

In a DNF formula, the semantics of $\phi \lor y = y$.

So, $\phi$ operates semantically as a DONT CARE depending on whether the context is a DNF or CNF formula.

Therefore, in both CNF and DNF formulae, $\phi$ can be safely removed in preprocessing and the resulting formula evaluated.

0
On

In an ideal world, the conjunction of no formulas (a CNF with no clauses) would be the always true formula $\top$. The disjunction of no formulas (an empty clause in a CNF) would be the always false formula $\bot$.

[Very generally, when you have an associative binary operation with an identity element, such as conjunction or disjunction of formulas, sum or product of numbers, union of sets, etc., the result of applying the operation to no elements should be the identity element. So the sum of no terms is $0$, the product of no factors is $1$, and the union of no sets is $\varnothing$.]

Unfortunately, not everyone agrees with my ideal world, so you can find other conventions in the literature. So you'll have to inspect whatever sources you're using to see what their conventions are.