Boolean Logic

One honest note before we start. Boolean logic is listed in the CBSE Class 11 Computer Science (083) syllabus under Unit 1, Computer Systems and Organisation. It does not have a chapter of its own in the NCERT Class 11 Computer Science textbook. So do not waste time hunting for "the NCERT chapter on Boolean logic" — there isn't one. The topic is examined straight from the syllabus line, and reference books cover it on their own. That is also why the exercise questions later in this chapter are written in the style a CBSE reference book sets, and are not quoted from any numbered NCERT chapter.

Why two values and not ten? Inside a chip, a signal is just a voltage on a wire. Voltages drift — with heat, with the length of the wire, with electrical noise from the motor of a fan sitting next to the machine. If we tried to represent ten digits as ten different voltage levels, a small drift would turn a 6 into a 7 and the machine would be wrong. So hardware designers gave up on ten levels and kept only two, placed as far apart as possible: close to 0 volts and close to the supply voltage. Now a drift of a few tenths of a volt changes nothing, because the two levels are nowhere near each other. We call the low one 0 and the high one 1. Everything else — Aadhaar numbers, UPI transactions, a Reel you scroll past — is built on top of those two states.

Two states also gave us a piece of luck. Mathematics for exactly two values already existed. George Boole worked it out in his 1854 book An Investigation of the Laws of Thought, long before electronics. In 1937 Claude Shannon, in his master's thesis at MIT, showed that Boole's algebra describes switching circuits exactly. That is the link between a school algebra topic and the chip in your phone.

The vocabulary you must get right.

• A Boolean value (or truth value) is one of exactly two things: True or False.
• A Boolean constant is a fixed truth value written directly: True, False (or 1, 0).
• A Boolean variable is a name that holds one of those two values and nothing else. In circuit questions we call them A, B, C.
• A logical statement (proposition) is a sentence that is definitely true or definitely false — "Riya scored 78" is one; "Riya scored well" is not, because "well" has no fixed cut-off.
• A Boolean expression combines Boolean values using operators such as NOT, AND, OR.

Different books write the same two values in different clothes. All of these mean the same thing:

Boolean values in Python. Python has a built-in type called bool with exactly two values, True and False. The capital letters matter — true is not defined and gives a NameError.

a = True
b = False
print(a, b)
print(type(a))
print(int(a), int(b))
print(True + True, True + False)

Real output:

True False

1 0
2 1

Look at the last line. True + True gave 2. That is not a bug. In Python bool is built on top of int, so True is 1 and False is 0 whenever arithmetic is involved. This is genuinely useful — it lets you count how many conditions are true just by adding them — but it also produces trick questions in exams, so remember it.

print(isinstance(True, int))
print(True == 1, False == 0)

True
True True

Truthiness: every value has a truth value. Python will happily treat non-Boolean values as True or False when a condition needs it. The rule is short: anything empty or zero counts as False, everything else counts as True.

print(bool(0), bool(1), bool(-7))
print(bool(0.0), bool(0.1))
print(bool(""), bool("0"), bool(" "))
print(bool([]), bool([0]))

False True True
False True
False True True
False True

Three of those catch students every year. bool(-7) is True — negative is not zero, so it is True. bool("0") is True — it is a string with one character in it, and a non-empty string is True regardless of what that character is. bool(" ") is True for the same reason: a space is a character. Only the truly empty string "" is False.

Worked example: turning a real rule into Boolean values. A school gives a merit certificate only if the student has passed and has at least 75% attendance. Take Riya: 78 marks, 68% attendance.

marks = 78
attendance = 68
P = marks >= 33
Q = attendance >= 75
print("P (passed)      :", P)
print("Q (attendance)  :", Q)
print("P and Q         :", P and Q)
print("P or  Q         :", P or Q)
print("not P           :", not P)

P (passed)      : True
Q (attendance)  : False
P and Q         : False
P or  Q         : True
not P           : False

