CS 245: Logic and Computation (Spring 2021)

Observe These Course Conventions

  1. In CS 245, the Natural Numbers start at 0. You were likely told in MATH 135 that the Natural Numbers start at 1. Many mathematicians and computer scientists would argue in favour of either choice. In CS 245 we choose 0.
  2. Subset Notation:
    1. X ⊂ Y indicates that X is a proper subset of Y.
    2. X ⊆ Y indicates that X is a proper subset of Y, or that X is equal to Y.
  3. Unless otherwise stated, English "or" means inclusive-or.
  4. English sentences of the form "if A then B" assert that, if A occurs, then B must also occur. It is not clear what the sentence asserts in the case when A does not occur. In formal logic, we will need to cover all possibilities, so we will assign a meaning to such a sentence, even in the case when A does not occur. Full details about this will be explained soon.
  5. Sometimes sentences of the form "if A then B" assert that A causes B. It turns out that the notion of causation is messy and does not translate well into formal logic. So we will not work with this type of causal sentence in CS 245.

Use the LEARN Site

  1. Pay attention to the schedule. The schedule will indicate when you will need to submit things for the course.
  2. Access the instructors' notes, which will cover the entire course.
  3. Watch the linked videos which accompany the notes, for additional explanation.
  4. Do the practice quizzes as they are posted, to get some early practice with the material.
  5. Download the bi-weekly Crowdmark assignments on Wednesdays. You will submit your assignment solutions the following Wednesday (in most weeks), on Crowdmark. Refer to the schedule for any exceptions to this default timing.
  6. Do the marked quizzes during the weeks where no Crowdmark assignment or Mid-Term Assessment is due.
  7. Download the tutorial notes after the synchronous tutorials.
  8. Attend the synchronous sessions with the instructors.

Use the Piazza Site

  1. Post appropriate questions to your classmates.
  2. Post private questions to your instructors.
  3. Use MathJax, MarkDown or the built-in symbol table to include mathematical symbols in your posts, to make them clearer.
  4. Monitor the email that is connected to Piazza, so that you will receive instructor announcements sent via the site.
  5. In accordance with university policies, please always be respectful and professional when posting to our course Piazza site. If you need to give feedback about an aspect of the course which you do not like, then please do so in a constructive manner.

Use MS Teams

  1. Attend the weekly tutorials.
  2. Attend office hours with the course staff.

Make The Most Of Instructor Office Hours

  1. The purpose of instructor office hours is to provide you with time to get your questions about the course material answered.
  2. Often, but not always, these questions will be about the assignment for that week.
  3. You will get the most out of the office hours if you arrive with a list of specific questions.
  4. Office hours are not meant to replace yout time spent reading and understanding the course notes, and watching the lecture videos.
  5. Attend office hours if there is anything about the course that you would like to discuss. If the scheduled hours don't suit you, then email your instructor for an appointment at another time.

Form Good Study Habits

  1. CS 245 is unique among your core CS courses, in that you will not write any code. The goal of the course is to make you a better thinker about your coding.
  2. You will have the opportunity to write many proofs during the course, using all the techniques you have learned in MATH 135. This will give you practice at writing up your arguments carefully and thoroughly.
  3. Often there will be multiple correct solutions to the questions you will work on. Some solutions will be more elegant than others. It will benefit you to understand the problems from several different angles. Your instructors will include multiple model solutions where appropriate, presenting the most elegant one first.
  4. Keep up with your course work, each week. Do not let things pile up on you.
  5. As with any mathematical course, we will continually build on everything we have already learned as we start on a new topic. Make sure that you have a firm grasp on the definitions introduced already, as they will be ingredients in the new material you are about to learn.

