Comp106 Logic

1.
The Foundations (Logic)

1.1, 1.2 Propositional Logic (Chapter numbers are from the 7 th
edition of your textbook)
Motivation: Basis of all mathematical reasoning and numerous applications in

computer science
▪ artificial intelligence
▪ computer programming and algorithm development
▪ design of computer circuits
▪ etc
By the end of these lectures, you will be able
• to translate daily language to precise logical expressions
“You cannot ride the roller coaster if you are less than 1.70m tall unless you are older than 18
years.”
“Everyone has exactly one best friend.”
• to verify your reasoning and conclusions
“If you are older than 18 years, then you can have a driving license.”  ??
“If you can have a driving license, then you are older than 18 years,” or
“If you cannot have a driving license, then you are not older than 18 years.”
Proposition: A statement that is either true or false, but not both.
e.g.
• Snow is white
• Rain is wet Propositions
• 1+1=2
• 2+3=7
• What time is it?

• Consider reading the material. Not Propositions
• x+1=2
• x+y=z
 Use letters to denote propositions:

p, q, r, s, …
Truth values: true T, false F

Compound Propositions
Many mathematical statements are constructed by combining propositions. Compound
propositions are formed by using logical operators such as:
▪ negation (NOT) ¬
▪ conjunction (AND) 
▪ disjunction (OR) 
▪ exclusive or (XOR) 
▪ implication (IF) →
▪ biconditional (IFF) ↔
Definition:Negation (NOT)
Let p be a proposition.
Negation of p is ¬p (not p)
e.g.
Proposition p: Today is Tuesday.
Negation of p: Today is not Tuesday
Truth table:
p ¬p
T F
F T
¬p: “It is not the case that p”

Definition: Conjunction (AND)
The proposition “ p and q ”
denoted by p  q
is T when both p and q are true,
is F otherwise.
The proposition p  q is called the conjunction of p and q.
Definition: Disjunction (OR)

The proposition “p or q”
denoted by p  q
is F when p and q are both false
is T otherwise
The proposition p  q is called disjunction of p and q.
Definition: Exclusive Or (XOR)

The exclusive or of p and q, p  q, is T when exactly one of p and q is true and is F
otherwise.
The exclusive or of p and q, p  q, is T when exactly one of p and q is true and is F
otherwise.
e.g.
p: “Snow is white”
q: “Snow is cold”
p  q  ??
p  q  ??
p  q  ??
Truth table:
p q pq pq pq
T T T T F
T F F T T
F T F T T
F F F F F
Definition: Implication (IF)
The implication p → q is F when p is T and q is F
is T otherwise.
p q p→q
T T T
T F F
F T T
F F T
e.g. “If today is Tuesday, then 2 + 2 = 10” (True)

“If today is Tuesday, then we have a quizze” (?)
p→q
p: premise (hypothesis)
q: conclusion (consequence)
“If you are blonde, then you have blue eyes”
Blonde and blue eyes  true

Blonde and brown eyes  false
Not blonde and blue eyes  true
Not blonde and brown eyes  true
Common ways of expressing implication:
if p then q
p implies q
p only if q
p is sufficient for q
q whenever p
q is necessary for p
q whenever p
q follows from p
p→q
Converse: q → p
Contrapositive: ¬q → ¬p
“If you are older than 18 years, then you can have a driving license”
Converse: “If you can have a driving license, then you are older than 18 years”
Contrapositive: “If you cannot have a driving license, then you are not older than 18 years”
Definition: Biconditional (IFF)
The biconditional p ↔ q is T when p and q have same truth value and is F otherwise.
P q p↔q p ↔ q is T if both p → q is T and q → p is T.

T T T
T F F “p if and only if q”
F T F “p is necessary and sufficient for q”
F F T “if p then q, and conversely”
p ↔ q is logically equivalent to say that p → q  q → p.

Translation from English to logical expression
Example:
“You cannot ride the roller coaster if you are less than 1.70m tall unless you
are older than 18 years.”
q: “You can ride the roller coaster”

