29 May 2025
Number Systems and Boolean Algebra
Positional notation, binary arithmetic and codes, switching logic, Boolean laws, canonical forms, SOP/POS reduction, and Karnaugh maps with don't-cares.
A digital word is a finite sequence of symbols. Its numerical value depends on the base; its logical meaning depends on the code or Boolean function assigned to it. Keeping those roles separate prevents, for example, confusing the BCD word 0101 1001 with one binary integer.
Positional number systems
In radix $r$, each digit satisfies $0\le d_i<r$, and
\[(d_nd_{n-1}\cdots d_0.d_{-1}\cdots d_{-m})_r =\sum_{i=-m}^{n}d_i r^i.\]Repeated division by $r$ produces integer digits from least to most significant. For $45_{10}$,
\[\begin{aligned} 45&=2(22)+1,&22&=2(11)+0,&11&=2(5)+1,\\ 5&=2(2)+1,&2&=2(1)+0,&1&=2(0)+1, \end{aligned}\]so the remainders read upward give $45_{10}=101101_2$. Repeated multiplication produces fractional digits:
\[0.625(2)=1.25\to1,\qquad 0.25(2)=0.50\to0,\qquad 0.50(2)=1.00\to1.\]Therefore
\[45.625_{10}=101101.101_2,\]and direct reconstruction checks the conversion:
\[2^5+2^3+2^2+2^0+2^{-1}+2^{-3}=45.625.\]Binary digits group exactly into octal and hexadecimal digits because $8=2^3$ and $16=2^4$:
\[1101011110_2=001\,101\,011\,110_2=1536_8,\] \[1101011110_2=0011\,0101\,1110_2=35E_{16}.\]The hexadecimal digit set is $0,1,\ldots,9,A,B,C,D,E,F$, with \(A_{16}=10_{10}\) through \(F_{16}=15_{10}\).
Binary addition, two’s complement, and subtraction
The one-column addition rules are
| $A$ | $B$ | carry in $C$ | sum bit | carry out |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Thus
\[\begin{array}{r} 00101101_2\\[-2pt] {}+00010111_2\\ \hline 01000100_2 \end{array} \qquad(45+23=68).\]An $n$-bit register stores integers modulo $2^n$. The two’s-complement representation of $-x$ is therefore
\[[-x]_{2^n}=2^n-x,\]because $x+(2^n-x)\equiv0\pmod{2^n}$. Operationally, invert all $n$ bits and add one. For eight bits,
\[37=00100101_2,\quad \overline{00100101}=11011010,\quad -37=11011011_2.\]Subtraction is addition of this modular inverse. For example,
\[\begin{array}{r} 01011011_2\;(91)\\[-2pt] {}+11011011_2\;(-37)\\ \hline 1\,00110110_2 \end{array}\]The ninth-bit carry is discarded, leaving \(00110110_2=54_{10}\). The signed range is
\[-2^{n-1}\le N\le 2^{n-1}-1.\]Adding equal-sign operands has overflow if the stored result has the opposite sign. Carry and signed overflow are different: carry describes unsigned arithmetic beyond $2^n-1$, whereas overflow describes failure of the signed range.
BCD and ASCII binary codes
A code assigns bit patterns to symbols; the pattern need not be interpreted as one positional binary number.
- In 8421 BCD, each decimal digit receives its own four-bit binary code. Hence $59_{10}$ is
0101 1001in BCD, not0011 1011, which is the binary representation of the integer 59. The six patterns1010through1111are not decimal digits. - ASCII assigns a seven-bit code to a character. The character
Ahas decimal code 65, so its seven-bit pattern is1000001. The digit characters0through9have codes0110000through0111001; their low four bits equal the corresponding BCD digit.
Switching circuits and elementary operations
Assign 1 to a closed switch and 0 to an open switch. Two series contacts conduct only if both are closed, so their switching function is $Y=AB$. Parallel contacts conduct if either branch is closed, so $Y=A+B$. A complemented contact implements $\overline A$.
| $A$ | $B$ | AND $AB$ | OR $A+B$ | NOT $\overline A$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
The Venn interpretation is exact: a point in $A\cap B$ has membership bits $(1,1)$ and hence $AB=1$; a point in $A\cup B$ has at least one membership bit equal to 1; a point in $U\setminus A$ has membership $\overline A=1$.
Boolean functions, postulates, and theorems
A Boolean function $F:{0,1}^n\to{0,1}$ assigns one output to every input word. Its truth table is therefore a complete definition with $2^n$ rows.
Boolean algebra uses closure and the following postulates, together with every equation obtained by interchanging $+$ with multiplication and $0$ with $1$:
\[\begin{aligned} A+0&=A, & A1&=A &&\text{(identities)},\\ A+B&=B+A, & AB&=BA &&\text{(commutativity)},\\ A(B+C)&=AB+AC, &(A+B)(A+C)&=A+BC &&\text{(distributivity)},\\ A+\overline A&=1, &A\overline A&=0 &&\text{(complements)}. \end{aligned}\]Interchanging the paired operations and constants is the duality principle. For example, the dual of $A+0=A$ is $A1=A$; complementation is unchanged.
Useful theorems follow from the postulates:
\[\begin{aligned} A+A&=A,&AA&=A &&\text{(idempotence)},\\ A+1&=1,&A0&=0 &&\text{(dominance)},\\ \overline{\overline A}&=A,&&&\text{(involution)},\\ A+AB&=A,&A(A+B)&=A &&\text{(absorption)},\\ \overline{A+B}&=\overline A\,\overline B, &\overline{AB}&=\overline A+\overline B &&\text{(De Morgan)}. \end{aligned}\]For absorption, no truth-table guess is needed:
\[A+AB=A(1+B)=A(1)=A.\]A second recurrent reduction is
\[(A+B)(A+\overline B) =A+A(B+\overline B)+B\overline B =A+A+0=A.\]De Morgan’s first law can also be checked row by row:
| $A$ | $B$ | $\overline{A+B}$ | $\overline A\,\overline B$ |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Canonical forms, SOP, and POS
For variables $A,B,C$, a minterm contains every variable once and is 1 for exactly one row. For example, $m_5=A\overline BC$ because $5=101_2$. A maxterm contains every variable once and is 0 for exactly one row; $M_5=\overline A+B+\overline C$.
If $F=1$ at rows $1,3,6,7$, its canonical sum of products is
\[\begin{aligned} F&=\Sigma m(1,3,6,7)\\ &=\overline A\,\overline B C+\overline ABC+AB\overline C+ABC. \end{aligned}\]The zero rows are $0,2,4,5$, so the same function has canonical product of sums
\[\begin{aligned} F&=\Pi M(0,2,4,5)\\ &=(A+B+C)(A+\overline B+C)(\overline A+B+C)(\overline A+B+\overline C). \end{aligned}\]Canonical terms contain all variables. A general SOP is an OR of product terms, and a general POS is an AND of sum terms. Algebra reduces the canonical SOP above without changing its truth table:
\[\begin{aligned} F&=\overline AC(\overline B+B)+AB(\overline C+C)\\ &=\overline AC+AB. \end{aligned}\]Karnaugh maps and incompletely specified functions
A Karnaugh map places truth-table rows in Gray order, so horizontally or vertically adjacent cells differ in one variable. The first and last rows are adjacent, as are the first and last columns. A group must contain $1,2,4,8,\ldots$ cells; every variable that changes inside the group disappears from its product term.
For
\[F=\Sigma m(1,3,7,11,15),\qquad d=\Sigma d(0,2,5),\]the set $d$ lists don’t-care inputs of an incompletely specified function. Those inputs are outside the required operating set, so each may be assigned 0 or 1 to reduce the implementation; a don’t-care need not be used.
Consequently,
\[\boxed{F=\overline A\,\overline B+CD}.\]The unused don’t-care $m_5$ may take either output value without altering the specification.
Editable switching/Venn TikZ · Editable Karnaugh-map TikZ · Maxima verification worksheet
Discussion