Computers, Algorithms, and Boolean Logic

How to use this guide

Read one short topic, hide it, and reconstruct its definition, rule, or diagram from memory. Attempt the mixed problems before opening their worked answers.

1. Day 0: Do the cold start, study §§2.1–2.3, explain the algorithm and stored-program ideas without looking, and solve practice 1, 3, 5, 8.
2. Day 1: Rebuild the propositional logic rules in §2.4 and solve practice 2, 12, 17, 22, 23.
3. Day 3: Work §§2.5–2.6 from memory; solve practice 4, 6, 7, 9, 11, 14, 15, 18, 20, 24, 25 and check every truth-table row.
4. About day 7: Reconstruct the gate circuits in §2.7, study §2.8, then solve practice 10, 13, 16, 19, 21.
5. About day 14: Re-derive the NAND circuit and take one exam-style problem under a timer.
6. Before the exam: Complete the self-check and both exam problems. Revisit each section named in a missed answer.

When stuck: attempt one small input by hand, name the rule you are applying, then check the result against a table or the definitions. If the prerequisites are missing, study one worked example and solve a fresh one cold.

How the chapter fits together

The route begins with precise procedures and machine execution, then moves from statements to Boolean expressions and finally to gates that implement those expressions.

2.1 Algorithms are finite, executable procedures

An algorithm turns a problem into steps that a person or machine can carry out. A precise procedure also makes it possible to decide whether it finishes and what output it should produce.

In plain words: an algorithm is a recipe precise enough for a machine to follow: it says what goes in, what to do at each step, and what comes out. It must also stop. “Keep improving the guess” only becomes an algorithm once it says when the guess is good enough.

From declarative facts to imperative steps

Declarative knowledge states facts. Imperative knowledge describes how to do something: a sequence of actions with a flow of control and a stopping condition. An algorithm is a finite, well-defined sequence of executable instructions for a class of problems or a computation.

The slides give a tiny example: even “1 + 2 + 3 =” is an algorithm, because it fixes the steps, their order and when you are finished.

An algorithm is more specific than “find a square root”: it says how to make and check successive guesses. The procedure in the notes starts with a guess g; if g² is close enough to x, it stops. Otherwise it replaces g with the average of g and x/g.

Trap: an iteration rule is not complete until it states what counts as close enough and what happens when that test is not met.

Near miss: “start at 1 and keep adding 1 until you reach the largest whole number” has finite text and steps anyone can carry out, but it never stops, because there is no largest whole number. It fails the finite-steps check, so it is not an algorithm.

Try the square-root algorithm lab

2.2 A stored-program computer executes instructions

At bottom a computer does two things: it calculates and it remembers results, and it only knows what it is told. A stored-program computer can carry out many different procedures because its instructions are data stored in memory. The same machine follows a different algorithm when the stored program changes.

In plain words: a computer only calculates and remembers. A stored-program computer keeps its instructions in the same memory as its data, so loading a different program turns the same hardware into a different machine. The processor takes each instruction from memory and carries it out.

Instructions, control flow, and architecture

A fixed-program computer, such as a calculator, does one built-in job. A stored-program computer stores and executes instructions, so its job can change. It keeps a sequence of instructions in memory. A processor executes them using primitive operations such as arithmetic or logic, simple tests, and moving data. Tests can change which instruction runs next; execution stops when the program says it is done or reaches its stopping condition.

The lecture lists six abstract Turing-machine primitives: move right, move left, print a symbol, scan the current symbol, erase it, and do nothing (halt). Modern programming languages package low-level actions into more convenient operations, and you can use abstract methods to create new primitives. A language gives you primitives; expressions are legal combinations of them; expressions and computations have values and meanings. A computable procedure can be expressed in different general-purpose languages, even though syntax and tools differ.

Memory hook: the algorithm is the recipe; the stored program is that recipe represented as instructions the machine can execute.

Near miss: a basic calculator with fixed buttons for +, −, × and ÷ calculates and remembers a result, but its procedures are built into its circuits rather than stored as instructions in memory; giving it a new procedure would mean building a new device. That is the difference a stored program makes.

2.3 Programs have syntax, static meaning, and behaviour

A computer needs instructions that are legal in its language and have a defined interpretation. Separating the kinds of errors helps explain why a program can be rejected, crash, or run while still giving the wrong answer.

