PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
CNF (Definition)

A propositional formula is a CNF formula, meaning Conjunctive Normal Form, if it is a conjunction of disjunction of literals (a literal is a propositional variable or its negation). Hence, a CNF is a formula of the form: $K_1 \wedge K_2 \wedge \ldots \wedge K_n$ where each $K_i$ is of the form $l_{i1} \vee l_{i2} \vee \ldots \vee l_{im}$ for literals $l_{ij}$ and some $m$ (which can vary for each $K_i$ .

Example: $(x\vee y \vee \neg z) \wedge (y\vee \neg w \vee \neg u) \wedge (x\vee v)$




"CNF" is owned by rspuzio. [ owner history (1) ]
(view preamble | get metadata)

View style:

See Also: DNF, atomic formula

Other names:  conjunctive normal form
Log in to rate this entry.
(view current ratings)

Cross-references: negation, variable, literals, disjunction, conjunction, formula
There are 5 references to this entry.

This is version 4 of CNF, born on 2003-10-16, modified 2004-03-09.
Object id is 5392, canonical name is CNF.
Accessed 5102 times total.

Classification:
AMS MSC03B05 (Mathematical logic and foundations :: General logic :: Classical propositional logic)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)