Lego Computer Science: Truth Tables

by Paul Curzon, Queen Mary University of London

Lego of a truth table for NOT P

Truth tables are a simple way of reason about logic that were popularised by the 20th century philosopher Ludwig Wittgenstein. They provide a very clear way to explain what logical operators like AND, OR and NOT mean (or in computational terms, what they do). They also give a simple way to do pure logical reasoning and so see if arguments follow logically. These logical operators crop up in logic circuits and in programs where decisions are being made so are vital to creating correct circuits and writing correct programs. Let’s see what a truth table is by making some from Lego.

Logic in Lego

First we need to represent the basic building blocks of logic in lego. We’ve seen in previous articles how to represent numbers, binary and even images in lego. We have seen that we do computation on symbols and we can use lego blocks as symbols. Logic can therefore be represented in lego symbols too.

We will look at a simple kind of logic called propositional logic (there isn’t actually just one kind of logic but lots of different kinds with different rules). Propositional logic is the simplest kind. It deals with propositions which are just statements that are either true or false (but we may not know which). For example, “Snoopy is a logician.” is a proposition. So are “The world is flat.”, “Water contains oxygen.” and “temperature > 0” as we might find in a program. For the purposes of logic itself, it doesn’t matter what the words actually mean or even what they are. We will therefore represent all propositions by square lego blocks of different colours.

Here we want the symbols to stand for logical things rather than numbers. There are lots of numerical values: things like 1, 5 and 77. There are only two logical values: TRUE and FALSE, often written just as T and F. We will use a blue lego block for the logical value TRUE, and a red block for the value FALSE. They are just symbols though so we could use any blocks and any colours, just as we could use other words for true and false as other languages do. We chose blue for true just because it rhymes so is easy to remember, and red more randomly because it is a common lego primary colour.

True and False lego. A square 2x2 blue block is True. A square 2x2 red block is false.
True and False lego. A square 2×2 blue block represents True. A square 2×2 red block is false.

What about representing the actual sentences stating purported facts like “Messi is the best footballer ever”, or in a program “n == 1”? Statements like this are called propositions. As far as reasoning logically goes the precise words or even language they are in do not matter. This is something Wittgenstein realised. When doing reasoning these basic propositions can be replaced by variables like P and Q and the logic won’t change. Rather than use letters we will just use different coloured lego blocks to stand for different propositions, emphasising that the words or even variable names do not matter. So we will use a yellow block for a variable P and a green block for a variable Q. Each of which could stand for absolutely any English proposition we like at any time (though if we want it to stand for a particular proposition then we should define which one clearly).

Yellow block for P and green block for Q
Propositional variables P and Q are represented by yellow and green blocks

Logical Symbols

What we are really interested in is not just true and false values but the logical operations on propositions. The core of these we use in everyday English: AND, OR and NOT, more technically known as conjunction, disjunction and negation in logic. There are several variations of the symbols used to represent these symbols just as there are for true and false. We will use the versions in lego as below.

Symbols for AND, OR and NOT in Lego
The logical operators AND, OR and NOT as lego symbols

These lego symbols will allow us to write out logical expressions about propositions: like “The cat is thirsty AND NOT the cat is hungry” which we might write in English as “The cat is thirsty and not hungry”. If we use a yellow block to mean “The cat is thirsty” and a green block to mean “The cat is hungry” then in lego logic we can write it as follows:

P AND (NOT Q) in Lego symbols
The cat is thirsty AND NOT the cat is hungry
P AND (NOT Q)

Of course the yellow and green brick are variables so by changing the propositions they represent it can stand for other things. It can also represent: ” The moon is blue AND NOT The moon is made of cheese.” where the yellow brick represents “The moon is blue” and the green brick represents “The moon is made of cheese”.

Think up some statements that involve AND, OR and NOT and then build representations of then in lego logic like the above.

The meaning of logical connectives

The above gives us symbols for the logical connectives, but so far they have no meaning: it is just syntax. Perhaps you think you know what the words mean. We use words like and, or and not in language rather imprecisely at times based on dictionary-style definitions. They essentially mean the same in English as in logic, but we need to define what they mean precisely. We do not want two different people to have two slightly different understandings of what they mean. This is where truth tables come in. A truth table tells us exactly, and without doubt, what the symbols for the operators mean. The give what is called by computer scientists a formal semantics to the logical connectives.

Let’s look at NOT first. A truth table is just a table that includes as rows all the combinations of true and false values of the variables in a logical expression together with an answer for those values. For example a truth table for the operator NOT, so telling us in all situations what (NOT a) means, is:

PNOT P
TRUEFALSE
FALSETRUE
A truth table for the NOT operator. Reading along the rows,
IF P is TRUE THEN (NOT P) is FALSE;
IF P is FALSE THEN (NOT P) is TRUE.

We can build this truth table in lego using our lego representation:

Lego of a truth table for NOT P

NOT only applies to one proposition, the one it negates, (it is a unary logical connective). That means we only need two rows in the table to cover the different possible values those propositions could stand for. AND (and OR) combine to two propositions (it is a binary logical connective). To cover all the possible combinations of the values of those propositions we need a table with four rows as there are four possibilities.

PQ P AND Q
TRUETRUETRUE
TRUEFALSEFALSE
FALSETRUEFALSE
FALSEFALSEFALSE
A truth table for the logical AND operator.

We can build this in Lego as:

Lego of a truth table for P AND Q

Reading along the rows this says that if both P and Q are blue (true) then the answer for P AND Q is true. Otherwise the answer is false (red). T

The following is the lego truth table for the logical OR operator

Lego of a truth table for P AND Q

The columns for the two variables yellow/green (P/Q) are the same, setting out all the possibilities. Now the answer is true (blue) if either operand is true (blue) and false (red) when both are false (red).

