Lego Computer Science: Logic with Truth Tables

by Paul Curzon, Queen Mary University of London

We have seen how to represent truth tables in lego. Truth tables are a way of giving precise meaning to logical operations like AND, OR and NOT. They are also give a way to do logical reasoning following a simple algorithm.

That’s Not Not True

You may have been pulled up in English and told you just said the opposite of what you meant, after saying something like “There ain’t no way I’m doing that”. This is a “double negative” as the “n’t” in “ain’t” is really “not” so followed by “no way” you are actually saying “not not way” or overall: “I am doing that”. Perhaps the most famous double negative is in the Rolling Stones song “(I can’t get no) satisfaction”. English is very flexible though and double negatives like this don’t cancel out but just become a different way of saying the negative version. In logic two negations do cancel out, though. Let’s take a purer version to work with: the statement “I am not not happy”. What does this mean? In logic the basic proposition here is “I am not happy”. The logical statement is “NOT (NOT (I am happy))”.

We can prove what this means using truth tables. We can do more than just prove what this single statement means. We can prove what all double negatives mean, more generally. We do this by replacing the proposition “I am happy” with a variable P. It now becomes NOT (NOT P) or in our lego version where we use a yellow brick to mean a proposition, P:

This is just syntax, just a sequence of symbols. It doesn’t give us any meaning on its own. We can build truth tables in Lego for that. We start from the variables that are at the inside of the logical expression which here is just the variable P. We list in a table column the possible values it can take (true or false).

This shows P (yellow) can be either be TRUE (blue) or FALSE (red). Now we build up the logical expression of interest a column at a time. NOT is applied to P, so we add a new column for NOT P and use the truth table for the operator, NOT, to tell us what lego brick to put in each row based on the lego brick already there. The NOT truth table is at the top of the page. It says if you have a blue brick in a row, place a red brick there. If you have a red brick, put a blue brick there. This gives us a new filled out column for (NOT P) which is just a copy of the NOT truth table (but bare with us that was just a simple case). We get:

Moving outwards in the expression NOT (NOT P)), we now look at the operator applied to (NOT P). It is NOT again. We add a new column to our truth table and again use the NOT truth table to work out the new values, but this time applied to the column before (the NOT P column). The NOT truth table says put a blue brick for a red brick, and a red brick for a blue brick in the column it is being applied to (the NOT P column). This gives:

The result is a truth table with coloured bricks identical to that of the original column for P. Switching back from lego bricks to what the columns mean, we have shown that the NOT(NOT P) column is the same as the P column, or in other words that NOT(NOT P) EQUALS P (whatever value P has).

We can actually go a step further though, because equivalence is just a logical operation with its own truth table. It gives true if the two operands have the same value and false otherwise (or in lego terms if the bricks are the same colour the answer is a blue brick and if they are different colours the answer is a red brick. The truth table looks like this:

We can use this truth table to calculate whether two lego truth table columns are equal or not just by looking up the combinations in this EQUALS truth table. Continuing our example we can carrying building our truth table about NOT(NOT P)). To make things clearer first add a column corresponding to P again. That means we will be applying the EQUALS operator to the last two columns. As before, for each row, look up the corresponding pattern for those last two columns in the EQUALS truth table to get the answer for that row. In the first row we have two blue bricks so that becomes a blue brick according tot he EQUALS truth table. In the next row we have two red bricks. That also becomes a blue brick. This gives:

The thing to notice here is that all the entries in the final answer column are blue lego pieces. Switching back from the lego world to the logic world, what does this mean? Blue is true so all rows in the answer are true. That means whatever value of the proposition P the answer to NOT (NOT P) EQUALS P is true. We have proved a theorem that this is always true. We have shown by building with lego that a double negation cancels itself out.

Logical expressions like this that are always true (whatever the values of the variables) are called tautologies. We can tell something is a tautology, so we have proved a theorem, just by the simple manual check that its truth table values are true (or in lego all blue).

