Logic, Gates, Machine
Licensed under ::
by ()
@


Logic, Gates, Machine

George%20Boole%20(1815%E2%80%931864)

George Boole (1815–1864)

In which the reader is made acquainted with a most singular Algebra, wherein there are but two numbers, and the sum of one and one is nothing at all.

Being an account of Mr. Boole’s Laws of Thought, set down in the year 1854 by a Professor of Queen’s College, Cork; of young Mr. Shannon’s relays, and the little gates that came of them; and of how one humble operation — the adding of One to a number — may be performed in three several fashions: by Logic, by Wire, and by the Machine of Mr. Turing.

Wherein the reader is required to lend a thumb, and to consult a partner upon sundry occasions; wherein it is demonstrated that the Carry may very conveniently be kept upon the thumb of the other hand; and wherein, at the last, Logic, Circuit and Machine are discovered to be one and the same contrivance in three different coats.

philosopher's definition of "thinking"

“We may say that thinking is essentially the activity of operating with signs.”

— Ludwig Wittgenstein, The Blue Book (1933–1934), p. 6 of the commonly used edition

Who Does the Thinking?

It is misleading then to talk of thinking as of a “mental activity”. We may say that thinking is essentially the activity of operating with signs. This activity is performed by the hand, when we think by writing; by the mouth and larynx, when we think by speaking; and, if we think by imagining signs or pictures I can give you no agent that thinks.
If then you say that in such cases the mind thinks, I would only draw your attention to the fact that you are using a metaphor, that here the mind is an agent in a different sense from that in which the hand can be said to be the agent in writing.
If again we talk about the locality where thinking takes place we have a right to say that this locality is the paper on which we write; or the mouth which speaks.

— Ludwig Wittgenstein, The Blue Book (1933–1934)

Keep this in mind today: in our exercises, whose hand does the thinking, and where is the carry kept?

Question of the Day

Question of the day: why does counting in binary work — and what is a machine doing when it counts?

You already know how: fold every 1 down, carry to the left, raise the first 0. You did it with a hand and with a Turing machine.

Today we ask why. One algorithm — add 1 — seen in three languages: Logic (Boole), Wire (Shannon), Machine (Turing).

Bring a thumb. Bring a partner. Both will be needed.

Warm-up · Count Together

In pairs. One of you counts in binary on one hand, from 0 up to 11. The other watches and says “stop!” at the first mistake.

Swap. Then count from 0 1 1 1 (7) — what happens, and who remembers the carry while the fingers fold down?

Keep that question. The rest of the session is its answer.

Two Values

Title%20page%20of%20Boole%26rsquo%3Bs%20Laws%20of%20Thought%2C%20London%201854

Title page of Boole’s Laws of Thought, London 1854

1854: George Boole, professor at Queen’s College Cork, publishes An Investigation of the Laws of Thought.

His claim: reasoning itself can be calculated — like algebra — if every statement is reduced to just two values: 1 (true) and 0 (false).

Leibniz’s old dream (calculemus!), now with rules.

A thumb is a perfect Boolean variable: up = 1, down = 0.

Three Operations

NOT flips: NOT 1 = 0, NOT 0 = 1.

AND: true only if both are true (both thumbs up).

OR: true if at least one is true.

aba AND ba OR b
0000
0101
1001
1111

The Fourth: XOR

XOR (exclusive or): true if the two inputs differ — one thumb up, not both.

aba XOR b
000
011
101
110

Note the last row: 1 XOR 1 = 0. Remember it — it will carry the whole session.

Which “or” Do You Mean?

In everyday speech “or” is ambiguous. Logic must not be.

sentencereading
“Soup or salad?” (the menu)XOR — not both (unless you pay extra)
“Smoke or heat sets off the alarm.”OR — and certainly if both
“Are you leaving today or tomorrow?”XOR — you cannot leave twice
“Bring a note from your doctor or your parents.”OR — two notes are no problem
“Milk or sugar in your coffee?”unclear! Both, surely?

Latin had two words for it: vel (inclusive: “one or the other or both”) and aut (exclusive: aut Caesar aut nihil). English has just one — and relies on you to guess.

Ambiguity by Design

Lawyers and programmers cannot afford to guess:

Contracts write “and/or” (inclusive) and “either … or …, but not both” (exclusive), because courts have argued over a bare “or”.

Programming languages give the two meanings different symbols: a || b (or) and a ^ b (xor).

Linguists note that the exclusive reading is often not part of the word at all: we infer “not both” (“if she could say ‘and’, she would have”).

This is Boole’s move: give each meaning its own symbol, and the ambiguity disappears — for a machine, there is no “you know what I mean”.