We have now created lego truth tables that give the meaning of each of these three logical connectives. They aren’t the only logical operators – in fact there are 8 possible binary ones. Have a go at building lego truth tables for other binary logical connectives such as exclusive-or which is true if exactly one of the operands is true, and equivalence which is true if both operands are the same truth value.

Truth tables give precise meanings to logical operators and so to logic. That is useful, but even more usefully, they give a way to reason logically in a clear, price way. By following a simple algorithm to build new truth tables from existing ones, we can prove general facts, that are ultimately about propositions, in lego… as we will see next.


Lego Computer Science

Image shows a Lego minifigure character wearing an overall and hard hat looking at a circuit board, representing Lego Computing
Image by Michael Schwarzenberger from Pixabay

Part of a series featuring featuring pixel puzzles,
compression algorithms, number representation,
gray code, binary and computation.

Lego Computer Science

Part 1: Lego Computer Science: pixel picture

Part 2: Lego Computer Science: compression algorithms

Part 3: Lego Computer Science: representing numbers

Part 4: Lego Computer Science: representing numbers using position

Part 5: Lego Computer Science: Gray code

Part 6: Lego Computer Science: Binary

Part 7: Lego Computer Science: What is computation (simple cellular automata)?

Part 8: Lego Computer Science: Truth tables

More on …


EPSRC supports this blog through research grant EP/W033615/1, The Lego Computer Science post was originally funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.

Jacquie Lawson: the multi-million pound greeting

by Paul Curzon, Queen Mary University of London

(from the cs4fn women are here special issue)

There is real money to be made out there in the virtual world – if you are willing to put in the effort to develop appropriate skills.

You don’t have to be young or a geek either. At the age of 62, grandmother Jacquie Lawson turned a hobby into a multi-million pound business. She is a trained illustrator having originally studied art at St Martins School of Art in London. She bought her first computer in 1998. Despite struggling at the start she taught herself to draw computer animations using Macromedia Flash.

Just for fun she made an animated Christmas e-card and sent it to friends. Her skill as an illustrator combined with her artistic flair meant that suddenly she was inundated with people wanting them from around the world – a wonderful example of viral marketing.

“The Internet is such a fantastic medium.
It ought to be better.”

She set up a business, launched the http://www.jacquielawson.com e-card website and is now the market leader – with double the visitors of its nearest rival. As Jacquie says about the Internet: “It’s such a fantastic medium. It ought to be better”.

She believes there is a lot of rubbish on the Internet – which means there is scope for skilled, creative people to make a difference by focusing on detail in what they do. Quality can stand out.

So develop the basic skills, have a great idea, throw in some business savvy…but most of all do it for fun, if you want to end up with a successful business.

Activity

Be inspired by Jacquie Lawson. Make your own computer greeting card for some special occasion (whether Valentine’s day, a birthday, Mothers day or Fathers Day…). It might be a still drawing or an animation. Perhaps it could even be a program. Use a technology you are familiar with, or learn one you haven’t used before for the occasion – Scratch perhaps or a drawing program. Learning new skills can be very rewarding and sometimes can lead to new opportunities.

More on …

Related Magazines …


EPSRC supports this blog through research grant EP/W033615/1. 

Ludwig Wittgenstein: tautology and truth tables

by Paul Curzon, Queen Mary University of London

A jigsaw of the word truth with pieces missing
Image by Gerd Altmann from Pixabay
Image by Gerd Altmann from Pixabay

Ludwig Wittgenstein is one of the most important philosophers of the 20th century. His interest was in logic and truth, language, meaning and ethics. As an aside he made contributions to logical thinking that are a foundation of computing. He popularised truth tables, a way to evaluate logical expressions, and invented the modern idea of tautology. His life shows that you do not have to set out with your life planned out to ultimately do great things.

Wittgenstein was born in Austria, of three-quarters Jewish descent, and actually went to the same school as Hitler at the same time, as they were the same age to within a week. Had he still been in Austria at the time of World War II he would undoubtedly have been sent to a concentration camp. Hitler presumably would not have thought much of him had he known more about him at school. Not only did he have a Jewish background, he was bisexual: it is thought he fell in love four times, once with a woman and three times with men.

Interested, originally, in flying and so aeronautic engineering he studied how kites fly in the upper atmosphere for his PhD in Manchester: flying the kites in the Peak District. He moved on to the study of propellors and designed a very advanced propellor that included mini jet engines on the propellor blades themselves. Studying propellors led him to an interest in advanced mathematics and then ultimately to the foundations of mathematics – a course about which, years later, he taught at Cambridge University that Alan Turing attended. Turing was teaching a course with the same title but from a completely different point of view at the time. His interest in the foundations of maths led to him thinking about what facts are, how they relate to thoughts, language and logic and what truth really was. However, World War I then broke out. During the war he fought for the Austro-Hungarian army, originally safe behind the lines but at his own request he was sent to the Russian Front. He was ultimately awarded medals for bravery. While on military leave towards the end of the war he completed the philosophical work that made him famous, the Tractatus Logico-Philosophicus. After the war though he went to rural Austria and worked as a monastery gardener and then as a primary school teacher. His sister suggested this was “like using a precision instrument to open crates”, though as he got into trouble for being violent in his punishments of the children the metaphor probably isn’t very good as he doesn’t sound like a great teacher and as a teacher he was more like a very blunt instrument.

In his absence, his fame in academia grew, however, and so eventually he returned to Cambridge, finally gained a PhD and ultimately became a fellow and then a Professor of Philosophy. By the time World War II broke out he was teaching philosophy in Cambridge but felt this was the wrong thing to be doing during a war, so despite now being a world famous philosopher went to work as a porter in Guy’s hospital, London.