The important thing to realise about this is all the reasoning can be done without knowing what the symbols mean, and certainly not worrying about English words, once you have the truth tables. You do it mechanically. You do not need to think about what, for example, red and blue mean until the end. At that point you return to the logical world to see what you have found out. All blue means it is always true! You can also at that point substitute back in actual words of interest into the statements proved. P means “I am happy”. We started by asking what “I am not not happy” means. We converted this to “NOT (NOT (I am happy))”. By swapping in “I am happy” for P in our theorem gives us that NOT (NOT “I am happy”) EQUALS “I am happy”, or that “I am not not happy.” just means the same as “I am happy”

We have been reasoning about English statements, but this kind of reasoning is the basis of all logical reasoning and essentially the basis of formal verification where the meaning of programs and hardware is checked to see if it meets a specification. It tells you what a test in a program like “if (! temperature != 0) …) means so does for example, or what a circuit with two NOT gates does.

And lego logic has even given us a way to prove things just by building with lego.

Lego Computer Science

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

Part 9: Lego Computer Science: Logic with 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.

Lego Computer Science: Truth Tables

by Paul Curzon, Queen Mary University of London

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.

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).

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.

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:

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:

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

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.

We can build this in Lego as:

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

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

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.

Ludwig Wittgenstein: tautology and truth tables

by Paul Curzon, Queen Mary University of London

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:

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.

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:

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.

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

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.

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:

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:

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)).

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.

Related Magazines …

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

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

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.”

More on …

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

The first computer music

by Paul Curzon, Queen Mary University of London

(updated from the archive)

The first recorded music by a computer program was the result of a flamboyant flourish added on the end of a program that played draughts in the early 1950s. It played God Save the King.

The first computers were developed towards the end of the second world war to do the number crunching needed to break the German codes. After the War several groups set about manufacturing computers around the world: including three in the UK. This was still a time when computers filled whole rooms and it was widely believed that a whole country would only need a few. The uses envisioned tended to be to do lots of number crunching.

A small group of people could see that they could be much more fun than that, with one being school teacher Christopher Strachey. When he was introduced to the Pilot ACE computer on a visit to the National Physical Laboratories, in his spare time he set about writing a program that could play against humans at draughts. Unfortunately, the computer didn’t have enough memory for his program.

He knew Alan Turing, one of those war time pioneers, when they were both at university before the War. He luckily heard that Turing, now working at the University of Manchester, was working on the new Feranti Mark I computer which would have more memory, so wrote to him to see if he could get to play with it. Turing invited him to visit and on the second visit, having had a chance to write a version of the program for the new machine, he was given the chance to try to get his draughts program to work on the Mark I. He was left to get on with it that evening.

He astonished everyone the next morning by having the program working and ready to demonstrate. He had worked through the night to debug it. Not only that, as it finished running, to everyone’s surprise, the computer played the National Anthem, God Save the King. As Frank Cooper, one of those there at the time said: “We were all agog to know how this had been done.” Strachey’s reputation as one of the first wizard programmers was sealed.

The reason it was possible to play sounds on the computer at all, was nothing to do with music. A special command called ‘Hoot’ had been included in the set of instructions programmers could use (called the ‘order’ code at the time) when programming the Mark I computer. The computer was connected to a loud speaker and Hoot was used to signal things like the end of the program – alerting the operators. Apparently it hadn’t occurred to anyone there but Strachey that it was everything you needed to create the first computer music.

He also programmed it to play Baa Baa Black Sheep and went on to write a more general program that would allow any tune to be played. When a BBC Live Broadcast Unit visited the University in 1951 to see the computer for Children’s Hour the Mark I gave the first ever broadcast performance of computer music, playing Strachey’s music: the UK National Anthem, Baa Baa Black Sheep and also In the Mood.

