PlanetMath (more info)
 Math for the people, by the people.
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
DNF (Definition)

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

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



"DNF" is owned by rspuzio. [ owner history (1) ]
(view preamble)

View style:

See Also: CNF, atomic formula

Other names:  disjunctive normal form

Attachments:
every proposition is equivalent to a proposition in DNF (Theorem) by rspuzio
Log in to rate this entry.
(view current ratings)

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

This is version 1 of DNF, born on 2004-03-09.
Object id is 5677, canonical name is DNF.
Accessed 3013 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)