r: “You are less than 1.70m tall”
s: “You are older than 18 years”
Let’s try….
Translation from English to logical expression
Example:
“You cannot ride the roller coaster if you are less than 1.70m tall unless you
are older than 18 years.”
q: “You can ride the roller coaster”

r: “You are less than 1.70m tall”
s: “You are older than 18 years”
(r  ¬s ) → ¬q
e.g.*:
p: “It is below freezing”

q: “It is snowing”
• “It is below freezing but not snowing.”
• “It’s below freezing or it’s snowing; but it’s not snowing if it’s below freezing.”
* exempli gratia
e.g.:
p: “It is below freezing”

q: “It is snowing”
• “It is below freezing but not snowing.”

p  ¬q
• “It’s below freezing or it’s snowing; but it’s not snowing if it’s below freezing.”
(p  q)  (p → ¬q)
and ≈ but
Logic and bit operations:
A bit has two possible values, 0 or 1.

Binary digit  bit (John Tukey, 1946)
In most programming languages, a variable is a Boolean variable if its value is

either T or F, or equivalently 0 or 1.
Bit operations  Logical operations

T → 1, F → 0
Bitwise OR, AND, XOR

1010 1110
1100 0101
1110 1111 bitwise OR
1000 0100 bitwise AND
0110 1011 bitwise XOR
1.3 Propositional Equivalences:
Definition: Logical equivalence

The propositions r and s are logically equivalent if r and s have the same truth values.
Notation: r  s
1.3 Propositional Equivalences
Definition: Logical equivalence

The propositions r and s are logically equivalent if r and s have the same truth values.
Notation: r  s
e.g.
Show that ¬(p  q)  ¬p ¬q (De Morgan’s law)
p q pq ¬(pq) ¬p ¬q ¬p  ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
Logical Equivalences
pTp
pFp Identity laws
pTT
pFF Domination laws
ppp
ppp Idempotent laws
¬(¬p)  p Double Negation law
pqqp
pqqp Commutative laws
(p  q)  r  p  (q  r)
(p  q)  r  p  (q  r) Associate laws
p  (q  r)  (p  q)  (p  r)
p  (q  r)  (p  q)  (p  r) Distributive laws
¬(p  q)  ¬p  ¬q
¬(p  q)  ¬p  ¬q De Morgan’s laws
Some additional useful logical equivalences:
p  ¬p  T
p  ¬p  F
(p → q)  (¬p  q)
(p ↔ q)  (p → q)  (q → p)
(p → q)  (¬q → ¬p)
You can show all these logical equivalences using truth tables.
Definition:
Tautology: A compound proposition that is always true
Contradiction: A compound proposition that is always false
Contingency: Neither tautology nor contradiction
e.g. p  ¬p p  ¬p
tautology contradiction
e.g.
Show that (p  q) → (p  q) is a tautology.
e.g.
Show that (p  q) → (p  q) is a tautology.
(p  q) → (p  q)  ¬(p  q)  (p  q)
 (¬p  ¬q)  (p  q) De Morgan
 (¬p  p)  (¬q  q) Assoc & Comm
TT
T
e.g.
Show that ¬(p → q)  p  ¬q
e.g.
Show that ¬(p ↔ q)  (p q)  (¬p  ¬q)
You can show these logical equivalences using truth tables or using known
equivalences.
Consistency of Propositions
Consider the following propositions for a system specification:
“Whenever the system software is being upgraded, users cannot access the file system”
“If users can access the file system, then they can save new files.”
“If users cannot save new files, then the system software is not being upgraded.”
Are they consistent?


p q r p → ¬q q→r ¬r → ¬p
The best way is to construct a truth T T T F T T
table with T T F F F F
p → ¬q, q → r, ¬r → ¬p F T T T T T
(but what are p, q, r ?) F T F T F T
T F T T T T
T F F T T F
F F T T T T
F F F T T T