While this was the first recorded computer music it is likely that Strachey was beaten to creating the first actual programmed computer music by a team in Australia who had similar ideas and did a similar thing probably slightly earlier. They used the equivalent hoot on the CSIRAC computer developed there by Trevor Pearcey and programmed by Geoff Hill. Both teams were years ahead of anyone else and it was a long time before anyone took the idea of computer music seriously.

Strachey went on to be a leading figure in the design of programming languages, responsible for many of the key advances that have led to programmers being able to write the vast and complex programs of today.

The recording made of the performance has recently been rediscovered and restored so you can now listen to the performance yourself:

Related Magazines …

This blog is funded by UKRI, through grant EP/W033615/1.

Recognising (and addressing) bias in facial recognition tech – the Gender Shades Audit #BlackHistoryMonth

Some people have a neurological condition called face blindness (also known as â€˜prosopagnosiaâ€™) which means that they are unable to recognise people, even those they know well – this can include their own face in the mirror! They only know who someone is once they start to speak but until then they canâ€™t be sure who it is. They can certainly detect faces though, but they might struggle to classify them in terms of gender or ethnicity. In general though, most people actually have an exceptionally good ability to detect and recognise faces, so good in fact that we even detect faces when theyâ€™re not actually there – this is called pareidolia – perhaps you see a surprised face in this picture of USB sockets below.

What if facial recognition technology isnâ€™t as good at recognising faces as it has sometimes been claimed to be? If the technology is being used in the criminal justice system, and gets the identification wrong, this can cause serious problems for people (see Robert Williams’ story in “Facing up to the problems of recognising faces“).

In 2018 Joy Buolamwini and Timnit Gebru shared the results of research theyâ€™d done, testing three different commercial facial recognition systems. They found that these systems were much more likely to wrongly classify darker-skinned female faces compared to lighter- or darker-skinned male faces. In other words, the systems were not reliable.

The Gender Shades Audit

Facial recognition systems are trained to detect, classify and even recognise faces using a bank of photographs of people. Joy and Timnit examined two banks of images used to train facial recognition systems and found that around 80 per cent of the photos used were of people with lighter coloured skin.Â

If the photographs aren’t fairly balanced in terms of having a range of people of different gender and ethnicity then the resulting technologies will inherit that bias too. Effectively the systems here were being trained to recognise light-skinned people.

The Pilot Parliaments Benchmark

They decided to create their own set of images and wanted to ensure that these covered a wide range of skin tones and had an equal mix of men and women (â€˜gender parityâ€™). They did this by selecting photographs of members of various parliaments around the world which are known to have a reasonably equal mix of men and women, and selected parliaments from countries with predominantly darker skinned people (Rwanda, Senegal and South Africa) and from countries with predominantly lighter-skinned people (Iceland, Finland and Sweden).Â

They labelled all the photos according to gender (they did have to make some assumptions based on name and appearance if pronouns werenâ€™t available) and used the Fitzpatrick scale (see Different shades, below) to classify skin tones. The result was a set of photographs labelled as dark male, dark female, light male, light female with a roughly equal mix across all four categories – this time, 53 per cent of the people were light-skinned (male and female).

Different shades

The Fitzpatrick skin tone scale (top) is used by dermatologists (skin specialists) as a way of classifying how someoneâ€™s skin responds to ultraviolet light. There are six points on the scale with 1 being the lightest skin and 6 being the darkest. People whose skin tone has a lower Fitzpatrick score are more likely to burn in the sun and not tan, and are also at greater risk of melanoma (skin cancer). People with higher scores have darker skin which is less likely to burn and they have a lower risk of skin cancer.Â

Below it is a variation of the Fitzpatrick scale, with five points, which is used to create the skin tone emojis that youâ€™ll find on most messaging apps in addition to the â€˜defaultâ€™ yellow.

Testing three face recognition systems

