CS 245  Logic and Computation
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 FirstOrder) <= 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:

She is clever and hardworking
Let p be “she is clever” and q be “she is hardworking”
Then we get (p ^ q) 
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) 
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
Administrivia
 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 “metasymbol”.
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 ith symbol of a is the same as the ith 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 kth symbol of ab is: + if k <= i, the kth 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.
 An expression consisting of a single symbol of P is a formula
 If phi is a formula, then the negation of phi is a formula
 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
 Nothing else is a formula
(Note the use of metasymbols phi and eta)
The following are wellformed formulas.
 p,q,r,s (rule 1)
 (not p) (rule 2, from #1)
 (r ^ q) (rule 3, from #1)
 ((not p) > s) (rule 3, from #2 and #1)
 ((r ^ q) v ((not p) > s)) (rule 3, from #3 and #4)
 (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 wellformed 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 nonsensical, 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 phi^{t}, determined as follows:
 p^{t} = t(p)
 (not phi)^{t} =
 T if phi^{t} = F
 F if phi^{t} = T
 (phi ^ eta)^{t} =
 T if phi^{t} = eta^{t} = T
 F otherwise
 (phi v eta)^{t} =
 T if phi^{t} = T or if eta^{t} = T
 F otherwise
 (phi > eta)^{t} =
 T if phi^{t} = F or if eta^{t} = T
 F otherwise
 (phi <> eta)^{t} =
 T if phi^{t} = eta^{t}
 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 welldefined? Or can a formula get two different meanings, i.e. ambiguous?
Theorem. Every formula has a unique derivation as a wellformed formula. That is, each formula has exactly one of the six forms:
 an atom
 (not phi)
 (phi ^ eta)
 (phi v eta)
 (phi > eta)
 (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.
Techniques
 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.
Example:
Lemma: Every wellformed 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.
Proof:
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 nonempty expression x such that phi is xy for some nonempty 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, alpha^{t} = T. Evaluates to true under any circumstances.
A formula alpha is a contradiction (aka unsatisifiable) iff for every truth eval t, alpha^{t} = 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,