In plain words: a program can go wrong at three levels. Syntax is grammar: are the symbols arranged legally? Static semantics is sense: do the legal pieces fit together, such as adding a number to a number? Semantics is meaning: what the program actually does when it runs, which may differ from what you intended.

Three checks on a program expression

Syntax asks whether the symbols form a legal expression. Static semantics asks whether a syntactically legal expression is meaningful under the language's rules, such as whether the operands have compatible types. Semantics is the meaning associated with an expression that passes those checks.

A syntactic error is common and easily caught. Only some languages check for static semantic errors before running, and these errors can cause unpredictable behaviour. A semantic error can be harder: the program may stop, run forever, or return an answer different from the programmer's intention. English can be ambiguous: “Flying planes can be dangerous” has two meanings. A program statement has exactly one meaning, but it may not be the one its author intended.

A program can contain definitions and commands. An interpreter evaluates them in a shell, or a compiler translates the program into processor instructions. Commands may be entered directly or saved in a file for the shell to read.

Trap: “it runs” does not mean “it is right”. A program with no syntax or static semantic errors can still give the wrong answer.

Near miss: a program meant to average three marks that computes a + b + c / 3 has legal syntax and no static semantic error, and it runs, but the division happens before the additions, so it returns the wrong value. It passes every check except doing what was meant.

2.4 Propositions turn logic into two-valued inputs

Boolean circuits calculate with truth values. Propositional logic gives precise rules for combining statements before those rules are translated into algebra or gates.

In plain words: a proposition is a statement that is either true or false, such as “it is raining”. Connectives build bigger statements from smaller ones: NOT flips the value, AND is true only when both parts are true, and OR is true when at least one is. Writing 1 for true and 0 for false turns these rules into arithmetic a circuit can do.

Statements and connectives

A proposition is a statement that is either true or false. Compound propositions use NOT, AND, and OR. In the notes' example, the umbrella output is true when it is raining or the forecast is bad.

For example, let R mean “it is raining” and W mean “the weather forecast is bad”. The umbrella decision is U = W ∨ R. If W = 0 and R = 1, then U = 1.

More complex decisions combine several operations. The lecture gives U = C′ · (W + R): take an umbrella when you are not taking the car and either the forecast is bad or it is raining. Parentheses matter because the operations have different precedence.

Near miss: in everyday speech “tea or coffee” often means one but not both, but this lecture’s OR is inclusive: A ∨ B is also true when both are true. Exclusive or is a separate operation, XOR (§2.7).

Try the Boolean decision lab

2.5 Boolean algebra and truth tables make the rules checkable

Boolean algebra replaces long verbal propositions with symbols and gives every operation a precise meaning. Truth tables then provide a direct way to calculate an expression for every possible input.

In plain words: Boolean algebra writes logic as short formulas: a prime ′ for NOT, · for AND and + for OR, with 1 for true and 0 for false. A truth table checks a formula by listing every combination of inputs with the output for each; with n inputs there are 2ⁿ rows.

Translate propositions into algebra

Boolean values use 1 for TRUE and 0 for FALSE. Variables stand for propositions. The supplied slides write NOT as a prime, OR as +, and AND as ·. Read the notation carefully: here + is logical OR, not ordinary arithmetic addition.

Enumerate every input

A truth table lists an expression's output for every assignment of its input variables. With n Boolean variables there are 2ⁿ assignments. Two expressions are equivalent when their output columns match in every row.

Implication (beyond the notes)

Implication is not in these slides; the “=>” on slide 24 only means “we could write”. Take this truth table as its definition: A ⇒ B is false only for A = 1, B = 0, so its column for (A,B) = 00, 01, 10, 11 is 1, 1, 0, 1. Evaluating A′ + B gives 1, 1, 0, 1 as well, so the two are equivalent.

Trap: three input variables require eight rows, not six. List all assignments before calculating an output column. And + means OR here, so 1 + 1 = 1.

Near miss: 1 + 1 looks as if it should be 2, but here + means OR, and 1 OR 1 = 1. A two-valued system has no 2.

Evaluate Boolean decisions in the lab

2.6 Boolean laws simplify expressions

Boolean laws let you transform an expression while preserving its output. Each identity can be checked with a truth table, and the same law can simplify the design of a circuit.

In plain words: Boolean laws are rewriting rules: each swaps an expression for another that gives the same output for every input, which a truth table can confirm. They shorten formulas, and a shorter formula means a circuit with fewer gates.