Exercise · Or or Xor?

In pairs. Take turns reading these sentences aloud; your partner decides OR or XOR and defends the choice with one sentence about the situation:

• “You can pay by card or cash.” • “Students or staff may enter.” • “A fine of fifty euros or three days in jail.” • “She speaks German or French.” • “Take the lift or the stairs.”

Which ones did you disagree on? Notice what you used to decide: not the word “or”, but knowledge of the world.

Now write one real sentence of your own in which the two readings lead to different consequences — a rule, a promise, a threat. Swap, and rewrite your partner’s so it can only be read one way.

Exercise · Thumb Logic

In pairs. Each of you hides a thumb behind your back (up = 1, down = 0) and shows it on three. The teacher calls the gate:

abANDORXORNAND
000001
010111
100111
111100

Show thumbs. As a pair, say the output before checking the table — then check it.

Reverse round: the teacher says gate and output (“XOR gives 1”); you show a pair of thumbs that produces it. Is the answer always unique? For which calls is there only one?

Laws of Algebra

Boole discovered that these operations obey laws, like numbers do:

lawin words
a AND 1 = aAND with 1 changes nothing
a AND 0 = 0AND with 0 kills everything
a OR 0 = aOR with 0 changes nothing
a AND a = arepeating yourself adds nothing
a AND (NOT a) = 0nothing is both true and false
NOT(a AND b) = (NOT a) OR (NOT b)De Morgan (Boole’s contemporary)

Laws like these let you simplify circuits and programs by pure calculation — no thumbs needed.

Algebra, Really

Why is it called algebra? Because the operations behave like arithmetic on 0 and 1:

AND is multiplication: a · b. NOT is 1 − a.

XOR is addition — but one that forgets the carry (addition modulo 2): 1 + 1 = 0.

Add two single bits properly and look at the two digits of the answer:

a + b= carry, sumcarrysum
0 + 00000
0 + 10101
1 + 00101
1 + 11010

The sum digit is XOR. The carry digit is AND. Arithmetic is logic.

A Relay Is a Logical Switch

AND%2C%20OR%2C%20NOT%2C%20XOR%2C%20NAND

AND, OR, NOT, XOR, NAND

1937: Claude Shannon, 21, writes his master’s thesis at MIT: A Symbolic Analysis of Relay and Switching Circuits.

His discovery: electrical switches obey Boole’s algebra. Two switches in series = AND (current flows only if both are closed). In parallel = OR. A relay that opens when energised = NOT.

So any Boolean formula can be built out of hardware — and any circuit can be checked by algebra.

The little symbols for such components are called gates:

NAND Is Enough

One gate is enough to build all the others: NAND (NOT(a AND b)), Sheffer 1913.

NOT a = a NAND a

a AND b = NOT (a NAND b) — i.e. a NAND followed by a NAND with itself.

a OR b = (NOT a) NAND (NOT b) — De Morgan at work.

A NAND gate in a chip costs four transistors. Billions of them, wired by algebra, are every computer you know.

Exercise · Build It from NAND

In pairs. One of you is the architect, the other the inspector.

Architect: on paper, draw XOR using only NAND gates (hint: four NANDs suffice; one of them is shared).

Inspector: feed all four input pairs through the drawing with your thumbs — one gate at a time, out loud. Compare with the XOR table.

If a row fails, find which gate lied. Then swap roles and build OR.

The Half-Adder

The%20half-adder%3A%20XOR%20gives%20the%20sum%20digit%2C%20AND%20gives%20the%20carry

The half-adder: XOR gives the sum digit, AND gives the carry

Put the two observations together: to add two bits b and c you need exactly two gates.

sum = b XOR c   carry = b AND c

This tiny circuit is called the half-adder. All arithmetic in your phone is built from it and its relatives.

Adding One Is Adding a Carry

Our algorithm increment is not a special case: to add 1, put a carry of 1 into the lowest position, then let every position run a half-adder.

c0 = 1 (that is the “+1”)

for every bit bi, from right to left:
outi = bi XOR ci
ci+1 = bi AND ci

The lowest bit has it easiest: b XOR 1 = NOT b — it always flips. Every higher bit flips only if the carry reached it — and the carry survives only through a chain of 1s.

Exercise · Paper Circuit

In pairs. Four numbers: 0101, 0111, 1011, 1111. Increment each using only the two formulas — no counting.

Split the labour like a circuit: one of you computes every XOR, the other every AND and keeps the carry. Fill in a table with columns b, c, out, c′ for each position, right to left.

Check against finger counting. Which number made the carry travel farthest? What is c after the last position of 1111?

Space: A Chain of Gates