His philosophical work was ground breaking mainly because of his arguments about language and meaning with respect to truth. However, a small part of has work has a very concrete relevance to computing. His thinking about truth and logic had led him to introduce the really important idea of a tautology as a redundant statement in logic. The ancient Greeks used the word but in a completely different sense of something made “true” just because it was said more than once, so argued to be true in a rhetorical sense. In computational terms Wittgenstein’s idea of a tautology is a logical statement about propositions that can be simplified to true. Propositions are just basic statements that may or may not be true, such as “The moon is made of cheese”. An example of a tautology is (a OR NOT(a)) where (a) is a variable that stands for a proposition so something that is either true or false. Putting in the concrete propositions “The moon is made of cheese” we get:

“(The moon is made of cheese) OR NOT (The moon is made of cheese)”

or in other words the statement

“The moon is made of cheese OR The moon is NOT made of cheese”

Logically, this is always true, whatever the moon is made of. “The moon is made of cheese” can be either true or false. Either it is made of cheese or not but either way the whole statement is true whatever the truth of the moon as one side or other of the OR is bound to be true. The statement is equivalent to just saying

“TRUE”

In other words, the original statement always simplifies to truth. More than that, whatever proposition you substitute in place of the statement “The moon is made of cheese” it still simplifies to true eg if we use the statement instead “Snoopy fought the Red Baron” then we get

“Snoopy fought the Red Baron OR NOT (Snoopy fought the Red Baron)”

Again, whatever the truth about Snoopy, this is a true statement. It is true whatever statement we substitute for (a) and whether it is true or false: (a OR NOT(a)) is a tautology guaranteed to be true by its logical structure, not by the meaning of the words of the propositions substituted in for a.

As part of this work Wittgenstein used truth tables, and is often claimed to have invented them. He certainly popularised them as a result of his work becoming so famous. However, Charles Sanders Peirce used truth tables first, 30 years earlier. The latter was a philosopher too, know as the “Father of Pragmatism” (so hopefully that means he wouldn’t have minded Wittgenstein getting all the credit!)

A truth table is just a table that includes as rows all the combinations of true and false values of the variables in logical expressions together with an answer for those values. For example a truth table for the operator NOT, so telling us in all situations what (NOT a) means, is:

aNOT a
TRUEFALSE
FALSETRUE
A truth table for the NOT operator. Reading along the rows,
IF a is TRUE then (NOT a) is FALSE; IF a is FALSE then (NOT a) is TRUE.

The first thing that is important about truth tables is that they give very clear and simple meaning (or “semantics”) to logical operators (like AND, OR and NOT) and so of statements asserting facts logically. Computationally, they make precise what the logical operators do, as the above table for NOT does. This of course matters a lot in programs where logical operators control what the program does. It also matters in hardware which is built up from circuits representing the logical operations. They provide the basis for understanding what both programs and hardware do.

The following is the truth table for the logical OR operator: again the last column gives the meaning of the operator so the answer of computing the logical or operation. This time there are two variables (a) and (b) so four rows to cover the combinations.

aba OR b
TRUETRUETRUE
TRUEFALSETRUE
FALSETRUETRUE
FALSEFALSEFALSE
A truth table for the logical OR operator. Reading along the rows,
IF a is TRUE and b is TRUE then (a OR b) is TRUE;
IF a is TRUE and b is FALSE then (a OR b) is TRUE;
IF a is FALSE and b is TRUE then (a OR b) is TRUE;
IF a is FALSE and b is FASLE then (a OR b) is FALSE;

Truth tables can be used to give more than just meaning to operators, they can be used for doing logical reasoning; to compute new truth tables for more complex logical expressions, including checking if they are tautologies. This is the basis of program verification (mathematically proving a program does the right thing) and similarly hardware verification. Let us look at (a OR (NOT a)). We make a column for (a) and then a second column gives the answer for (NOT a) from the NOT truth table. Adding a third column we then look up in the OR truth table the answers given the values for (a) and (NOT a) on each row. For example, if a is TRUE then NOT a is FALSE. Looking up the row for TRUE/FALSE in the OR table we see the answer is TRUE so that goes in the answer column for (a OR (NOT a)). The full table is then:

aNOT aa OR (NOT a)
TRUEFALSETRUE
FALSETRUETRUE
A truth table for the a OR NOT a. Reading along the rows,
IF a is TRUE then (a OR (NOT a)) is TRUE;
IF a is FALSE then (a OR (NOT a)) is TRUE;

Truth tables therefore give us an easy way to see if a logical expression is a tautology. If the answer column has TRUE as the answer for every row, as here, then the expression is a tautology. Whatever the truth of the starting fact a, the expression is always true. It has the same truth table as the expression TRUE (a) where TRUE is an operator which gives answer true whatever its operand.

aTRUE
TRUETRUE
FALSETRUE
A truth table for the TRUE operator. Whatever its operand it gives answer TRUE.

We can do a similar thing for (a AND (NOT a)). We need the truth table for AND to do this.

aba AND b
TRUETRUETRUE
TRUEFALSEFALSE
FALSETRUEFALSE
FALSEFALSEFALSE
A truth table for the logical AND operator.

We fill in the answer column based on the values from the (a) column and the (NOT a) column looking up the answer in the truth table for AND.

aNOT aa AND (NOT a)
TRUEFALSEFALSE
FALSETRUEFALSE
A truth table for the a AND (NOT a). Reading along the rows,
IF a is TRUE then a AND (NOT a) is FALSE;
IF a is FALSE then a AND (NOT a) is FALSE;

