A magazine where the digital world meets the real world.
On the web
- Home
- Browse by date
- Browse by topic
- Enter the maze
- Follow our blog
- Follow us on Twitter
- Resources for teachers
- Subscribe
In print
What is cs4fn?
- About us
- Contact us
- Partners
- Privacy and cookies
- Copyright and contributions
- Links to other fun sites
- Complete our questionnaire, give us feedback
Search:
Logic and Proof FUNdamentals
It is often said that being good at Maths is important for Computer Scientists. So what's the link? Well a lot of the more obviously fun sides of maths are actually computer science too, like how to do puzzles such as Rubik's Cubes, puzzles about weird and wonderful characters crossing rivers, how to win at strategy games, and doing Sudoku. The Maths you do in solving a Sudoku is the same kind of reasoning as that behind getting computer programs to work.
It is not so much the actual Maths you learn at school that is important. It is more that a similar way of thinking is important: logical reasoning. Doing Maths at school is one good way to start to learn how to think that way. So if you are good at Maths you will probably be good at Computer Science, though (using a bit of logical reasoning) that doesn't mean the opposite follows of course.
Start with a Magic Trick
It is important that we are sure that the programs we write - rules for the computer to follow - do work as they are supposed to. The same goes if you are following the rules of a magic trick. You'd look a bit stupid if your magic only worked some times. If the program you wrote and sold doesn't always work, you could lose a lot of money.
Boolean Maths
Digital computers treat everything as 1s and 0s, true or false, black or white. That is all that digital means. Whether it is a picture, text, a program or a music file, it is all just a long series of specially coded 1s and 0s to the computer. That is what gives the computer it's strength. All information of whatever kind can ultimately be manipulated in a standard way using simple operations with some simple maths behind them: boolean logic. All Boolean logic is really about is answering questions such as: given what you know about the truth of two separate pieces of information, is it true that both are the case?
I do not have a mohican haircut. Do I have both a mohican AND black hair? Even without knowing the colour of my hair we can conclude I don't have both just by applying some boolean logic. Even if I do have black hair I still don't have both.
The same kind of reasoning is ultimately what computers do on all the information they process. It is both how the basic building blocks of programs work and how the building blocks of the hardware works too. That is why both programmers and hardware designers have to be able to think logically.
Seeing Patterns
Most people think Maths is about numbers. Actually it's more about seeing patterns. One part of this is recognizing the essence of some problem is really the same as another one you've seen before: they follow the same pattern. Being able to see this essence of a problem is an important skill you learn as a Computer Scientist. If you have written a program to solve some problem, it's really useful if you can show a different problem is the same one in disguise. If it is then you don't have to write a whole new program. Sometimes seeing the link can also turn an apparently difficult program into something really easy to write. It makes business sense too. You can write one core program then sell it to different clients as different products!
Have a go at playing Texting Marakech Seen it before?
A couple of mysterious books: Russel's Paradox
Here is what at first looks like a simple a problem to try, but that actually involves some deep Maths. Write a book. Not a novel. A book of lists. There are lots of those about - lists of films, lists of singles,... Your book 'Book 1: The Bumper Book of lists listing themselves' must list all the books that mention themselves. (Lots of books (or even websites) refer to themselves, for example if we were to list all the best websites about computer science we would reference cs4fn naturally!)
Now, once you've finished that, answer this question. Does your 'Book 1: The Bumper Book of lists listing themselves' list itself? It may or may not. Perfectly Ok either way, of course. So far so good.
Now write a second book, the sequel 'Book 2: The Bumper Book of lists NOT listing themselves'. It should be a list of all books that don't mention themselves. Finished? Now another question, just to check you did finish. Does your second book mention itself?
Simple enough question you might think. It either does or it doesn't, and depending on the answer it must go into one of the two books, Book 1 or 2 that you've written. Let us suppose Book 2 lists itself for a moment. Then there is a problem because if it does mention itself, it shouldn't be listed in Book 2. It is only for books not listing themselves. Hmmm! Clearly it shouldn't mention itself then. But if it doesn't mention itself, then it should be one of the books listed in Book 2, because all those listed in Book 2 donŐt list themselves...Arghhhh!
This paradox, called Russell's Paradox lies at the heart of a result about what maths computers themselves (or humans for that matter) can actually do. The same problem leads to a whole series of Mission Impossible problems for computers.
Extracting ALL the information: Try a Kakuro
Newspaper puzzles like Sudoku and Kakuro are good examples of how lots of people find logic and proof a fun challenge. All those commuters are doing it to wind down from work. Sudoku and similar puzzles have little to do with numbers and everything to do with logic. To solve them you have to extract the last drop of information from a situation. Programmers are doing the same kind of fun thinking every time they write code. When a program works you get the same kind of kick as when you write the last number into the Sudoku.
Other Kinds of Maths
Some school Maths is really important if you are interested in specializing in particular areas of Computer Science. For example Computer Vision, Graphics and the games based on them uses a lot of matrix maths. It turns out that to work out what is going on in the world.
Computer Security, and in particular encryption, has made use of some very obscure maths called Number theory about things like the prime numbers. Once upon a time it was thought Number Theory was of no use to anyone - there for the challenge rather than to ever have any effect on the world. Turns out it is the key to e-commerce: sending money digitally and signing documents digitally so they can't be forged is only possible thanks to prime numbers.
A different kind of maths again, known as Bayesian Reasoning, is used is the basis of making decisions when not all the facts are known. What is the likelihood of one thing happening given what you know about other things. It can be used to determine the risks of a software project failing, about complex DNA evidence in court cases or even about who is most likely to win the World Cup...
So different areas of Computer Science that you could specialize in might or might not involve some branch of Maths. On the whole though the link is that Computer Science has some very simple and fun Maths at its core. So think clearly.