Core identities

De Morgan's rules

Negating a compound expression changes its operation and negates each input: NOT of an OR becomes an AND of the negations, and NOT of an AND becomes an OR of the negations.

Trap: De Morgan swaps the operator as well as priming each input. (A + B)′ is not A′ + B′.

Near miss: (A · B)′ = A′ · B′ looks natural, but try A = 1, B = 0: the left side is (0)′ = 1 and the right side is 0 · 1 = 0. De Morgan’s law also swaps the operator: (A · B)′ = A′ + B′.

Test grouping and precedence in the lab

2.7 Logic gates implement Boolean functions

A gate is a circuit block whose output follows a Boolean rule. Algebra connects a circuit diagram to its expression and makes it possible to build several operations from a universal gate.

In plain words: a logic gate is a small circuit that computes one Boolean operation; its output stands for 1 or 0 according to its inputs. A small circle on an output means the result is inverted, turning AND into NAND and OR into NOR. NAND alone can build every other gate, so it is called universal.

Read and combine gates

AND, OR, and NOT gates represent the corresponding operations. A small circle at a gate output indicates inversion, producing NAND or NOR. Follow a multi-gate circuit from its inputs toward its output, giving each intermediate signal a name.

NAND is a universal gate

The lecture calls a set of functions complete when combinations of those functions can generate any Boolean function. NAND alone is complete, so it is also called a universal gate. NAND and NOR are the commonly used building blocks because they are easy to construct from transistors.

Memory hook: bubbles on outputs mean “invert this result”; translate them as a prime before simplifying.

Near miss: XOR and OR agree on three of the four input rows; they differ only at A = B = 1, where OR gives 1 and XOR gives 0. A circuit that mixes them up is right three times out of four and still wrong.

Build with NAND in the lab

2.8 Physical circuits take time to switch

A Boolean truth table describes the stable input-output rule. Real circuits also have timing behaviour because their physical components need time to change state.

In plain words: a truth table says which output a gate settles on, but not when. A real gate is built from physical parts that take a short time to switch, so for a moment after an input changes, the output can still show the old value.

From ideal logic to a real signal

The final slides contrast an ideal, instantaneous gate with real switching. They identify time delay and saturation as limits on how quickly a physical circuit can change its output. Slide 48 shows the output of a NOT built from NAND following a gradual curve across a time Δt rather than jumping. Real gates are built from transistors; slide 49 shows a transistor-transistor logic (TTL) NAND gate. A logic diagram therefore describes function, while a timing diagram is needed to reason about when a change becomes visible.

Trap: do not claim that a real gate changes output at exactly the same instant as its input. The lecture explicitly notes switching delay.

Near miss: a circuit whose truth table is exactly right can still show a wrong value for a moment: if two signals reach a gate along paths with different delays, the gate briefly sees the new value on one input and the old value on the other. Correct logic is not the same as correct timing.

Compare logic and timing in the lab

Formula map and symbols

Check every answer: confirm the operator precedence, list every input assignment, and test the expression against one row that should make it true and one that should make it false.

Derive it cold

Rebuild each result from its definition before opening the worked examples.

1. Run the square-root update twice from x = 16 and g = 3; show each average. §2.1
2. Explain why the sequence, control flow, and stop rule all matter to a recipe. §2.1
3. Build the umbrella table for U = C′ · (W + R) with its partial results. §2.5
4. Take the truth-table definition of A ⇒ B and show its equivalence to A′ + B. §2.5
5. Prove one De Morgan law by comparing its truth-table outputs. §2.6
6. Build NOT, AND, OR and NOR from NAND, naming the law for each. §2.7
7. Translate the two-stage NAND circuit into an expression, then simplify it to X = A′ + B · C. §2.7

Explain it

Answer each question aloud in your own words, then compare with the model answer.

1. Why is a stopping condition part of an algorithm?
2. Why can the same computer execute different algorithms?
3. Why is “3 + 'hi'” different from an expression with invalid syntax?
4. Why does a truth table with n inputs have 2ⁿ rows?
5. Why do parentheses change C′ · (W + R) compared with C′ · W + R?
6. Why is NAND called functionally complete?
7. Why is a Boolean truth table not enough to describe a real circuit's timing?

Mixed practice

Try all 25 problems before opening the worked answers. They alternate across topics so you must choose the rule, not just repeat the previous one.