This shows that it is not a tautology as not all rows have answer TRUE. In fact, we can see from the table that this actually simplifies to FALSE. It can never be true whatever the facts involved as both (a) and (NOT a) are never true about any proposition (a) at the same time.

Here is a slightly more complicated logical expression to consider: ((a AND b) IMPLIES a). Is this a tautology? We need the truth table for IMPLIES to work this out:

aba IMPLIES b
TRUETRUETRUE
TRUEFALSEFALSE
FALSETRUETRUE
FALSEFALSETRUE
A truth table for the logical IMPLIES logical operator.

When we look up the values from the (a AND b) column and the (a) column in the IMPLIES truth table, we get the answers for the full expression ((a AND b) IMPLIES a) and find that it is a tautology as the answer is always true:

aba AND ba(a AND b) IMPLIES a
TRUETRUETRUETRUETRUE
TRUEFALSEFALSETRUETRUE
FALSETRUEFALSEFALSETRUE
FALSEFALSEFALSEFALSETRUE
A truth table for the logical expression (a AND b) IMPLIES a.

Using the same kind of approach we can use truth tables to check if two expressions are equivalent. If they give the same final column of answers for the same inputs then they are interchangeable. Let’s look at (b OR (NOT a)).

abNOT a(b OR (NOT a))
TRUETRUEFALSETRUE
TRUEFALSEFALSEFALSE
FALSETRUETRUETRUE
FALSEFALSETRUETRUE
A Truth table for the logical expression (b OR (NOT a)).

This gives exactly the same answers in the final column as the truth table for IMPLIES above, so we have just shown that:

(a IMPLIES b) IS EQUIVALENT TO (b OR (NOT a))

We have proved a theorem about logical implication. (a IMPLIES b) has the same meaning as, so is interchangeable with, (b OR (NOT a)). All tautologies are interchangeable of course as they are all equivalent in their answers to TRUE. If we give a truth table for IS EQUIVALENT TO we could even show equivalences like the above are tautologies!

Tautologies, and equivalences, once proved, can also be the basis of further reasoning. Any time we have in a logical expression (a IMPLES b), for example, we can swap it for (b OR (NOT a)) knowing they are equivalent.

Truth tables helped Wittgenstein think about arguments and deduction of facts using rules. In particular, he decided special rules that other philosophers suggested should be used in deduction, were not necessary, as such. Deduction instead works simply from the structure of logic that means logical statements follow from other logical statements. Truth tables gave a clear way to see the equivalences resulting from the logic. Deduction is not about meanings in language but about logic. Truth tables meant you could decide if something was true by looking at equivalences so ultimately tautologies. They showed that some statements were universally true just by inspection of the truth table. For computer scientists they gave a way to define what logical operations mean and then reason about digital circuits and programs they designed, both to help understand, so write them, and get them right.

Wittgenstein started off as an engineer interested in building flying machines, moved to become a mathematician, a soldier, a gardener and a teacher, as well as a hospital porter, but ultimately he is remembered as a great philosopher. Abstract though his philosophy was, along the way he provided computer scientists and electrical engineers useful tools that helped them build thinking machines.


More on …

Related Magazines …

cs4fn Issue 14 ccover

EPSRC supports this blog through research grant EP/W033615/1, and through EP/K040251/2 held by Professor Ursula Martin. 

Alan Turing’s life

by Jonathan Black, Paul Curzon and Peter W. McOwan, Queen Mary University of London

From the archive

Alan Turing smiling

Alan Turing was born in London on 23 June 1912. His parents were both from successful, well-to-do families, which in the early part of the 20th century in England meant that his childhood was pretty stuffy. He didn’t see his parents much, wasn’t encouraged to be creative, and certainly wasn’t encouraged in his interest in science. But even early in his life, science was what he loved to do. He kept up his interest while he was away at boarding school, even though his teachers thought it was beneath well-bred students. When he was 16 he met a boy called Christopher Morcom who was also very interested in science. Christopher became Alan’s best friend, and probably his first big crush. When Christopher died suddenly a couple of years later, Alan partly helped deal with his grief with science, by studying whether the mind was made of matter, and where – if anywhere – the mind went when someone died.

The Turing machine

After he finished school, Alan went to the University of Cambridge to study mathematics, which brought him closer to questions about logic and calculation (and mind). After he graduated he stayed at Cambridge as a fellow, and started working on a problem that had been giving mathematicians headaches: whether it was possible to determine in advance if a particular mathematical proposition was provable. Alan solved it (the answer was no), but it was the way he solved it that helped change the world. He imagined a machine that could move symbols around on a paper tape to calculate answers. It would be like a mind, said Alan, only mechanical. You could give it a set of instructions to follow, the machine would move the symbols around and you would have your answer. This imaginary machine came to be called a Turing machine, and it forms the basis of how modern computers work.

Code-breaking at Bletchley Park

By the time the Second World War came round, Alan was a successful mathematician who’d spent time working with the greatest minds in his field. The British government needed mathematicians to help them crack the German codes so they could read their secret communiqués. Alan had been helping them on and off already, but when war broke out he moved to the British code-breaking headquarters at Bletchley Park to work full-time. Based on work by Polish mathematicians, he helped crack one of the Germans’ most baffling codes, called the Enigma, by designing a machine (based on earlier version by the Poles again!) that could help break Enigma messages as long as you could guess a small bit of the text (see box). With the help of British intelligence that guesswork was possible, so Alan and his team began regularly deciphering messages from ships and U-boats. As the war went on the codes got harder, but Alan and his colleagues at Bletchley designed even more impressive machines. They brought in telephone engineers to help marry Alan’s ideas about logic and statistics with electronic circuitry. That combination was about to produce the modern world.

Building a brain

