Analyse a small combinational circuit such as a half adder.
Combinational logic means circuits whose output depends only on the present inputs — no memory, no history. Such a circuit is completely described by its truth table, which lists an output for every input combination, and for n inputs there are 2n rows. The basic gates and their tables are the vocabulary.
Four of the basic gates in distinctive-shape notation. A bubble on the output means the function is inverted.
A
B
AND
OR
XOR
NAND
NOR
0
0
0
0
0
1
1
0
1
0
1
1
1
0
1
0
0
1
1
1
0
1
1
1
1
0
0
0
The two-input gates, all four input combinations.
Two identities do most of the algebraic work, and they are worth knowing as a single idea rather than two rules. De Morgan's theorems say that inverting the output of an AND turns it into an OR of inverted inputs, and vice versa:
A⋅B=Aˉ+BˉA+B=Aˉ⋅BˉDe Morgan's theorems
Practically, this is how you convert a circuit into the gates you actually have. It also explains the bubble notation: a NAND is an AND with an inverted output, but by De Morgan it is equally an OR with inverted inputs — the same physical gate, read two ways, and choosing the reading that makes a schematic clearer is a real skill.
Now a real circuit. Adding two single bits produces a sum bit and a carry bit — and inspecting the truth table shows the sum is exactly XOR and the carry is exactly AND. That circuit is the half adder, and chaining full adders built from it is how every processor performs arithmetic.
The half adder: SUM is A XOR B, CARRY is A AND B. Where wires cross without a dot, they are not connected.
A
B
SUM
CARRY
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
The half adder's truth table — SUM is the XOR column, CARRY the AND column.
WORKED EXAMPLE
Applying De Morgan
A design needs A⋅B⋅C but only two-input NOR gates are available.
By De Morgan: A⋅B⋅C=Aˉ+Bˉ+Cˉ.
An OR of inverted inputs — and a NOR with its output inverted is an OR, while a NOR with tied inputs is an inverter.
So: invert each input with a tied-input NOR, OR them in a NOR-plus-inverter tree, and the function is built entirely from the available part.
Convert to an OR of complements, then build OR from NOR.WORKED EXAMPLE
Reading a circuit's table
Given two gates: Y=A+B feeding an inverter.
NOR then NOT: the inverter undoes the bubble, so Y=A+B — a plain OR.
Confirm from the table above: the NOR column, inverted: 1,0,0,0 inverted is 0,1,1,1, which is the OR column. ✓
Always confirm algebra against the table. The table cannot be wrong; algebra can.
The pair is an OR gate.
PRACTICE
Q1
Write the output column for a two-input XNOR gate.
Q2
Use De Morgan to rewrite X+Y using only AND and NOT.
Q3
Show how to make an inverter from a single NAND gate, and then an AND gate from two NANDs.
Q4
A half adder receives A=1, B=1. What are SUM and CARRY, and why does this case explain the word "half"?