Logic Gates; Combinational Logic Circuits

Logic Gates

12.1 Basic Gates

Gate	Symbol	Boolean	Truth Table (2-input)
AND	&	Y = A·B	00→0, 01→0, 10→0, 11→1
OR	≥1	Y = A+B	00→0, 01→1, 10→1, 11→1
NOT	△	Y = Ā	0→1, 1→0

12.2 Derived Gates

Gate	Expression	Note
NAND	(AB)'	Universal gate
NOR	(A+B)'	Universal gate
XOR	A⊕B = A'B+AB'	1 if odd number of 1s
XNOR	(A⊕B)'	1 if even number of 1s

12.3 Universal Gates

NAND and NOR can implement ANY Boolean function:

NOT from NAND: A NAND A = A'
AND from NAND: (A NAND B) NAND (A NAND B) = AB
OR from NAND: (A NAND A) NAND (B NAND B) = A+B

12.4 Truth Table Size

For n inputs: 2ⁿ rows

Example: 6-input OR gate → 2⁶ = 64 input combinations

Combinational Logic Circuits

Definition: Output depends only on present inputs — no memory.

13.1 Half Adder

Adds two 1-bit numbers A and B.

A	B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Equations:

S = A ⊕ B
C = A · B

Limitation: Cannot handle carry-in from previous stage.

13.2 Full Adder

Adds A, B and Cin (carry-in).

A	B	Cin	Sum	Cout
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

Equations:

Sum = A ⊕ B ⊕ Cin
Cout = AB + ACin + BCin

13.3 Half Subtractor

A	B	Diff (D)	Borrow (B)
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

D = A ⊕ B
B = A' · B

13.4 Full Subtractor

D = A ⊕ B ⊕ Bin
Bout = A'B + A'Bin + B·Bin

13.5 n-bit Parallel Adder

n full adders cascaded — adds two n-bit numbers with carry propagation.

A0..An ──┬── FA0 ── FA1 ── ... ── FAn ── Cout
B0..Bn ──┘ ↑ ↑ ↑
 Cin=0 C0 C(n-1)

13.6 Multiplexer (MUX)

Many inputs, one output — data selector.

n select lines → 2ⁿ inputs
2:1 MUX → 1 select line
4:1 MUX → 2 select lines
8:1 MUX → 3 select lines

Boolean expression (4:1): F = S1'S0'·D0 + S1'S0·D1 + S1S0'·D2 + S1S0·D3

Applications:

Data routing
Parallel-to-serial conversion
Time/frequency multiplexing

13.7 Demultiplexer (DEMUX)

One input, many outputs — inverse of MUX.

1:4 DEMUX → 2 select lines
Applications: serial data transmission, decoder design, test equipment

13.8 Decoder

Converts n-bit binary input → one of 2ⁿ outputs active.

2-to-4 decoder: 2 inputs, 4 outputs
3-to-8 decoder: 3 inputs, 8 outputs

Applications: Address decoding, instruction decoding, BCD-to-decimal

13.9 Encoder

Inverse of decoder — 2ⁿ inputs → n outputs (one hot input).

Priority encoder: handles multiple simultaneous inputs
Applications: keyboard encoding, shaft position