Skip to main content
Engineering LibreTexts

Introduction

  1. Last updated
  2. Save as PDF
  • Page ID
    9658

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Logic originally meant ‘the word’ or ‘what is spoken’ in Ancient Greece, and today means ‘thought’ or ‘reason’. 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. 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 and logic, and related mathematical concepts such as sets, are foundational for computer science. A third of your TUDelft CSE curriculum is mathematics for the first year: 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 Reasoning & Logic.

    The foundational mathematical skills you learn in Reasoning & Logic are used in all the other mathematics courses, and in Computer Organisation, Algorithms & Data Structures, Information & Data Management, Machine Learning, and many other courses. Logic is studied 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:

    1. Translate a logically precise claim to and from natural language.
    2. Describe the operation of logical connectors and quantifiers.
    3. Describe the notion of logical validity.
    4. Explain and apply basic set operations.
    5. Define and perform computations with functions, relations and equivalence classes.
    6. Construct a direct or indirect proof—by contradiction, division into cases, general- isation, or (structural) induction—or counterexample for (in)valid arguments or logical equivalence in propositional or predicate logic and in set theory.
    7. Construct and interpret recursive definitions.
    8. Identify what type of proof is appropriate for a given claim.
    9. Construct the right function or relation given a description(in natural language or formal notation).
    10. Develop specifications for verification tools like SAT or SMT solvers.
    11. Interpret the response of verification tools like SAT or SMT solvers.

    We do not cover every topic at the same level of detail and some topics(SAT and SMT solvers) we do not cover at all, and the lectures will not cover everything in the book. Some topics in the lectures which 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

    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?