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.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

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

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.