Five%20half-adders%3A%20the%20algorithm%20laid%20out%20in%20space

Five half-adders: the algorithm laid out in space

Build the circuit literally: one half-adder per bit, the carry wired from each to its left neighbour.

It is called a ripple-carry circuit: change the input and the carry ripples through the chain like a row of dominoes.

A 64-bit number needs 64 adders. The algorithm is spread out in space.

Time: One Gate Pair, Many Steps

The%20same%20algorithm%20laid%20out%20in%20time

The same algorithm laid out in time

Now the other idea. Do not build five adders. Build one and walk it along the number.

Each step it reads one bit from a tape, computes XOR and AND, writes the result, and moves one cell to the left.

But then the carry from this step must wait for the next one. Something must remember it. That memory is the machine’s state.

The Thumb Is the State

Look again at the rule table of our Turing machine — the one from the Alan session — and write the state as a bit: CARRY = 1, HALT = 0.

state creads bwritesnext statemove
1 (CARRY)010 (HALT)left
1 (CARRY)101 (CARRY)left
0 (HALT)000—
0 (HALT)110—

Writes = b XOR c. Next state = b AND c. The rule table of the machine is the half-adder’s truth table.

A Turing machine is a half-adder with a memory and a moving head. The carry is the thumb of the other hand.

Exercise · Two Hands, One Machine

Alone, then compare. Right hand = tape (thumb is the lowest bit). Left thumb = the state c.

Raise your left thumb: you are adding 1. Now walk along the right hand, thumb to little finger. At every finger say out loud: “out = b XOR c” (set the finger to that value) and “c = b AND c” (set your left thumb to that).

Once the left thumb is down you may stop — nothing further can change.

Count from 0 to 31 this way. Then 31 + 1: the left thumb is still up after the little finger. That is the carry that fell off the tape — overflow. Turing’s tape is infinite; your hand is not.

Exercise · Human Turing Machine

In pairs. Two roles. TAPE: write six cells on paper, e.g. 0 1 0 1 1 1, and cover all but the cell under the head with your hand. MACHINE: you have only a rule card (the table of the previous folio) and your left thumb as the state. You may never see the whole number.

Loop: MACHINE says “read!” — TAPE reveals the bit under the head. MACHINE looks up the row and says “write w, move left”, updating the thumb. TAPE writes and moves the head one cell left. Stop when the thumb is down.

Run 010111, 001111, 111111. Convert to decimal to check. What happens in the last run when the head falls off the tape?

Swap roles. Afterwards discuss: did either of you ever need to know what number it was? Where, physically, was the carry stored?

Exercise · Break the Machine

In pairs. First: the forgetful machine. It has no thumb: at every cell it behaves as if c = 1 (it always flips the bit and always moves on).

Run it on 0101. What should the answer be? Which inputs does the forgetful machine happen to get right, among the sixteen four-bit numbers?

Then the challenge: run it backwards. Design a rule table for subtract 1 (state BORROW) — hint: it is the increment table with the roles of 0 and 1 exchanged. Test it by counting down from 8 on your hands.

Check yourselves: BORROW reads 0 → write 1, move left, stay in BORROW; BORROW reads 1 → write 0, HALT. In algebra: out = b XOR w, w′ = (NOT b) AND w. (And the forgetful machine is right on 0111 and 1111 only.)

Three Languages, One Algorithm

Logic (Boole 1854)Wire (Shannon 1937)Machine (Turing 1936)
what it isformulascircuit of gatestape, head, states
sum digitout = b XOR cXOR gatewrite rule
carryc′ = b AND cAND gate + wirenext state (thumb)
many bitssame formula for each ia chain: spaceone gate pair, repeated: time

Same algorithm, three notations. Algebra says what, gates say with what, the machine says in what order.

And the translation between them is mechanical — which is exactly why computers can exist.

Why Does a Machine That Learns Care?

Every neural network, every language model, runs on chips made of billions of gates just like the ones you drew today — XOR, AND, NAND, wired by algebra and clocked through time.

When people say “the machine computes”, this is all it means: logic, laid out in space, unrolled in time.

Learning does not change that. It changes only which numbers sit in the tape. Next time: how those numbers came to be tuned — Claude, Marvin, John and the others.

Debrief

In pairs, three minutes: explain to each other, without notes, why the sum digit is XOR and the carry is AND.

Then answer the question of the day in two sentences: why does counting in binary work, and what is a machine doing when it counts?

Write down where your thumb was needed. That is the whole difference between a calculator and a table of formulas: memory.

Feedback · Checkout Time

Is there something you like about this seminar?

Is there something you don’t like?

Is there something new and useful you learned during this seminar?