Joy and Timnit tested the three commercial face recognition systems against their new database of photographs – a fair test of a wide range of faces that a recognition system might come across – and this is where they found that the systems were less able to correctly identify particular groups of people. The systems were very good at spotting lighter-skinned men, and darker skinned men, but were less able to correctly identify darker-skinned women, and women overall.Â Â

These tools, trained on sets of data that had a bias built into them, inherited those biases and this affected how well they worked. Joy and Timnit published the results of their research and it was picked up and discussed in the news as people began to realise the extent of the problem, and what this might mean for the ways in which facial recognition tech is used.Â

There is some good news though. The three companies made changes to improve their facial recognition technology systems and several US cities have already banned the use of this tech in criminal investigations, and more cities are calling for it too. People around the world are becoming more aware of the limitations of this type of technology and the harms to which it may be (perhaps unintentionally) put and are calling for better regulation of these systems.

Furtherreading

â€¢ Study finds gender and skin-type bias in commercial artificial-intelligence systems (11 February 2018) MIT News
â€¢ Facial recognition software is biased towards white men, researcher finds (11 February 2018) The Verge
â€¢ Go read this special Nature issue on racism in science (21 October 2022) The Verge

More technical articles

â€¢ Joy Buolamwini and Timnit Gebru (2018) Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification, Proceedings of Machine Learning Research 81:1-15.
â€¢ The unseen Black faces of AI algorithms (19 October 2022) Nature News & Views

See more in ‘Celebrating Diversity in Computing‘

We have free posters to download and some information about the different people who’ve helped make modern computing what it is today.

Or click here: Celebrating diversity in computing

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

Devices that work for everyone #BlackHistoryMonth

by Jo Brodie, Queen Mary University of London

In 2009 Desi Cryer, who is Black, shared a light-hearted video with a serious message. Heâ€™d bought a new computer with a face tracking cameraâ€¦ which didnâ€™t track his face, at all. It did track his White colleague Wandaâ€™s face though. In the video (below) he asked her to go in front of the camera and move from side to side and the camera obediently tracked her face – wherever she moved the camera followed. When Desi moved back in front of the camera it stopped again. He wondered if the computer might be racist…

Another video (below), this time from 2017, showed a dark-skinned man failing to get a soap to dispenser to give him some soap. Nothing happened when he put his hand underneath the sensor but as soon as his lighter-skinned friend put his hand under it – out popped some soap! The only way the first man could get any soap dispensed was to put a white tissue on his hand first. He wondered if the soap dispenser might be racist…

Whatâ€™s going on?

Probably no-one set out to maliciously design a racist device but designers might need to check that their products work with a range of different people before putting them on the market. This can save the company embarrassment as well as creating something that more people want to buy.

Sensors working overtime

Both devices use a sensor that is activated (or in these cases isnâ€™t) by a signal. Soap dispensers shine a beam of light which bounces off a hand placed below it and some of that light is reflected back. Paler skin reflects more light (and so triggers the sensor) than darker skin. Next to the light is a sensor which responds to the reflected light – but if the device was only tested on White people then the sensor wasnâ€™t adjusted for the full range of skin tones and so wonâ€™t respond appropriately. Similarly cameras have historically been designed for White skin tones meaning darker tones are not picked up as well.

Things can be improved!

Itâ€™s a good idea, when designing something that will be used by lots of different people, to make sure that it will work correctly with everyone. Having a diverse design team and, importantly, making sure that everyone feels empowered to contribute is a good way to start. Another is to test the design with different target audiences early in the design process so that changes can be made before itâ€™s too late. How a company responds to feedback when theyâ€™ve made an oversight is also important. In the case of the computer company they acknowledged the problem and went to work to improve the cameraâ€™s sensitivity.

A problemwithpulse oximeters