The problem was that the engineers and code-breakers were still having to make a new machine for every job they wanted it to do. But Alan still had his idea for the Turing machine, which could do any calculation as long as you gave it different instructions. By the end of the war Alan was ready to have a go at building a Turing machine in real life. If it all went to plan, it would be the first modern electronic computer, but Alan thought of it as “building a brain”. Others were interested in building a brain, though, and soon there were teams elsewhere in the UK and the USA in the race too. Eventually a group in Manchester made Alan’s ideas a reality.

Troubled times

Not long after, he went to work at Manchester himself. He started thinking about new and different questions, like whether machines could be intelligent, and how plants and animals get their shape. But before he had much of a chance to explore these interests, Alan was arrested. In the 1950s, gay sex was illegal in the UK, and the police had discovered Alan’s relationship with a man. Alan didn’t hide his sexuality from his friends, and at his trial Alan never denied that he had relationships with men. He simply said that he didn’t see what was wrong with it. He was convicted, and forced to take hormone injections for a year as a form of chemical castration.

Although he had had a very rough period in his life, he kept living as well as possible, becoming closer to his friends, going on holiday and continuing his work in biology and physics. Then, in June 1954, his cleaner found him dead in his bed, with a half-eaten, cyanide-laced apple beside him.

Alan’s suicide was a tragic, unjust end to a life that made so much of the future possible.

More on …

Related Magazines …

cs4fn issue 14 cover

This blog is funded through EPSRC grant EP/W033615/1.

Cognitive crash dummies

by Paul Curzon, Queen Mary University of London

The world is heading for catastrophe. We’re hooked on power hungry devices: our mobile phones and iPods, our Playstations and laptops. Wherever you turn people are using gadgets, and those gadgets are guzzling energy – energy that we desperately need to save. We are all doomed, doomed…unless of course a hero rides in on a white charger to save us from ourselves.

Don’t worry, the cognitive crash dummies are coming!

Actually the saviours may be people like professor of human-computer interaction, Bonnie John, and her then grad student, Annie Lu Luo: people who design cognitive crash dummies. When working at Carnegie Mellon University it was their job to figure out ways for deciding how well gadgets are designed.

If you’re designing a bridge you don’t want to have to build it before finding out if it stays up in an earthquake. If you’re designing a car, you don’t want to find out it isn’t safe by having people die in crashes. Engineers use models – sometimes physical ones, sometimes mathematical ones – that show in advance what will happen. How big an earthquake can the bridge cope with? The mathematical model tells you. How slow must the car go to avoid killing the baby in the back? A crash test dummy will show you.

Even when safety isn’t the issue, engineers want models that can predict how well their designs perform. So what about designers of computer gadgets? Do they have any models to do predictions with? As it happens, they do. Their models are called ‘human behavioural models’, but think of them as ‘cognitive crash dummies’. They are mathematical models of the way people behave, and the idea is you can use them to predict how easy computer interfaces are to use.

There are lots of different kind of human behavioural model. One such ‘cognitive crash dummies’ is called ‘GOMS’. When designers want to predict which of a few suggested interfaces will be the quickest to use, they can use GOMS to do it.

Send in the GOMS

Suppose you are designing a new phone interface. There are loads of little decisions you’ll have to make that affect how easy the phone is to use. You can fit a certain number of buttons on the phone or touch screen, but what should you make the buttons do? How big should they be? Should you use gestures? You can use menus, but how many levels of menus should a user have to navigate before they actually get to the thing they are trying to do? More to the point, with the different variations you have thought up, how quickly will the person be able to do things like send a text message or reply to a missed call? These are questions GOMS answers.

To do a GOMS prediction you first think up a task you want to know about – sending a text message perhaps. You then write a list of all the steps that are needed to do it. Not just the button presses, but hand movements from one button to another, thinking time, time for the machine to react, and so on. In GOMS, your imaginary user already knows how to do the task, so you don’t have to worry about spending time fiddling around or making mistakes. That means that once you’ve listed all your separate actions GOMS can work out how long the task will take just by adding up the times for all the separate actions. Those basic times have been worked out from lots and lots of experiments on a wide range of devices. The have shown, on average, how long it takes to press a button and how long users are likely to think about it first.

GOMS in 60 seconds?

GOMS has been around since the 1980s, but wasn’t being used much by industrial designers. The problem is that it is very frustrating and time-consuming to work out all those steps for all the different tasks for a new gadget. Bonnie John’s team developed a tool called CogTool to help. You make a mock-up of your phone design in it, and tell it which buttons to press to do each task. CogTool then worked out where the other actions, like hand movements and thinking time, are needed and makes predictions.

Bonnie John came up with an easier way to figure out how much human time and effort a new design uses, but what about the device itself? How about predicting which interface design uses less energy? That is where Annie Lu Luo, came in. She had the great idea that you could take a GOMS list of actions and instead of linking actions to times you could work out how much energy the device uses for each action instead. By using GOMS together with a tool like CogTools, a designer can find out whether their design is the most energy efficient too.

So it turns out you don’t need a white knight to help your battery usage, just Annie Lu Luo and her version of GOMS. Mobile phone makers saw the benefit of course. That’s why Annie walked straight into a great job on finishing university.


This article was originally published on the CS4FN website and appears on pages 12 and 13 of issue 9 (‘Programmed to save the world‘) of the CS4FN magazine, which you can download (free) here along with all of our other free material.

See also the concept of ‘digital twins’ in this article from our Christmas Advent Calendar: Pairs: mittens, gloves, pair programming, magic tricks.


Related Magazine …

This blog is funded through EPSRC grant EP/W033615/1.

Chatbot or Cheatbot?

by Paul Curzon, Queen Mary University of London