p q r p → ¬q q→r ¬r → ¬p
The best way is to construct a truth T T T F T T
table with T T F F F F
p → ¬q, q → r, ¬r → ¬p F T T T T T
(but what are p, q, r ?) F T F T F T
T F T T T T
If we can find a truth value T F F T T F
assignment such that all propositions F F T T T T
are T, then they are consistent, F F F T T T
otherwise inconsistent.
1.4 Predicates and Quantifiers:
Subject Predicate
Statement: x is greater than 3
This is a propositional function.
We can express it in another form:

P(x): x > 3
Then what are the truth values of P(4) and P(2) ?

Definition 1: Universal Quantification of P(x)
is the proposition “P(x) is T for all values of x in the universe of discourse (domain).”
Notation: x P(x)
“for all x P(x)”
“for every x P(x)”
: Universal quantifier
e.g.
“Every student in this class has studied calculus.”
Definition 1: Universal Quantification of P(x)
is the proposition “P(x) is T for all values of x in the universe of discourse (domain).”
Notation: x P(x)
“for all x P(x)”
“for every x P(x)”
: Universal quantifier
e.g.
“Every student in this class has studied calculus.”
Express this as a universal quantification.
Let P(x) denote “x has studied calculus”
Then x P(x), where universe of discourse is all the students in the class.
DOMAIN (universe of discourse) MUST BE SPECIFIED!!
OR
x (S(x) → P(x))
where
S(x) denotes “x is in the class”
Universe of discourse is the set of all students.
e.g.
What is the truth value of x P(x), where
P(x): “x2 < 10 ”
Universe of discourse: x  {1,2,3,4}
x P(x)  P(1)  P(2)  P(3)  P(4)

F
Definition 2: The Existential Quantification of P(x)
is the proposition “there exists an element x in the universe of discourse (domain)
such that P(x) is true.”
Notation:
x P(x)
“there exists an x s.t. P(x)”
“there is at least one x s.t. P(x)”
 : Existential quantifier
e.g.
P(x): x > 3 x  {…, –1, 0, 1,…}
x P(x)  T
e.g.
P(x): x = x +1, x  R
x P(x)  F
e.g.
P(x): x2 > 10, x  {1, 2, 3, 4}
x P(x)  P(1)  P(2)  P(3)  P(4)

T
1.5 Nested Quantifiers:
Translating Sentences into Logical Expression
e.g.
Let B (x,y): “y is the best friend of x”

Universe of discourse for both x and y is the set of all students in this class.
Universe of discourse is all the students in this class.

Let B(x,y): “y is the best friend of x”
“For every person x, there is a person y such that y is the best friend of x and
if z is a person other than y, then z is not the best friend of x.”
x y ( B(x, y)  ( z (z  y) → ¬B(x, z) ) ) 
x y z B(x, y)  ( (z  y) → ¬B(x, z) )
Remark:
Q(x) → y P(x,y) )  y ( Q(x) → P(x,y) )
So we can write
x (Q(x) → y P(x,y) )  x y ( Q(x) → P(x,y) )
Remark:
Q(x) → y P(x,y) )  y ( Q(x) → P(x,y) )
So we can write
x (Q(x) → y P(x,y) )  x y ( Q(x) → P(x,y) )
But we cannot write

x (y P(x,y) → Q(x))  x y ( P(x,y) → Q(x) ) (wrong!)
since
y ( P(x,y) → Q(x) ) is not logically equivalent to (y P(x,y) ) → Q(x)
Remark:
Q(x) → y P(x,y) )  y ( Q(x) → P(x,y) )
So we can write
x (Q(x) → y P(x,y) )  x y ( Q(x) → P(x,y) )
But we cannot write

x ((y P(x,y)) → Q(x))  x y ( P(x,y) → Q(x) ) (wrong!)
since
y ( P(x,y) → Q(x) ) is not logically equivalent to (y P(x,y) ) → Q(x)
e.g.
Consider P(x,y): “Student x solves question y”, Q(x): “Student x passes the exam”
So be careful when replacing quantifiers!

