CS 245 - Logic and Computation
Instructor: Collin Roberts
Section: 003
Location: MC 2034
Time: Tuesdays and Thursdays 1:00pm - 2:20pm
Tutorials: MC 2035 Fridays 8:30am - 9:20am
Term: Spring 2016

May 3, 2016 - Lecture 1

Section 003
Email: cd2rober@uwaterloo.ca
Office: DC 2128

CS 245 -> Formal Logic

1) Propositional
2) Predicate (aka First-Order) <= THE REAL GOAL

Crowdmark for assignments.
Assignments DUE AT 12:00 ON WEDNESDAYS
Recommended Text: Logic in Computer Science, 2nd Ed. by Huth and Ryan

Learn: Course Outline, Notes, Additional Notes - Roberts
Refer to the Course Schedule

Grading Scheme

  • Assignments (10 in total, best 9 out of 10) - 20%
  • Midterm (4:30pm - 6:20pm, June 9, 2016) - 35 %
  • Final - 45%

Week 1: Introduction, Basic examples, formal syntax and semantics, and properties via induction.
Reading: HR 1.1, 1.3, 1.4.2, Slides to p51

Propositional Logic

LOGIC = systematic study of the principles of reasoning and inference

  • To model the computer hardware, software, and embedded systems we create/encounter, in order to reason about those objects in a rigorous manner
  • To understand how to develop systems that can themselves apply reason and make inferences (AI)
  • To define a computer required logic (Turing 1936)
  • CS gave the first definition of “rigorous argument” (an argument that may be checked by a machine; machine returns true if proof is correct)

Example: If the train arrives late and there are no taxis at the station, then John is late for his meeting.

John is not late for his meeting.

The train did arrive late.

Therefore, there were taxis at the station.

Q: Is this argument valid? Why/Why not?

Q: What is the structure of this argument?
A: If p and not q, then r. Not r. p. Therefore q.

p = “the train arrives late”
q = “there are taxis at the station”
r = “John is late for his meeting”

What if we reassign meanings to p, q, and r? We will get an equally valid argument.

The factual content of statements (p, q, r) doesn’t matter. The relationships among the statements govern the argument.

So what constitutes a “statement”?
What do logical relationships mean?

We shall start with Propositional Logic, a basic form of logic.

A proposition is a declarative sentence that is either true or false.

Either the proposition is true, or the proposition is false. It is never both true and false.

e.g. If Kathleen Wynne is a Liberal, then Stephen Harper is a Tory.

p->q: If p then q; p is sufficient for q, q is necessary for p.

p <-> q: p if and only if q (p iff q); p is equivalent to q; p exactly if q; p is necessary and sufficient for q.

Translating from English to propositional logic examples:

  1. She is clever and hard-working
    Let p be “she is clever” and q be “she is hard-working”
    Then we get (p ^ q)

  2. If he does not study hard then he will fail
    Let p be “he studies hard” and q be “he will fail”
    Then we get ((NOT p) -> q)

  3. If it rains, he will be at home; otherwsie he will go to the market or to school.
    Let p be “it rains”, q be “he will be at home”, r be “he will go to the market”, s be “he will go to school”
    Then we get ((p -> q) ^ ((NOT p) -> (r v s)))

Some sentences are not propositions:

  • interrogative: where shall we go to eat?
  • imperative: please pass the salt
  • ambiguous: time flies like an arrow
  • nonsense: uwgod
  • otherwise problematic: This sentence is false

May 5, 2016


  • A01 posted, due May 11
  • A01 study exercises posted on Learn. Not to be handed in, extra practice
  • Course staff office hours posted on Learn

Goals for Today

  • Up to Slide 50, at least up to truth tables
  • Syntax - Propositional
  • Semantics - Propositional

Atomic and Compound Propositions

In propositional logic, simple atomic propositions are the basic building blocks. We connect atomic propositions into compound propositions, and then analyze sets of interrelated propositions. Typical questions:

  • Does a given sequence of propositions form a valid argument?
  • Can all propositions in a given set be true simultaneously?

First, we must answer the Q: What is a proposition?
Propositions are represented by formulas. A formula consists of a sequence of symbols. There are 3 kinds of symbols:

  • Propositional variables: usually lower case Latin letters (e.g. p, q, r) perhaps with subscripts
  • Connectives: We shall use negation, ^(and), v(or), -> and <-> (Others are possible)
  • Punctuation: Only two, ( and ) (we could avoid them)