1. List the three ingredients of a recipe that make it an algorithm in the practical definition from the lecture.
2. Let A=1 and B=0. Evaluate A ∧ B, A ∨ B, and ¬A.
3. A machine stores instructions and uses tests to change which step runs next. Which computer model from the lecture does this describe?
4. How many rows are needed for a truth table with four Boolean inputs?
5. Classify “3 + 'hi'” using the lecture's distinction between syntax and static semantics.
6. Rewrite (A · B)′ using a De Morgan law.
7. For A=1 and B=0, evaluate A ⇒ B and A′ + B. What do you observe?
8. For x=9 and current guess g=2, calculate the next square-root guess using (g + x/g)/2.
9. Rewrite (A + B + C)′ using De Morgan's law.
10. State the difference between an ideal Boolean gate model and a physical circuit model.
11. Let A=0, B=1, C=1. Evaluate A′ + B · C using the stated precedence.
12. Give one possible behaviour of a semantic error even when a program is syntactically valid.
13. For A=1 and B=1, find A XOR B and A XNOR B.
14. Simplify A · A + A using Boolean laws.
15. In C notation, which operator is logical AND: & or &&?
16. A two-stage NAND circuit has I=(A · B)′ and X=(I · C)′. Simplify X.
17. After the first square-root update, explain what the algorithm does if the stopping test still fails.
18. Simplify (A + B)′ · (A + B) using a complement law.
19. For the circuit in problem 16, find X when A=0, B=1, C=0, working through the gates.
20. What is the maximum number of Boolean functions of three input variables? Treat a Boolean function as one choice of output bit for each truth-table row.
21. Write A + B using only NAND operations, then name the law that makes it work.
22. What can a stored-program computer do that a calculator, as a fixed-program computer, cannot?
23. Classify each as a syntax error, a static semantic error, or valid: "hi"5, 3 + "hi", 3.2 * 5.
24. Let V=(C + R) · W′. List every input (C,R,W) that gives V=1.
25. For C=1, W=1, R=1, evaluate C′ · W + R and C′ · (W + R).

Exam-style problems

Set a timer for about 20 minutes per problem. Show intermediate steps and identify the rule behind each conclusion.

1 · From a recipe to an algorithm

For this practice variation on the lecture's square-root recipe, make the stopping test explicit. For positive x, start with a positive guess g, test whether |g²−x| is below a tolerance ε, stop if so, and otherwise set g to (g+x/g)/2 and repeat.

1. Write the sequence of steps in plain language, including the control flow and stop condition.
2. For x=25, g=4, and ε=0.01, calculate two successive guesses and decide whether the second estimate passes the stopping test. If not, does the third?
3. Explain which algorithm properties are demonstrated by the finite instruction list, the tolerance test, and the repeated update. Name one additional condition needed to justify that every run halts.
4. Let the proposition S mean |g²−x|<ε. Write the condition for doing another update as a Boolean expression, and state its value at the first guess of part 2.

2 · Simplify and check a NAND circuit

A circuit has I=(A·C)′ and X=(B·I)′. Assume Boolean inputs.

1. Use Boolean algebra to simplify X.
2. Write the full truth table of X for A,B,C from 000 to 111.
3. Explain why the circuit can be built using NAND gates alone and why its physical output may not change instantaneously.

Slips in the notes

These were checked against the slides. Learn the corrected form, and expect that the slide wording may still be used in the course.

Self-check

Use day 0 to learn and practise. Tick a skill only in a later session, at least one day afterward, when you can demonstrate it without notes. Listed problems provide evidence.

• Explain the algorithm requirements and run the square-root update. (1, 8, 17)
• Describe the stored-program model and instruction classes. (3, 22)
• Distinguish syntax, static semantics, and semantic errors. (5, 12, 23)
• Evaluate NOT, AND, and inclusive OR, and name their C operators. (2, 7, 15)
• Determine truth-table size and enumerate inputs. (4, 20, 24)
• Apply precedence and parentheses correctly. (11, 25)
• Show A⇒B=A′+B with a complete truth table (beyond the notes). (7)
• Use complement, idempotent, and De Morgan laws. (6, 9, 14, 18)
• Translate, simplify and build NAND circuits. (16, 19, 21)
• Distinguish XOR from XNOR by input agreement. (13)
• Explain the difference between Boolean behaviour and switching time. (10)
• Rebuild the listed derivations from definitions.
• Solve both multi-part problems and justify each step.