The Order of Quantifiers
The order of quantifiers is important !!! unless all quantifiers are universal or
existential.
e.g.
x y P(x,y) is not equivalent to y x P(x,y).
Let P(x,y) be the statement “ x + y = 0 ”.
x y P(x,y) : “ For every real number x there is a real number y such that x+y=0.”
y x P(x,y) : “ There is a real number y such that for every real number x, x+y=0.”
Negation of Quantified Statements:
¬(x P(x))  x ¬P(x)  x P(x) is false
¬(x P(x))  x ¬P(x)  x P(x) is false

e.g.
“There exists a living person who is 150 years old.”
Write down as a logical expression using predicates and quantifiers and then negate:
Let P(x): “x is 150 years old,” and the universe of discourse is set of living people.
e.g.
“There exists a living person who is 150 years old.”
Write down as a logical expression using predicates and quantifiers and then negate:
Let P(x): “x is 150 years old,” and the universe of discourse is set of living people.
x P(x)
“There exists a living person who is 150 years old.” x P(x)
Negation of x P(x)?
“There exists a living person who is 150 years old.” x P(x)
Negation of x P(x)?
¬(x P(x))  x ¬P(x) which means
“Every living person is not 150 years old,” or equivalently “no living person is 150
years old.”
In the previous example, what changes if the universe of discourse is modifed as “the
set of all people”. Then we would need another propositional function, e.g., R(x): “x is
a living person”.
“There exists a living person who is 150 years old”  ?

In the previous example, what changes if the universe of discourse is modifed as “the
set of all people”. Then we would need another propositional function, e.g., R(x): “x is
a living person”.
“There exists a living person who is 150 years old” 

x P(x)  R(x)
Negation: x ¬P(x)  ¬R(x)  x P(x) → ¬R(x)  x R(x) → ¬P(x) which means

“For every person x, if x is living, x is not 150 years old,” or equivalently “no living
person is 150 years old”, which is the same as before.
You can show the equivalences ¬(x P(x))  x ¬P(x) and ¬(x P(x))  x ¬P(x)
by using De Morgan’s rule.
You can show the equivalences ¬(x P(x))  x ¬P(x) and ¬(x P(x))  x ¬P(x)
by using De Morgan’s rule.
e.g.
P(x): x2 > 10, x  {1, 2, 3, 4}
Negation of x P(x) ?
¬x P(x)  ¬(P(1)  P(2)  P(3)  P(4))

 ¬P(1)  ¬P(2)  ¬P(3)  ¬P(4) by De Morgan’s rule
 x ¬P(x)
e.g.
Show that ¬x y P(x,y)  xy ¬P(x,y)
Hint: Negate successively two times.
e.g. Negate xy xy = 1
xy xy ≠ 1
e.g. Negate “Some student in this class has solved every exercise in the book.”
“Some student in this class has not solved every exercise in the book.” Not correct!!!
Let S(x,y) be “student x has solved exercise y”, where the universe of discourse for x is
the set of students in this class, and for y, the set of exercises in the book.
e.g. Negate “Some student in this class has solved every exercise in the book.”
“Some student in this class has not solved every exercise in the book.” Not correct!!!
Let S(x,y) be “student x has solved exercise y”, where the universe of discourse for x is
the set of students in this class, and for y, the set of exercises in the book.
¬xy S(x,y)  xy ¬S(x,y)
“For every student in this class there is an exercise that she or he has not solved.”
Equivalently “No student in this class has solved every exercise in the book.”
e.g. Negate “Everyone has exactly one best friend.”
Universe of discourse is the set of all students in the class (for both x and y).
Let B (x,y): “y is the best friend of x”.
x y z B (x, y)  ((z  y) → ¬B (x, z))
Negation: “Everyone does not have exactly one best friend.” ? Not very informative!
e.g. Negate “Everyone has exactly one best friend.”
Universe of discourse is the set of all students in the class (for both x and y).
Let B (x,y): “y is the best friend of x”.
x y z B (x, y)  ((z  y) → ¬B (x, z))
Negation: “Everyone does not have exactly one best friend.” ? Not very informative!
¬x yz B (x, y)  ((z  y) → ¬B (x, z) ) 
x ¬y z B (x, y)  ((z  y) → ¬B (x, z) ) 
xy ¬z B (x, y)  ((z  y) → ¬B (x, z) ) 
xy z ¬(B (x, y)  ((z  y) → ¬B (x, z) )) 
xy z ¬B (x, y)  ¬((z  y) → ¬B (x, z) )) 
xy z ¬B (x, y)  ((z  y)  B (x, z) ))
“There is a person x such that, for every person y,