Every formula is a sequence of symbols, but not every sequence of symbols is a formula. We call an arbitrary finite sequence of symbols an expression (or string)

An expression is a finite sequence of symbols. The length of an expression is its number of symbols. We often use a letter that is not formally a symbol in order to name an expression. For example, alpha. This is an example of a “meta-symbol”.

Some terminology for expressions

Two expressions a and b are equal written as a=b, iff they are of the same length, say n, and if n>0, then for all i in [1…n] the i-th symbol of a is the same as the i-th symbol of b.

We write ab to mean the concatenation of two expressions a and b.

Formal Definition of Concatenation

If a is an expression of length i and b is an expression of length j, then ab is an expression of length i+j. We have the k-th symbol of ab is: + if k <= i, the k-th symbol of a + if k > i, the (k - i)-th symbol of b

Definition of “Formula”

Let P be a set of propositional variables. We define the set of formulas over P inductively as follows.

  1. An expression consisting of a single symbol of P is a formula
  2. If phi is a formula, then the negation of phi is a formula
  3. If phi is a formula and eta is a formula, then each of (phi and eta), (phi or eta), (phi -> eta), and (phi <-> eta) is a formula
  4. Nothing else is a formula

(Note the use of meta-symbols phi and eta)

The following are well-formed formulas.

  1. p,q,r,s (rule 1)
  2. (not p) (rule 2, from #1)
  3. (r ^ q) (rule 3, from #1)
  4. ((not p) -> s) (rule 3, from #2 and #1)
  5. ((r ^ q) v ((not p) -> s)) (rule 3, from #3 and #4)
  6. (not (r ^ q)) (rule 2, from #3)

The 6 Kinds of Formulas From the definition, we see that there are six kinds of formulas:

  • A propositional variable = ATOM
  • A formula (not phi) = NEGATION
  • A formula (phi ^ eta) = CONJUNCTION
  • A formula (phi v eta) = DISJUNCTION
  • A formula (phi -> eta) = IMPLICATION
  • A formula (phi <-> eta) = EQUIVALENCE

Q: Can a formula have two or more kinds? No.

Semantics of Propositional Logic

The semantics of a logic describes how to interpret the well-formed formulas of the logic. The semantics of propositional logic is “compositional”: the meaning of a whole formula derives from the meaning of its parts. In propositional logic, we need to give meaning to atoms, connectives, and formulae. For example, the interpretation of the formula (p ^ q) depends on three things, the meaning of p, the meaning of q, and the meaning of ^.

Definition: A truth evaluation is a function (P -> {T, F}) with the set of all proposition symbols as domain and {F, T} as range. A truth eval assigns a value to every propositional variable. If t(p) = T, then we say “t makes p true”, if t(p) = F, then we say “t makes p false”. A propositional variable has no intrinsic meaning. It gets a meaning only via an evaluation.

Formally, a connective represents a function from truth values to truth values. The connective (not) is unary; it maps one value to one value. The other connectives are binary, they map two values to one value.

-> : “Truth is Preserved”; if there is not truth to preserve, the meaning is T. T->F is F because truth is not preserved.
E.g. “If everyone is a child, then the moon is made of blue cheese” comes out true (seems non-sensical, but propositional logic gives every formula a meaning)

Summary of the Value of a Formula Fix a truth evaluation t. Every formula phi has a value under t, denoted phit, determined as follows:

  1. pt = t(p)
  2. (not phi)t =
    • T if phit = F
    • F if phit = T
  3. (phi ^ eta)t =
    • T if phit = etat = T
    • F otherwise
  4. (phi v eta)t =
    • T if phit = T or if etat = T
    • F otherwise
  5. (phi -> eta)t =
    • T if phit = F or if etat = T
    • F otherwise
  6. (phi <-> eta)t =
    • T if phit = etat
    • F otherwise

The value of a formula comes from the values of its variables, combined as given by its connectives. The valuation t is necessary. WIthout a valuation, a formula has no value.

Unique Readability of Formulae We have defined the semantics of a formula forom its ysyntax. Is this well-defined? Or can a formula get two different meanings, i.e. ambiguous?

Theorem. Every formula has a unique derivation as a well-formed formula. That is, each formula has exactly one of the six forms:

  1. an atom
  2. (not phi)
  3. (phi ^ eta)
  4. (phi v eta)
  5. (phi -> eta)
  6. (phi <-> eta)

We prove this by mathematical induction.

Review of Induction Suppose P names a property. We write P(2) to mean “2 has property P”, or “P holds for 2”.

A statement “every natural number has property P” corresponds to a sequence of statements:
P(0), P(1), P(2), P(3),…

Principles of Mathematical Induction Suppose we establish two things: that + 0 has property P, and that + whenever any number has property P, then the next number also has property P. Then we may conclude that every natural number has property P.


  • To talk about something, give it a name.
    E.g. property P, number k
  • A formula is a textual object. We can subsitute one symbol or expression for another
  • The induction principle gives a template:
    • proof has 2 parts: basis and inductive step
    • In the inductive step, hypothesize P(k) and prove P(k+1)

May 6, 2016 - Tutorial 1

A few exercises of truth tables, translations, and structural induction:

My 10, 2016 - Lecture 3

Induction Continued

  • structural induction (proving facts about formulae)
    • prove unique readbility
  • equivalence (semantic)
  • entailment

Note: The negation of an atomic proposition is no longer an atomic proposition.

Structural Induction

A formula (anything built according to the inductive definition of a formula (4 rules)) is not a natural number, but it suffices to prove any one of the following: + For every natural number n, every formula with n or fewer symbols has property P + For every natural number n, every formula with n or fewer connectives has property P

Theorem (Principle of Structural Induction): Let R be a property. Suppose that
1. For each atomic formula p, we have R(p)
2. For each formula phi, if R(phi) then R((not phi))
3. For each pair of formulae phi and eta, and each connective *, if R(phi) and R(eta) then R((phi * eta))

Then R(phi) for every formula phi.

It is a special case of mathematical induction.

Lemma: Every well-formed formula has an equal number of left and right parentheses

Proof: Use structural induction. The property to prove is R(phi): phi has an equal number of left and right parentheses for every formula phi

Base case: phi is an atom. phi has no parentheses - only a propositional variable. Thus R(phi) holds.

IH: Formulae phi and eta both have property R.

IS: We need to prove each of the formulae (not phi), (phi ^ eta), (phi v eta), (phi -> eta) and (phi <-> eta). WLOG, consider (phi ^ eta)

Notation: For any formula zeta, let op(zeta) denote the number of ‘(‘ in zeta, and let cl(zeta) denote the number of ‘)’ in zeta.

We calculate
op((phi ^ eta)) = 1 + op(phi) + op(eta) = 1 + cl(phi) + cl(eta) (R(phi) and R(eta)) = cl((phi ^ eta))

(Also prove the unary NOT case)

Unique Readability Proof
Theorem: Every formula is exactly one of the six kinds, and in each case it is of that form in exactly one way.

Add in more stuff to the proof (1. the first symbol of phi is either ‘(‘ or a variable; 2. phi has an equal number of ‘(‘ and ‘)’, and each proper prefix of phi has more ‘(‘ than ‘)’ (parentheses are balanced))

A proper prefix of phi is a non-empty expression x such that phi is xy for some non-empty expression y.

Property P(n): 1, 2, and 3. phi has unique construction as a formula, which is what we are trying to prove here.

Aside: To Show x is unique:
1) Let x’ have same properties as x
2) Prove x’ = x

Let phi be an arbitrary formula. We prove for any natural number n, every formula phi

Base cases:
Case 1: k=0 binary connective symbols. We prove by induction on the number of unary connective symbols (i.e. NOT) in phi + Base (0 NOTs): the only possibility is phi = p, for some propositional variable p. Then phi has properties 1, 2, 3 (thus R) (2. No proper prefixes) + IH: (> 0 NOTs):

Tautology, Contradiction, and Satisfiable

A formula alpha is a tautology iff for every truth eval t, alphat = T. Evaluates to true under any circumstances.

A formula alpha is a contradiction (aka unsatisifiable) iff for every truth eval t, alphat = F. Evaluates to false under any circumstances.
E.g. p ^ NOT p

A formula alpha is a satisfiable iff it is not a contradiction. Evaluates to at least one true under all circumstances.

How to prove that a formula is a tautology? One method is to fill out a truth table. Can we do better? We can analyze what would happen if we did. We can use a valuation tree

May 12, 2016 - Lecture 4

  • Equivalence
  • Entailment
  • Adequate sets of connectives

Equivalent formulae have the same final column in their truth tables - they have the same value under any valuation.

Recall a valuation t is a function t: P->{T, F}, i.e. a assignment of F or T to very propositional variable

Commutativity, Associativity, Distributivity, Idempotence, Double Negation, DML,