# Can kCNF have less than k variables per clause?

An example given by my prof in her notes:

The following formula is in 4CNF: $(w\vee y\vee \neg z)\wedge(w\vee\neg x\vee z)\wedge(w\vee\neg x\vee \neg y\vee z)$

I originally thought that maybe the example was a typo, but given a definition she gave before that, saying that "A formula is in kCNF if it has a maximal of k variables per disjunction". Is this technically 4CNF if it has two clauses that don't have 4 variables in it?

-

## 1 Answer

Yes, to your title question. A statement in kCNF form can have fewer than $k$ variables in a clause. Put differently, a statement in kCNF form has AT MOST (maximum of) $k$ variables per clause/conjunct.

The fact that one of the conjuncts (clause) in your example has $4$ variables (the third/last clause) means it qualifies as 4CNF statement. It doesn't matter that two of the clauses do not have 4 variables in it.

-
So does it follow then that CNF is the same as kCNF? – agent154 Feb 21 '13 at 16:07
It could, depending on k. Your example wouldn't qualify as a 3CNF, but it is both a CNF and a 4CNF statement. – amWhy Feb 21 '13 at 16:09
Yes I am, thanks. – agent154 Feb 21 '13 at 17:36
You're welcome! – amWhy Feb 21 '13 at 17:40