During the coronavirus pandemic many people bought a â€˜pulse oximeterâ€™, a device which clips painlessly onto a finger and measures how much oxygen is circulating in your blood (and your pulse). If the oxygen reading became too low people were advised to go to hospital. Oximeters shine red and infrared light from the top clip through the finger and the light is absorbed diferently depending on how much oxygen is present in the blood. A sensor on the lower clip measures how much light has got through but the reading can be affected by skin colour (and coloured nail polish). People were concerned that pulse oximeters would overestimate the oxygen reading for someone with darker skin (that is, tell them they had more oxygen than they actually had) and that the devices might not detect a drop in oxygen quickly enough to warn them.

In response the UK Government announced in August 2022 that it would investigate this bias in a range of medical devices to ensure that future devices work effectively for everyone.

Further reading

See also Is your healthcare algorithm racist? (from issue 27 of the CS4FN magazine).

See more in ‘Celebrating Diversity in Computing‘

We have free posters to download and some information about the different people who’ve helped make modern computing what it is today.

Or click here: Celebrating diversity in computing

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

Hidden Figures: NASA’s brilliant calculators #BlackHistoryMonth

by Paul Curzon, Queen Mary University of London

NASA Langley was the birthplace of the U.S. space program where astronauts like Neil Armstrong learned to land on the moon. Everyone knows the names of astronauts, but behind the scenes a group of African-American women were vital to the space program: Katherine Johnson, Mary Jackson and Dorothy Vaughan. Before electronic computers were invented ‘computers’ were just people who did calculations and that’s where they started out, as part of a segregated team of mathematicians. Dorothy Vaughan became the first African-American woman to supervise staff there and helped make the transition from human to electronic computers by teaching herself and her staff how to program in the early programming language, FORTRAN.

The women switched from being the computers to programming them. These hidden women helped put the first American, John Glenn, in orbit, and over many years worked on calculations like the trajectories of spacecraft and their launch windows (the small period of time when a rocket must be launched if it is to get to its target). These complex calculations had to be correct. If they got them wrong, the mistakes could ruin a mission, putting the lives of the astronauts at risk. Get them right, as they did, and the result was a giant leap for humankind.

See the film ‘Hidden Figures’ for more of their story (trailer below).

This story was originally published on the CS4FN website and was also published in issue 23, The Women Are (Still) Here, on p21 (see ‘Related magazine’ below).

See more in ‘Celebrating Diversity in Computing‘

We have free posters to download and some information about the different people who’ve helped make modern computing what it is today.

Or click here: Celebrating diversity in computing

Related Magazine …

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

Christopher Strachey and the secret of being a Wizard Debugger

by Paul Curzon, Queen Mary University of London

(from the archive)

Elite computer programmers are often called wizards, and one of the first wizards was Christopher Strachey, who went on to be a pioneer of the development of programming languages. The first program he wrote was an Artificial Intelligence program to play draughts: more complicated (and fun) than the programs others were writing at the time. He was not only renowned as a programmer, but also as being amazingly good at debugging – getting them actually to work. On a visit to Alan Turing in Manchester he was given the chance to get his programs working on the Ferranti Mark I computer there. He did so very quickly working through the night to get them working, and even making one play God Save the King on the hooter. He immediately gained a reputation as being a “perfect” programmer. So what was his secret?

No-one writes complex code right first time, and programming teams spend more time testing programs than writing them in the first place to try and find all the bugs – possibly obscure situations where the program doesn’t do what the person wanted. A big part of the skill of programming is to be able to think logically and so be able to work through what the program actually does do, not just what it should do.

So what was Strachey’s secret that made him so good at debugging? When someone came to him with code that didn’t work, but they couldn’t work out why, he would start by asking them to explain how the program worked to him. As they talked, he would sit back, close his eyes and think about something completely different: a Beethoven symphony perhaps. Was this some secret way to tap his own creativity? Well no. What would happen is as the person explained the program to him they would invariable stop at some point and say something like: “Oh. Wait a minute…” and realise their mistake. By getting them to explain he was making them work through in detail how the program worked. Strachey’s reputation would be enhanced yet again.

