1. Introduction and Learning Objectives#
Logic originally meant ‘the word’ or ‘what is spoken’ in Ancient Greece, and today means ‘thought’ or ‘reason’.[1] As a subject, logic is concerned with the most general laws of truth. Why study this kind of reasoning in computer science?
Logic is important because digital computers work with precision, and because designing algorithms requires precision, and because comparing algorithms requires precision.
Even when when a computer is, seemingly, computing with vague or imprecise quantities, the underlying computation is precise.[2] For example, when a deep neural network is being trained to recognise cats, the algorithm being used to train the network is specified precisely. More than this, the criteria we use to assess whether the network has learned well enough are also specified precisely. And any theoretical properties about the algorithm have been proven precisely.
Reasoning, logic, and related mathematical concepts such as sets, are foundational for computer science. One third of your first year TUDelft CSE curriculum is mathematics: Reasoning & Logic, Calculus, Linear Algebra and Probability Theory & Statistics.
As a computer scientist, you have to be capable of solving complex problems. One important aspect is to be able to come to the right conclusions. On the basis of theorems and partial observations you can acquire more knowledge and evidence to help prove that a specific conclusion is mathematically and logically correct. You learn how to do this with the course Reasoning & Logic.
The foundational mathematical skills you learn in Reasoning & Logic are used in all the other mathematics courses you will take, and in Computer Organisation, Algorithms & Data Structures, Information & Data Management, Machine Learning, and many other courses. In fact, logic is studied and used not only in mathematics and computer science, but also in philosophy (since Ancient Greece) and today in fields such as linguistics and psychology.
This book is designed to help you achieve the learning goals of Reasoning & Logic:
Translate a logically-precise claim to and from natural language.
Describe the operation of logical connectors and quantifiers.
Describe the notion of logical validity.
Explain and apply basic set and graph operations.
Define and perform computations with functions, relations and equivalence classes.
Construct and interpret recursive definitions, including recursive data structures like trees.
Construct an appropriate function or relation given a description (in natural language or formal notation).
Construct a direct or indirect proof (by contradiction, division into cases, generalisation, or [structural] induction) or logical equivalence—or counterexample for (in)valid arguments—in propositional logic, predicate logic and set theory.
Identify what type of proof is appropriate for a given claim.
Solve simple Boolean Satisfiability (SAT) instances.
Develop specifications for verification tools like SAT or SMT solvers.
Interpret the response of verification tools like SAT or SMT solvers.
Warning
We do not cover every topic at the same level of detail. Some topics have extra podcast videos to accompany the book. Other topics, such as SAT and SMT solvers, we do not cover at all. Further, the lectures will not cover everything in the book. Some topics in the lectures you will prepare for using other materials: these will be announced.
Note
Starred sections in the contents of this book are not included in the syllabus for Reasoning & Logic.
Note
We include solutions to some of the exercises, starting on Section 6. Exercises that have a solution are marked with a dagger (†) symbol. You can contribute solutions to the other exercises!
The theme of the book is about coming to the right conclusion: proving the logical validity of arguments. What is a valid argument? When is an argument logically valid and when is it not? How can we determine whether an argument is logically valid? How can we derive a logically valid conclusion from the premises? Or how can we prove that a conclusion is not a logical consequence of the premises? And how can we use these abilities in computer science?
We will begin by talking further about logic.