y is not the best friend of x,
OR there exists a person z other than y such that z is the best friend of x”.
An alternative way of expressing the above negation (easier to interpret):
xy z ¬B (x, y)  ((z  y)  B (x, z) )) 

xy z B (x, y) → ((z  y)  B (x, z) ))
xy z ¬B (x, y)  ((z  y)  B (x, z) )) 

xy z B (x, y) → ((z  y)  B (x, z) ))

if y is the best friend of x,
then there exists a person z other than y such that z is the best friend of x”.
xy z ¬B (x, y)  ((z  y)  B (x, z) )) 

xy z B (x, y) → ((z  y)  B (x, z) ))

if y is the best friend of x,
then there exists a person z other than y such that z is the best friend of x”.
We could rephrase the same statement as:

“There is a person x such that, x has no best friend or x has more than one best friend.”
or “There is a person who has no best friend or has more than one best friend.”
e.g. Negate x ( (y P(x,y)) → Q(x) )
¬ x ((y P(x,y)) → Q(x))  x ¬ ((y P(x,y)) → Q(x))  x ¬ (¬ (y P(x,y))  Q(x))
 x ( (y P(x,y))  ¬Q(x) )
Note that
x ( (y P(x,y))→ Q(x) ) is not logically equivalent to x y ( P(x,y) → Q(x) )
1.6/1.8/1.9 Mathematical Reasoning & Methods of Proof
We will learn:
1. Rules of reasoning; how to reason correctly
2. Methods of proof; how to show whether a given (mathematical) statement is
true or not
Rules of Inference: (Rules of reasoning)
Are used to draw conclusions from other assertions and tie the steps of a proof.
Basic rule of inference: Modus ponens
(p  (p → q)) → q
e.g.
“If it is sunny today, then we’ll play soccer. It is sunny today, so we’ll play soccer”.
Are used to draw conclusions from other assertions and tie the steps of a proof.
(p  (p → q)) → q
e.g.
Another notation:
p
p→q
q

(p  (p → q)) → q : Tautology
e.g.
p q p→q (p  (p → q)) → q
T T T T
T F F T
F T T T
F F T T
e.g.
If it is sunny today, then we’ll play soccer. We’ll play soccer, so it is sunny today.
e.g.
[(p → q)  q] → p
e.g.
[(p → q)  q] → p NOT a tautology

F when p is F and q is T
Therefore, this is not a correct way of reasoning.

e.g.
It is sunny now. Therefore, it’s sunny or snowy now. Tautology.
p Addition Rule
pq
e.g.
It is windy and raining now. Therefore, it is windy now. Tautology.
pq Simplification Rule
p
Rule of
Inference Tautology Name
p p → (p  q) Addition
pq
pq (p  q ) → p Simplification
p
p ((p)  (q)) → (p  q) Conjunction
q
pq
p [p  (p → q)] → q Modus Ponens
p→q
q
¬q [¬q  (p → q)] → ¬p Modus Tollens
p→q
 ¬p
p→q [(p → q)  (q → r)] → (p → r) Hypothetical
q→r Syllogism
p→r
pq [(p  q )  ¬p] → q Disjunctive
¬p Syllogism
q
e.g. Show that hypotheses
“If you help me, then I will finish writing the program,” “If you do not help me, then I will go to
sleep early,” and “If I go to sleep early, then I will wake up feeling refreshed”
lead to the conclusion:

