1. Introduction

In this course, we will study logic and its connections to computer science. Before we dive into more detail about exactly what we will cover, let’s first pause to consider a basic question:

Why study logic?

Because logic is the language of computers. But more importantly because it can help teach us How Not to Be Wrong. For over two thousand years, philosophers have thought about how we can learn what is true about the world. The results of this quest include science and mathematics. But more directly, it also led to the development of logic.

Logic is the study of reasoning, and its goal is to provide a method to determine when an argument is valid or invalid. A typical example of a valid argument is the following classic deduction:

All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.

This argument is intuitively valid: when the first two lines are true, the conclusion in the third line must necessarily be true as well. But it might also give the impression that there isn’t much to be gained by studying in more detail why that argument was valid. However, logical arguments can also be more involved. Consider this example due to Charles Dodgson (aka Lewis Carroll):

No kitten that loves fish is unteachable.
No kitten without a tail will play with a gorilla.
Kittens with whiskers always love fish.
No teachable kitten has green eyes.
No kittens have tails unless they have whiskers.

What can we conclude about kittens with green eyes from these five statements?

We can also find logical arguments at the heart of many recreational games. The Murdle series of books and the Clues By Sam online game, for example, both centre around the development of valid chains of logical reasoning. And so do puzzles like Sudoku, even though in this case the presence of logical reasoning is not quite so explicit. To see this, consider the following puzzle.

Sudoku puzzle

Which number should go in the middle square of the puzzle? The only possible option can be determined with logical reasoning.

These examples hopefully already suffice to show that logical arguments are not all as “easy” as the first one. There are also many other more serious examples of logical arguments that can be found throughout all of mathematics: there, the entire structure of mathematical proofs of theorems relies on the logical arguments contained within those proofs being valid.

And the challenge of studying logic becomes even more apparent when we take a step back from individual arguments and ask about what must be true of all of them. Can we formally define what makes a logical argument valid or not? Can we design an algorithm that verifies the correctness of arguments? Try it now! You’ll find that before you can do that, there is a lot of groundwork that we need to cover. As a first step, we need to define more precisely what is an argument and what makes it valid. Then once we have done this by introducing a formal logic model, we need to analyze it and prove that the properties we want it to possess do hold. As we will see throughout this course, these tasks are challenging and can be particularly interesting.

A Brief Overview

The course will cover three main topics.

Propositional Logic is the simplest model of logic that we will study in the course. The basic object we study in this model is the proposition, a statement that is true or false. We will see how logical arguments can be converted into sequences of propositions, how we can determine whether these arguments are valid or not, and how we can obtain formal proofs of formal arguments.

First-Order Logic is the next model of logic that we will study. We will consider the same high-level questions that we examined in propositional logic in this system as well, and we will see how the richer structure of first-order logic lets us formalize much of mathematics.

Computation is the final main topic covered in the course. We will introduce Turing machines and see how they can be used to study all reasonable models of computers. Most notably, we will see how Turing machines can reveal the fundamental limitations of computers.

These three topics provide only a partial introduction to the areas of logic and of computation. As time permits, we will cover some additional topics or provide pointers for additional directions of study.

Fundamentals of Propositional Logic

A proposition is a statement that is either True or False.

Some examples of propositions include

The sky is blue.
Vancouver is the capital of Canada.
Every natural number greater than 2 is the sum of two prime powers.

As the examples demonstrate, a proposition can be known to be true or false, or it can be open. But, crucially, a proposition must be either true or false. Questions, commands, or other phrases that can’t be deemed to be true or false do not represent propositions.

Logical connectives are special words like “and” and “or” that let us combine individual propositions to form new ones. For example, the first two propositions above can be combined together to form the proposition

The sky is blue or Vancouver is the capital of Canada.

Propositions obtained in this way by combining simpler propositions with logical connectives are called compound propositions. Propositions that cannot be broken up into simpler propositions in this way are called atomic propositions.

There are a number of different logical connectives that we can consider. We will study five of them:

In propositional logic, we are not interested in propositions in isolation but rather in how they can be combined to form logical arguments. In this model of logic, an argument is a (finite or infinite) set of propositions that we call the premises of the argument along with a single proposition that forms its conclusion.

A logical argument is valid if whenever the premises are all true, then the conclusion must be true as well. It is invalid if this is not necessarily the case.

To determine if an argument is valid, we generally proceed with a three-step process:

  1. Syntax: Translate the argument from English to a formal propositional logic language.
  2. Semantics: Use the truth table method to establish or refute the validity of the formal argument.
  3. Formal Deduction: Give a formal proof of valid arguments.

This is the process we will define and study in the next few lectures.