display | more...
(Also called DNF). The form of a compound in logic, when it is expressed as a series of disjuncts, where each disjunct is either a simple proposition (or negation of) or a conjunction of simple propositions and negations of simple propositions.

And now in English: It is when a compound is in the form of "Ifs of ands" (or sums of products). For example, a compound in DNF would be:

(A ^ B) v (~C) v (~C ^ C ^ ~A) v (B)

The following is not in DNF:

(A v B) v (C)

Any compound can be written in DNF.


Now if somebody could only tell me the HTML tags for "or" and "and"... v and ^ just don't cut it.

For every Boolean function, there exists a corresponding disjunctive normal form. As stated by Footprints, the form only uses negation ( ¬ ), disjunction ( ∨ ), and conjunction ( ∧ ). Because of this, the set S of logical connectives {¬, ∧, ∨} is functionally complete. In general, a set of logical connectives L is said to be functionally complete if every Boolean function in any number of variables can be expressed by a sentence containing logical connectives only from L.

Here is a step-by-step process for constructing a disjunctive normal form from any Boolean function. For example, let a Boolean function f(p, q, r) be defined by the truth table below:
 p  q  r  | f(p,q,r)
----------+----------
 0  0  0  |    1
 0  0  1  |    1
 0  1  0  |    0
 0  1  1  |    0
 1  0  0  |    1
 1  0  1  |    0
 1  1  0  |    0
 1  1  1  |    0
For the first row with f = 1, variables p, q, and r are all equal to 0. For this row and only for this row is ¬p, ¬q, and ¬r all true. This can be expressed as (¬p ∧ ¬q ∧ ¬r). Add this next to row 1:
 p  q  r  | f(p,q,r)
----------+----------
 0  0  0  |    1     (¬p ∧ ¬q ∧ ¬r)
 0  0  1  |    1
 0  1  0  |    0
 0  1  1  |    0
 1  0  0  |    1
 1  0  1  |    0
 1  1  0  |    0
 1  1  1  |    0
 
Continue analysis in this fashion for all rows with f = 1:
 p  q  r  | f(p,q,r)
----------+----------
 0  0  0  |    1     (¬p ∧ ¬q ∧ ¬r)
 0  0  1  |    1     (¬p ∧ ¬q ∧  r)
 0  1  0  |    0
 0  1  1  |    0
 1  0  0  |    1     ( p ∧ ¬q ∧ ¬r)
 1  0  1  |    0
 1  1  0  |    0
 1  1  1  |    0
 
Compound these terms into one formula with disjunctions:
p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ ¬qr) ∨ (p ∧ ¬q ∧ ¬r)
This formula is true iff the list of values (p, q, r) corresponds to a row with f = 1. ∴ The formula is logically equivalent to f. This form of formula is called the disjunctive normal form, which every Boolean function has. Since the form consists only of connectives from set S, S is functionally complete. Other examples of functionally complete sets include {¬, ∨}, {¬, ∧}, {}, and {}.

Here are some logical equivalents to other common connectives in disjunctive normal form:

(p ⇒ q) ≡ (¬ p ∨ q)
(p ⇔ q) ≡ ((p ∧ q) ∨ (¬ p ∧ ¬ q))

Log in or register to write something here or to contact authors.