TOPICS
Search

Disjunctive Normal Form


A statement is in disjunctive normal form if it is a disjunction (sequence of ORs) consisting of one or more disjuncts, each of which is a conjunction (AND) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). Disjunctive normal form is not unique.

The Wolfram Language command LogicalExpand[expr] gives disjunctive normal form (with some contractions, i.e., LogicalExpand attempts to shorten output with heuristic simplification).

Examples of disjunctive normal forms include

A
(1)
(A ^ B) v (!A ^ C)
(2)
(A ^ B ^ !A) v (C ^ !B) v (A ^ !C)
(3)
A ^ B
(4)
A v (B ^ C),
(5)

where  v denotes OR,  ^ denotes AND, and ! denotes NOT (Mendelson 1997, p. 30). Some authors also exclude statements containing both statement letters and their negations, which would exclude the third example above.

Every statement in logic consisting of a combination of multiple  ^ ,  v , and !s can be written in disjunctive normal form.


See also

AND, Conjunctive Normal Form, Disjunct, Disjunction, Literal, Normal Form, OR, Statement Letter

Explore with Wolfram|Alpha

References

Mendelson, E. Introduction to Mathematical Logic, 4th ed. London: Chapman & Hall, p. 30, 1997.

Referenced on Wolfram|Alpha

Disjunctive Normal Form

Cite this as:

Weisstein, Eric W. "Disjunctive Normal Form." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DisjunctiveNormalForm.html

Subject classifications