“If I do not finish writing the program, then I’ll wake up feeling refreshed.”
Let
p: “you help me”
q: “I’ll finish writing the program”
r: “I’ll go to sleep early”
s: “I’ll wake up feeling refreshed”
e.g. Show that hypotheses
“If you help me, then I will finish writing the program,” “If you do not help me, then I will go to
sleep early,” and “If I go to sleep early, then I will wake up feeling refreshed”
lead to the conclusion:

“If I do not finish writing the program, then I’ll wake up feeling refreshed.”
Let
p: “you help me”
q: “I’ll finish writing the program”
r: “I’ll go to sleep early”
s: “I’ll wake up feeling refreshed”
Step Reason
1. p → q hypothesis
2. ¬q → ¬p contrapositive of step 1
3. ¬p → r hypothesis
4. ¬q → r hypothetical syllogism using steps 2, 3
5. r → s hypothesis
6. ¬q → s hypothesis syllogism using steps 4, 5
Rules of Inference for Quantified Statements
Universal instantiation: x P(x)

 P(c) if c  U
U: universe of discourse
Universal generalization:
P(c) for an arbitrary cU
 x P(x)
Existential instantiation:
If x P(x) is true then x P(x)

we know one c exists  P(c) for some element c  U
s.t. P(c) is true.
Existential generalization:
If we know one c in U P(c) for some element c  U

s.t. P(c) is true then  x P(x)
x P(x) is true
e.g.
i) “All lions are fierce”
ii) “Some lions do not drink coffee”
Does i) and ii) imply that “some fierce creatures do not drink coffee” ?
P(x): “x is a lion”
Q(x): “x is fierce”
R(x): “x drinks coffee”
Universe of discourse is the set of all creatures.
e.g.
i) x (P(x) → Q(x))
ii) x (P(x)  ¬R(x))
i)  ii) ? x (Q(x)  ¬R(x))
e.g.
i) x (P(x) → Q(x))
ii) x (P(x)  ¬R(x))
i)  ii) ? x (Q(x)  ¬R(x))
(ii) implies that there is some x1 such that P(x1)  ¬R(x1) by Existential Instantiation.
Hence by (i), Q(x1) is true (using Simplification and Modus Ponens rules).
¬R(x1) is also true by using again Simplification rule.
Then Q(x1)  ¬R(x1) which implies that x (Q(x)  ¬R(x)) by Existential Generalization.
Fallacies: Types of incorrect reasoning:
Fallacy of affirming the conclusion:
e.g.
“If you have solved every problem in this book, then you know Discrete Math.
You know Discrete Math. Therefore, you have solved every problem in this book.”
[(p → q)  q] → p NOT a tautology

Fallacy of denying the hypothesis:
“If you are older than 18 years, then you can have a driving license. You are not older
than 18 years, so you can’t have a driving license.”
[(p → q)  ¬p] → ¬q NOT a tautology

Begging the question fallacy: When one or more steps of a proof are based on the truth
of the statement being proved (circular reasoning)
Methods of Proving Theorems
Theorem: A statement that can be shown to be true.

Proof: Arguments which show that a theorem is true.
Axioms: Underlying assumptions about a mathematical structure.
Definitions: Rules of the game!
Methods of Proving Theorems
Theorem: A statement that can be shown to be true.

Proof: Arguments which show that a theorem is true.
Axioms: Underlying assumptions about a mathematical structure.
Definitions: Rules of the game!
To prove a theorem, you usually start from premises (conditions), and using known
theorems, axioms and definitions, you construct a sequence of steps that leads to the
conclusion (forward reasoning).
Example - Fermat’s Last Theorem:
The equation
xn+yn = zn
has no solution in integers x, y, and z with xyz  0, whenever n is an integer with n > 2.
Put forward in the 17th century, but formally proved only in 1990s.
Some further terminology:
Lemma: A simple theorem that is used in the proof of other theorems.