There is a lesson here for anyone wishing to be a good programmer. Spending time explaining your program is also a good way to find problems. It is also an important part of learning to program, and ultimately becoming a wizard.

Related Magazines …

This blog is funded by UKRI, through grant EP/W033615/1.

Sophie Wilson: Where would feeding cows take you?

Chip design that changed the world

by Paul Curzon, Queen Mary University of London

(Updated from the archive)

Some peopleâ€™s innovations are so amazing it is hard to know where to start. Sophie Wilson is like that. She helped kick start the original 80â€™s BBC micro computer craze, then went on to help design the chips in virtually every smartphone ever made. Her more recent innovations are the backbone that is keeping broadband infrastructure going. The amount of money her innovations have made easily runs into tens of billions of dollars, and the companies she helped succeed make hundreds of billions of dollars. It all started with her feeding cows!

While still a student Sophie spent a summer designing a system that could automatically feed cows. It was powered by a microcomputer called the MOS 6502: one of the first really cheap chips. As a result Sophie gained experience in both programming using the 6502â€™s set of instructions but also embedded computers: the idea that computers can disappear into other everyday objects. After university she quickly got a job as a lead designer at Acorn Computers and extended their version of the BASIC language, adding, for example, a way to name procedures so that it was easier to write large programs by breaking them up into smaller, manageable parts.

Acorn needed a new version of their microcomputer, based on the 6502 processor, to bid for a contract with the BBC for a project to inspire people about the fun of coding. Her boss challenged her to design it and get it working, all in only a week. He also told her someone else in the team had already said they could do it. Taking up the challenge she built the hardware in a few days, soldering while watching the Royal Wedding of Charles and Diana on TV. With a day to go there were still bugs in the software, so she worked through the night debugging. She succeeded and within the week of her taking up the challenge it worked! As a result Acorn won a contract from the BBC, the BBC micro was born and a whole generation were subsequently inspired to code. Many computer scientists, still remember the BBC micro fondly 30 years later.

That would be an amazing lifetime achievement for anyone. Sophie went on to even greater things. Acorn morphed into the company ARM on the back of more of her innovations. Ultimately this was about returning to the idea of embedded computers. The Acorn team realised that embedded computers were the future. As ARM they have done more than anyone to make embedded computing a ubiquitous reality. They set about designing a new chip based on the idea of Reduced Instruction Set Computing (RISC). The trend up to that point was to add ever more complex instructions to the set of programming instructions that computer architectures supported. The result was bloated systems that were hungry for power. The idea behind RISC chips was to do the opposite and design a chip with a small but powerful instruction set. Sophieâ€™s colleague Steve Furber set to work designing the chipâ€™s architecture – essentially the hardware. Sophie herself designed the instructions it had to support – its lowest level programming language. The problem was to come up with the right set of instructions so that each could be executed really, really quickly – getting as much work done in as few clock cycles as possible. Those instructions also had to be versatile enough so that when sequenced together they could do more complicated things quickly too. Other teams from big companies had been struggling to do this well despite all their clout, money and powerful computer mainframes to work on the problem. Sophie did it in her head. She wrote a simulator for it in her BBC BASIC running on the BBC Micro. The resulting architecture and its descendants took over the world, with ARMâ€™s RISC chips running 95% of all smartphones. If you have a smartphone you are probably using an ARM chip. They are also used in game controllers and tablets, drones, televisions, smart cars and homes, smartwatches and fitness trackers. All these applications, and embedded computers generally, need chips that combine speed with low energy needs. That is what RISC delivered allowing the revolution to start.

If you want to thank anyone for your personal mobile devices, not to mention the way our cars, homes, streets and work are now full of helpful gadgets, start by thanking Sophie…and sheâ€™s not finished yet!

Related Magazines …

This blog is funded by UKRI, through grant EP/W033615/1.