Riya passed, so P is True. Her attendance is short, so Q is False. The certificate rule is P AND Q, which is False — no certificate. Notice what happened: a school rule written in English became two Boolean variables and one operator. That is the whole point of the subject.

The truth table. A Boolean expression has only finitely many possible inputs, so unlike ordinary algebra we can simply list every case and check. That list is a truth table. With n input variables there are 2ⁿ rows, because each variable independently takes 2 values.

n = 3
print("Variables:", n, "-> rows =", 2 ** n)
rows = 0
for A in [0, 1]:
    for B in [0, 1]:
        for C in [0, 1]:
            rows = rows + 1
            print(A, B, C)
print("Rows printed:", rows)

Variables: 3 -> rows = 8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Rows printed: 8

Always write the rows in normal binary counting order — 00, 01, 10, 11 for two variables; 000, 001, 010, ... , 111 for three. Examiners expect that order, and it makes it obvious if you have skipped a row. Look at the eight lines the program printed: the nested for loops produced exactly that order for free, which is why we will use them for every table in this chapter.

With two values there are only so many useful things you can do to them. Three operators cover the ground: NOT, AND and OR. Everything else in this chapter — NAND, NOR, XOR, whole processors — is these three, wired together.

NOT (complement, inverter). It has one input. It flips it. That's all.

print("A | NOT A")
print("--+------")
for A in [0, 1]:
    print(A, "|", int(not A))

A | NOT A
--+------
0 | 1
1 | 0

Written algebraically, NOT A is A' (some books put a bar over the A). Because flipping twice returns you to the start, (A')' = A. That is called the law of involution or double complement, and it is worth remembering because it lets you cancel pairs of bars in simplification questions.

AND (logical product). Output is 1 only when every input is 1. Think of two switches in series on the same wire: the bulb glows only if both are closed. Real example: a UPI payment goes through only if the PIN is correct AND the balance is enough. One failure kills it.

OR (logical sum). Output is 0 only when every input is 0 — equivalently, 1 if at least one input is 1. Two switches in parallel: the bulb glows if either one is closed. Real example: you can log in to a portal with your roll number OR your registered mobile number.

print("A B | A.B | A+B")
print("----+-----+----")
for A in [0, 1]:
    for B in [0, 1]:
        print(A, B, "|", int(A and B), " |", int(A or B))

A B | A.B | A+B
----+-----+----
0 0 | 0  | 0
0 1 | 0  | 1
1 0 | 0  | 1
1 1 | 1  | 1

Why the odd notation? AND is written like multiplication, A.B or just AB, and OR is written like addition, A + B. Boole picked those symbols because AND behaves exactly like multiplying: 0·0 = 0, 0·1 = 0, 1·1 = 1 — identical to the AND column. OR almost behaves like adding, and the one place it does not is the last row: in Boolean algebra 1 + 1 = 1, not 2. There is no value 2 to go to. Get that one exception into your head and the notation stops being confusing.

An aside that explains why only a handful of gates have names: with 2 inputs there are 4 rows in the truth table, and each row's output can independently be 0 or 1, so there are 2⁴ = 16 different two-input Boolean functions in total. Only about six of them are useful enough to be given names and built as physical gates.

Precedence: which operator goes first. Just as × binds tighter than + in arithmetic, in Boolean work not binds tightest, then and, then or. Python follows the same order.

print(True and False)
print(True or False)
print(not True)
print(not True and False)
print(not (True and False))
print(True or False and False)
print((True or False) and False)

False
True
False
False
True
True
False

Read lines 4 and 5 together. not True and False is (not True) and False = False and False = False, because not grabs only the value immediately after it. not (True and False) is not False = True. Same words, brackets moved, opposite answer. Lines 6 and 7 make the same point for and versus or: True or False and False evaluates the and first, giving True or False = True, while the bracketed version gives False. In the exam, when in doubt, put brackets — you lose no marks for extra brackets and you lose the whole question for a missing one.

A Python-only detail: and / or do not return True or False. They return one of the actual operands. Python evaluates left to right and stops as soon as the answer is certain — this is called short-circuit evaluation.

