Boolean logic formulas

Identity, null (dominance), idempotent, complement and involution laws; each left-hand law is the dual of the one beside it.

The second one (OR over AND) has no counterpart in ordinary algebra; it is the step that turns an SOP into a POS.

First row: in an SOP, a product term that contains every literal of another product term is redundant; dually, in a POS, a sum term that contains every literal of another sum term is redundant. Second row (the redundant-literal rule): when a literal stands alone as a term, its complement can be deleted from every other term.

Two terms that are identical except for one variable, true in one and complemented in the other, merge into one and that variable drops out. Every K-map group and every Quine–McCluskey step is this law.

It applies when exactly one variable appears true in one term and complemented in the other. The consensus term is then the AND of the remaining literals ($BC$) in an SOP, or the OR of the remaining literals ($B+C$) in a POS, and it is redundant. If two or more variables are opposed there is no consensus term. The redundant term still matters for hazards (last section).

Break the bar, change the operator. Applied to a whole expression it gives the complement: swap $+$ and $\cdot$, swap 0 and 1, and complement every literal.

Multiplying out gives $A\overline{A}+AC+\overline{A}B+BC$. $A\overline{A}=0$, and $BC$ is the consensus term of $AC$ and $\overline{A}B$, so both drop. A fast route from POS to SOP.

Holds for any function and any chosen variable; it is the basis of multiplexer realisations and of the substitution shortcuts below.

$S$ is the set of rows where $f=1$, written $\sum m(S)$. Example: $f(A,B,C)=\sum m(1,4,7)=\prod M(0,2,3,5,6)$.

Complementing swaps the index set. Keeping the same indices and switching $\sum$ to $\prod$ gives $\overline{f}$, not $f$.

Each variable appears at most once in the term. Use it to count minterms fast. Overlapping terms must be counted once, so list the minterms whenever terms can overlap.

Counts every function of $n$ variables, including the constants 0 and 1 and functions that ignore some variables. For $n=2$ there are 16, which is why there are 16 possible two-input gates.

Swapping $+$ and $\cdot$ (and 0 and 1) in any expression of $f$ gives this same function. Row $2^n-1-j$ is the bitwise complement of row $j$.

Rows $i$ and $2^n-1-i$ must have opposite outputs, so exactly one of each complementary pair is a minterm and a self-dual function has exactly $2^{n-1}$ minterms. Every self-dual function is therefore neutral (next block), but a neutral function need not be self-dual. Examples: any single literal, $A\oplus B\oplus C$, and the majority function $AB+BC+CA$.

Self-dual: the $2^n$ rows form $2^{n-1}$ complementary pairs, each with 2 choices. Symmetric: the output depends only on how many inputs are 1, which takes $n+1$ values.

Inclusion–exclusion over the variables a function may ignore. For $n=1,2,3,4$ it gives 2, 10, 218 and 64594.

Groups must be rectangles (wrap-around allowed) whose sides are 1, 2 or 4 cells long, so a group holds 1, 2, 4, 8 or 16 cells; in a 5-variable map a group may also be the same rectangle on both halves. A variable that changes inside the group drops out; one fixed at 1 appears uncomplemented and one fixed at 0 appears complemented. A 3-cell or L-shaped group is not a single term.

XOR is commutative and associative. Complementing one input complements the output; complementing both leaves it unchanged.

AND distributes over XOR, but OR does not. If $AB=0$ (the terms never both equal 1) then $A+B=A\oplus B$.

Here $A\odot B\odot C$ means two cascaded 2-input XNOR gates, $(A\odot B)\odot C$: it gives the 3-input XOR, not its complement. An $n$-variable XOR has $2^{n-1}$ minterms and no two of them are adjacent on a K-map (a checkerboard), so its minimal SOP needs all $2^{n-1}$ terms of $n$ literals each.