CS 245 — Lecture 1

What is this course about?

This course is about logic. Specifically, this course is about mathematical logic and the role it plays in computer science. Logic in this sense is a field of mathematics, like algebra or number theory. In fact, you can find a number of logicians hanging out in the pure math department and by taking this course, you won't be allowed to take their version of a mathematical logic course, PMATH 330.

Why should you take this course?

Because you have to in order to get your degree. Of course, another way of asking this question is "Why are we making you take this course?" I suspect more than one student has wondered this and I think that it's a question worth thinking about.

What is logic?

First, we need to answer the obvious question: What is logic? A very dictionary definition of logic will tell you that it is the study of reasoning, inference, and deduction. The word logic comes from the Greek word logykos, which means "pertaining to reason" and you may not be surprised to learn that the study of logic stretches all the way back to Ancient Greece with Aristotle.

Consider the following argument.

• If you live alone, you must have a cat.
• I live alone.
• Therefore, I have a cat.

Is this argument convincing? Is it valid? Is it true?

• If you wake the prince up, you will be cursed.
• I woke the prince up.
• Therefore, I was cursed.

The above two arguments have the same structure:

• If $p$, then $q$.
• $p$.
• Therefore, $q$.

That is, we have obtained $q$ from some established facts $p$ and the rule "if $p$ then $q$". The idea here is that we set up some rules and some facts and we can begin to derive some new statements. An interesting question is: what kinds of rules and facts would we need in order to make the kinds of arguments we want to make?

This is what we consider the syntactic notion of truth. We say $S$ is true if we can prove it from basic facts $A_1, \dots, A_n$ by following some rules. In other words, truth is determined by manipulating elements of statements according to some rules.

Note that our arguments above are valid only in the structural sense. That is, the syntax of the argument is valid, but it says nothing about the truth of those statements.

What if we do want to consider an argument based on the truth of our basic facts rather than the structure of an argument?

This is what we call the semantic notion of truth. We say $S$ is true if all interpretations of $S$ that are true for all facts $A_1, \dots, A_n$ must also be true for $S$. In other words, there is no way to interpret $S$ as false without also falsifying an axiom, so $S$ must be true.

Mathematical logic is concerned with the question of whether these two notions of truth are the same. In doing so, it leads us to some interesting questions outside of computer science. For instance, are all things that we consider as "true" actually provable? Is everything we can prove actually true?

Suppose we wanted to determine whether some statement of mathematical fact was true. If it's true, we should be able to prove it. If it's false, we should be able to find a counterexample. It seems like, at the very least, if we had enough information, we should be able to encode it and let a computer handle the mechanical proof part of it. After all, computers are very good at that sort of thing.

This was exactly the kind of question that logicians were interested in back in 1900. Is it possible to encode the rules of mathematics as logical statements and just have a machine do the hard work of coming up with proofs for it, if we have enough rules? That certainly sounds like the kind of thing we want computers to do nowadays. As we'll see later in the course, it turns out that we can't. In fact, it is this unfortunate development that leads directly into the birth of computer science as a discipline.

This connection is not just a historical note. The relationship between syntax and semantics is one that's central to computer science, as you'll see when you take CS 241. A program (and in fact, all data) is just a sequence of symbols. The meaning and interpretation of the program occurs when it is actually run.

Our goal, as in most theoretical computer science courses, is to formalize all of these notions and study them using mathematical tools. We will formalize the notions of proof and truth, syntax and semantics, and so on and ultimately show that the two notions coincide, and the consequences that arise from this fact.

What will we be covering in this course?

There are roughly four broad topics that this course will cover.

1. Propositional logic, and
2. Predicate logic. These two together can really be considered one large topic, on first-order logic. This is the language that we use to model and reason about things.
3. Program verification. This involves using first-order logic to formally prove the correctness of some piece of code.
4. Undecidability. This is the idea that there are some problems that cannot be solved using computers. This is a consequence of the properties of first-order logic.

Propositional Logic

Definition 1.1. A proposition is a declarative statement that is either true or false.

For example,

• The fish is fresh.
• The sum of 3 and 5 is 15.
• Boxes are very popular.
• There are infinitely many primes $p$ such that $p+2$ is also prime.

Not every sentence is a proposition.

• Eight hats.
• Please stand clear of the doors.
• What are birds?

Definition 1.2. An atomic proposition cannot be broken down into smaller propositions. A compound proposition is not atomic.

We represent propositions by formulas which are made up of symbols. There are three kinds of symbols that we use for formulas.

• Propositional variables, which by convention are lowercase letters $p,q,r,\dots$,
• Connectives, $\neg,\wedge,\vee,\rightarrow$,
• Punctuation, $(,)$.

We assign propositional variables to represent atomic propositions and we can represent compound propositions by using formulas which combine atomic propositions as propositional variables with connectives.

Suppose we have the following propositions.

• $p$: Flights to Tokyo are under 800 CAD.
• $q$: I can take two weeks off.
• $r$: I can fly to Tokyo.

Definition 1.3. We will consider the following connectives.

• $\neg p$ is called negation and is pronounced "not $p$". For instance, $\neg q$ is the proposition "I cannot take two weeks off". Note that negation is a unary connective, in that it only applies to one formula, while all the other connectives are binary. Observe that because of this, we tend to express atomic propositions positively.
• $p \wedge q$ is called conjunction, and is pronounced "$p$ and $q$". This connective expresses the idea that both $p$ and $q$ are true. For instance, $q \wedge r$ is the proposition "I can take two weeks off and I can fly to Tokyo".
• $p \vee q$ is called disjunction and is pronounced "$p$ or $q$". For example, $q \vee r$ is the proposition "I can take two weeks off or I can fly to Tokyo". One tricky thing to note with English is that many times we use "or" to mean "exclusive or". For instance, when you are asked whether you prefer beef or chicken, the expectation is that you may only choose one and not both. This logical connective allows for both $p$ and $q$ to be true, which corresponds to something like "and/or" in English.
• $p \rightarrow q$ is called implication and is pronounced "if $p$, then $q$". For example, $p \rightarrow r$ would be the proposition "If flights to Tokyo are under 900 CAD, then I can fly to Tokyo". The direction in which you read this connective is very important. For instance, it may be the case that flights to Tokyo may not be under 900 CAD but I may still be able to fly.

This set of connectives is due to George Boole in 1854, the namesake for Boolean algebra. Note that this is not an exhaustive list of how to formulate these connectives in natural language. English (and other languages) have a variety of ways to express each of these connectives without using the words "not", "and, "or", "implies", and so on.

• $\neg p$: $p$ does not hold, $p$ is false, it is not the case that $p$
• $p \wedge q$: $p$ but $q$, not only $p$ but $q$, $p$ while $q$, $p$ despite $q$, $p$ yet $q$, $p$ although $q$
• $p \vee q$: $p$ or $q$ or both, $p$ and/or $q$
• $p \rightarrow q$: $p$ implies $q$, $p$ only if $q$, $q$ when $p$, $p$ is sufficient for $q$, $q$ is necessary for $p$