print(5 and 0)
print(0 and 5)
print(5 or 0)
print(0 or 7)
print("" or "Guest")
n = 0
print(n != 0 and 100 // n > 5)

0
0
5
7
Guest
False

5 and 0 gave 0, not False. For and, Python checks the left side: 5 is truthy, so the answer depends entirely on the right side, and it hands back the right side unchanged. For 0 and 5, the left side is falsy, so the result is already decided and Python returns 0 without even looking at 5. or works the mirror image, which is why "" or "Guest" is the standard way to supply a default name.

Worked example: short-circuiting as a safety net. The last line above is the interesting one. n is 0, so n != 0 is False, so Python never evaluates 100 // n and there is no crash. Swap the two conditions and the protection disappears. Saved as guard.py and run, this is the real Python 3 output:

n = 0
print(100 // n > 5 and n != 0)

Traceback (most recent call last):
  File "guard.py", line 2, in 
    print(100 // n > 5 and n != 0)
          ~~~~^^~~
ZeroDivisionError: integer division or modulo by zero

That error is left here on purpose. In pure Boolean algebra A and B equals B and A (the commutative law), and the truth tables really are identical. In Python the values match but the behaviour does not, because one order divides by zero and the other never gets there. So the guard condition always goes first.

Do not confuse and with &. Python also has bitwise operators &, | and ^ which work on the individual bits of integers. They are not the same thing.

print(2 and 3)
print(2 & 3)
print(2 or 3)
print(2 | 3)

3
2
2
3

2 and 3 is 3 (short-circuit: 2 is truthy so return the right operand). 2 & 3 is 2, because 2 is binary 10, 3 is binary 11, and ANDing bit by bit gives 10 = 2. For 0/1 values the two agree, which is exactly why they are so easy to mix up.

Once you have NOT, AND and OR, three more combinations turn up so often that they get their own names and their own gate symbols: NAND, NOR and XOR. A fourth, XNOR, is worth knowing as XOR's opposite.

• NAND = NOT + AND. Take an AND gate and invert its output. So NAND gives 0 only when both inputs are 1, and 1 in every other case. Expression: (A.B)'.
• NOR = NOT + OR. Take an OR gate and invert its output. NOR gives 1 only when both inputs are 0. Expression: (A+B)'.
• XOR (exclusive OR) = 1 when the inputs are different. It is the "one or the other, but not both" gate. Symbol: A ⊕ B.
• XNOR = NOT of XOR = 1 when the inputs are the same. It is an equality checker. Symbol: (A ⊕ B)'.

The names give away the construction. NAND is "Not AND", NOR is "Not OR". On a circuit diagram this is drawn as the AND or OR shape with a small circle (a "bubble") stuck on the output — the bubble always means "inverted here".

All four in one table, generated rather than copied:

print("A B | NAND | NOR | XOR | XNOR")
print("----+------+-----+-----+-----")
for A in [0, 1]:
    for B in [0, 1]:
        nand = int(not (A and B))
        nor  = int(not (A or B))
        xor  = int(A != B)
        xnor = int(A == B)
        print(A, B, "|  ", nand, " | ", nor, " | ", xor, " | ", xnor)

A B | NAND | NOR | XOR | XNOR
----+------+-----+-----+-----
0 0 |   1  |  1  |  0  |  1
0 1 |   1  |  0  |  1  |  0
1 0 |   1  |  0  |  1  |  0
1 1 |   0  |  0  |  0  |  1

Check it against the plain AND and OR table from the previous section. The AND column reads 0, 0, 0, 1 down the page and the NAND column reads 1, 1, 1, 0 — the same column with every entry flipped, row by row, each row staying where it is. The same holds for OR (0, 1, 1, 1) and NOR (1, 0, 0, 0). Be careful here: flipping each entry is not the same as turning the column upside down. Reading the AND column bottom-to-top gives 1, 0, 0, 0, which is the NOR column, not NAND — a genuinely costly slip in an exam. If you ever forget a NAND table, write the AND table and invert each output where it stands.

Worked example: three ways to write XOR, all the same. XOR is the one gate students define three different ways, so let us prove the definitions agree instead of trusting memory. The classical algebraic form is A'B + AB' — "A is 0 and B is 1, or A is 1 and B is 0". Python can express the same idea as A != B, and for integer 0/1 values as the bitwise A ^ B.

ok = True
for A in [0, 1]:
    for B in [0, 1]:
        xor_def = int((A and not B) or (not A and B))
        xor_ne  = int(A != B)
        xor_xop = A ^ B
        print(A, B, xor_def, xor_ne, xor_xop)
        if not (xor_def == xor_ne == xor_xop):
            ok = False
print("All three agree:", ok)
print("6 ^ 3 =", 6 ^ 3)

0 0 0 0 0
0 1 1 1 1
1 0 1 1 1
1 1 0 0 0
All three agree: True
6 ^ 3 = 5

The three columns after A and B are identical on every row, so all three forms are the same function. Note the caution though: ^ is the bitwise XOR. It matches only because our values are 0 and 1. On larger numbers it works bit by bit — the last line shows 6 ^ 3 is 5, since 110 XOR 011 = 101. In a written CBSE answer, use A'B + AB'.

XOR earns its keep in three places you will meet again: it is the sum bit of binary addition (0+0=0, 0+1=1, 1+0=1, 1+1=0 with a carry), it is how parity bits detect a single-bit error in transmitted data, and it is the core of the simplest encryption schemes, because XORing twice with the same key returns the original.

Universal gates: why factories mostly make NAND. A gate is called universal if you can build every other gate out of copies of it alone. NAND is universal. So is NOR. Here are the three NAND constructions you must be able to reproduce:

• NOT: tie both inputs of one NAND together. A NAND A = (A.A)' = A' (using A.A = A).
• AND: a NAND followed by a NAND-as-inverter. (A NAND B) NAND (A NAND B) = ((A.B)')' = A.B. Two gates.
• OR: invert both inputs first, then NAND them. (A NAND A) NAND (B NAND B) = (A'.B')' = A + B by De Morgan. Three gates.

print("A B | NOT A | A.B | A+B   (all built only from NAND)")
print("----+-------+-----+----")
for A in [0, 1]:
    for B in [0, 1]:
        n1 = int(not (A and A))
        n2 = int(not (A and B))
        andAB = int(not (n2 and n2))
        nA = int(not (A and A))
        nB = int(not (B and B))
        orAB = int(not (nA and nB))
        print(A, B, "|   ", n1, " | ", andAB, " | ", orAB)

A B | NOT A | A.B | A+B   (all built only from NAND)
----+-------+-----+----
0 0 |    1  |  0  |  0
0 1 |    1  |  0  |  1
1 0 |    0  |  0  |  1
1 1 |    0  |  1  |  1

Every single not and and in that program appears in the fixed pattern not (x and y), that is, as a NAND — and the three columns come out exactly as the NOT, AND and OR tables. So NAND alone is enough.

Why this matters commercially. If one gate type can do everything, a fabrication plant can standardise on a single cell and repeat it millions of times, which is cheaper and easier to test than manufacturing many different gate types. NAND also happens to be compact in CMOS technology — a two-input CMOS NAND is built from four transistors — and it is naturally inverting, which suits the way CMOS transistors work. NOR is universal in exactly the same way (tie its inputs for NOT, and so on), and appears in the exam just as often, so learn both sets of constructions.

Two Boolean expressions are equivalent if they produce identical truth tables. That is the only test there is. And since the tables are finite, equivalence is always checkable — you never have to take it on faith, which is a luxury ordinary algebra does not give you.

Why bother shrinking expressions? Because every operator in the expression becomes a physical gate on the chip. Fewer gates means less silicon area, less power drawn from the battery, less heat, and a shorter chain of gates for the signal to travel through, which means a faster circuit. A simplification question is really a cost question.

The basic laws. Learn these as a block; almost every simplification is a sequence of them.

Two of these deserve a second look. A + 1 = 1 feels wrong until you remember that OR means "at least one input is 1" — if one input is permanently 1, the output is permanently 1 whatever A does. And the first distributive law, A + B.C = (A + B).(A + C), is true in Boolean algebra but flatly false in ordinary arithmetic (2 + 3×4 is not (2+3)×(2+4)). Boolean algebra is not arithmetic wearing a hat; it is its own system that happens to borrow the symbols.

Notice how the table is arranged in pairs. That is the principle of duality: take any valid Boolean identity, swap every AND with OR and every 0 with 1, and you get another valid identity. It halves what you have to memorise.

Let us not just assert the single-variable laws — check them:

checks = {"A+0=A":True, "A+1=1":True, "A.0=0":True, "A.1=A":True,
          "A+A=A":True, "A.A=A":True, "A+A'=1":True, "A.A'=0":True,
          "(A')'=A":True}
for A in [0, 1]:
    if int(A or 0) != A: checks["A+0=A"] = False
    if int(A or 1) != 1: checks["A+1=1"] = False
    if int(A and 0) != 0: checks["A.0=0"] = False
    if int(A and 1) != A: checks["A.1=A"] = False
    if int(A or A) != A: checks["A+A=A"] = False
    if int(A and A) != A: checks["A.A=A"] = False
    if int(A or (not A)) != 1: checks["A+A'=1"] = False
    if int(A and (not A)) != 0: checks["A.A'=0"] = False
    if int(not (not A)) != A: checks["(A')'=A"] = False
for law in checks:
    print(law, "->", checks[law])

A+0=A -> True
A+1=1 -> True
A.0=0 -> True
A.1=A -> True
A+A=A -> True
A.A=A -> True
A+A'=1 -> True
A.A'=0 -> True
(A')'=A -> True

De Morgan's laws. These are the two the board asks about, so state them precisely:

• First law: (A . B)' = A' + B' — the complement of a product is the sum of the complements.
• Second law: (A + B)' = A' . B' — the complement of a sum is the product of the complements.

In plain words: break the bar and change the sign. When you push a NOT inside a bracket, every AND becomes an OR and every OR becomes an AND, and every variable picks up its own complement. The mistake worth guarding against is writing (A.B)' = A'.B' — that is wrong, and the truth table below shows exactly which rows it fails on.

You can also feel why it is true in ordinary language. "It is not the case that (I passed AND I have 75% attendance)" means "either I did not pass, OR I do not have 75% attendance" — one failure is enough. The AND turned into an OR because there are two separate ways for the AND to fail.

Worked example: verifying both laws by truth table. This is the standard 3-mark answer, so learn the layout.

print("A B | (A.B)' | A'+B' | (A+B)' | A'.B'")
print("----+--------+-------+--------+------")
law1 = True
law2 = True
for A in [0, 1]:
    for B in [0, 1]:
        L1 = int(not (A and B))
        R1 = int((not A) or (not B))
        L2 = int(not (A or B))
        R2 = int((not A) and (not B))
        print(A, B, "|   ", L1, "  |  ", R1, "  |   ", L2, "  |  ", R2)
        if L1 != R1:
            law1 = False
        if L2 != R2:
            law2 = False
print()
print("De Morgan 1  (A.B)' = A'+B'  holds:", law1)
print("De Morgan 2  (A+B)' = A'.B'  holds:", law2)

A B | (A.B)' | A'+B' | (A+B)' | A'.B'
----+--------+-------+--------+------
0 0 |    1   |   1   |    1   |   1
0 1 |    1   |   1   |    0   |   0
1 0 |    1   |   1   |    0   |   0
1 1 |    0   |   0   |    0   |   0

De Morgan 1  (A.B)' = A'+B'  holds: True
De Morgan 2  (A+B)' = A'.B'  holds: True

Column 3 matches column 4 on all four rows, and column 5 matches column 6 on all four rows. Both laws verified. Now look at the wrong version: is (A.B)' equal to A'.B'? Compare column 3 with column 6. On row 0 1 column 3 is 1 but column 6 is 0, and on row 1 0 the same thing happens. They differ, so the shortcut is false — and one counter-example row is already enough to disprove an identity.

De Morgan extends to any number of variables: (A + B + C)' = A'.B'.C'. Do not take that on trust either — run the same style of check across all eight rows of a three-variable table:

holds = True
for A in [0, 1]:
    for B in [0, 1]:
        for C in [0, 1]:
            L = int(not (A or B or C))
            R = int((not A) and (not B) and (not C))
            if L != R:
                holds = False
print("(A+B+C)' = A'.B'.C' holds:", holds)

(A+B+C)' = A'.B'.C' holds: True

Worked example: simplify A.B + A.B' + A'.B

1. Group the first two terms, which share A: A.B + A.B' = A.(B + B') — distributive law.
2. B + B' = 1 — complement law. So that part becomes A . 1 = A by identity.
3. The expression is now A + A'.B.
4. By the redundancy law, A + A'.B = A + B.

Three AND gates, two OR gates and two inverters collapse into a single OR gate. Verify:

print("A B | AB+AB'+A'B | A+B")
print("----+------------+----")
same = True
for A in [0, 1]:
    for B in [0, 1]:
        left  = int((A and B) or (A and not B) or ((not A) and B))
        right = int(A or B)
        print(A, B, "|      ", left, "     | ", right)
        if left != right:
            same = False
print("Simplification correct:", same)

A B | AB+AB'+A'B | A+B
----+------------+----
0 0 |       0      |  0
0 1 |       1      |  1
1 0 |       1      |  1
1 1 |       1      |  1
Simplification correct: True

Where De Morgan actually helps you in code. A condition like not (marks >= 33 and attendance >= 75) is hard to read. De Morgan's first law rewrites it as marks < 33 or attendance < 75 — "failed, or short on attendance" — which reads the way a teacher would say it, and drops the bracket and the not entirely. The last worked exercise at the end of this chapter runs both versions over a failing, a borderline and a comfortable value of each field and prints the two columns side by side, so you can see for yourself that they agree on all nine combinations.

A logic circuit (or logic diagram) is a Boolean expression drawn as a picture. Inputs enter on the left, gates sit in the middle, the output leaves on the right. Two skills are examined: reading a given circuit to write its expression, and drawing a circuit for a given expression. Both are mechanical once you know the steps.

Standard gate symbols, described in words so you can recognise them in a question paper:

The bubble is the key to reading a diagram fast: a bubble anywhere means "invert at this point". A wire may also split and feed two gates — that is called fan-out, and it is perfectly legal. What is never legal is joining the outputs of two gates onto one wire.

Worked example 1: circuit to expression. A and B go into an OR gate. The OR output goes into a NOT gate. The NOT output and input C go into an AND gate, whose output is F.

Level 1          Level 2           Level 3

A ---+
     +--[ OR ]--+
B ---+          |
                +--[ NOT ]--+
                            |
                            +--[ AND ]-- F
C --------------------------+

Method: label every gate output as you move left to right, then substitute back.

1. Output of the OR gate: T1 = A + B
2. Output of the NOT gate: T2 = T1' = (A + B)'
3. Output of the AND gate: F = T2 . C = (A + B)' . C

Note that this two-gate combination — OR followed by NOT — is exactly a NOR gate, so the same circuit can be redrawn with one NOR gate instead of two gates. Now the truth table. Three inputs, so eight rows, in binary counting order:

print("A B C | (A+B)' | F = (A+B)'.C")
print("------+--------+-------------")
for A in [0, 1]:
    for B in [0, 1]:
        for C in [0, 1]:
            t = int(not (A or B))
            F = int(t and C)
            print(A, B, C, "|   ", t, "   |      ", F)

A B C | (A+B)' | F = (A+B)'.C
------+--------+-------------
0 0 0 |    1    |       0
0 0 1 |    1    |       1
0 1 0 |    0    |       0
0 1 1 |    0    |       0
1 0 0 |    0    |       0
1 0 1 |    0    |       0
1 1 0 |    0    |       0
1 1 1 |    0    |       0

F is 1 on exactly one row, A=0, B=0, C=1. That makes sense from the expression: you need A and B both off for the NOR to give 1, and C on for the AND to pass it through. Keeping the intermediate column (A+B)' in the table is what earns method marks — never jump straight to the final column.

Worked example 2: expression to circuit, and why simplifying pays. Draw a circuit for F = A.(B + C). Start from the innermost bracket: an OR gate takes B and C; its output and A go into an AND gate. Two gates, two levels.

The distributive law says this equals A.B + A.C, which needs two AND gates and one OR gate — three gates for the same job. Same truth table, more hardware:

print("A B C | A.(B+C) | A.B + A.C")
print("------+---------+----------")
same = True
for A in [0, 1]:
    for B in [0, 1]:
        for C in [0, 1]:
            L = int(A and (B or C))
            R = int((A and B) or (A and C))
            print(A, B, C, "|    ", L, "   |     ", R)
            if L != R:
                same = False
print("Distributive law holds:", same)

A B C | A.(B+C) | A.B + A.C
------+---------+----------
0 0 0 |     0    |      0
0 0 1 |     0    |      0
0 1 0 |     0    |      0
0 1 1 |     0    |      0
1 0 0 |     0    |      0
1 0 1 |     1    |      1
1 1 0 |     1    |      1
1 1 1 |     1    |      1
Distributive law holds: True

Identical columns, so the two circuits are interchangeable. If you were manufacturing this, you would pick the two-gate version. This is the whole business case for Boolean simplification.

Worked example 3: the half adder. Here is a circuit that does something real. Add two single bits: 0+0=0, 0+1=1, 1+0=1, and 1+1=10 in binary, which is a sum bit of 0 with a carry of 1. Look at the required columns and you will recognise them — the sum column is XOR, the carry column is AND.

A --+
    +--[ XOR ]-- SUM
B --+

A --+
    +--[ AND ]-- CARRY
B --+

The same two input wires A and B feed both gates; they are drawn twice above only for clarity. That is fan-out, not duplication of the inputs.

print("A B | SUM | CARRY")
print("----+-----+------")
for A in [0, 1]:
    for B in [0, 1]:
        s = int(A != B)
        c = int(A and B)
        print(A, B, " | ", s, " |  ", c)

A B | SUM | CARRY
----+-----+------
0 0  |  0  |   0
0 1  |  1  |   0
1 0  |  1  |   0
1 1  |  0  |   1

Two gates. That is binary addition of one bit, and chaining circuits like this is literally how the adder inside a processor is built.

Worked example 4: designing from a requirement (SOP method). A safety valve must open when at least two of its three sensors A, B and C report danger. This is the majority or 2-of-3 circuit.

The Sum of Products method turns any truth table into an expression: for every row where the output is 1, write one AND term with each variable included plain if it is 1 in that row and complemented if it is 0; then OR all those terms together. Here, though, there is a shortcut — "at least two are 1" means at least one of the three pairs is both-1, so F = A.B + B.C + A.C.

print("A B C | F (at least 2 of 3)")
print("------+--------------------")
for A in [0, 1]:
    for B in [0, 1]:
        for C in [0, 1]:
            F = int((A and B) or (B and C) or (A and C))
            print(A, B, C, "|         ", F)

A B C | F (at least 2 of 3)
------+--------------------
0 0 0 |          0
0 0 1 |          0
0 1 0 |          0
0 1 1 |          1
1 0 0 |          0
1 0 1 |          1
1 1 0 |          1
1 1 1 |          1

F is 1 on exactly the four rows that have two or more 1s, and 0 on the four rows that have one or none. The circuit needs three 2-input AND gates feeding one 3-input OR gate — four gates, two levels. Using two 2-input OR gates instead would make it five gates and three levels, and three levels is slightly slower, because the signal must pass through one more gate before the output settles.