Chapter 10: Evolution of Computing
The lift in a four-storey building will not move until two things are true at the same time: the door is properly shut, and somebody has pressed a button. Miss out either one and nothing happens. There is no arguing with it and no “almost shut”. Inside that lift there is no clever machine making up its mind — only a small circuit that checks two switches and gives the same answer every single time.
Machines have worked like this for most of the last hundred years. A washing machine, a traffic signal at a busy crossing, a calculator, the ticket printer at a railway counter — each one follows fixed rules built out of the only two values an electronic circuit really handles: on and off.
Then people began asking machines harder questions. Is the animal in this photograph a dog or a goat? Will it rain here tomorrow afternoon? Is this handwritten letter an a or a u? For these, there is no switch to check and no single certain answer — and that is where a new way of computing had to begin. See Fig. 10.0-1.
Diagram
Fig. 10.0-1 – split picture. Left half: a lift door with two labelled switches, “door closed” and “button pressed”, both feeding into a small box marked “circuit”, with an arrow from the box to the lift motor; caption strip below reads “fixed rules, one certain answer”. Right half: a phone camera pointed at an animal with a question mark above it, and a rain cloud over a school building with a question mark; caption strip below reads “real questions, uncertain answers”
This chapter will answer all five.
10.1 Why a Computer Works with Just Two Values
Look at the switch on your classroom wall. It has exactly two positions — on and off. There is no position that means “half on”. That is not a weakness of the switch; it is the reason it is so dependable. Anybody walking past can tell, from across the room, which of the two positions it is in.
Inside a computer, information travels as electricity through very thin wires. Electricity is not perfectly steady. It dips a little, it rises a little, and nearby motors and mobile phones add small disturbances called electrical noise. So the machine needs a way of storing information that survives all this wobbling.
Suppose a circuit tried to use ten different voltage levels, one for each of the digits 0 to 9. The levels would sit very close together, and a small dip could turn a 6 into a 5. Now suppose it uses only two levels, one near the bottom and one near the top. Even a fairly large wobble still leaves each level clearly on its own side. Two values are chosen not because the machine is simple-minded, but because two values can be told apart with almost no chance of error.
10.1.1 Bits and the Binary Number System
If a machine has only two symbols to write with, how does it write a number like seven? The same way you write large numbers with just ten symbols — by using more than one digit and giving each position a value of its own.
Each single 0 or 1 that a machine stores is called a bit, short for binary digit.
In the number system we use every day, moving one place to the left multiplies the place value by ten: 1, 10, 100, 1000. In the binary number system, there are only two symbols, so moving one place to the left multiplies the place value by two: 1, 2, 4, 8, 16 and so on. This system is also called the base-2 system, because everything is built on the number two.
Table 10.1 shows the numbers 0 to 9 written in binary using four bits. Notice how the pattern in the right-hand column simply repeats 0, 1 while the columns to its left change more slowly.
To read a binary number, write the place value above each bit and add up the place values that have a 1 under them.
Going the other way is just as easy. To write 13 in binary, take the largest place value that fits — 8 — and put a 1 there. That leaves 13 − 8 = 5. The next place value, 4, fits into 5, so put a 1 there, leaving 5 − 4 = 1. The place value 2 does not fit into 1, so put a 0 there. Finally 1 fits exactly, so put a 1 in the last place. The answer is 1101.
Everything a computer holds ends up as bits: a number, a letter you type, a photograph, a song, the reading from a sensor on a robot. The pattern of 0s and 1s is different for each kind of data, but the storage is always the same two symbols.
10.1.2 High and Low: The Digital Signal
A 0 or a 1 has to be something real inside the wire. What is it, actually?
It is a voltage. In a circuit that runs on a 5 V supply, a voltage close to 0 V is read as one value and a voltage close to 5 V is read as the other. The low one is called logic 0, and the high one is called logic 1. Other circuits use different supply voltages — 3.3 V is also common — but the idea does not change: one level near the bottom, one level near the top, and nothing in between that the circuit is willing to accept.
A voltage used in this way is called a digital signal. See Fig. 10.1-1.
Diagram
Fig. 10.1-1 – a voltage-versus-time graph shaped like a square wave. The horizontal axis is labelled “time” and the vertical axis “voltage”. A shaded band near the bottom of the axis is labelled “logic 0 (low)” and a shaded band near the top is labelled “logic 1 (high)”. The wave jumps between the two bands, and the empty region between the two bands is marked “not used”
A circuit built to work with such signals is called a digital circuit. Because it follows a fixed set of logic rules — this input pattern always gives that output — it is also called a logic circuit. Almost every electronic device you use, from a calculator to the controller board on a robot, is built from digital circuits.
There is one honest limitation here. The world outside the circuit is not made of two levels. Light, temperature, sound and pressure all change smoothly. A digital circuit has to draw a line somewhere and call everything on one side “low” and everything on the other side “high”. A reading that sits very close to that line can flip from one value to the other for no useful reason. You will see later in this chapter why that hard line causes trouble with real-life problems.
10.2 Binary Logic
Knowing that a machine stores 0s and 1s does not yet explain how it takes a decision. For that, the 0s and 1s have to stand for something a decision can be built on.
Read the notice on a computer lab door: you may enter if you are carrying your ID card and you are wearing shoes. Two conditions. Each one is either satisfied or not satisfied — there is no middle answer. And the two are joined by the word and, which tells you exactly how to combine them.
This is the shape of almost every decision a machine takes. A few conditions, each one either satisfied or not, joined by words such as and, or and not. Since a condition has only two possible states, the two states fit the machine’s two symbols perfectly: 1 for satisfied and 0 for not satisfied. Working with conditions in this way is called Boolean logic, and it is what turns a set of switches into a decision.
10.2.1 Boolean Values and Boolean Variables
A statement such as the tank is full is either true or false. Nothing else. These two answers are called Boolean values, and in a circuit they are written as 1 for true and 0 for false.
Now think about how a machine keeps track of such a statement. The tank is not always full, so the answer keeps changing. The machine needs a named place to hold the current answer, and that named place is called a Boolean variable.
Boolean variables are usually given short names such as A, B and Y, exactly as letters are used in algebra. In a real circuit each variable is tied to something physical: A might be the wire coming from a switch on a door, B the wire from a level sensor in a tank, and Y the wire going out to a motor.
10.2.2 The NOT, AND and OR Operations
Conditions on their own are not enough. The lab notice had to join two conditions before it meant anything. Boolean logic has three basic ways of joining or changing conditions, and every decision a digital circuit takes is built out of these three.
Turning a condition around
Sometimes the useful fact is the opposite of what the sensor reports. A pump should run when the tank is not full. The NOT operation takes one value and gives the opposite value: it turns 1 into 0, and 0 into 1. It is written with a bar over the letter, so the opposite of A is written \(\overline{A}\), where A is the original condition. The result is also called the complement of A.
Insisting on both
The lab rule needed the ID card and the shoes. The AND operation takes two or more values and gives 1 only when every one of them is 1. If even one input is 0, the result is 0. It is written like multiplication: \(Y = A \cdot B\), or simply \(Y = AB\), where A and B are the input conditions and Y is the result.
An everyday match: a microwave oven heats only when the door is shut and the timer is running. Both, together, or nothing happens.
Accepting either
Sometimes any one reason is enough. A school buzzer for early dispersal might sound if the principal presses the button or if the fire alarm is triggered. The OR operation gives 1 when at least one of its inputs is 1, and gives 0 only when every input is 0. It is written like addition: \(Y = A + B\).
Notice that the dot and the plus sign are borrowed from arithmetic, but they are not arithmetic. In Boolean logic \(1 + 1 = 1\), because “at least one condition is satisfied” is still simply true.
10.2.3 Truth Tables
Once two or three conditions are joined together, it becomes hard to keep every case in your head. Did you check what happens when the first condition is satisfied but the second is not? A truth table removes the guesswork by listing every possible combination of inputs, one per row, along with the output for that combination.
The number of rows is fixed by the number of inputs:
\[\text{number of rows} = 2^{n}\]
where \(n\) is the number of input variables. Two inputs give 4 rows, three inputs give 8 rows, and four inputs give 16 rows. Nothing is left out, which is exactly the point.
Take a real rule. A school water pump should run only when the tank is not full and the electricity supply is on. Call the two inputs A for “tank is full” and B for “supply is on”, and call the output Y for “pump runs”. In symbols the rule is \(Y = \overline{A} \cdot B\). See Fig. 10.2-1.
Diagram
Fig. 10.2-1 – a simple sketch showing an overhead water tank with a level sensor labelled “A: tank is full” and a mains supply line labelled “B: supply is on”. Both labels lead by arrows into a box marked with the expression Y = (NOT A) AND B, and one arrow leaves the box towards a pump labelled “Y: pump runs”
To build the table, write down all four combinations of A and B, work out \(\overline{A}\) in a middle column, and then apply the AND operation to \(\overline{A}\) and B. The middle column is not part of the answer; it is there so the working stays visible, just as rough work does in a sum.
Read the second row. The tank is not full and the supply is on, so the pump runs. Every other row gives 0, which is what you would want: no pumping into a full tank, and no pretending to pump when there is no supply.
10.3 Logic Gates
The NOT, AND and OR operations are ideas. Ideas do not switch on a pump. Something physical has to take the incoming voltages, work out the answer and send out a voltage of its own.
That something is a logic gate. It is a tiny electronic circuit with one or more input wires and a single output wire. Whatever pattern of high and low voltages arrives at the inputs, the gate puts out the one voltage that the operation calls for.
Because the rule never changes, the same inputs always give the same output — the fifth time, the thousandth time, on a hot afternoon or a cold morning. That reliability is the whole reason machines are built this way.
The six gates you will meet are the AND gate, the OR gate, the NOT gate, the NAND gate, the NOR gate and the EX-OR gate. Each one is drawn with its own symbol so that a circuit diagram can be read at a glance.
10.3.1 The AND, OR and NOT Gates
These three gates carry out the three basic Boolean operations directly. Every other gate can be described in terms of them. Their symbols are shown in Fig. 10.3-1.
Diagram
Fig. 10.3-1 – three gate symbols drawn side by side and labelled. Left: the AND gate, a flat-backed shape with a rounded right end, two input lines A and B on the left, output Y on the right. Middle: the OR gate, a curved-back shape with a pointed right end, inputs A and B, output Y. Right: the NOT gate, a triangle pointing right with a small circle at its tip, single input A, output Y
The AND gate
Some machines must not start unless every safety condition is met at the same time. A power press in a workshop, for example, is often fitted with two start buttons placed far apart, so that the operator’s hands are both occupied and clear of the moving part. The machine runs only when both buttons are held down.
The AND gate does exactly this. Its output is 1 only when all of its inputs are 1. If any one input is 0, the output is 0. It is written as \(Y = A \cdot B\), or simply \(Y = AB\).
The OR gate
A house may have a calling bell at the front gate and another at the side gate. Either one should ring the same buzzer inside. One reason is enough.
The OR gate gives an output of 1 when at least one of its inputs is 1. Its output is 0 only when every input is 0. It is written as \(Y = A + B\).
The NOT gate
A level sensor in a water tank reports “full”. The pump, however, needs to know “not full”. Rather than change the sensor, the circuit flips its answer.
The NOT gate has just one input and one output, and its output is always the opposite of its input. It is written as \(Y = \overline{A}\). Because it turns a value into its opposite, it is also called an inverter.
The small circle at the tip of the NOT gate symbol is the part that stands for inversion. Wherever you see that circle on any gate symbol, it means the output has been flipped.
10.3.2 The NAND, NOR and EX-OR Gates
The remaining three gates are shortcuts. Each one does the work of two gates at once, which saves space, wiring and cost on a real board. Their symbols are shown in Fig. 10.3-2.
Diagram
Fig. 10.3-2 – three gate symbols drawn side by side and labelled. Left: the NAND gate, the AND shape with a small circle at its output, inputs A and B, output Y. Middle: the NOR gate, the OR shape with a small circle at its output, inputs A and B, output Y. Right: the EX-OR gate, the OR shape with an extra curved line drawn just outside its left edge, inputs A and B, output Y
The NAND gate
Suppose a warning lamp must glow whenever a machine is not fully ready — that is, whenever it is not true that both conditions are met. That needs an AND followed by a NOT, and the NAND gate does both in one component.
The NAND gate gives 0 only when all its inputs are 1, and gives 1 in every other case. It is written as \(Y = \overline{A \cdot B}\).
The NOR gate
A control panel might need a lamp that glows only when nothing at all is happening — no motor running, no heater on. The NOR gate is an OR followed by a NOT.
Its output is 1 only when every input is 0. If any input is 1, the output is 0. It is written as \(Y = \overline{A + B}\).
The EX-OR gate
Now think about a staircase light with one switch at the bottom and one at the top. Flipping either switch changes the state of the lamp. The lamp is on when the two switches are in different positions and off when they match.
That is the EX-OR gate, short for exclusive-OR. Its output is 1 when its two inputs are different, and 0 when they are the same. It is written as \(Y = A \oplus B\).
This is the “one or the other, but not both” meaning that ordinary speech usually attaches to the word or. Because it detects a difference, the EX-OR gate is used to compare two bits and report whether they match — a useful step when a machine checks whether data has been received correctly.
10.4 Building a Condition Out of Gates
A single gate handles a single joining word. Real rules are rarely that short. Here is one from a school building:
The lamp above the main gate should glow when it is dark, and either the automatic timer says it is night duty hours or the guard has pressed the manual switch.
There are three conditions in that sentence and two joining words. No single gate can handle it. What is needed is a way of turning a sentence like this into a set of gates wired together — and the wiring has to follow the sentence exactly, or the lamp will behave in ways nobody intended.
The written form of the rule, using Boolean symbols, is called a Boolean expression. Writing the expression first is what makes the wiring straightforward.
Applying the method
Take the gate lamp rule. The three conditions are: it is dark, the timer says night duty hours, and the guard has pressed the manual switch. Call them A, B and C, and call the lamp output Y.
The sentence treats the timer and the manual switch as one unit — either of them will do — so those two go inside a bracket with an OR between them. That whole unit is then combined with darkness using AND, because both parts are needed:
\[Y = A \cdot (B + C)\]
Draw the bracket first. B and C go into an OR gate. The output of that OR gate, along with A, goes into an AND gate, and the output of the AND gate is Y. See Fig. 10.4-1.
Diagram
Fig. 10.4-1 – circuit diagram. Input lines B and C on the left feed an OR gate; the OR gate output is labelled B + C and runs into the lower input of an AND gate. Input line A runs from the left into the upper input of the same AND gate. The AND gate output on the right is labelled Y = A · (B + C)
Three inputs mean eight rows in the truth table. Table 10.9 works the circuit out one gate at a time: the column B + C is the OR gate’s output, and the last column applies the AND gate to A and that result.
Read the top half of the table. Whenever A is 0 — that is, whenever it is daylight — the lamp stays off no matter what the timer or the guard does. That is exactly what the rule asked for, and seeing it in the table is far safer than assuming it.
Diagram
Fig. 10.4-2 – the incorrect circuit for comparison. Inputs A and B feed an AND gate whose output is labelled A · B; that output and input line C feed an OR gate whose output is labelled Y = A · B + C. A small cross or “incorrect wiring” tag is placed beside the diagram
10.5 Deterministic Computing
Every gate you have met obeys a fixed rule. Wire a few thousand of them together and you get a processor; write instructions for that processor and you get a program. At no point does the fixed-rule habit get left behind. It runs all the way up from the single gate to the finished machine.
This gives computing a quality that is easy to take for granted. Type the same sum into a calculator on Monday and on Friday and you get the same answer. Print the same report card twice and the two copies match. There is a name for computing that behaves in this way, and it is worth understanding clearly, because the whole story of artificial intelligence begins where this kind of computing runs out.
10.5.1 What Makes a Computation Deterministic
Before naming the idea, it helps to fix two small words. The input is whatever a task is given to work on — the numbers you type, the reading from a sensor. The output is the result it produces.
A set of steps for turning an input into an output is called an algorithm.
Now suppose an algorithm has no step anywhere that depends on chance. Every step is decided entirely by the values it is working on. Run it again with the same input and it will pass through exactly the same steps in exactly the same order and land on exactly the same output. Computing of this kind is called deterministic computation.
Here is an ordinary algorithm of this type.
The percentage in step 5 uses the formula
\[\text{percentage} = \dfrac{\text{marks obtained}}{\text{maximum marks}} \times 100\]
where marks obtained is the total scored and maximum marks is the largest total possible.
Work the same sum tomorrow and you will get 370 marks and 74% again. That is determinism, and it is the reason nobody expects a report card to change on its own.
10.5.2 Deterministic Problems in Everyday Life
Not every problem suits this style of computing, but a great many do. A deterministic problem is one that has a single correct answer which can be reached by applying fixed rules to the given information. There is nothing left to judge.
Table 10.10 lists a few such problems and the rule that settles each one.
Look at the last two rows in particular. A robot arm that must place a part in the same spot every time, and a signal that must give the same green time every cycle, both need answers that never wander. Deterministic computing is not an old-fashioned way of working — it is the right way to work whenever the answer must be exact and repeatable.
10.5.3 Why Computers Suit Deterministic Work
Traditional computers were built for this kind of work, and they are extremely good at it. There are a few clear reasons.
They are precise. A calculation is carried out to the same accuracy every time, so results can be trusted without being checked by hand.
They are fast and repeatable. The same steps can be run millions of times over, and the millionth run is as exact as the first. A human doing repeated arithmetic gets tired; a processor does not.
They do not add variation of their own. Unless a program has been deliberately written to bring in randomness, nothing inside the machine wanders. That is why the same input gives the same output.
They handle rules well. Comparing values, checking conditions and following a rule book are precisely what a machine built out of logic gates does naturally. Systems that work by applying stored rules — a billing counter, a payroll program, an examination result system — fit this shape exactly.
They work in a controlled setting. A processor sits inside a sealed case at a steady voltage, away from the wind and dust that would disturb a measurement made outdoors.
There is one honest limitation, and it matters. A deterministic machine is faithful, not wise. If the rule it has been given is wrong or unfair, it will apply that wrong rule to every case, at full speed, without ever hesitating. Consistency is only a virtue when the rule being applied consistently is a good one.
10.6 The Limits of Deterministic Computing
Fixed rules work beautifully as long as the world behaves the way the rules assume. Step outside that comfortable region and the same faithfulness turns into a problem.
Ask a calculator for 370 ÷ 500 and it answers instantly. Ask a computer whether it will rain over your school tomorrow afternoon, and no amount of arithmetic settles it. The difference is not the size of the calculation. It is the kind of question being asked.
10.6.1 Real-Life Problems Carry Uncertainty
When a machine works on a real situation, it does not work on the situation itself. It works on a simplified description of it — a few measurements, a few assumptions, a few rules. That description is called a model.
A deterministic model assumes that every input is known exactly and stays as it is. That assumption is fine for a report card, where the marks really are known exactly. It is much shakier outdoors.
Consider a farm sorting tomatoes by ripeness with a camera and a fixed rule: anything redder than a set level is called ripe, anything below it is called unripe. The rule is clear and the machine will follow it perfectly. But sunlight changes through the day, a cloud passes, dust settles on the lens, and a tomato that sits close to the set level gets called ripe in one hour and unripe in the next. See Fig. 10.6-1.
Diagram
Fig. 10.6-1 – a horizontal scale labelled “how red the tomato looks”, with a single vertical dashed line across it labelled “level set by the rule”. Two tomatoes that look almost identical are drawn just either side of the line; the one on the left is tagged “called unripe” and the one on the right “called ripe”. A small sun and cloud above the scale are joined by an arrow to the line, labelled “lighting shifts the reading”
This gap between the tidy model and the untidy world is called uncertainty. It creeps in from several directions at once: measurements are never perfectly accurate, some information is simply missing, and the situation keeps changing while the machine is still working on it.
Handwriting shows the same thing. Ask thirty students to write the letter a and you get thirty shapes, no two alike. A rule such as “a circle with a stroke on its right” will match many of them and quietly fail on the rest. Real examples vary, and a rule written for the neat case does not cover the variety.
10.6.2 Where a Deterministic Model Struggles
The difficulties fall into a few recognisable groups.
Inputs are not exactly known
A deterministic model treats each input as a fixed, correct number. Weather forecasting depends on temperature, pressure, humidity and wind measured at scattered stations, with gaps in between and a small error attached to every reading. The model is being fed values it cannot fully trust.
Complex systems get oversimplified
To keep the rules manageable, a model leaves things out. A traffic model that assumes every vehicle moves at a steady speed and that no junction ever jams is easy to compute and does not describe an actual city road at half past four in the afternoon.
The rules are rigid
When conditions change, a rule-based system does not adjust; it has to be rewritten. A school bus schedule built on fixed running times needs redoing the day a road is dug up, because nothing in it can bend.
Small changes can grow large
Some systems are extremely sensitive to their starting conditions. In weather, a tiny error in today’s measurement can grow into a completely different picture a week later. Share prices behave similarly, which is why no fixed formula predicts them.
Rare events are not covered
Rules are written for what usually happens. A flood-risk model built on the rainfall of ordinary years may badly underestimate the once-in-a-century downpour, simply because such an event was never part of the rules.
The rule book grows out of control
For a question like “is this handwritten letter an a?”, every new style of writing demands another rule, and the exceptions never stop arriving. Long before the system works, the rule book becomes impossible to write or maintain.
None of this makes deterministic computing wrong. It makes it the wrong tool for one particular class of problems — the ones where the information is incomplete, the examples vary, and the honest answer is “probably”. A different way of computing is needed for those.
10.7 Probabilistic Computing and the Need for AI
If the honest answer to a question is “probably”, then a machine that can only answer “yes” or “no” is answering the wrong question. What is needed is a way of computing that can produce a chance instead of a certainty, and can say how strong that chance is.
10.7.1 What Probabilistic Computation Means
Start with the word itself. A probability is a number that says how likely something is. It runs from 0, meaning it never happens, to 1, meaning it always happens, and it is often written as a percentage instead — 0.75 and 75% mean the same thing.
Where does such a number come from? Usually from a record of what has happened before. Suppose a class keeps a simple weather diary for 40 school days, noting whether the sky was cloudy at 8 a.m. and whether it rained later that day. Their record is shown in Table 10.11.
Look at the first row. On 24 cloudy mornings, rain followed on 18 days and did not follow on 6. The same input — a cloudy sky — was followed by two different outcomes. No fixed rule can cover both. A probability can.
\[P = \dfrac{\text{number of times the outcome happened}}{\text{number of times the situation occurred}}\]
where P is the probability of the outcome in that situation.
Notice what the answer is and is not. It does not promise rain. It says that in this record, three cloudy mornings out of four were followed by rain — useful enough to decide whether to carry an umbrella, and honest about the fourth morning.
Computing that works in this way is called probabilistic computation.
Because such a system draws on large records and repeats calculations over and over, it needs a fast processor and plenty of memory. That is exactly what modern computers have, which is why this style of computing has spread only in recent decades even though the mathematics behind it is much older.
10.7.2 Deterministic and Probabilistic Computation Compared
The two ways of computing are not rivals. They answer different kinds of question, and Table 10.12 sets the differences side by side.
The last row is worth reading twice. Nobody wants a billing counter that gives a different total each time, and nobody expects a weather forecast to be certain. Choosing between the two styles means asking what kind of answer the problem actually has.
10.7.3 AI Discretion: Knowing When AI Is Not Needed
Problems in the right-hand column of Table 10.12 are where artificial intelligence (AI) does its work. AI systems learn patterns from large collections of past examples and then give an answer along with how confident that answer is. This lets machines take on a whole class of problems that fixed rules could never reach: reading handwriting, recognising a face, spotting a diseased leaf in a field photograph, forecasting demand at a shop.
The difference in style shows up clearly in something as ordinary as temperature. Give a machine a fixed rule that 35 °C counts as hot, and 34.9 °C is cool — not slightly less hot, but cool, because the rule allows nothing in between. A person standing in that room would not speak like this at all. They would say cool, pleasant, warm or hot, sliding gradually from one word to the next according to how the day feels to them. See Fig. 10.7-1.
Diagram
Fig. 10.7-1 – two temperature scales drawn one above the other over the same range. The upper scale, labelled “a fixed rule”, is split by a single sharp line, with everything on the left tagged “cool” and everything on the right tagged “hot”; the two temperatures just either side of the line are marked to show how close they are. The lower scale, labelled “how a person describes it”, shades smoothly from left to right through the words cool, pleasant, warm and hot, with no sharp boundaries
This does not mean the sharp rule should always be replaced. Deciding when AI is the right tool, and when it is not, is called AI Discretion.
For a deterministic problem, a fixed rule is not merely good enough — it is better. It gives the exact answer, it runs on very little computing power, it can be checked line by line, and it produces the same result every time. Adding AI to a problem like adding up a bill would make the system slower, costlier, harder to explain and less certain, in exchange for nothing at all.
10.8 Summary
- A computer works with only two values because voltage inside a circuit drifts, and two widely separated levels can still be told apart correctly, while ten close levels could not.
- Each single 0 or 1 is a bit, short for binary digit. Numbers are written in the binary number system, where place values double: 1, 2, 4, 8 and so on.
- A digital signal is a voltage allowed to take only two levels, a low one standing for 0 and a high one standing for 1. A circuit built to work with such signals is a digital circuit, also called a logic circuit.
- Boolean logic treats a condition as either true or false, written as 1 or 0. A Boolean variable is a named store holding one of these two values.
- The three basic operations are NOT, which gives the opposite value; AND, which gives 1 only when every input is 1; and OR, which gives 1 when at least one input is 1.
- A truth table lists every possible combination of inputs together with the output for each. The number of rows is 2 raised to the number of inputs.
- A logic gate is an electronic circuit that carries out one logic rule on digital inputs and produces a single digital output.
- The AND, OR and NOT gates carry out the three basic operations. The NAND gate is an AND followed by a NOT, the NOR gate is an OR followed by a NOT, and the EX-OR gate gives 1 only when its two inputs are different.
- A rule written in words becomes a Boolean expression, and the expression is then drawn as gates, working outwards from the innermost bracket. Brackets decide the wiring, so dropping them changes the circuit’s behaviour.
- An algorithm is a finite set of clearly stated steps that turns an input into an output.
- A deterministic computation always produces the same output for the same input, following the same sequence of steps, with no randomness anywhere in it.
- A deterministic problem has a single correct answer reachable by fixed rules — totalling a bill, sorting names, positioning a robot arm. Computers suit such work because they are precise, fast, repeatable and good at following rules.
- A model is a simplified description of a real situation. A deterministic model assumes every input is known exactly, which fails when measurements are incomplete, examples vary, small errors grow, or rare events occur.
- Probabilistic computation works with probabilities instead of certainties, giving the possible outcomes and how likely each one is. The same input may lead to different outcomes.
- Artificial intelligence works on this probabilistic class of problems, learning patterns from past examples and reporting how confident its answer is.
- AI Discretion means choosing the right tool: for a deterministic problem a fixed rule is exact, cheap, checkable and consistent, so AI is not needed there.
10.9 Key Terms
- Algorithm — a finite set of clearly stated steps that takes an input and produces the required output.
- AND operation — a Boolean operation whose result is 1 only when every one of its inputs is 1.
- Artificial intelligence (AI) — the branch of computing in which machines learn patterns from past examples to work on problems whose answers are not certain.
- Binary digit — the full name of a bit; a single 0 or 1.
- Binary number system — the number system that uses only the symbols 0 and 1, in which each place value is twice the one to its right.
- Bit — the smallest piece of information a computer can hold, having the value 0 or 1.
- Boolean expression — a rule written using Boolean symbols, with a bar for NOT, a dot for AND and a plus sign for OR.
- Boolean logic — working with conditions that are either true or false, written as 1 or 0, and combining them using NOT, AND and OR.
- Boolean variable — a named quantity that can hold only one of two values at any moment, 0 or 1.
- Deterministic computation — computation that always produces the same output for the same input, following the same sequence of steps, with no randomness.
- Deterministic problem — a problem that has a single correct answer which fixed rules can work out from the given information.
- Digital circuit — an electronic circuit that works with digital signals and follows a fixed set of logic rules; also called a logic circuit.
- Digital signal — a voltage allowed to take only two levels, a low level standing for 0 and a high level standing for 1.
- Input — whatever a task is given to work on, such as typed numbers or a sensor reading.
- Logic gate — an electronic circuit that takes one or more digital inputs and produces a single digital output according to a fixed logic rule.
- Model — a simplified description of a real situation that a machine uses to work out answers about it.
- NOT operation — a Boolean operation on a single value that gives the opposite value, turning 1 into 0 and 0 into 1.
- OR operation — a Boolean operation whose result is 1 when at least one of its inputs is 1.
- Output — the result a task produces from its input.
- Probabilistic computation — computation that works with probabilities and uncertainty, giving the possible outcomes and how likely each one is instead of a single certain answer.
- Truth table — a table listing every possible combination of input values for a circuit or expression, together with the output produced for each.
- Uncertainty — the gap between a machine’s simplified model and the real situation, caused by measurements that are not exact, information that is missing, or conditions that keep changing.
10.10 Objective Questions
The output of a two-input AND gate is 1 when
- at least one input is 1
- both inputs are 1
- both inputs are 0
- the two inputs are different
Which of the following is a deterministic problem?
- Forecasting tomorrow afternoon’s rainfall
- Recognising a handwritten letter
- Totalling the items on a shop bill
- Predicting the price of a share next week
A single 0 or 1 stored by a computer is called a ______.
A truth table for a circuit with three inputs has ______ rows.
State whether the following is true or false: in Boolean logic, the OR operation gives 0 when both its inputs are 1.
Match each gate in Column A with its property in Column B.
Column A Column B a. NOT gate i. Output is 1 only when both inputs are 1 b. NOR gate ii. Output is the opposite of its single input c. EX-OR gate iii. Output is 1 only when every input is 0 d. AND gate iv. Output is 1 only when the two inputs are different Write the everyday decimal value of the binary number 1110.
10.11 Concept Questions
Explain why a digital circuit uses only two voltage levels instead of ten different levels, one for each decimal digit.
Define deterministic computation and give one example of it from a school office.
Differentiate between the OR gate and the EX-OR gate, using the case where both inputs are 1 to bring out the difference.
A ceiling fan should run when the room switch is on and either the wall regulator is turned up or the remote is used. Write the Boolean expression for this rule, and state what would change in the circuit’s behaviour if the brackets were left out.
A student scores 68, 74, 59, 82 and 90 in five subjects, each carrying a maximum of 100 marks. Work out the total marks and the percentage, showing your steps. Then explain why the same five marks will always give the same percentage, no matter how often the calculation is repeated.
Some problems are best handled by fixed rules and others by probabilistic computation. Explain the difference between the two kinds of problem, giving one example of each, and state why adding artificial intelligence to the first kind brings no benefit.
10.12 Case-Based Questions
A school science club is wiring a fan for the greenhouse. The fan should run only when the temperature is above a set level and the door is closed. Let A be 1 when the temperature is above the set level, B be 1 when the door is closed, and Y be 1 when the fan runs.
- Write the Boolean expression for Y and name the gate needed.
- Draw the complete truth table for this rule, showing all four rows.
- The club later decides that the fan must also run whenever a smoke sensor gives an output of 1, whatever the door position. Name the extra gate that would be needed and state where it would be placed in the circuit.
A school canteen keeps a record over 30 working days of whether the day had games practice and whether the samosa tray sold out. Their record is given below.
- Using this record, work out the probability that the tray sells out on a games day, and write it as a percentage.
- State whether “will the tray sell out tomorrow?” is a deterministic or a probabilistic problem, and give a reason for your answer.
- The manager suggests a fixed rule: always prepare extra trays on games days. Using the record, state one limitation of this rule.