Logic and deduction are core thinking skills but also an important intellectual pursuit at least since the Ancient Greeks. In the computer age it is at the core of how computers work as well core to how we get programs right. It is also the subject of maths, computer science and philosophy research in its own right. Theoretical Computer Science explores the mathematics behind computation: looking at the limits of what computation and computers can possibly do, and building the solid foundations for doing new things or old things in better ways. It has led to new and better kinds of programming languages, better tools for finding bugs, and set the foundations for Artificial Intelligence, to give just a few examples. Being able to think precisely is at its core.
Learn about logic but also practice it and become a better thinker as well as a better computer scientist
Read about logic and the research around it or skip to the bottom for a range of logic puzzles including advice on solving them.
Playing Tantrix: P=NP?
You can find computer science everywhere – even in popular Solitaire games and puzzles. Most people have played games like Tetris, Battleships, Mastermind, Tantrix and Minesweeper at some point. In fact, all these games have a link to one of the deepest, fundamental problems remaining in Computer Science. They are all linked to a famous equation that is to do with the ultimate limitations of computers. (Read on)
Conjuring with logic: the remote control red-black mind-meld
We outline a magic trick and show how to prove it works. Magic tricks are just algorithms – they involve a magician following the steps of the trick precisely. But how can a magician be sure a trick will definitely work when they do it in front of an audience? Just like computer scientists who can prove their algorithms always work, a magician can use logic and deduction to be sure their tricks always work too. … (read on)
Kakuro, Logic and Computer Science
To be a good computer scientist you have to enjoy problem solving. That is what it’s all about: working out the best way to do things. You also have to be able to think in a logical way: be a bit of a Vulcan. But what does that mean? … (read on)
Perceptrons and the AI Winter
A simple, but misunderstood, theoretical result about a little gadget called a perceptron that is now the basis of machine learning tools, led to the AI winter that set back AI development decades. Learn about perceptrons and how theoretical computer science can help us understand AI … (read on)
From Logic to Rules
One way to use logical thinking is to deduce new facts but then turn them into IF-THEN rules. They tell us an action to do IF something is true. For example: IF both cards are the same THEN shout SNAP! Once we have IF-THEN rules we can use them as the basis of a program. We can see how this works, and how it involves various computational thinking skills with a simple logical thinking puzzle...(Read on)
Ludwig Wittgenstein: tautology and truth tables
Ludwig Wittgenstein is one of the most important philosophers of the 20th century. His interest was in truth and he made contributions to logical thinking that are a foundation of computing. He invented the modern idea of tautology as something that is true whatever the situation and also popularised truth tables, now used as a simple way to understand logical operations and logical expressions … (read on)
Peter Landin: Elegance from Logic
A key idea behind programming language design is that a language should make it easy to write complex algorithms in simple and elegant ways. It turns out that logic is key to that. Through his work on programming language design, Peter Landin as much as anyone, promoted both elegance and the linked importance of logic in programming.…(read on)
The logic behind syntactic sugar
Computer Scientists talk about “Syntactic Sugar”. But in what way might a program be made sweet? It is all about how necessary a feature of a language is. The phrase was invented by Peter Landin. He realised it made it easier to define the meaning of languages in logic and made the definitions more elegant.…(read on)
Philippa Gardner bringing law and order to a wild west
The computing world is a wild west, with bugs in software the norm, and malicious people and hostile countries making use of them to attack people, companies and other nations. We can do better. Philippa Gardner has dedicated her working life to rectifying this by providing ways to verify software, so mathematically prove such trust-based properties hold of it. (read on)
Superhero Syllogisms
Superheroes don’t just have physical powers. Often they come out on top because of their mental abilities. Sherlock is a good example, catching villains through logical thinking. Anyone can get better at thinking! Just practice. Here we learn from the ancient greeks… (read on)
The Logic Piano
Victorian, William Stanley Jevons was a famous economist in his day. He was the first economist to raise the issue of the ecological impact of economics.Jevons had other strings to his bow though and one of the strangest for the time if also incredibly forward thinking was his 1869 “logic piano”: a device that looked a little like a piano but that “played” logic. … (read on)
A handshaking puzzle
Logical reasoning and proof, whether done using math notation or informally in your head, is an important tool of computer scientists. The idea of proving, however, is often daunting for beginners and it takes a lot of practice to master this skill. Here we look at a simple puzzle to get you started, and look at how AIs do… (read on)
Shafi Goldwasser and the Zero Knowledge Proof
Shafi Goldwasser, one of the greatest living computer scientists, won the Turing Award in 2012 (equivalent to a Nobel Prize). Her work helped turn cryptography from a dark art into a science. If you’ve ever used a credit card through a web browser, for example, her work was helping you stay secure. Her greatest achievement, with Silvio Micali and Charles Rackoff, is the “Zero knowledge proof”…. (read on)
Lego Computer Science: Truth Tables
Truth tables are a simple way of reasoning about logic. 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. Let’s see what a truth table is by making some from Lego…. (read on)
Lego Computer Science – Logic with Truth tables
Prove logical facts, like what double negation means, just by mechanically following truth table rules to create new lego proof truth tables. Get all blue (so a tautology) and you have proved a theorem (read on)
The Logic of Queens
Queens is a fairly simple kind of logic puzzle found for example on LinkedIn. Doing daily logic puzzles is good both for mental health and to build logical thinking skills. As with programming, solving logic puzzles is mostly about pattern matching rather than logic per se. The logic mainly comes in working out the patterns. (read on)
Barbara Liskov: Byzantine birthdays
The ACM Turing Award, which Barbara Liskov won, is the computing equivalent of a Nobel Prize. She was awarded it for more than 40 years’ work. Her early work on programming languages has been used in every significant new language that has been invented since. More recently she has moved on to problems about ‘distributed systems’: computer systems involving lots of separate computers that have to work together. That’s where the arguing comes in. (read on)
Logic Puzzles
Grid Logic Puzzles
Given some basic facts, use logic and deduction to work out all the facts. (Read on…)
Queens Puzzles
Work out where all the Queens go so there is one in each area and only one in each row and column. (Read on)
Eating at Quonk: a tough puzzle?
Pairs eat out, but who dines at Quonk? The puzzle is based on one devised by psychologists as part of research into whether we humans naturally think logically or not… (Read on)
Conjuring with Logic and Deduction
Find out how we can prove that magic tricks work just as we prove software works in out book on Conjuring with Computation… (Read on)
Subscribe to be notified whenever we publish a new post to the CS4FN blog.
This blog is funded by EPSRC on grant EP/W033615/1.
cs4fn 