Corollary: A proposition that can be established directly from a theorem.
Conjecture: A statement whose truth-value is unknown. If a proof can be found, then it
becomes a theorem.
Some further terminology:
Lemma: A simple theorem that is used in the proof of other theorems.

Corollary: A proposition that can be established directly from a theorem.
Conjecture: A statement whose truth-value is unknown. If a proof can be found, then it
becomes a theorem.
Example: (Goldbach’s conjecture)
“Every even positive integer greater than 4 is the sum of two primes”.
Direct proof: (forward reasoning)
Many theorems are implications:
p→q
To prove, we need to show that whenever p is T, q is also T.

This implies that the case p true and q false never occurs.
Direct proof: (forward reasoning)
Many theorems are implications:
p→q
To prove, we need to show that whenever p is T, q is also T.

This implies that the case p true and q false never occurs.
e.g. p q
Prove that, nZ, if n is odd, then n2 is odd.
n is odd  k Z such that n = 2k + 1  n2 = 4k2 + 4k + 1 = 2(2k2 + 2k) +1

 n2 is odd.
Indirect proof: (backward reasoning)
p → q  ¬q → ¬p (contrapositive)
Indirect proof: (backward reasoning)
p → q  ¬q → ¬p (contrapositive)
e.g.
Prove that, nZ, if 3n + 2 is odd, then n is odd.
Let n be even. Then k Z s.t. n = 2k  3n + 2 = 6k + 2 = 2(3k + 1)

 3n + 2 is even too.
Proof by contradiction:
e.g. Prove that 2 is irrational.

Suppose that 2 is not irrational, that is,

suppose 2 = a/b, where a and b have no common factors

 2 = a2/ b2  2b2 = a2
 a2 is even  a is even  c Z s.t. a = 2c
 2b2 = 4c2  b2 = 2c2

 b2 is even  b is even
 2 | a  2 | b  a and b have common factors  contradiction!
 2 is irrational.

 2 = a2/ b2  2b2 = a2
 a2 is even  a is even  c Z s.t. a = 2c
 2b2 = 4c2  b2 = 2c2

 b2 is even  b is even
 2 | a  2 | b  a and b have common factors  contradiction!
 2 is irrational.
Method: Suppose we want to prove p is true. We start assuming p is false and then
proceed. If we end up with a contradiction, then we conclude that the assumption “p is
false” is false, i.e., p is true.
Proof by cases:
p→q s.t. p  (p1  p2  …  pn)
We can use the following logical equivalence:

[ (p1 p2 …  pn) → q ]  [(p1→q)  (p2→q)  …  (pn→q)]
Proof by cases:
p→q s.t. p  (p1  p2  …  pn)

[ (p1 p2 …  pn) → q ]  [(p1→q)  (p2→q)  …  (pn→q)]
e.g.
Prove that, nZ, if n is not divisible by 3, then n2  1 (mod 3).

Proof by cases:
p→q s.t. p  (p1  p2  …  pn)

[ (p1 p2 …  pn) → q ]  [(p1→q)  (p2→q)  …  (pn→q)]
e.g.

q: n2  1 (mod 3)
p: n is not divisible by 3  p1: n  1 (mod 3), p2 : n  2 (mod 3)  p  p1 p2
Proof by cases:
p→q s.t. p  (p1  p2  …  pn)

[ (p1 p2 …  pn) → q ]  [(p1→q)  (p2→q)  …  (pn→q)]
e.g.

q: n2  1 (mod 3)
p: n is not divisible by 3  p1: n  1 (mod 3), p2 : n  2 (mod 3)  p  p1 p2
If p1 is T:
k Z s.t. n = 3k + 1  n2 = 9k2 + 6k + 1 = 3 (3k2 + 2k) + 1
 n2  1 (mod 3)
If p2 is T:
k Z s.t. n = 3k + 2  n2 = 9k2 + 12k + 4 = 3(3k2 + 4k + 1) + 1
 n2  1 (mod 3)
 (p1 → q)  (p2 → q) is T  p → q is T
