Logic gates, half adders and full adders

Learning goals and model

Connect Boolean expressions to gates, distinguish a half adder from a full adder, derive sum and carry from truth tables, and trace a small unsigned ripple-carry addition. Prerequisites: Boolean AND, OR, NOT and XOR, positional binary notation and fixed-width unsigned range. Gate inputs and outputs are ideal bits 0 or 1, evaluated after signals have settled. A combinational circuit's stable outputs depend only on its current inputs; it has no stored state in this model. Sequential circuits, clocking, flip-flops, signed overflow and physical gate delays require later lessons.

A gate is a building block implementing a Boolean function. A wire carries a bit; branching a wire sends the same value to several inputs, not a new independent variable. Read a circuit from inputs through intermediate signals to outputs. Name every intermediate signal to make its meaning auditable.

1. Gates as functions

NOT produces A′. Two-input AND produces AB, OR produces A+B, and XOR produces A⊕B. NAND means NOT-AND: (AB)′. NOR means NOT-OR: (A+B)′. XNOR means NOT-XOR: (A⊕B)′. In these formulas + means Boolean OR, not integer addition.

A	B	AND	OR	XOR	NAND	NOR	XNOR
0	0	0	0	0	1	1	1
0	1	0	1	1	1	0	0
1	0	0	1	1	1	0	0
1	1	1	1	0	0	0	1

NAND and NOR are each universal: networks using only that gate type can implement NOT, AND and OR, and therefore any finite Boolean function expressible in sum-of-products form. With NAND, NOT A=NAND(A,A). Let t=NAND(A,B); then AND(A,B)=NAND(t,t). Let u=NAND(A,A), v=NAND(B,B); then NAND(u,v)=A+B by De Morgan. These constructions prove functional sufficiency, not that every resulting implementation has minimum gate count.

Similarly NOR(A,A)=A′. Invert the output of NOR(A,B) using a self-connected NOR to obtain OR. Feeding complemented A and B into NOR produces AB. Tying both inputs to one signal is an intentional connection, not two independent inputs.

2. One-bit addition has two outputs

In this section, a+b means ordinary integer addition of bit values, whereas a⊕b and ab mean Boolean XOR and AND. Adding two bits can yield 0,1 or 2. A single bit cannot encode all three values, so use a sum bit s with weight 1 and carry bit c with weight 2. The defining integer identity is a+b=2c+s.

a	b	Integer a+b	Carry c	Sum s
0	0	0	0	0
0	1	1	0	1
1	0	1	0	1
1	1	2	1	0

This is a half adder: s=a⊕b and c=ab. At 1+1, the output pair (c,s) is (1,0), representing binary 10, or integer 2. Using OR for s would incorrectly produce (1,1), representing 3. Always label the pair order; (sum,carry) and (carry,sum) are different reporting conventions.

A half adder has no incoming carry input. It suffices for the lowest column of an addition when the specified initial carry is 0. Higher columns generally need to incorporate a carry from their lower neighbor, so use a full adder there.

3. Derive the full adder

A full adder accepts a,b,c_in and outputs s,c_out satisfying a+b+c_in=2c_out+s in integer arithmetic. The total ranges from 0 through 3. The sum bit is its parity, s=a⊕b⊕c_in. Carry-out is 1 exactly when at least two inputs are 1. In Boolean notation, c_out=ab+ac_in+bc_in, where + in this expression is OR.

a	b	c_in	Integer total	c_out	s
0	0	0	0	0	0
0	0	1	1	0	1
0	1	0	1	0	1
0	1	1	2	1	0
1	0	0	1	0	1
1	0	1	2	1	0
1	1	0	2	1	0
1	1	1	3	1	1

“Exactly two inputs are 1” is not the carry rule: the 111 row also produces carry 1. “Any input is 1” is also wrong: rows with just one 1 have no carry. These two errors confuse a majority function with equality or OR.

4. Build a full adder from two half adders

First half adder: p=a⊕b and g=ab. Second half adder: s=p⊕c_in and h=pc_in. Combine the two carries with OR: c_out=g+h. Here p is called propagate and g generate under this XOR-propagate convention. Some texts use a different propagate definition; use the equations explicitly rather than relying on the word alone.

Why does the construction work? If a=b=1, g=1 and p=0, so carry is generated regardless of c_in. If exactly one of a,b is 1, g=0 and p=1, so incoming carry passes through: c_out=c_in. If a=b=0, both p and g are 0, so carry is zero. These cases exhaust all input pairs. Also g and h cannot both be 1, though OR is the stated combining function.

Worked input a=1,b=0,c_in=1: p=1, g=0, s=1⊕1=0, h=1, c_out=1. The reconstruction 2×1+0=2 matches 1+0+1. At 111, p=0,g=1,s=1,h=0,c_out=1, reconstructing 3.

5. Trace unsigned ripple-carry addition

An n-bit ripple adder chains full adders. Index bits from i=0 at the least significant end. Column i consumes a_i,b_i,c_i and produces s_i,c_(i+1). Its identity is a_i+b_i+c_i=s_i+2c_(i+1). The carry flows toward more significant columns, even though numbers are normally written most significant bit first.