Practise Your Abstract Thinking Skills

  1. Dealing with things abstractly has the benefit that we ignore irrelevant details, and focus on the important features of some object.
  2. This makes our analysis applicable in the maximum number of situations, which is desirable.
  3. The cost is that our definitions must also be stated abstractly. This can make definitions more challenging to understand.
  4. This is a natural extension of the approach taken in MATH 135. Recall the definition of a natural number, p > 1, being prime: every Natural number divisor, d, of p, either equals 1 or equals p.
    1. This definition ranges over all the divisors of p, and it asserts that a statement (which is written using an English "or") holds for each of them.
    2. This definitinon makes no attempt to explicitly list all prime numbers. Indeed, this would be futile because there are infinitely many primes.
    3. Instead the definition provides a test which can be applied to any natural number p > 1. For some choices of p (e.g. p = 6), the test answers "no". For some choices of p (e.g. p = 7), the test answers "yes".
    4. We can think of this test for primeness as partitioning the set of Natural numbers into the primes and the non-primes (i.e. 0, 1, and the composite Natural numbers).
  5. Both the objects we will study, and the way we will study them, have been chosen to provide you with practice at logical thinking.
  6. There will be many subtleties to grapple with throughout the course. Your instructors will make every effort to point them out, and to illuminate all the relevant details about them.

Practise Writing Things Formally

  1. The course emphasizes writing things formally, in particular,
    1. studying the syntax of formulas separate from their semantic meanings, and
    2. writing formal deduction proofs.
  2. Get used to writing things up according to given formal rules, without reference to any semantic meaning.
  3. We will use variables formally throughout the course.
    1. Some of these variables will be used in the style of MATH 135, i.e. giving a short name to an object to provide a concise way to refer to it.
    2. Some of the variables will be used in the setting of formal logic. We will explain this fully when we start into first-order logic.
  4. The instructors will follow the mathematical conventions from the text by Lu, as best we can. The instructors will not require you to be as careful about following these conventions as we will be.

If Applicable, Typeset Your Mathematics Correctly

To enter symbols not on your keyboard, there are several methods.

Use whichever one (or several) that you find easiest.

The table lists most of the non-alphabetic symbols we shall use in the course. To understand the types of symbol ("logical", etc.) see the next section and also the whole of the course. Alphabetic symbols (letters) and others that appear on a keyboard (e.g., '+') are are omitted, since they don't normally pose a problem.

List of symbols, in Unicode, HTML, and LaTeX
  Symbol Codepoint HTML
name
LaTeX
name
Description/meaning
decimalhex
Logical symbols 
¬172U+00AC¬\neg, \lnotnot (negation)
8743U+2227∧\landand (conjunction)
8744U+2228∨\loror (disjunction)
8594U+2192→\rightarrowimplies
8596U+2194↔\leftrightarrowif and only if
8704U+2200∀ \forallfor all, for every, for each
8707U+2203∃\exists there exists, for some
8776U+2248≈\approxequals [in Lu]
Metalogical symbols 
8658U+21D2⇒\Rightarrowimplies (material implication)
8866U+22A2⊢\vdashproves [in Formal Deduction]
8872U+22A8⊨\vDash(tauto)logically implies
8722U+2212−\ensuremath{-}[used in rule names]

In addition to the above, we shall also use common keyboard symbols, such as '+', '=', etc., with their usual meanings.

Symbols that can appear in formulas

Each type of formula (propositional, first-order, etc.) has two kinds of symbols specified for it.
Logical symbols.
These have a specific meaning, as defined by the logic. Examples: connectives, quantifiers.
"Non-logical" symbols.
Specified symbols, whose meaning is specified separately. The specification is called a (truth) valuation.
Most of the symbols that you have encountered in formulas of university mathemetics fall into the category of non-logical symbols. For example, while 'π' is often used to denote a particular ratio, in other contexts it may denote something else entirely, such as a permutation.

You will probably also have seen some of the logical symbols, such as ∀, →, etc.; however, their usage is generally informal outside of mathematical logic.

"Meta-symbols" (which cannot appear in formulas)

In mathematical logic, the basic objects we study are formulas. In order to use mathematics to discuss formulas, we of course use normal mathematical symbolism. To minimize confusion, we distinguish between the "symbols" that occur in formulas and the "symbols" that we use to describe formula. The latter are called "meta-symbols". (It can take a while to get used to the distinction, but thereafter it proves quite helpful.)

For example, the symbols '→' and '⇒' both appear in the table above with the meaning "implies". They are distinct symbols, and may not be interchanged. The one-line '→' is a formal symbol. Use it in formulas. The two-line '⇒' is a meta-symbol. It may not appear in a formula, although it will frequently occur between formulas.