e.g. (iff)
Prove that, nZ, n is odd if and only if n2 is odd.
p: n is odd, q: n2 is odd  Prove p ↔ q

e.g. (iff)
We have to show two things:
i) p → q:
ii) q → p:
e.g. (iff)
We have to show two things:
i) p → q: we already showed it.

ii) q → p: use indirect proof s.t. ¬p → ¬q
k Z s.t. n =2k  n2 = 4k2 = 2(2k2) which is even.

Theorems and Quantifiers:
Constructive Existence proof:
Prove x P(x) : Find an a s.t. P(a) is true
Non-constructive existence proof:
x P(x) ? : Prove or disprove the existence of an a s.t. P(a) is true, without explicitly
finding it.
Theorems and Quantifiers:
Constructive Existence proof:
Prove x P(x) : Find an a s.t. P(a) is true
Non-constructive existence proof:
x P(x) ? : Prove or disprove the existence of an a s.t. P(a) is true, without explicitly
finding it.
Counter-example:
x P(x) ?
Find a for which P(a) is also false;

which means x P(x) is false.
e.g.
Show that ‘all primes are odd’ is false.
x =2 even and prime
 it is false.

Comp106 Logic

Uploaded by

Copyright:

Available Formats

Comp106 Logic

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Comp106 Logic

Uploaded by

Copyright:

Available Formats

1.

The Foundations (Logic)

Motivation: Basis of all mathematical reasoning and numerous applications in

• What time is it?

 Use letters to denote propositions:

Truth values: true T, false F

¬p: “It is not the case that p”

Definition: Disjunction (OR)

Definition: Exclusive Or (XOR)

e.g. “If today is Tuesday, then 2 + 2 = 10” (True)

Blonde and blue eyes  true

P q p↔q p ↔ q is T if both p → q is T and q → p is T.

p ↔ q is logically equivalent to say that p → q  q → p.

q: “You can ride the roller coaster”

q: “You can ride the roller coaster”

p: “It is below freezing”

• “It is below freezing but not snowing.”

p: “It is below freezing”

• “It is below freezing but not snowing.”

A bit has two possible values, 0 or 1.

In most programming languages, a variable is a Boolean variable if its value is

Bit operations  Logical operations

Bitwise OR, AND, XOR

Definition: Logical equivalence

Definition: Logical equivalence

¬(¬p)  p Double Negation law

Tautology: A compound proposition that is always true

Contradiction: A compound proposition that is always false

Contingency: Neither tautology nor contradiction

Consider the following propositions for a system specification:

Are they consistent?

Consider the following propositions for a system specification:

Are they consistent?

Consider the following propositions for a system specification:

Are they consistent?

Statement: x is greater than 3

This is a propositional function.

We can express it in another form:

Then what are the truth values of P(4) and P(2) ?

Express this as a universal quantification.

Let P(x) denote “x has studied calculus”

x P(x)  P(1)  P(2)  P(3)  P(4)

x P(x)  P(1)  P(2)  P(3)  P(4)

Translating Sentences into Logical Expression

Let B (x,y): “y is the best friend of x”

Universe of discourse is all the students in this class.

Q(x) → y P(x,y) )  y ( Q(x) → P(x,y) )

Q(x) → y P(x,y) )  y ( Q(x) → P(x,y) )

But we cannot write

Q(x) → y P(x,y) )  y ( Q(x) → P(x,y) )

But we cannot write

So be careful when replacing quantifiers!

Let P(x,y) be the statement “ x + y = 0 ”.

¬(x P(x))  x ¬P(x)  x P(x) is false

¬(x P(x))  x ¬P(x)  x P(x) is false

¬(x P(x))  x ¬P(x)  x P(x) is false

¬(x P(x))  x ¬P(x)  x P(x) is false

¬(x P(x))  x ¬P(x)  x P(x) is false

¬(x P(x))  x ¬P(x)  x P(x) is false