Speech bubbles
Image by Clker-Free-Vector-Images from Pixabay
IImage by Clker-Free-Vector-Images from Pixabay 

The chatbots have suddenly got everyone talking, though about them as much as with them. Why? Because one, chatGPT has (amongst other things) reached the level of being able to fool us into thinking that it is a pretty good student.

It’s not exactly what Alan Turing was thinking about when he broached his idea of a test for intelligence for machines: if we cannot tell them apart from a human then we must accept they are intelligent. His test involved having a conversation with them over an extended period before making the decision, and that is subtly different to asking questions.

ChatGPT may be pretty close to passing an actual Turing Test but it probably still isn’t there yet. Ask the right questions and it behaves differently to a human. For example, ask it to prove that the square root of 2 is irrational and it can do it easily, and looks amazingly smart, – there are lots of versions of the proof out there that it has absorbed. It isn’t actually good at maths though. Ask it to simply count or add things and it can get it wrong. Essentially, it is just good at determining the right information from the vast store of information it has been trained on and then presenting it in a human-like way. It is arguably the way it can present it “in its own words” that makes it seem especially impressive.

Will we accept that it is “intelligent”? Once it was said that if a machine could beat humans at chess it would be intelligent. When one beat the best human, we just said “it’s not really intelligent – it can only play chess””. Perhaps chatGPT is just good at answering questions (amongst other things) but we won’t accept that as “intelligent” even if it is how we judge humans. What it can do is impressive and a step forward, though. Also, it is worth noting other AIs are better at some of the things it is weak at – logical thinking, counting, doing arithmetic, and so on. It likely won’t be long before the different AIs’ mistakes and weaknesses are ironed out and we have ones that can do it all.

Rather than asking whether it is intelligent, what has got everyone talking though (in universities and schools at least) is that chatGPT has shown that it can answer all sorts of questions we traditionally use for tests well enough to pass exams. The issue is that students can now use it instead of their own brains. The cry is out that we must abandon setting humans essays, we should no longer ask them to explain things, nor for that matter write (small) programs. These are all things chatGPT can now do well enough to pass such tests for any student unable to do them themselves. Others say we should be preparing students for the future so its ok, from now on, we just only test what human and chatGPT can do together.

It certainly means assessment needs to be rethought to some extent, and of course this is just the start: the chatbots are only going to get better, so we had better do the thinking fast. The situation is very like the advent of calculators, though. Yes, we need everyone to learn to use calculators. But calculators didn’t mean we had to stop learning how to do maths ourselves. Essay writing, explaining, writing simple programs, analytical skills, etc, just like arithmetic, are all about core skill development, building the skills to then build on. The fact that a chatbot can do it too doesn’t mean we should stop learning and practicing those skills (and assessing them as an inducement to learn as well as a check on whether the learning has been successful). So the question should not be about what we should stop doing, but more about how we make sure students do carry on learning. A big, bad thing about cheating (aside from unfairness) is that the person who decides to cheat loses the opportunity to learn. Chatbots should not stop humans learning either.

The biggest gain we can give a student is to teach them how to learn, so now we have to work out how to make sure they continue to learn in this new world, rather than just hand over all their learning tasks to the chatbot to do. As many people have pointed out, there are not just bad ways to use a chatbot, there are also ways we can use chatbots as teaching tools. Used well by an autonomous learner they can act as a personal tutor, explaining things they realise they don’t understand immediately, so becoming a basis for that student doing very effective deliberate learning, fixing understanding before moving on.

Of course, a bigger problem, if a chatbot can do things at least as well as we can then why would a company employ a person rather than just hire an AI? The AIs can now a lot of jobs we assumed were ours to do. It could be yet another way of technology focussing vast wealth on the few and taking from the many. Unless our intent is a distopian science fiction future where most humans have no role and no point, (see for example, CS Forester’s classic, The Machine Stops) then we still in any case ought to learn skills. If we are to keep ahead of the AIs and use them as a tool not be replaced by them, we need the basic skills to build on to gain the more advanced ones needed for the future. Learning skills is also, of course, a powerful way for humans (if not yet chatbots) to gain self-fulfilment and so happiness.

Right now, an issue is that the current generation of chatbots are still very capable of being wrong. chatGPT is like an over confident student. It will answer anything you ask, but it gives wrong answers just as confidently as right ones. Tell it it is wrong and it will give you a new answer just as confidently and possibly just as wrong. If people are to use it in place of thinking for themselves then, in the short term at least, they still need the skill it doesn’t have of judging when it is right or wrong.

So what should we do about assessment. Formal exams come back to the fore so that conditions are controlled. They make it clear you have to be able to do it yourself. Open book online tests that become popular in the pandemic, are unlikely to be fair assessments any more, but arguably they never were. Chatbots or not they were always too easy to cheat in. They may well be good still for learning. Perhaps in future if the chatbots are so clever then we could turn the Turing test around: we just ask an artificial intelligence to decide whether particular humans (our students) are “intelligent” or not…

Alternatively, if we don’t like the solutions being suggesting about the problems these new chatbots are raising, there is now another way forward. If they are so clever, we could just ask a chatbot to tell us what we should do about chatbots…

.

More on …

Related Magazines …

Issue 16 cover clean up your language

This blog is funded through EPSRC grant EP/W033615/1.

Daphne Oram: the dawn of music humans can’t play

by Paul Curzon, Queen Mary University of London

Music notes over paint brush patterns
Image by Gerd Altmann from Pixabay

What links James Bond, a classic 1950s radio comedy series and a machine for creating music by drawing? … Electronic music pioneer: Daphne Oram.