Add A=1011 and B=0110 with c_0=0. The table is deliberately ordered from the lowest column upward:

Column i	a_i	b_i	c_i	s_i	c_(i+1)
0	1	0	0	1	0
1	1	1	0	0	1
2	0	1	1	0	1
3	1	0	1	0	1

Read stored bits in the opposite direction, s_3s_2s_1s_0=0001. Final carry c_4=1. The exact five-bit result is 10001, which is 17=11+6. For unsigned four-bit storage, low=1 and carry-out=1; discarding carry does not change the mathematical sum into 1.

For general unsigned inputs, the weighted column identities combine to A+B+c_0=S+2^n c_n, with 0≤S<2^n. Internal carry terms cancel when columns are summed. Thus S is the total modulo 2^n, and final carry signals unsigned addition overflow. Do not use final carry alone to diagnose signed overflow; that is a different interpretation and is outside this lesson.

Checking circuits and limits

For one full adder, exhaustively test all eight rows and the integer identity. For a chain, test zeros, maximum values, a carry starting in the low column, a long carry chain and both c_0 values. A ripple arrangement establishes functional correctness; exact latency cannot be stated without a delay model. Real outputs may momentarily change while carry propagates. This lesson checks final steady-state values and makes no clock-frequency claim.

Original practice: six single-correct MCQs

These are original foundation questions, not previous-year questions. Choose exactly one option for each.

C01. What does NAND(A,A) implement?

A. A B. 0 C. A′ D. 1

Answer: C

A is incorrect: NAND(A,A) complements A rather than copying it.

B is incorrect: at A=0 the output is 1, so it is not constant 0.

C is correct: NAND(A,A)=(AA)′=A′ by idempotence.

D is incorrect: at A=1 the output is 0, so it is not constant 1.

C02. For a half adder with a=b=1, what is the ordered pair (sum, carry)?

A. (0,1) B. (1,0) C. (1,1) D. (0,0)

Answer: A

A is correct: sum=1⊕1=0 and carry=1×1=1, so 2×carry+sum=2.

B is incorrect: this reverses the requested order and would encode integer 1.

C is incorrect: using OR for sum produces this wrong pair, which would encode 3.

D is incorrect: the carry is 1; this pair would encode 0.

C03. A full adder receives a=1,b=1,c_in=1. What are (sum, carry-out)?

A. (0,1) B. (1,0) C. (0,0) D. (1,1)

Answer: D

A is incorrect: the sum of three 1s is odd, so the sum bit is 1.

B is incorrect: total 3 needs carry 1, not 0.

C is incorrect: neither output can be 0 because total 3 has binary representation 11.

D is correct: integer total is 3=2×1+1, giving sum 1 and carry-out 1.

C04. Using p=a⊕b and g=ab, which Boolean expression is the full-adder carry-out?

A. p+c_in B. g+pc_in C. gc_in D. p⊕c_in

Answer: B

A is incorrect: at a=1,b=0,c_in=0 it gives 1, although total 1 has no carry.

B is correct: a carry is generated by g or propagated when p and c_in are both 1.

C is incorrect: at a=b=1,c_in=0, g=1 already generates a carry, but gc_in gives 0.

D is incorrect: this expression gives the sum bit, not carry-out.

C05. A 4-bit unsigned ripple adder adds A=1001, B=0111, with c_0=1. What are (low four bits, final carry)?

A. 0001, 1 B. 0000, 1 C. 10001, 0 D. 1111, 0

Answer: A

A is correct: 9+7+1=17=1×16+1, so low bits are 0001 and final carry is 1.

B is incorrect: this ignores the incoming carry 1 and computes only 9+7.

C is incorrect: 10001 is the full five-bit result, not four retained bits.

D is incorrect: 1111 encodes 15, not the required exact total 17.

C06. Which statement correctly describes a half adder and a full adder?

A. A half adder accepts an incoming carry, but a full adder does not. B. Both have one output because each input is one bit. C. A half adder adds two bits; a full adder also accepts an incoming carry bit. D. A full adder always has carry-out 1.

Answer: C

A is incorrect: it reverses the input capabilities.

B is incorrect: each has separate sum and carry outputs to represent the total.

C is correct: the full adder combines a,b,c_in while the half adder combines only a,b.

D is incorrect: inputs 000 or any row with exactly one 1 produce carry-out 0.

Syllabus alignment and scope

This is an introductory lesson within Digital Logic, not complete GATE CS Digital Logic coverage. The official GATE 2027 CS syllabus includes Boolean algebra and minimization, combinational and sequential design, and number representation and arithmetic. Karnaugh maps, tabular minimization, sequential design, signed-number arithmetic and floating-point arithmetic require further lessons. The syllabus verifies relevance; examples and questions here are original.

Official GATE 2027 CS syllabus, Section 2 (checked 2026-10-14).

Technical convention reference; original worked examples and practice: MIT Computation Structures combinational logic.