True or False: Logic

Some sentences are either true or false. “Kathmandu is the capital of Nepal” is true. “Pokhara is in the Terai” is false: Pokhara is in the hills. A sentence like that is called a statement.

Other sentences are neither. “Close the door” is an instruction, “Is it raining?” is a question, and “Wow!” is a feeling. None of them is true or false. “Momo is the best food” is an opinion: true for some people and false for others, so a computer can’t work with it either.

A computer works with statements whose answer is exactly one of the two. In Unit 3 you met them in programs as conditions, like age < 13, and their values, true and false, as the Boolean data type. Since Grade 6 you have also known that a computer is built from switches that are on or off, and that a bit is 1 or 0. These are the same two values with different names:

Truth tables and logic circuits are usually written with 1 and 0, so this unit uses both.

Logic is the study of how true and false statements are combined. The kind of logic computers use, with just two values, is called Boolean logic. It has three basic logical operators: AND, OR and NOT. Each one takes true and false values and gives back a true or false value.

Here is a rule from a school notice: “You may join the science trip if your parents have signed the form and you have paid the fee.” A student who has done both may go. A student who has done only one, or neither, may not.

In logic, AND joins two statements, and the result is true only when both of them are true. If either one is false, or both are, the result is false.

There are only four possible cases, and you can show all of them in a table. Call “the form is signed” A, and “the fee is paid” B:

A table like this, with one row for every possible combination of inputs and the result for each, is called a truth table. The values you start with (here A and B) are the inputs; the result is the output. AND gives 1 in only one row of its four: the row where both inputs are 1.

Notice the order of the rows: 00, 01, 10, 11. That is counting in binary, 0, 1, 2, 3, as in Unit 2. Writing the rows in this order makes sure you don’t miss one or write one twice.

A solar street light with a motion sensor follows an AND rule: it comes on when it is dark AND something is near. Here is the rule in blocks. The blocks run once for each row of the truth table, and the table shows what light holds after each run.

A different notice: “Students can pay the fee in cash or by mobile wallet.” A student who pays either way is fine.

OR joins two statements, and the result is true when at least one of them is true: the first, the second, or both. It is false only when both are false.

OR gives 0 in only one row, the row where both inputs are 0. That is the opposite pattern to AND, which gives 1 in only one row.

The third operator is the simplest. NOT takes one statement and turns it into its opposite: NOT true is false, and NOT false is true. Its truth table has only two rows, because it has only one input:

If raining is true, NOT raining is false. If “the tank is full” is false, “NOT the tank is full” is true: the tank is not full.

NOT is most useful together with AND and OR. Think of the water pump many houses in Nepal use to fill the tank on the roof. It should run when there is water to pump AND the tank is NOT full. If the second part were left out, the pump would carry on after the tank was full, and the water would overflow from the roof.

You have now seen the truth table of each operator on its own. A truth table can be made for any combination of them, and it is the surest way to know exactly what a rule does: it lists every possible case, so nothing is left to guesswork.

To make one:

1. List the inputs in the first columns.
2. Write every combination of inputs, counting in binary. With 1 input there are 2 rows; with 2 inputs, 4 rows; with 3 inputs, 8. Each extra input doubles the rows: with n inputs there are 2ⁿ rows, the same as the patterns n bits can make in Unit 2.
3. Work out the expression one step at a time, in a column for each step, from the inside out. Each new column uses only the columns to its left.

When an expression mixes operators, NOT is done first, then AND, then OR, just as × is done before + in maths. Brackets change the order, as they do in maths. So NOT A AND B means (NOT A) AND B, while NOT (A AND B) means: work out A AND B first, then turn it round.

So far AND, OR and NOT have been ideas. Inside a computer they are made of electricity.

Look at the two circuits in Figure 4.1. Each has a battery, a bulb and two switches, A and B. A closed switch lets the current through (1); an open switch stops it (0); the bulb is 1 when it is lit.

A computer does the same with transistors, the tiny switches you met in Grade 6, which are switched by electricity instead of by a finger. A few transistors joined together make a logic gate: a tiny circuit that takes inputs (usually two; a NOT gate has one), each 1 or 0 (a wire with a voltage on it, or without), and gives one output by the rule of AND, OR or NOT. There is an AND gate, an OR gate and a NOT gate (a NOT gate is also called an inverter).

Each gate has its own symbol, used in circuit diagrams all over the world, and in exams.

One gate on its own can only do AND, OR or NOT. Join them, with the output of one gate wired to an input of another, and you can make any rule at all. Gates wired together like this make a logic circuit.

Start with the street light from earlier: the light comes on when it is dark AND someone is near. In the widget below the sensors are switches, and the lamp is the light. Its goal column shows what the light should do in each row.

Now the water pump. It must run when there is water in the well AND the tank is NOT full. That needs two gates: a NOT, and an AND.

The inverter light

In the years of load-shedding, many homes in Nepal had an inverter: a box that charges a battery while the mains electricity is on, and powers some lights from the battery when it goes off. A light on an inverter shines when its switch is on AND there is power from the mains OR the battery:

switch AND (mains OR battery)

The brackets matter. Without them, AND would be done first, and the rule would mean (switch AND mains) OR battery: the light would come on from the battery even with its switch off.

Rules in notices, games and machines are often written in words. To make a computer follow one, or to build it from gates, you first write it as logic. Here is how:

1. Find the statements: the parts that are true or false. Give each a short name.
2. Find the joining words, and turn each into AND, OR or NOT.
3. Put brackets round any part that must be worked out first.
4. Check it with a truth table: does every row do what the rule means?

The joining words aren’t always “and”, “or” and “not”:

“Unless” brings in an exception: the rule works except when the second part is true. In everyday talk that means the exception stops it, so in a rule for a machine or a program we write AND NOT. (Strictly, “A unless B” only says what happens when B is false, so logic books sometimes write it A OR B; you will meet that in later grades.)

In Unit 3 an if block checked one condition. With and, or and not blocks, one if can check several at once.

A trip is for Grades 6 to 8. The condition “the grade is 6, 7 or 8” is two conditions joined: grade > 5 and grade < 9. Here is a program for the trip, but its author used the wrong word.

NOT is useful in programs too. In Unit 3’s guessing game, the loop asked if found = false. The same can be written if not found: “if we haven’t found it yet”.

AND, OR and NOT are also how you tell a search what you want. Each web page either has a word or doesn’t: true or false. A search for two words joined by AND finds the pages that have both; OR finds the pages that have either; NOT leaves out the pages with a word.

The widget shows twelve made-up pages about wildlife in Nepal. The two circles hold the pages with the word rhino and the pages with the word Chitwan; the pages with both are where the circles overlap. A picture like this, of groups as overlapping circles, is called a Venn diagram, after John Venn, an English mathematician who drew them in 1880.

So:

• AND narrows a search: fewer pages, each with all your words. Use it when a search finds too much.
• OR widens it: more pages, with any of the words. Use it for words that mean the same thing: momo OR dumpling.
• NOT cuts out what you don’t want: jaguar NOT car finds the animal, not the car.

The filters in a shopping app often work the same way. Tick two brands, and you see phones of either brand: OR. Tick a brand and a price range, and you see only phones that are both: AND.