Disjunctive normal form
Any compound proposition can be rewritten in its disjunctive normal form (DNF) as a disjunction of conjunctions. The only logical operators allowed in DNF are \(\lnot\), \(\land\), and \(\lor.\) Additionally, \(\lnot\) and \(\land\) can only operate on individual propositions.
To rewrite a compound proposition in DNF, consider all the different ways it can be true.
Let's convert \(p \rightarrow q\) into DNF. We know \(p \rightarrow q\) is true when \(p\) is true
and
\(q\) is true, or when \(p\) is false and \(q\) is true, or when \(p\) is false and \(q\) is false.
Therefore, its disjunctive normal form must be:
$$p \rightarrow q \equiv (p \land q) \lor (\lnot p \land q) \lor (\lnot p \land \lnot q)$$
Logic & Proofs
Integer •
Rational number •
Inequality •
Real number •
Theorem •
Proof •
Statement •
Proof by exhaustion •
Universal
generalization •
Counterexample •
Existence proof •
Existential
instantiation •
Axiom •
Logic •
Truth •
Proposition •
Compound proposition •
Logical operation •
Logical equivalence •
Tautology •
Contradiction •
Logic law •
Predicate •
Domain •
Quantifier •
Argument •
Rule of inference •
Logical proof •
Direct proof •
Proof by
contrapositive •
Irrational number •
Proof by
contradiction •
Proof by cases •
Summation •
Disjunctive normal
form
Set Theory
Set •
Element •
Empty set •
Universal set •
Subset •
Power set •
Cartesian product •
String •
Binary string •
Empty string •
Set operation •
Set identity •
Set proof
Functions
Algorithms
Relations
Number Theory
Induction
Combinatorics
Graph Theory
Graph •
Walk •
Subgraph •
Regular graph •
Complete graph •
Empty graph •
Cycle graph •
Hypercube graph •
Bipartite graph •
Component •
Eulerian circuit •
Eulerian trail •
Hamiltonian cycle •
Hamiltonian path •
Tree •
Huffman tree •
Substring •
Forest •
Path graph •
Star •
Spanning tree •
Weighted graph •
Minimum spanning tree
•
Greedy algorithm •
Prim's algorithm
Recursion