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

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

# 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!)

It just disappeared in a puff of logic.

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.

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