Boolean Logic and Gates

From switches to logic

Module 1 said everything is bits. To compute with bits, a computer uses logic gates: tiny circuits, each made from a few transistors, that take one or two bits in and produce one bit out ¹. A transistor is an electrically controlled switch; arranged in small groups, transistors implement each gate’s rule ¹. Everything a processor does, adding, comparing, choosing, remembering, is built by wiring gates together, then wiring those circuits together, layer upon layer ¹.

A gate’s behavior is fully described by its truth table: its output for every combination of inputs ¹.

AND, OR, NOT

The three basic gates ¹:

• AND outputs 1 only when both inputs are 1.
• OR outputs 1 when either input is 1 (or both).
• NOT has one input and flips it.

They’re the same and, or, and not you use in the shell’s &&, ||, and !, and in the logic of everyday rules: “the light comes on if it’s dark AND someone’s in the room.”

More gates

Three more come up constantly ¹:

• NAND: NOT of AND. 0 only when both inputs are 1.
• NOR: NOT of OR. 1 only when both inputs are 0.
• XOR, exclusive or: 1 when exactly one input is 1. It answers “are these two bits different?”

In diagrams, the small circle on NAND and NOR means “then NOT” ¹.

Anything from a few

AND, OR, and NOT together can build any circuit at all, and smaller sets work too: AND with NOT is enough, since A OR B equals NOT(NOT A AND NOT B) ¹. In fact NAND alone can make all the others. NOT A is A NAND A; AND is NAND followed by NOT; OR is NAND of the two inputs’ NOTs. The next lesson’s Python program builds every gate, and then an adder, from a single nand function, which shows how little you need to start from.

From a truth table to a circuit

Designing a circuit follows a recipe ¹:

1. Write the truth table: every combination of inputs and the output you want.
2. For each row where the output is 1, write an AND of the inputs that makes that row true.
3. OR those together.
4. Translate the expression into gates.

For a 1-bit equality circuit, A == B, the output is 1 in two rows: both 0, and both 1. That gives (NOT A AND NOT B) OR (A AND B): two NOTs, two ANDs, and an OR ¹. (It’s the same as NOT (A XOR B), which is why XOR is the “different” gate.) Real designers then simplify, to use fewer gates and shorter paths ¹.

Many bits at once

A gate works on single bits, but a processor applies the same gate to every bit of a number side by side: a 64-bit AND is 64 one-bit AND gates in a row ¹. Programming languages expose exactly this as bitwise operators.

Bitwise operators in bash

bash’s arithmetic has them ²: & (AND), | (OR), ^ (XOR), ~ (NOT), and << and >> (shift left and right):

me@linuxbox:~$ echo $(( 12 & 10 )) $(( 12 | 10 )) $(( 12 ^ 10 ))
8 14 6
me@linuxbox:~$ echo $(( 2#1100 & 2#1010 ))
8

In binary: 1100 & 1010 is 1000 (8), 1100 | 1010 is 1110 (14), and 1100 ^ 1010 is 0110 (6), column by column.

Masks. AND with a pattern of 1s keeps just those bits and clears the rest:

me@linuxbox:~$ echo $(( 0xC8 & 0x0F ))
8

0x0F is 00001111, so this keeps the low four bits of 11001000: 1000, 8. File permissions work this way: the “others may write” bit is one bit in the mode, tested with a mask (Shell course, module 3).

Shifts. Shifting left by one doubles a number, and right by one halves it, dropping the remainder, just as moving digits in decimal multiplies or divides by ten:

me@linuxbox:~$ echo $(( 5 << 1 )) $(( 5 << 3 )) $(( 40 >> 2 ))
10 40 10

NOT flips every bit, all 64 of them in bash, so ~0 is all ones, which in two’s complement is −1 (module 1):

me@linuxbox:~$ echo $(( ~0 ))
-1

Your turn

So

Logic gates, built from a few transistors each, compute on bits: AND (both), OR (either), NOT (flip), and NAND, NOR, and XOR (exactly one). AND, OR, and NOT can build any circuit, and NAND alone can too. A truth table becomes a circuit by ANDing the inputs for each row that outputs 1 and ORing the rows together. Processors apply gates to every bit of a number at once, and bash exposes that as &, |, ^, ~, <<, and >>: masks keep chosen bits, shifts multiply and divide by two.