Learning to Program - A Beginners Guide - Part Eight - Working With Logic
We've already seen conditional statements like "if this statement is true then…" and "while this statement is true, do…"
In this section, we're going to look inside these kinds of statements, and focus on the bit that is just about truth and falsity. As usual, the approach will be to learn how to refine a statement from regular language into a rigorous, precise and repeatable form that is useful to a computer, but captures the real-world intent. Ultimately these kinds of statements underpin all of the decision making processes in our programs.
The notion of truth and falsity has two important characteristics for digital computers.
First, it is definite - there is no room for doubt or ambiguity. A statement is either true, or it is false. It can't be a bit true. Or sort-of-false, if you look at it in a certain way. All of those grey areas in real life go out of the window, and you are left with TRUE and FALSE.
Second, since it considers only two values - TRUE and FALSE - this lends itself to being represented by a transistor in its ON and OFF states. By convention, TRUE is conventionally represented by ON (a bit with a 1 in it) while FALSE is represented by OFF (a bit with a 0 in it). But we're skipping ahead a little.
Propositions and operators
In regular English language, propositions are usually bound up with conditionals of some kind, and are frequently used in combination with one another.
"If you've cleaned your bedroom and you've done the washing up, then you can go out and play."
"If virtuacorp shares reach 1.30 or they drop below 0.9, then we'll sell."
The conditional part of both of these sentences is the if - then wrapper around the proposition.
Between the if and then, each of the sentences above actually contains two propositions, which I've highlighted in green and blue to distinguish them from each other.
In each case, the two propositions are combined by an operator (highlighted in purple). In the first case this operator is the word and; in the second case it is the word or.
Our understanding of ordinary language tells us what these operators do: the first (and) means that the whole proposition is true if and only if both propositions are true. The second (or) means that the whole proposition is true if either proposition is true.
You'll notice that each operator has the effect of combining the two propositions on either side of it into a single result. (We call these binary operators because they have two operands. You may remember that we've seen the word operand before!) We're very familiar with this kind of operator in everyday maths.
$$ z = x + y$$
The add operator in regular maths is a binary operator; it takes the expressions on either side of it, and combines them to form a result.
$$ z = x \times y$$
The multiplication operator is another binary operator; it also takes the expressions on either side of it, and combines them to form a result.
Spot test: Can you name two other binary operators you're very familiar with?
Answer: There are several you could pick - the most obvious are probably subtraction and division.
If you said negation - then yes, that is an operator, but it is not a binary operator. It operates on only one value: the value that is to be negated, so it is called a unary operator.
\(z = -y\ \)
You'll also notice the multiplication and addition operators appear between their operands, so we often call them infix operators, whereas the negation operator appears before its operand, so we call it a prefix operator.
So, we can recognize binary and unary operators in regular maths. What about our logical operators, and and or? Can we write those natural language expressions in a more formal way, too?
Let's call the two propositions in the first statement \(p\_1\ \) ("you have cleaned your bedroom") and \(p\_2\ \) ("you have done the washing up"), and the overall proposition \(p\ \) .
We can then write the statement "you've cleaned your bedroom and you've done the washing up" like this
\(p=p\_1 \land p\_2\ \)
We've just added to the list of weird symbols we will one day take for granted. We don't bat an eyelid at \(+\ \) for 'plus' or \(\times\ \) for 'multiplied by' (or, indeed 'p' for "a curious plosive noise we make by violently forcing air through our tightly closed lips as we open our mouth"). This new one is \(\land \ \) and it means 'and'.
This expression, then, just means that if \(p\_1\ \) is true, and \(p\_2\ \) is true, then \(p\ \) is true, otherwise \(p\ \) is false.
Similarly, if \(p\_1\ \) is ("virtuacorp shares reach 1.30") and \(p\_2\ \) is ("virtuacorp shares drop below 0.9"), then we can write the statement "virtuaCorp shares reach 1.30 or they drop below 0.9" as
\(p=p\_1 \lor p\_2\ \)
This means that If \(p\_1\ \) is true, or \(p\_2\ \) is true, then \(p\ \) is true, otherwise \(p\ \) is false, and the symbol \(\lor \ \) represents 'or'.
As well as the binary operators \(\land \ \) and and \(\lor \ \) or, there is a logical unary operator called not which is a part of the family. It has the effect of making a true proposition false and a false proposition true.
If \(p\_1\ \) is ("virtuacorp shares have reached 1.30") then the statement ("virtuacorp shares have not reached 1.30") can be represented by
\(p= \lnot p\_1\ \)
Here are the two families of operators we've seen so far - the familiar ones from everyday maths, and their logical equivalents.
| MULTIPLY | ADD | NEGATE |
|---|---|---|
| \(x \times y\ \) | \(x + y\ \) | \(-x\ \) |
| AND | OR | NOT |
| \(x \land y\ \) | \(x \lor y\ \) | \(\lnot x\ \) |
Truth tables
One way to express what they do is to draw up truth tables for the operators. Given the truth value of each of two propositions, it shows the result of applying a given operator to them.
Here's the truth table for the \(\land \ \) operator (AND). We write the two operands for the operator in the first two columns, and the result in the 3rd column.
| \(p\_1\ \) | \(p\_2\ \) | \(p\ \) |
|---|---|---|
| False | False | False |
| False | True | False |
| True | False | False |
| True | True | True |
Spot test: Can you write out the truth table for the \(\lor\ \) operator? Remember that the result is true if either proposition is true. Give it a go before you look at the answer below.
Answer: Here's the truth table for the \(\lor\ \) operator (OR).
| \(p\_1\ \) | \(p\_2\ \) | \(p\ \) |
|---|---|---|
| False | False | False |
| False | True | True |
| True | False | True |
| True | True | True |
Spot test: what about the truth table for the \(\lnot\ \) operator? Remember that it is a unary operator, so it only has one operand. Again, give it a go before you look at the answer below.
Answer: Here's the truth table for the \(\lnot\ \) operator (NOT).
| \(p\_1\ \) | \(p\ \) |
|---|---|
| False | True |
| True | False |
Boolean algebra
As we mentioned earlier, computers aren't great with complex notions like truth and falsity.
However, they are good with the numbers 0 and 1.
If we use 1 to represent true, and 0 to represent false, we can write our propositions in a way that makes them easier for a computer to understand.
So, if, for example \(x=1\ \) and \(y=0\ \) , then it follows that
\(x \land y=1 \land 0=0\ \)
\(x \lor y=1 \lor 0=1\ \)
\(\lnot x=\lnot 1=0\ \)
\(\lnot y=\lnot 0=1\ \)
We call this Boolean algebra, named for George Boole, who was a 19th Century British mathematician.
We can write out truth tables for these Boolean operators in exactly the same way as we could for our propositions earlier.
Spot test: for which operator is this the truth table?
| \(x\ \) | \(y\ \) | \(z\ \) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Answer: \(\land\ \) (AND)
It turns out that the set of values \({0,1}\ \) and the three operators \({ \land , \lor ,\lnot }\ \) are all we need to construct any Boolean expression we care to think of.
Composition and operator precedence
What happens if we try to compose several binary operators into a more complex expression?
Let's start out (as usual) by looking at this in the familiar world of every day maths
\(a=x+y+z\ \)
That just means add x and y then add z to get the result. But what about this?
\(a=x \times y+z\ \)
Do we multiply x by y, then add z, or multiply x by the result of adding y and z?
We sort this out by applying a convention called operator precedence. By convention, negation takes precedence over multiplication and division, which take precedence over addition and subtraction. So, we would understand the previous equation to mean:
\(a=(x \times y)+z\ \)
This shows us another good (often better!) way of sorting out what we mean when we write down an expression full of operators. We use parentheses (this just means "round brackets" - and is the plural of parenthesis) to indicate which parts of the sum we should calculate as a unit. This can avoid a lot of confusion and helps the reader a lot. It is quite clear that \(a=(x \times y)+z\ \) is not the same as \(a=x \times (y+z)\ \)
Logical operators compose in exactly the same way. NOT takes precedence over AND, which takes precedence over OR.
So
\(0 \lor \lnot 0 \land 1 \land 1 = 0 \lor ((( \lnot 0) \land 1) \land 1) = 1\ \)
Derived operators
The three logical operators we've already seen are all you need to construct a Boolean algebra. However, some special combinations of operators are so useful that we give them names.
Let's think about the light in a stairwell for a minute. It has two switches, one at the top, and one at the bottom. Both switches are off, and so the light is off. I want to go upstairs to bed, so I flip the switch at the bottom to "on", and the light comes on. I trudge up the stairs, trying not to spill my bedtime cocoa (or gin and tonic or whatever), and blearily flip the switch at the top to "on". The light goes off. In the cold, winter's morning, I awake, bright eyed and ready for a day's work, and leap out of bed to head downstairs for a cup of tea (or gin and tonic or whatever). Being a winter's morning, it is still dark, so I flip the switch at the top of the stairs to "off". The light comes on. I bound downstairs two at a time, flip the switch at the bottom to "off" and the light goes off.
We will not look any further into the grim details of my day, but draw out a table describing the states of the switches and the lights throughout that story.
| Switch 1 | Switch 2 | Light |
|---|---|---|
| Off | Off | Off |
| On | Off | On |
| On | On | Off |
| Off | On | On |
| (Off) | (Off) | (Off) |
This looks an awful lot like a Boolean truth table
| x | y | z |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
If both operands are different, then the result is 1. If they are the same, the result is 0. We call this exclusive OR, or sometimes XOR, and it is denoted by the symbol \(\oplus\ \) .
\(0 \oplus 0=0\ \) \(1 \oplus 0=1\ \) \(0 \oplus 1=1\ \) \(1 \oplus 1=0\ \)
However useful this may be (we've already seen a real, practical example of its use in the light switches) - it is not one of our primitive operators. Instead, you can construct it as a combination of the operators AND, OR and NOT.
Let's try an exercise now.
Exercise: Write a Boolean expression using AND, OR and NOT that is equivalent to XOR.
To help you work out the answer to the exercise we're about to try, we can use the interactive programming environment that we installed in our setting up section to experiment with logic.
The setup instructions for this F# environment are here.
Start it up by opening a command prompt / console and typing fsi (Windows) fsharpi (Linux/Mac)
Using F# to experiment with logic
F# understands about Boolean values and operators. It calls the values true and false, and the AND operator is &&, the OR operator is || (you'll probably find this pipe character near the left shift key, or near the return key on the right of the keyboard, but your keyboard layout may vary) and the NOT operator is the word not.
Let's give this a try. First, we could try \(\lnot false \ \)
Type
not false;;
and press return.
(Remember that ;; at the end of the line tells the F# interpreter that we're done with our input and it should execute what we've typed.)
F# responds with the following:
val it : bool = true
You can read that as: "the resulting value ('it') is a bool and that value is true". Which is exactly what we'd expect from this \(\lnot false\ \) .
Let's try a binary operator - AND, say. What's the result of \(true \land false\ \) ? In F#, the AND operator is represented by &&, so we can type:
true && false;;
F# responds:
val it : bool = false
which we read as "the resulting value ('it') is a bool and that value is false"
Spot test: What about OR. What's the result of \(true \lor false\ \) ? OR is represented by || in F#. So what will you type, and what will the F# runtime's output be? As usual, work it out, try it in F#, then check the answer here.
Answer:
true || false;;
val it : bool = true
which we read as "the resulting value ('it') is a bool and that value is true".
A quick aside about the life of a programmer before we get to the answer
Do try this out before looking at the answer. It might take you some time, but don't worry - work it through carefully, and you'll get there in the end.
You'll be doing a lot of this in real, day-to-day programming jobs wherever you are in the stack, and you want to train your brain to think in this way.
One problem with most modern programming is that we have to do an awful lot of donkey work setting up the environment we're working in, preparing data to match the requirements of some 3rd party code we have to integrate with, or dealing with the operating system, programming language and runtime (more on those later), laying out forms or rendering the visuals our User Experience and Design team have lovingly prepared for us. So much so that for many programmers, this seems to be all of the job.
Faced with the need to get some visual to animate in to a web page, they read a book, or search for a blog , and find some code that (pretty much) does the job, with nice step-by-step instructions on how to get it into their application. They bookmark the page, and that tool or code sample becomes part of their development armoury. When they see a problem like that one, they reach for that tool. They're often productive and they get the job done. (Not inventing everything from scratch is a really important part of programming - we're always building on other people's skills and experience.)
However, they often don't really understand why that code did the job for them, or what the constraints were, or under what circumstances it might fail.
And when faced with a knotty piece of business-driven logic like the examples we've seen (even something as simple as a pair of light switches - and real business logic is often much more complicated than this) they don't have the discipline, experience or tools to analyse it to a sufficient level of detail even to get the basic logic right - let alone think about the edge cases. And that's one of the primary sources of bugs in our systems.
We all get sucked into this way of working from time to time - pressure to deliver often leads us to take supposed short-cuts, and hack our way through the problem to some kind of working solution. It is very tempting to take a working example from the web and hammer it in to our application, without taking the time to go back (at some point) and really understand what it does. But that approach usually comes back to bite us later on.
This whole course is about diving into the craft of programming and starting the long journey to really understand (at some level) what we do when we write programs. That's why I'm encouraging you to do the exercises, and not just read the question, and then the answer, and move on.
Also, the people who really understand this stuff, and come in and analyse the mess other people have made of their logic, or advise people how not to get in a mess in the first place, get paid a heck of a lot more than the people doing the day-to-day grind, and (probably) have much more fun to boot. So there are incentives for this investment of your time and brain-power!
OK, you can get back to working on the exercise, now that you're armed with something that lets you quickly test your efforts.
Exercise: Write a Boolean expression using AND, OR and NOT that is equivalent to XOR.
Answer:
Probably the easiest way to approach this problem is through the truth table.
Let's remind ourselves of the truth table for XOR.
| \(x\ \) | \(y\ \) | \(x \oplus y\ \) |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Now, if we discard the rows that produce a false result:
| \(x\ \) | \(y\ \) | \(x \oplus y\ \) |
|---|---|---|
| 1 | 0 | 1 |
| 0 | 1 | 1 |
Looking at the table above, we build terms for each row by ANDing together the operands. If there is a 1 in the column, we just take the operand itself. Otherwise we take its complement.
So, in this case our two terms are:
| \(x\ \) | \(y\ \) | term |
|---|---|---|
| 1 | 0 | \(x \land \lnot y\ \) |
| 0 | 1 | \(\lnot x \land y\ \) |
We now OR those terms together to produce the result.
\(x \oplus y = (x \land \lnot y) \lor (\lnot x \land y)\ \)
This is sometimes called a sum of products approach (thinking about the relationship of OR with addition, and AND with multiplication).
Another way of doing it would be the product of sums approach. In this case, we only look at the false columns in the truth table.
| \(x\ \) | \(y\ \) | \(x \oplus y\ \) |
|---|---|---|
| 1 | 1 | 0 |
| 0 | 0 | 0 |
As the name implies, this time we build rows by ORing together the operands.
| \(x\ \) | \(y\ \) | term |
|---|---|---|
| 1 | 1 | \(x \lor y\ \) |
| 0 | 0 | \(\lnot x \lor \lnot y\ \) |
Then we AND together those terms to produce the result.
\(x \oplus y = (x \lor y) \land (\lnot x \lor \lnot y )\ \)
If you didn't know about the truth-table technique, we could also look at the expression in words "it is true if (x or y) is true, but not if (x and y) is true
This leads us to yet another expression:
\(x \oplus y = (x \lor y) \land \lnot (x \land y)\ \)
So many possible expressions for the same result! In a later section, we're going to look at the rules of Boolean algebra that let us transform from one to another, and find a suitably compact form.
Let's pick one and prove to ourselves that it works by trying a simple example for \(true \oplus false\ \) in F#.
\(x \oplus y=(x \lor y) \land \lnot (x \land y)\ \)
This can be expressed as:
(true || false) && not (true && false);;
That produces the result:
val it : bool = true
So far, so good, but we really need to produce the whole truth table. It will be a bit boring typing that whole expression out every time, so in the next section, we'll learn how to use F# to ease the pain for us.