Oram was one of the earliest musicians to experiment with electronic music, and was the first woman to create an electronic instrument. She realised that the advent of electronic music meant composers no longer had to worry about whether anyone could actual physically perform the music they composed. If you could write it down in a machine readable way then machines could play it electronically. That idea opened up whole new sounds and forms of music and is an idea that pop stars and music producers still make use of today.

She learnt to play music as a child and was good enough to be offered a place at the Royal College of Music, though turned it down. She also played with radio electronics with her brothers, creating radio gadgets and broadcasting music from one room to another. Combining music with electronics became her passion and she joined the BBC as a sound engineer. This was during World War 2 and her job included being the person ready during a live music broadcast to swap in a recording at just the right point if, for example, there was an air raid that meant the performance had to be abandoned. The show, after all, had to go on.

Composing electronic music

She went on to take this idea of combining an electronic recording with live performance further and composed a novel piece of music called Still Point that fully combined orchestral with electronic music in a completely novel way. The BBC turned down the idea of broadcasting it, however, so it was not played for 70 years until it was rediscovered after her death, ultimately being played at a BBC Prom.

Composers no longer had to worry
about whether anyone could actually
physically perform the music they composed

She started instead to compose electronic music and sounds for radio shows for the BBC which is where the comedy series link came in. She created sound effects for a sketch for the Goon Show (the show which made the names of comics including Spike Milligan and Peter Sellers). She constantly played with new techniques. Years later it became standard for pop musicians to mess with tapes of music to get interesting effects, speeding them up and down, rerecording fragments, creating loops, running tapes backwards, and so on. These kinds of effects were part of amazing sounds of the Beatles, for example. Oram was one of the first to experiment with these kinds of effects and use them in her compositions – long before pop star producers.

One of the most influential things she did was set up the BBC Radiophonic Workshop which went on to revolutionise the way sound effects and scores for films and shows were created. Oram though left the BBC shortly after it was founded, leaving the way open for other BBC pioneers like Delia Derbyshire. Oram felt she wasn’t getting credit for her work, and couldn’t push forward with some of her ideas. Instead Oram set herself up as an independent composer, creating effects for films and theatre. One of her contracts involved creating electronic music that was used on the soundtracks of the early Bond films starring Sean Connery – so Shirley Bassey is not the only woman to contribute to the Bond sound!

The Music Machine

While her film work brought in the money, she continued with her real passion which was to create a completely new and highly versatile way to create music…by drawing. She built a machine – the Oramics Machine – that read a composition drawn onto film reels. It fulfilled her idea of having a machine that could play anything she could compose (and fulfilled a thought she had as a child when she wondered how you could play the notes that fell between the keys on a piano!).

Image by unknown photographer from wikimedia.

The 35mm film that was the basis of her system that dates all the way back to the 19th century when George Eastman, Thomas Edison and Kennedy Dixon pioneered the invention film based photography and then movies. It involved a light sensitive layer being painted on strips of film with holes down the side that allowed the film to be advanced. This gave Oram a recording media. She could etch or paint subtle shapes and patterns on to the film. In a movie light was shone through the film, projecting the pictures on the film on to the screen. Oram instead used light sensors to detect the patterns on the film and convert it to electronic signals. Electronic circuitry she designed (and was awarded patents for) controlled cathode ray tubes that showed the original drawn patterns but now as electrical signals. Ultimately these electrical signals drove speakers. Key to the flexibility of the system was that different aspects of the music were controlled by patterns on different films. One for example controlled the frequency of the sound, others the timbre or tone quality and others the volume. These different control signals for the music were then combined by Oram’s circuitry. The result of combining the fine control of the drawings with the multiple tapes meant she had created a music machine far more flexible in the sound it could produce than any traditional instrument or orchestra. Modern music production facilities use very similar approaches today though based on software systems rather than the 1960s technology available to Oram.

Ultimately, Daphne Oram was ahead of her time as a result of combining her two childhood fascinations of music and electronics in a way that had not been done before. She may not be as famous as the great record producers who followed her, but they owe a lot to her ideas and innovation.

More on …

Related Magazines …


EPSRC supports this blog through research grant EP/W033615/1. 

Kimberly Bryant, founder of Black Girls Code, born 14 January 1967

Kimberly Bryant from Black Girls Code pictured at the SXSW conference in 2016, https://en.wikipedia.org/wiki/Kimberly_Bryant_(technologist)
Kimberly Bryant in 2016, credit

Kimberly Bryant was born on 14 January 1967 in Memphis, Tennessee and was enthusiastic about maths and science in school, describing herself as a ‘nerdy girl’. She was awarded a scholarship to study Engineering at university but while there she switched to Electrical Engineering with Computer Science and Maths. During her career she has worked in several industries including pharmaceutical, biotechnology and energy.

She is most known though for founding Black Girls Code. In 2011 her daughter wanted to learn computer programming but nearly all the students on the nearest courses were boys and there were hardly any African American students enrolled. Kimberly didn’t want her daughter to feel isolated (as she herself had felt) so she created Black Girls Code (BGC) to provide after-school and summer school coding lessons for African American girls. BGC has a goal of teaching one million Black girls to code by 2040 and every year thousands of girls learn coding with their peers.

She has received recognition for her work and was given the Jefferson Award for Community Service for the support she offered to girls in her local community, and in 2013 Business Insider included her on its list of The 25 Most Influential African-Americans in Technology. When Barack Obama was the US President the White House website honoured her as one of its eleven Champions of Change in Tech Inclusion – Americans who are “doing extraordinary things to expand technology opportunities for young learners – especially minorities, women and girls, and others from communities historically underserved or underrepresented in tech fields.”


This blog is funded through EPSRC grant EP/W033615/1.

Bringing people closer when they’re far away

This article was written a few years ago, before the Covid pandemic led to many more of us keeping in touch from a distance…

