Logic Fundamentals

Digital electronics represents information with a finite set of levels. Binary systems use two logic states, written 0 and 1. A logic value is an abstract state; the corresponding voltage range depends on the logic family.

Number Systems and Binary Representation

For radix $r$, a positional number $(d_nd_{n-1}\ldots d_0.d_{-1}\ldots d_{-m})_r$ has value

$$\boxed{N=\sum_{k=-m}^{n}d_kr^k},\qquad 0\le d_k<r.$$

System	Base	Digits	Main use
Binary		, 1	Native representation of logic and storage
Octal		–7	Compact grouping of three binary bits
Decimal		–9	Human-readable quantities
Hexadecimal		–9, A–F	Compact grouping of four binary bits

Number systems used in digital electronics.

Conversion rules.

• To convert an integer from decimal to base $r$, divide repeatedly by $r$ and read the remainders from last to first.

• To convert a decimal fraction, multiply repeatedly by $r$ and read the integer parts in order. A non-terminating result must be rounded to a stated number of places.

• For binary–octal conversion, group bits in threes about the radix point. For binary–hexadecimal conversion, group them in fours.

Note

Example — Radix conversion

Using positional weights,

$$(2D.6)_{16}=2(16)+13+\frac{6}{16}=(45.375)_{10}.$$

Replacing each hexadecimal digit by four bits gives

$$(2D.6)_{16}=(0010\,1101.0110)_2=(101101.011)_2.$$

An $n$-bit word has $2^n$ distinct patterns. Their interpretation depends on the chosen code.

Representation	Range for $n$ bits	Zero	Negative-value rule
Unsigned	$0$ to $2^n-1$	one	Not available
Sign magnitude	$-(2^{n-1}-1)$ to $2^{n-1}-1$	two	Set sign bit to 1
One’s complement	$-(2^{n-1}-1)$ to $2^{n-1}-1$	two	Complement every bit
Two’s complement	$-2^{n-1}$ to $2^{n-1}-1$	one	Complement and add 1

Common binary integer representations.

For an $n$-bit two’s-complement word $b_{n-1}\ldots b_0$,

$$\boxed{N=-b_{n-1}2^{n-1}+\sum_{k=0}^{n-2}b_k2^k}.$$

To form $-N$, invert all $n$ bits of $N$ and add 1, discarding any carry beyond the word. For example, in eight bits,

$$+37=0010\,0101, \qquad -37=1101\,1011.$$

Sign extension copies the sign bit into new high-order positions; zero extension is correct only for unsigned values.

Note

Key Point — Carry and signed overflow are different

An unsigned addition overflows when a carry leaves the most-significant bit. Two’s-complement addition overflows when equal-sign operands produce a result with the opposite sign, equivalently when the carry into the sign bit differs from the carry out.

Binary-coded decimal (BCD) stores each decimal digit separately in four bits. Thus $59_{10}=0101\,1001_{\mathrm{BCD}}$, whereas ordinary binary gives $59_{10}=0011\,1011_2$. The six patterns 1010–1111 are invalid BCD digits.

Basic Logic Gates

In positive logic, the higher specified voltage range represents 1 and the lower range represents 0. The intermediate voltage interval is normally undefined, not a third state.

Symbols and Boolean expressions of the basic logic gates. An output bubble denotes inversion; XOR has an additional curved input line.

Gate	Expression	Output condition
BUFFER	$Y=A$	follows the input
NOT	$Y=\overline A$	1 when $A=0$
AND	$Y=AB$	1 only when every input is 1
OR	$Y=A+B$	1 when any input is 1
NAND	$Y=\overline{AB}$	complement of AND
NOR	$Y=\overline{A+B}$	complement of OR
XOR	$Y=A\oplus B$	1 when the inputs differ
XNOR	$Y=\overline{A\oplus B}$	1 when the inputs agree

Boolean functions of the basic gates.

$A$	$B$	$AB$	$A+B$	$\overline{AB}$	$\overline{A+B}$	$A\oplus B$	$\overline{A\oplus B}$

Complete two-input truth table.

Boolean Algebra

Boolean variables take values in $\{0,1\}$. Addition denotes OR, multiplication denotes AND, and an overbar denotes NOT.

Core Boolean identities.

Law	OR form	AND form
Identity	$A+0=A$	$A\cdot 1=A$
Null	$A+1=1$	$A\cdot 0=0$
Idempotent	$A+A=A$	$AA=A$
Complement	$A+\overline A=1$	$A\overline A=0$
Involution	$\overline{\overline A}=A$	—
Commutative	$A+B=B+A$	$AB=BA$
Associative	$A+(B+C)=(A+B)+C$	$A(BC)=(AB)C$
Distributive	$A+BC=(A+B)(A+C)$	$A(B+C)=AB+AC$
Absorption	$A+AB=A$	$A(A+B)=A$
De Morgan	$\overline{A+B}=\overline A\,\overline B$	$\overline{AB}=\overline A+\overline B$

The principle of duality interchanges $+$ with multiplication and 0 with 1. Every valid identity therefore has a valid dual. De Morgan’s laws also show why NAND and NOR are universal:

$$\overline A=\overline{AA}=\overline{A+A}, \qquad AB=\overline{\overline{AB}\,\overline{AB}}, \qquad A+B=\overline{\overline{A+B}+\overline{A+B}}.$$

Logic Expressions and Truth Tables

A truth table defines a function row by row. An expression may be written in two canonical forms:

• sum of minterms: OR the product term for every row where $F=1$; write $F=\Sigma m(\cdots)$;

• product of maxterms: AND the sum term for every row where $F=0$; write $F=\Pi M(\cdots)$.

In a minterm, use the uncomplemented variable for a row value 1 and the complemented variable for 0. In a maxterm the convention is reversed.

For example,

$$F(A,B,C)=\Sigma m(1,2,3,5,7)$$

has a 1 in rows 001, 010, 011, 101 and 111. Its canonical SOP is

$$\overline A\,\overline B C+\overline A B\overline C+ \overline A BC+A\overline BC+ABC.$$

Karnaugh-map simplification

Adjacent K-map cells differ in one variable. Group 1s for SOP or 0s for POS in rectangles containing $1,2,4,8,\ldots$ cells. Groups may wrap across an edge, overlap, and should be as large as possible. A variable disappears from a term when it changes within a group.

A $\setminus$ BC	00	01	11	10
0	0	1	1	1
1	0	1	1	0

The four cells with $C=1$ give $C$; the remaining pair at $A=0,B=1$ gives $\overline A B$. Hence

$$\boxed{F=C+\overline A B}.$$

Do not treat diagonally touching cells as adjacent, and keep row/column order Gray-coded: 00, 01, 11, 10.

From Requirement to Circuit

1. Define input and output variables, including active-HIGH or active-LOW conventions.

2. Build the truth table and mark impossible states as don’t-cares only when the hardware guarantees they cannot occur.

3. Write canonical SOP or POS, then simplify algebraically or by K-map.

4. Select gates or a universal NAND/NOR realization and draw every inversion explicitly.

5. Verify all input rows and estimate logic depth, loading and delay.

For a combinational path with gate delays $t_1,t_2,\ldots,t_k$, a conservative worst-case estimate is

$$\boxed{t_{pd,path}\approx\sum_{i=1}^{k}t_i}.$$

The physical design must also respect fan-out, noise margins, supply limits and unused-input rules of its chosen logic family.

Note

Key Point — Core checks

Keep the representation and the circuit separate: a bit pattern has no signed meaning until a code is declared, and a Boolean 1 has no voltage until a logic family is declared. Derive the expression from the truth table, simplify it, then verify the final circuit against the same table.