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