by Paul Curzon, Queen Mary University of London

Photo shows two children playing with a tin-can telephone, which lets them talk to each other at a distance. Picture credit Jerry Loick KONZI and Wikipedia. Original photograph can be found here.

Living far away from the person you love is tough. You spend every day missing their presence. The Internet can help, and many couples in long-distance relationships use video chat to see more of each other. It’s not the same as being right there with someone else, but couples find ways to get as much connection as they can out of their video chats. Some researchers in Canada, at the University of Calgary and Simon Fraser University, interviewed couples in long-distance relationships to find out how they use video chat to stay connected.

Nice to see you

The first thing that the researchers found is perhaps what you might expect. Couples use video chat when it’s important to see each other. You can text little messages like ‘I love you’ to each other, or send longer stories in an email, and that’s fine. But seeing someone’s face when they’re talking to you feels much more emotionally close. One member of a couple said, “The voice is not enough. The relationship is so physical and visual. It’s not just about hearing and talking.” Others reported that seeing each other’s face helped them know what the other person was feeling. For one person, just seeing his partner’s face when she was feeling worn out helped him understand her state of mind. In other relationships, seeing one another helped avoid misunderstandings that come from trying to interpret tone of voice. Plus, having video helped couples show off new haircuts or clothes, or give each other tours of their surroundings.

Hanging out on video

The couples in the study didn’t use video chat just to have conversations. They also used it in a more casual way: to hang out with each other while they went about their lives. Their video connections might stay open for hours at a time while they did chores, worked, read, ate or played games. Long silences might pass. Couples might not even be visible to each other all the time. But each partner would, every once in a while, check back at the video screen to see what the other was up to. This kind of hanging out helped couples feel the presence of the other person, even if they weren’t having a conversation. One participant said of her partner, “At home, a lot of times at night, he likes to put on his PJs and turn out all the lights and sit there with a snack and, you know, watch TV… As long as you can see the form of somebody that’s a nice thing. I think it’s just the comfort of knowing that they’re there.”

Some couples felt connected by doing the same things together in different places. They shared evenings together in living rooms far away from each other, watching the same thing on television or even getting the same movie to watch and starting it at the same time. Some couples had dinner dates where they ordered the same kind of takeaway and ate it with each other through their video connection.

Designing to connect

This might not sound like research about human-computer interaction. It’s about the deepest kind of human interaction. But good computer design can help couples feel as connected as possible. The researchers also wanted to find out how they could help couples make their video chats better. Designers of the future might think about how to make gadgets that make video chat easier to do while getting on with other chores. It’s difficult to talk, film yourself, cook and move through the house all at the same time. What’s more, today’s gadgets aren’t really built to go everywhere in the house. Putting a laptop in a kitchen or propping one up in a bed doesn’t always work so well. The designers of operating systems need to work out how to do other stuff at the same time as video. If couples want to have a video chat connection open for hours, sometimes they might need to browse the web or write a text message at the same time. And what about couples who like to fall asleep next to one another? They might need night-vision cameras so they can see their partner without disturbing their sleep.

We’re probably going to have more long- distance relationships in the future. Easy, cheap travel makes it easier to move to faraway places. You can go to university abroad, and join a company with offices on every continent. It’s an awfully good thing that technology is making it easier to stay connected with the people who are important too. Video chat is not nearly as good as feeling your lover’s touch, but when you really miss someone, even watching them do chores helps.


This article was originally published on CS4FN and can also be found on pages 4 and 5 of CS4FN Issue 15, Does your computer understand you?, which you can download as a PDF. All of our free material can be downloaded here: https://cs4fndownloads.wordpress.com/


Related Magazine …

This blog is funded through EPSRC grant EP/W033615/1.

Hedy Lamarr: The movie star, the piano player and the torpedo

by Peter W McOwan, Queen Mary University of London

(from the archive)

Hedy Lamarr
eBay, Public domain, via Wikimedia Commons

Hedy Lamarr was a movie star. Back in the 1940’s, in Hollywood’s Golden Age, she was considered one of the screen’s most beautiful women and appeared in several blockbusters. But Hedy was more than just good looks and acting skills. Even though many people remembered Hedy for her pithy quote “Any girl can be glamorous. All she has to do is stand still and look stupid”, at the outbreak of World War 2 she and composer George Antheil invented an encryption technique for a torpedo radio guidance system!

Their creative idea for an encryption system was based on the mechanism behind the ‘player piano’ – an automatic piano where the tune is controlled by a roll of paper with punched holes. The idea was to use what is now known as ‘frequency hopping’ to overcome the possibility of the control signal being jammed by the enemy. Normal radio communication involves the sender picking a radio frequency and then sending all communication at that frequency. Anyone who tunes in to that frequency can then listen in, but also jam it by sending their own more powerful signal at the same frequency. That’s why non-digital radio stations constantly tell you their frequency “96.2 FM” or whatever. Frequency hopping involves jumping from frequency to frequency throughout the broadcast. Then, only if sender and receiver share the secret of exactly when the jumps will be made, and to what frequencies, can the receiver pick up the broadcast or jam it. That is essentially what the piano roll could do. It stored the secret.

Though the navy didn’t actually use the method during World War II, they did use the principles during the Cuban missile crisis in the 1960’s. The idea behind the method is also used in today’s GPS, Wi-Fi, Bluetooth and mobile phone technologies, underpinning so much of the technology of today. In 2014 she was inducted into the US national inventor’s hall of fame.


Click the player below or download the audio file (.m4a) to listen to this article read by Jo Brodie.


More on …

Related Magazines …


EPSRC supports this blog through research grant EP/W033615/1, and through EP/K040251/2 held by Professor Ursula Martin.