Enriched Introduction to Theory of Computation
CSC 240
Winter 2013
Faith Ellen
CSC 240 Enriched Introduction to Theory of Computation
Logic helps us communicate precisely. ◮ program specifications
◮ database queries
◮ circuits
CSC 240 Enriched Introduction to Theory of Computation
Propositions
A proposition is a statement that is either true or false. Examples of propositions:
◮ 2+3=5
CSC 240 Enriched Introduction to Theory of Computation
Propositions
A proposition is a statement that is either true or false. Examples of propositions:
◮ 2+3=5 ◮ 1+1=3
CSC 240 Enriched Introduction to Theory of Computation
Propositions
A proposition is a statement that is either true or false. Examples of propositions:
◮ 2+3=5
◮ 1+1=3
◮ Foreverynon-negativeintegern,n2+n+41isprime.
CSC 240 Enriched Introduction to Theory of Computation
Propositions
A proposition is a statement that is either true or false. Examples of propositions:
◮ 2+3=5
◮ 1+1=3
◮ Foreverynon-negativeintegern,n2+n+41isprime.
◮ Every even integer greater than 2 is the sum of 2 prime numbers.
CSC 240 Enriched Introduction to Theory of Computation
Ambiguous sentences:
◮ You may have cake or ice cream.
◮ If you can solve any problem in the course, then you will get an A.
◮ Two sisters reunited after 18 years at a checkout counter.
CSC 240 Enriched Introduction to Theory of Computation
Connectives can change or combine propositions.
Boolean variable:
a variable that has only two possible values, true and false.
◮ MIT book: denoted by T and F.
◮ Course notes: denoted by 1 and 0.
Truth table
◮ columns for different combinations of Boolean variables
◮ one row for each possible assignment of values to the Boolean variables.
CSC 240 Enriched Introduction to Theory of Computation
Negation
The negation of P is denoted by: NOT(P), ¬P, ∼ P, P
P NOT(P) FT TF
CSC 240 Enriched Introduction to Theory of Computation
Negation
The negation of P is denoted by: NOT(P), ¬P, ∼ P, P
P NOT(P) NOT(NOT(P)) FTF TFT
P and NOT(NOT(P)) are logically equivalent: they have identical columns in the truth table.
CSC 240 Enriched Introduction to Theory of Computation
Conjunction
TheconjunctionofPandQisdenotedby: PANDQ,P∧Q,P&Q,P·Q
P Q PANDQ FFF FTF TFF TTT
CSC 240 Enriched Introduction to Theory of Computation
Disjunction
ThedisjunctionofPandQisdenotedby: PORQ,P∨Q,P+Q
P Q PORQ FFF FTT TFT TTT
CSC 240 Enriched Introduction to Theory of Computation
Exclusive-Or
The exclusive-or of P and Q is denoted by: P XOR Q, P ⊕ Q
P Q PORQ PXORQ FFFF FTTT TFTT TTTF
CSC 240 Enriched Introduction to Theory of Computation
NOT NOT(P) P Q PORQ (PORQ) NOT(P) NOT(Q) AND
NOT(Q) FFFTTTT FTTFTFF TFTFFTF TTTFFFF
De Morgan’s Laws:
NOT(P OR Q) and NOT(P) AND NOT(Q) are logically equivalent. NOT(P AND Q) and NOT(P) OR NOT(Q) are logically equivalent.
CSC 240 Enriched Introduction to Theory of Computation
if(x > 0||(x <= 0&&y > 100))
Let A denote ‘x > 0’ and let B denote ‘y > 100’. A OR (NOT(A) AND B)
A B AORB NOT(A)
NOT(A)
A OR
(NOT(A) AND B) FFFTFF FTTTTT TFTFFT TTTFFT
A OR ((NOT A) AND B) is logically equivalent to A OR B
AND B
CSC 240 Enriched Introduction to Theory of Computation
if(x > 0||(x <= 0&&y > 100))
Let A denote ‘x > 0’ and let B denote ‘y > 100’. A OR (NOT(A) AND B)
A B AORB NOT(A)
NOT(A)
A OR
(NOT(A) AND B) FFFTFF FTTTTT TFTFFT TTTFFT
A OR ((NOT A) AND B) is logically equivalent to A OR B
if(x > 0||y > 100)
AND B
CSC 240 Enriched Introduction to Theory of Computation
Implication
Implicationisdenotedby: PIMPLIESQ,P→Q,P ⇒Q,P ⊃Q P is the hypothesis.
Q is the conclusion.
P Q P IMPLIES Q FFT FTT TFF TTT
P IMPLIES Q is logically equivalent to NOT(P) OR Q.
CSC 240 Enriched Introduction to Theory of Computation
Implication
Implicationisdenotedby: PIMPLIESQ,P→Q,P ⇒Q,P ⊃Q P is the hypothesis.
Q is the conclusion.
P Q P IMPLIES Q NOT(P) NOT(P) OR Q FFTTT FTTTT TFFFF TTTFT
P IMPLIES Q is logically equivalent to NOT(P) OR Q.
CSC 240 Enriched Introduction to Theory of Computation
Examples of P IMPLIES Q in English P implies Q.
◮ Getting perfect on the final exam implies you will get an A in the course.
If P, [then] Q.
◮ If the list is empty, then the search is unsuccessful. ◮ If the input is positive, the program halts.
Q if P.
◮ The program halts if the input is positive.
P only if Q.
◮ The search is successful only if the list is nonempty.
CSC 240 Enriched Introduction to Theory of Computation
More Examples of P IMPLIES Q in English When[ever] P, [then] Q.
◮ When the robot detects an obstacle, it turns. Q when[ever] P.
◮ The robot turns whenever it detects an obstacle.
P only when Q.
◮ The search is successful only when the list is nonempty.
Only when Q, P.
◮ Only when the network is connected, will the broadcast be successful.
CSC 240 Enriched Introduction to Theory of Computation
Even More Examples of P IMPLIES Q in English P is is sufficent/enough for Q.
◮ Having a good initial value is sufficient for the method to converge. For Q, P is sufficient/enough.
◮ For the method to converge, a good initial value is enough . Q is necessary for P.
◮ At least 40% on the final exam is necessary for passing CSC240. For P, Q is necessary.
◮ To pass CSC240, at least 40% on the final exam is necessary . P requires Q.
◮ A successful message receipt requires sending an acknowledgement. CSC 240 Enriched Introduction to Theory of Computation
NOT(Q) IMPLIES NOT(P) is the contrapositive of P IMPLIES Q Q IMPLIES P is the converse of P IMPLIES Q
P NOT(Q) Q
P Q IMPLIES NOT(P) NOT(Q) IMPLIES IMPLIES
Q NOT(P) P FFTTTTT FTTTFTF TFFFTFT TTTFFTT
CSC 240 Enriched Introduction to Theory of Computation
NOT(Q) IMPLIES NOT(P) is the contrapositive of P IMPLIES Q Q IMPLIES P is the converse of P IMPLIES Q
P NOT(Q) Q
P Q IMPLIES NOT(P) NOT(Q) IMPLIES IMPLIES
Q NOT(P) P FFTTTTT FTTTFTF TFFFTFT TTTFFTT
NOT(NOT(P)) IMPLIES NOT(NOT(Q)) is the contrapositive of NOT(Q) IMPLIES NOT(P)
CSC 240 Enriched Introduction to Theory of Computation
Equivalence
The equivalence of P and Q is denoted by: PIFFQ,P↔Q,P ⇔Q,P=Q,P≡Q Itisreadas: PisequivalenttoQ,PifandonlyifQ, P is necessary and sufficient for Q
P Q PIFFQ FFT FTF TFF TTT
CSC 240 Enriched Introduction to Theory of Computation
Predicates
A predicate is a proposition whose truth depends on the value of one or more variables.
Examples of predicates: x3≥8
CSC 240
Enriched Introduction to Theory of Computation
Predicates
A predicate is a proposition whose truth depends on the value of one or more variables.
Examples of predicates: x3≥8
a4+b4+c4=d4
CSC 240
Enriched Introduction to Theory of Computation
Predicates
A predicate is a proposition whose truth depends on the value of one or more variables.
Examples of predicates:
x3≥8
a4+b4+c4=d4
This predicate is true when a = 95800, b = 217519, c = 414560, and d = 422481.
CSC 240
Enriched Introduction to Theory of Computation
Predicates
A predicate is a proposition whose truth depends on the value of one or more variables.
Examples of predicates:
x3≥8
a4+b4+c4=d4
This predicate is true when a = 95800, b = 217519, c = 414560, and d = 422481.
(x+1)2>0
CSC 240
Enriched Introduction to Theory of Computation
Predicates
A predicate is a proposition whose truth depends on the value of one or more variables.
Examples of predicates:
x3≥8
a4+b4+c4=d4
This predicate is true when a = 95800, b = 217519, c = 414560, and d = 422481.
(x+1)2>0
It snowed today.
CSC 240
Enriched Introduction to Theory of Computation
A small database:
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
Then a : E → {T,F}.
A predicate is a function whose range is {T,F}.
Let s(e) = ‘salary of employee e’. This is not a predicate. ‘s(e) ≥ 1000’ is a predicate.
CSC 240
Enriched Introduction to Theory of Computation
A small database:
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
Then a : E → {T,F}.
A predicate is a function whose range is {T,F}.
a(e) = T if e = Ron a(e) = F if e = Andy
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification
Every employee made at least 1000. Each employee made at least 1000. All employees make at least 1000. Employees make at least 1000.
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification
Every employee made at least 1000. Each employee made at least 1000. All employees make at least 1000. Employees make at least 1000.
∀e ∈ E.a(e)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∀e ∈ E.a(e)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∀e ∈ E.a(e)
This proposition is false, since Andy made less than 1000.
To show that ∀x ∈ D.p(x) is false, give a counterexample: an x ∈ D such that p(x) is false.
CSC 240
Enriched Introduction to Theory of Computation
Each employee made less than 6000.
CSC 240
Enriched Introduction to Theory of Computation
Each employee made less than 6000. Written in logic:
Let l(e) = ‘employee e made less than 6000’. ∀e ∈ E.l(e)
CSC 240
Enriched Introduction to Theory of Computation
Each employee made less than 6000. Written in logic:
Let l(e) = ‘employee e made less than 6000’. ∀e ∈ E.l(e)
Foralle∈E,letl(e)=‘emadelessthan6000’. ∀e ∈ E.l(e)
CSC 240
Enriched Introduction to Theory of Computation
Each employee made less than 6000. Written in logic:
Let l(e) = ‘employee e made less than 6000’. ∀e ∈ E.l(e)
Foralle∈E,letl(e)=‘emadelessthan6000’. ∀e ∈ E.l(e)
Incorrect definition of l(e):
Let l(e) = ‘e made less than 6000’.
CSC 240
Enriched Introduction to Theory of Computation
Each employee made less than 6000. Written in logic:
Let l(e) = ‘employee e made less than 6000’. ∀e ∈ E.l(e)
Foralle∈E,letl(e)=‘emadelessthan6000’. ∀e ∈ E.l(e)
∀e∈E.(emadelessthan6000)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let E denote the set of employees. For all e ∈ E, let
l(e) = ‘e made less than 6000’. ∀e ∈ E.l(e)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let E denote the set of employees. For all e ∈ E, let
l(e) = ‘e made less than 6000’. ∀e ∈ E.l(e)
This proposition is true. Check the salary of every employee.
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∀e ∈ E.NOT(a(e))
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∀e ∈ E.NOT(a(e))
False. Tom is a counterexample.
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∀e ∈ E.NOT(a(e))
False. Tom is a counterexample. NOT(∀e ∈ E.a(e))
CSC 240
Enriched Introduction to Theory of Computation
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∀e ∈ E.NOT(a(e))
False. Tom is a counterexample. NOT(∀e ∈ E.a(e))
True, since ∀e ∈ E.a(e) is false.
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification
There is an employee who made at least 1000. There exists an employee who made at least 1000. Some employee made at least 1000.
For some employee e, e made at least 1000.
At least one employee made at least 1000.
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification
There is an employee who made at least 1000. There exists an employee who made at least 1000. Some employee made at least 1000.
For some employee e, e made at least 1000.
At least one employee made at least 1000.
∃e ∈ E.a(e)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∃e ∈ E.a(e)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∃e ∈ E.a(e)
This proposition is true. Tom is an example that demonstrates this.
To show that ∃x ∈ D.p(x) is true, give an example: an x ∈ D such that p(x) is true.
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let a(e) = ‘employee e made at least 1000’. Let E denote the set of employees.
∃e ∈ E.a(e)
This proposition is true. Tom is an example that demonstrates this. To show that ∃x ∈ D.p(x) is true, give an example:
an x ∈ D such that p(x) is true.
Provided D ̸= φ,
if ∀x ∈ D.p(x) is true, then ∃x ∈ D.p(x) is true.
CSC 240
Enriched Introduction to Theory of Computation
Some employee made at least 6000.
CSC 240
Enriched Introduction to Theory of Computation
Some employee made at least 6000. Written in logic:
Let g(e) = ‘employee e made at least 6000’. ∃e ∈ E.g(e)
CSC 240
Enriched Introduction to Theory of Computation
Some employee made at least 6000. Written in logic:
Let g(e) = ‘employee e made at least 6000’. ∃e ∈ E.g(e)
∃e ∈ E.NOT(l(e))
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let E denote the set of employees. For all e ∈ E, let
g(e) = ‘e made at least 6000’. ∃e ∈ E.g(e)
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Let E denote the set of employees. For all e ∈ E, let
g(e) = ‘e made at least 6000’. ∃e ∈ E.g(e)
This proposition is false. Check the salary of every employee.
CSC 240
Enriched Introduction to Theory of Computation
Quantification with Negation
∃x ∈ D.p(x) is false when p(x) is false for every x ∈ D.
NOT(∃x ∈ D.p(x)) is logically equivalent to ∀x ∈ D.NOT(p(x)). NOT(∃x ∈ D.p(x)) IFF ∀x ∈ D.NOT(p(x)) is true.
CSC 240
Enriched Introduction to Theory of Computation
Quantification with Negation
∃x ∈ D.p(x) is false when p(x) is false for every x ∈ D.
NOT(∃x ∈ D.p(x)) is logically equivalent to ∀x ∈ D.NOT(p(x)). NOT(∃x ∈ D.p(x)) IFF ∀x ∈ D.NOT(p(x)) is true.
∀x ∈ D.p(x) is false when there exists a counterexample. NOT(∀x ∈ D.p(x)) IFF ∃x ∈ D.NOT(p(x)) is true.
CSC 240
Enriched Introduction to Theory of Computation
An employee made at least 1000.
CSC 240
Enriched Introduction to Theory of Computation
An employee made at least 1000.
Written in logic: ∀e∈E.a(e) ∃e∈E.a(e)
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification with Disjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Every employee made at least 1000 or every employee made less than 5000.
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification with Disjunction
Every employee made at least 1000 or every employee made less than 5000.
Let b(e) =
‘employee e made less than 5000’.
(∀e ∈ E.a(e)) OR (∀e ∈ E.b(e))
false
Andy is a counterexample to ∀e ∈ E.a(e) Ron is a counterexample to ∀e ∈ E.b(e)
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification with Disjunction
Every employee made at least 1000 or every employee made less than 5000.
(∀e ∈ E.a(e)) OR (∀e ∈ E.b(e)) Every employee made at least 1000 or
less than 5000.
∀e ∈ E.(a(e) OR b(e))
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification with Disjunction
Every employee made at least 1000 or every employee made less than 5000.
(∀e ∈ E.a(e)) OR (∀e ∈ E.b(e)) Every employee made at least 1000 or
less than 5000.
∀e ∈ E.(a(e) OR b(e))
If (∀x ∈ D.p(x)) OR (∀x ∈ D.q(x)) is true, then ∀x ∈ D.(p(x) OR q(x)) is true.
The converse is not always true.
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification with Conjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Every employee made at least 1000 and every employee made less than 5000.
Every employee made at least 1000 and less than 5000.
CSC 240
Enriched Introduction to Theory of Computation
Universal Quantification with Conjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Every employee made at least 1000 and every employee made less than 5000.
Every employee made at least 1000 and less than 5000.
(∀x ∈ D.p(x)) AND (∀x ∈ D.q(x)) is equivalent to ∀x ∈ D.(p(x) AND q(x)).
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification with Conjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Some employee made at least 1000 and less than 1500.
Some employee made at least 1000 and some employee made less than 1500.
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification with Conjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Some employee made at least 1000 and less than 1500.
Some employee made at least 1000 and some employee made less than 1500.
If ∃x ∈ D.(p(x) AND q(x)) is true,
then (∃x ∈ D.p(x)) AND (∃x ∈ D.q(x)) is true. The converse is not always true.
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification with Conjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Some employee made at least 1000 and less than 1500.
Some employee made at least 1000 and some employee made less than 1500.
If ∃x ∈ D.(p(x) AND q(x)) is true,
then (∃x ∈ D.p(x)) AND (∃x ∈ D.q(x)) is true. The converse is not always true.
(∃x ∈ D.p(x)) AND (∃y ∈ D.q(y))
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification with Conjunction
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
Some employee made at least 1000 and less than 1500.
Some employee made at least 1000 and some employee made less than 1500.
If ∃x ∈ D.(p(x) AND q(x)) is true,
then (∃x ∈ D.p(x)) AND (∃x ∈ D.q(x)) is true. The converse is not always true.
(∃x ∈ D.p(x)) AND (∃y ∈ D.q(y)) is equivalent to ∃x ∈ D.∃y ∈ D.(p(x) AND q(y))
(∀x ∈ D.p(x)) OR (∀y ∈ D.q(y)) is equivalent to ∀x ∈ D.∀y ∈ D.(p(x) OR q(y))
CSC 240
Enriched Introduction to Theory of Computation
Existential Quantification with Disjunction
∃x ∈ D.(p(x) OR q(x)) is equivalent to (∃x ∈ D.p(x)) OR (∃x ∈ D.q(x)).
CSC 240
Enriched Introduction to Theory of Computation
More Quantification
Some female employee made at least 1000.
E = the set of employees.
a(e) = ‘employee e made at least 1000’.
CSC 240
Enriched Introduction to Theory of Computation
More Quantification
Some female employee made at least 1000. E = the set of employees.
a(e) = ‘employee e made at least 1000’. Let F = the set of female employees.
∃e ∈ F.a(e)
Fore∈E,letf(e)=‘eisfemale’.
∃e ∈ E.(f (e) AND a(e))
Let A = the set of employees who made at least 1000. Let f (e) = ‘employee e is female’.
∃e ∈ A.f (e)
CSC 240
Enriched Introduction to Theory of Computation
All female employees made at least 1000.
E = the set of employees.
A = the set of employees who made at least 1000. F = the set of female employees.
a(e) = ‘employee e made at least 1000’.
f (e) = ‘employee e is female’.
CSC 240
Enriched Introduction to Theory of Computation
All female employees made at least 1000.
E = the set of employees.
A = the set of employees who made at least 1000. F = the set of female employees.
a(e) = ‘employee e made at least 1000’.
f (e) = ‘employee e is female’.
∀e∈F.a(e)
CSC 240
Enriched Introduction to Theory of Computation
All female employees made at least 1000. For all employees, if the employee is female,
then she made at least 1000.
If an employee is female, then she made at least 1000.
E = the set of employees.
A = the set of employees who made at least 1000. F = the set of female employees.
a(e) = ‘employee e made at least 1000’.
f (e) = ‘employee e is female’.
∀e∈F.a(e)
∀e∈E.(f(e)IMPLIESa(e))
CSC 240
Enriched Introduction to Theory of Computation
All female employees made at least 1000. For all employees, if the employee is female,
then she made at least 1000.
If an employee is female, then she made at least 1000.
E = the set of employees.
A = the set of employees who made at least 1000. F = the set of female employees.
a(e) = ‘employee e made at least 1000’.
f (e) = ‘employee e is female’.
∀e∈F.a(e)
∀e∈E.(f(e)IMPLIESa(e))
∀e∈E.(e∈F IMPLIESe∈A).
CSC 240
Enriched Introduction to Theory of Computation
Some x with property p also has property q. ∃x ∈ D.(p(x) AND q(x))
Every x with property p also has property q. ∀x ∈ D.(p(x) IMPLIES q(x))
CSC 240
Enriched Introduction to Theory of Computation
Some x with property p also has property q. ∃x ∈ D.(p(x) AND q(x))
Every x with property p also has property q. ∀x ∈ D.(p(x) IMPLIES q(x))
There is no x with property p that also has property q.
Every x with property p does not have property q.
Not every x with property p also has property q.
There is some x with property p that does not have property q.
CSC 240
Enriched Introduction to Theory of Computation
Some x with property p also has property q. ∃x ∈ D.(p(x) AND q(x))
Every x with property p also has property q. ∀x ∈ D.(p(x) IMPLIES q(x))
There is no x with property p that also has property q. NOT(∃x ∈ D.(p(x) AND q(x)))
Every x with property p does not have property q. ∀x ∈ D.(p(x) IMPLIES NOT(q(x)))
Not every x with property p also has property q. NOT (∀x ∈ D.(p(x) IMPLIES q(x)))
There is some x with property p that does not have property q. ∃x ∈ D.(p(x) AND NOT(q(x)))
CSC 240
Enriched Introduction to Theory of Computation
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
All employees that made at least 6000 are female.
Let E = the set of employees.
Let g(e) = ‘employee e made at least 6000’. Let f (e) = ‘employee e is female’.
∀e ∈ E.(g(e) IMPLIES f (e))
CSC 240
Enriched Introduction to Theory of Computation
All employees that made at least 6000 are female.
Let E = the set of employees.
Let g(e) = ‘employee e made at least 6000’. Let f (e) = ‘employee e is female’.
∀e ∈ E.(g(e) IMPLIES f (e))
∀e ∈ E.(NOT(f (e)) IMPLIES NOT(g(e))) All male employees made less than 6000.
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
CSC 240
Enriched Introduction to Theory of Computation
All employees that made at least 6000 are female.
Let E = the set of employees.
Let g(e) = ‘employee e made at least 6000’. Let f (e) = ‘employee e is female’.
∀e ∈ E.(g(e) IMPLIES f (e))
∀e ∈ E.(NOT(f (e)) IMPLIES NOT(g(e)))
All male employees made less than 6000.
∀e ∈ E.(g(e) IMPLIES f (e)) is vacuously true.
employee
gender
salary
Andy Donna Leslie Ron Tom
M F F M M
0
3000
5000
5700
1800
CSC 240
Enriched Introduction to Theory of Computation
Mixing Quantifiers
i -o1
1 H
HHj m * H
Let I = {i , i , i }. 1 2 3
H
iHjo2 123
2 H
3 Hj
H Hj m * H
LetO={o ,o ,o }.
Let c(i,o) = ‘input i connects to output o’.
i H o3 ∀o ∈ O.∃i ∈ I.c(i,o)
Every output has some input that connects to it. true
∃i ∈ I.∀o ∈ O.c(i,o)
Some input connects to all outputs. false
CSC 240
Enriched Introduction to Theory of Computation
Mixing Quantifiers
i -o1
1 H
HHj m * H
Let I = {i , i , i }. 1 2 3
H
iHjo2 123
2 H
3 Hj
H
jH m
* H
i H o3
LetO={o ,o ,o }.
Let c(i,o) = ‘input i connects to output o’.
∀o ∈ O.∃i ∈ I.c(i,o)
Every output has some input that connects to it. true
∃i ∈ I.∀o ∈ O.c(i,o)
Some input connects to all outputs. false
(∃x ∈ D.∀y ∈ D′.p(x, y)) IMPLIES (∀y ∈ D′.∃x ∈ D.p(x, y))
CSC 240
Enriched Introduction to Theory of Computation
Mixing Quantifiers
i -o1 1 H
H
jH m
Let I = {i , i , i }. 1 2 3
* H H
LetO={o ,o ,o }. iHjo2 123
2 H
3 Hj
Every output has some input that connects to it. true ∃i ∈ I.∀o ∈ O.c(i,o)
Some input connects to all outputs. false
(∃x ∈ D.∀y ∈ D′.p(x, y)) IMPLIES (∀y ∈ D′.∃x ∈ D.p(x, y)) ∀y ∈ D′.∃xy ∈ D.p(xy,y)
H Hj m * H
Let c(i,o) = ‘input i connects to output o’.
i H o3 ∀o ∈ O.∃i ∈ I.c(i,o)
CSC 240
Enriched Introduction to Theory of Computation
lim f (x) = d x→a
∀ε ∈ R+.∃δ ∈ R+.∀x ∈ R. (|x − a| < δ IMPLIES |f (x) − d| < ε) f ∈O(g)
∃c ∈ R+ .∃b ∈ N. (x ≥ b IMPLIES f (x ) ≤ cg (x ))
f ∈Ω(g)
∃c ∈ R+ .∃b ∈ N. (x ≥ b IMPLIES f (x ) ≥ cg (x ))
CSC 240
Enriched Introduction to Theory of Computation
Let M : R × C → {T,F} Every row of M contains T.
CSC 240
Enriched Introduction to Theory of Computation
Let M : R × C → {T,F}
Every row of M contains T. ∀x ∈ R.∃y ∈ C.M(x,y)
CSC 240
Enriched Introduction to Theory of Computation
Let M : R × C → {T,F} Every row of M contains T.
∀x ∈ R.∃y ∈ C.M(x,y) NOT(∀x ∈ R.∃y ∈ C.M(x,y))
Not every row of M contains T. ∃x ∈ R.NOT(∃y ∈ C.M(x,y))
Some row of M does not contain T.
∃x ∈ R.∀y ∈ C.NOT(M(x,y)) Some row of M is all F.
CSC 240
Enriched Introduction to Theory of Computation
Let M : R × C → {T,F} Every row of M contains T.
∀x ∈ R.∃y ∈ C.M(x,y) NOT(∀x ∈ R.∃y ∈ C.M(x,y))
Not every row of M contains T. ∃x ∈ R.NOT(∃y ∈ C.M(x,y))
Some row of M does not contain T. ∃x ∈ R.∀y ∈ C.NOT(M(x,y))
Some row of M is all F.
NOT(∃y ∈ C.∀x ∈ R.M(x,y)) is equivalent to ∀y ∈ C.∃x ∈ R.NOT(M(x,y))
The negation of ‘Some column of M is entirely T’ is ‘Every column of M contains F’.
CSC 240
Enriched Introduction to Theory of Computation
Problem 1
Write the following sentence in logic, using the notation from the course slides (and MIT book):
The lockdown won’t end unless the infection rate has decreased.
Problem 1
Write the following sentence in logic, using the notation from the course slides (and MIT book):
The lockdown won’t end unless the infection rate has decreased.
Let L denote “The lockdown will end”.
Let D denote “The infection rate has decreased”. (NOT L) UNLESS D
The lockdown will not end unless the infection rate has decreased.
Let L denote “The lockdown will end”.
Let D denote “The infection rate has decreased”.
Which of the following mean the same as (NOT L) UNLESS D?
1. If the infection rate has decreased, the lockdown will end. D IMPLIES L
2. If the infection rate has decreased, the lockdown will not end. D IMPLIES (NOT L) or, equivalently, L IMPLIES (NOT D)
3. If the infection rate has not decreased, the lockdown will end. (NOT D) IMPLIES L or, equivalently, (NOT L) IMPLIES D
4. If the infection rate has not decreased, the lockdown will not end.
(NOT D) IMPLIES (NOT L) or, equivalently, L IMPLIES D
The lockdown will not end unless the infection rate has decreased.
Let L denote “The lockdown will end”.
Let D denote “The infection rate has decreased”.
If the infection rate has not decreased, the lockdown will not end. (NOT L) UNLESS D means the same as L IMPLIES D
If the lockdown ends, the infection rate has decreased.
(NOT P) UNLESS Q means the same as P IMPLIES Q
I won’t give you cake unless you have eaten your vegetables.
(NOT P) UNLESS Q means the same as P IMPLIES Q
I won’t give you cake unless you have eaten your vegetables.
Let P denote “I will give you cake”.
Let Q denote “you have eaten your vegetables”.
(NOT P) UNLESS Q means the same as P IMPLIES Q
I won’t give you cake unless you have eaten your vegetables.
Let P denote “I will give you cake”.
Let Q denote “you have eaten your vegetables”.
Suppose the child eats their vegetables.
If the parent gives doesn’t give the child cake, did the parent lie?
(NOT P) UNLESS Q means the same as P IMPLIES Q
I won’t give you cake unless you have eaten your vegetables.
Let P denote “I will give you cake”.
Let Q denote “you have eaten your vegetables”.
Suppose the child eats their vegetables.
If the parent gives doesn’t give the child cake, did the parent lie?
P IFF Q
(NOT P) UNLESS Q means the same as P IMPLIES Q
I won’t give you cake unless you have eaten your vegetables.
Let P denote “I will give you cake”.
Let Q denote “you have eaten your vegetables”.
Suppose the child eats their vegetables.
If the parent gives doesn’t give the child cake, did the parent lie?
P IFF Q
avoid using UNLESS, DESPITE, NOT WITHSTANDING
Problem 2
Consider a circuit with three Boolean inputs, x1, x0, and b and three Boolean outputs, c, y1, and y0, where the string cy1y0 represents the sum of b and the number represented by the string x1x0.
x1 x0 +b
c y1 y0
(a) Express each output as a combination of the inputs, using logical connectives.
Problem 2
Consider a circuit with three Boolean inputs, x1, x0, and b and three Boolean outputs, c, y1, and y0, where the string cy1y0 represents the sum of b and the number represented by the string x1x0.
x1 x0 +b
c y1 y0
(a) Express each output as a combination of the inputs, using
logical connectives.
Generalize your circuit to have n + 1 inputs, xn−1, . . . , x0, b and n+1 outputs, c, yn−1,...,y0.
Consider a circuit with three Boolean inputs, x1, x0, and b and three Boolean outputs, c, y1, and y0, where the string cy1y0 represents the sum of b and the number represented by the string x1x0.
(a) Express each output as a combination of the inputs, using logical connectives.
y0 = x0 XOR b
y1 =x1 XOR (x0 AND b)
c=x1 ANDx0 ANDb
This is called a 2-bit half-adder.
Consider a circuit with three Boolean inputs, x1, x0, and b and three Boolean outputs, c, y1, and y0, where the string cy1y0 represents the sum of b and the number represented by the string x1x0.
(a) Express each output as a combination of the inputs, using logical connectives.
y0 = x0 XOR b
y1 =x1 XOR (x0 AND b)
c=x1 ANDx0 ANDb
AND is associative:
(A AND B) AND C is logically equivalent to A AND (B AND C) so brackets are not needed, i.e. it is fine to write A AND B AND C.
AND is associative:
(A AND B) AND C is logically equivalent to A AND (B AND C).
Which among OR, XOR, IMPLIES, and IFF are associative?
AND is associative:
(A AND B) AND C is logically equivalent to A AND (B AND C).
Which among OR, XOR, IMPLIES, and IFF are associative?
F IMPLIES (F IMPLIES F) = T, but (F IMPLIES F) IMPLIES F = F. Therefore IMPLIES is not associative.
OR, XOR, and IFF are all associative.
(b) Generalize your circuit to have n + 1 inputs, xn−1, . . . , x0, b and n+1 outputs, c, yn−1,...,y0.
y0 = x0 XOR b
c1 = x0 AND b
yi =xi XORci,fori=1,...,n−1
ci+1=xi ANDci,fori=1,...,n−1
c = cn
The idea is that ci denotes the carry into column i from column
i − 1, where the columns are numbered from right to left, starting with 0.
This can be written more succinctly, as follows:
c0 = b
yi =xi XORci,fori=0,...,n−1
ci+1=xi ANDci,fori=0,...,n−1
c = cn
Problem 5
Which of the following statements are true and which are false? Explain.
a. ∀x∈N.∃y∈N.(2x−y=0)
b. ∃y∈N.∀x∈N.(2x−y=0)
c. ∀x ∈ N.(x < 10 IMPLIES ∀y ∈ N.(y < x IMPLIES y < 9))
a. ∀x∈N.∃y∈N.(2x−y=0)
a. ∀x∈N.∃y∈N.(2x−y=0)True Given x ∈ N, let y = 2x.
a. ∀x∈N.∃y∈N.(2x−y=0)True Given x ∈ N, let y = 2x.
b. ∃y∈N.∀x∈N.(2x−y=0)
a. ∀x∈N.∃y∈N.(2x−y=0)True Given x ∈ N, let y = 2x.
b. ∃y∈N.∀x∈N.(2x−y=0)False Given y ∈ N, let x = y + 1. Then 2x − y = 2(y + 1) − y = y + 2 > 0.
a. ∀x∈N.∃y∈N.(2x−y=0)True Given x ∈ N, let y = 2x.
b. ∃y∈N.∀x∈N.(2x−y=0)False Given y ∈ N, let x = y + 1. Then 2x − y = 2(y + 1) − y = y + 2 > 0.
c. ∀x ∈ N.(x < 10 IMPLIES ∀y ∈ N.(y < x IMPLIES y < 9))
a. ∀x∈N.∃y∈N.(2x−y=0)True Given x ∈ N, let y = 2x.
b. ∃y∈N.∀x∈N.(2x−y=0)False Given y ∈ N, let x = y + 1. Then 2x − y = 2(y + 1) − y = y + 2 > 0.
c. ∀x ∈ N.(x < 10 IMPLIES ∀y ∈ N.(y < x IMPLIES y < 9)) True
If x < 10 then x ≤ 9. Hence, if y < x, then y < 9.
Problem 6
Write a predicate floor : R × Z → {T,F} such that
for x ∈ R and y ∈ Z,
floor(x,y) = T if y is the largest integer less than or equal to x.
Problem 6
Write a predicate floor : R × Z → {T,F} such that
for x ∈ R and y ∈ Z,
floor(x,y) = T if y is the largest integer less than or equal to x.
In definitions, the English word ‘if’ often means ‘if and only if’.
Problem 6
Write a predicate floor : R × Z → {T,F} such that
for x ∈ R and y ∈ Z,
floor(x,y) =
T if y is the largest integer less than or equal to x.
F otherwise.
Problem 6
Write a predicate floor : R × Z → {T,F} such that
for x ∈ R and y ∈ Z,
floor(x,y) = T if y is the largest integer less than or equal to x.
Write a predicate round : R × Z → {T,F} such that for x ∈ R and y ∈ Z,
round(x,y) = T if y is the closest integer to x
Problem 6
Write a predicate floor : R × Z → {T,F} such that
for x ∈ R and y ∈ Z,
floor(x,y) = T if y is the largest integer less than or equal to x.
For x ∈ R and y ∈ Z, let
floor(x,y) = “(y ≤ x) AND ∀z ∈ Z.[(z ≤ x) IMPLIES (z ≤ y)]”
Problem 6
Write a predicate floor : R × Z → {T,F} such that
for x ∈ R and y ∈ Z,
floor(x,y) = T if y is the largest integer less than or equal to x.
For x ∈ R and y ∈ Z, let
floor(x,y) = “(y ≤ x) AND ∀z ∈ Z.[(z ≤ x) IMPLIES (z ≤ y)]”
For x ∈ R and y ∈ Z, let
floor (x , y ) = “(y ≤ x ) AND (x < y + 1)”
Write a predicate round : R × Z → {T,F} such that for x ∈ R and y ∈ Z,
round(x,y) = T if y is the closest integer to x.
For x ∈ R and y ∈ Z, let
round (x , y ) = “∀z ∈ Z.(|y − x | ≤ |z − x |)” or, alternatively, round (x , y ) = “|y − x | ≤ .5”
Note that both round(.5,1) = T and round(.5,0)= T.
Modify this predicate so that if x = y + .5 for some integer y , then round (x , y + 1) = T, but round (x , y ) = F.
Question from CSC240 Regular Tutorial 1 TA: Kayman Brusse
Question: Why are the solutions to part (c) equivalent? Why can you bring the introduction of z into the implication, and why does the quantifier change?
Answer: In tutorial, I said: because the variable z does not appear in the consequent w(y,x) of the impli- cation.
This was not a very helpful response, so here is a more complete answer. It suffices to see that the statements
∀z∈P.(t(x,y,z)IMPLIESw(y,x)) and ((∃z∈P.t(x,y,z))IMPLIESw(y,z))
are equivalent. There are laws which allow you to transform one statement into another, such that both statements are logically equivalent. These laws are covered in Video Lecture 4. In particular (see timestamp 10:30), the law that can be used here is the following: If D is a set, p(x) is a predicate and E is a formula such that the variable x does not occur in E then
∀x ∈ D.(p(x) IMPLIES E) is logically equivalent to (∃x ∈ D.p(x)) IMPLIES E
As an exercise, once you have watched Lecture 4 and understand what it means for two formulas to be logically equivalent, you should try to derive that this law from other transformations. That is, give a sequence of transformations that turn the formula on the left into the formula on the right. Doing this will help you understand why the quantifier needs to change when you bring the formula inside the implication.
This law is also discussed in the Course Notes for CSCB38/236/240 (see IIe on page 160). These notes use different notation, but they show how to derive this law from other transformations.
1
1.
2.
Solutions to
CSC240 Winter 2021 Homework Assignment 1
(a) Every integer in S occurs infinitely many times. (b) S=(S1,S2,...)whereSi =2foralli≥1.
(c) S=(S1,S2,...)whereSi =iforalli≥1.
Let P denote the set of all functions from D×D into D∪{}. Note that P can also be written as (D ∪ {})D×D.
For any two Sukodu puzzles P and A, let consistent : P × P → {T,F} denote the predicate such that consistent(P, A) is true when every nonempty grid location in P has the same value in A.
So,consistent(P,A)=∀i∈D.∀j∈D.(NOT(P[i,j]=) IMPLIES(P[i,j]=A[i,j])).
For any A ∈ P, let rowsOK : P → {T,F} denote the predicate such that rowsOK(A) is T if and only if every row of A contains each of the numbers in D.
Then rowsOK(A) = ∀i ∈ D.∀d ∈ D.∃j ∈ D.(A[i, j] = d).
Similarly, let columnsOK : P → {T,F} denote the predicate such that columnsOK(A) is T if and only if every column of A contains each of the numbers in D.
Then columnsOK(A) = ∀j ∈ D.∀d ∈ D.∃i ∈ D.(A[i, j] = d).
Finally, we let subgridsOK : P → {T,F} denote the predicate such that subgridsOK(A) is T if and only if each of the k2 disjoint subgrids of A contains each of the numbers in D.
To write this predicate, let M = {i ∈ Z | 1 ≤ i ≤ k} denote the rows and columns in the upper leftmost subgrid and let L = {u·k | (u ∈ N)AND(0 ≤ u ≤ k−1)} denote the possible row and column offsets for each of the other subgrids. Then, for each r,c ∈ L, {(r + i,c + j) | i,j ∈ M} is the set of the grid locations of the k × k subgrid whose topmost row is r + 1 and whose leftmost column is c + 1.
Hence subgridsOK(A) = ∀r ∈ L.∀c ∈ L.∀d ∈ D.∃i ∈ M.∃j ∈ M.A[r + i, c + j] = d. Combining all these, we get the predicate correct : P × P → {T,F}, where correct(P, A) =
consistent(P,A) AND rowsOK(A) AND columnsOK(A) AND subgridsOK(A).
1
Validity and Satisfiability
Validity
A propositional formula is an expression built up from Boolean variables using connectives such as
AND, OR, NOT, IMPLIES, IFF, XOR.
It does not contain predicates or quantifiers.
A propositional formula is valid or a tautology if all its truth table entries are true.
Examples:
P OR NOT(P)
NOT(P OR Q) IFF (NOT(P) AND NOT(Q))
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
Validity
A propositional formula is an expression built up from Boolean variables using connectives such as
AND, OR, NOT, IMPLIES, IFF, XOR.
It does not contain predicates or quantifiers.
A propositional formula is valid or a tautology if all its truth table entries are true.
Examples:
P OR NOT(P)
NOT(P OR Q) IFF (NOT(P) AND NOT(Q))
A IFF B, where A and B are logically equivalent
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
A propositional formula is unsatisfiable or a contradiction if all its truth table entries are false.
Examples:
P AND NOT(P)
NOT(A), where A is a tautology
A propositional formula is satisfiable if it is not unsatisfiable.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
A truth assignment is a function from
a set of propositional variables to {T, F}.
Example τ : {P,Q} → {T, F}.
Each row in a truth table corresponds to a different truth
assignment with the same domain.
An algorithm to determine if a propositional formula is satisfiable: Construct its truth table.
If a formula has n variables, there are 2n rows in its truth table.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
SAT
The satisfiability problem or SAT:
decide whether a given propositional formula is satisfiable.
Input: a propositional formula
Output: YES if the formula is satisfiable, NO if it is unsatisfiable.
P = all decision problems that can be solved in polynomial time.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
SAT
The satisfiability problem or SAT:
decide whether a given propositional formula is satisfiable.
Input: a propositional formula
Output: YES if the formula is satisfiable, NO if it is unsatisfiable.
P = all decision problems that can be solved in polynomial time. NP = all decision problems that can be verified in polynomial time.
SAT ∈ NP.
Example: (P OR NOT(Q)) AND (NOT(P) OR Q) is satisfiable, because τ((P OR NOT(Q)) AND (NOT(P) OR Q)) = T, where τ(P) = F and τ(Q) = F.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
SAT
The satisfiability problem or SAT:
decide whether a given propositional formula is satisfiable.
Input: a propositional formula
Output: YES if the formula is satisfiable, NO if it is unsatisfiable.
P = all decision problems that can be solved in polynomial time. NP = all decision problems that can be verified in polynomial time.
SAT ∈ NP.
Example: (P OR NOT(Q)) AND (NOT(P) OR Q) is satisfiable, because τ((P OR NOT(Q)) AND (NOT(P) OR Q)) = T, where τ(P) = F and τ(Q) = F.
THEOREM[Cook] SAT ∈ P if and only if P = NP.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
DNF
A literal is a variable or the negation of a variable.
It is easy to solve satisfiability for a formula that is the conjunction of literals.
Examples:
P AND NOT(Q) AND R is satisfiable.
P AND NOT(Q) AND R AND NOT(P) is unsatisfiable.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
DNF
A literal is a variable or the negation of a variable.
It is easy to solve satisfiability for a formula that is the conjunction of literals.
Examples:
P AND NOT(Q) AND R is satisfiable.
P AND NOT(Q) AND R AND NOT(P) is unsatisfiable.
Check that the formula does not contain a variable and its negation.
A propositional formula is in disjunctive normal form if it is a disjunction of conjunctions of literals.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
DNF: a disjunction of conjunctions of literals
THEOREM Every propositional formula is logically equivalent to a propositional formula in DNF.
PQR FFFF FFTF FTFF F T T T TFFF TFTF TTFF TTTF
NOT(P)ANDQANDR
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
DNF: a disjunction of conjunctions of literals
THEOREM Every propositional formula is logically equivalent to a propositional formula in DNF.
PQR FFFF FFTF FTFF F T T T TFFF T F T T TTFF T T T T
NOT(P)ANDQANDR PANDNOT(Q)ANDR PANDQANDR
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
DNF: a disjunction of conjunctions of literals
THEOREM Every propositional formula is logically equivalent to a propositional formula in DNF.
PQR FFFF FFTF FTFF F T T T TFFF T F T T TTFF T T T T
NOT(P)ANDQANDR PANDNOT(Q)ANDR PANDQANDR
(NOT(P) AND Q AND R) OR (P AND NOT(Q) AND R) OR (P AND Q AND R) is a DNF formula for the last column.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
DNF: a disjunction of conjunctions of literals
THEOREM Every propositional formula is logically equivalent to a propositional formula in DNF.
PQR FFFF FFTF FTFF F T T T TFFF T F T T TTFF T T T T
NOT(P)ANDQANDR PANDNOT(Q)ANDR PANDQANDR
(NOT(P) AND Q AND R) OR (P AND R) is another DNF formula for the last column.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF
A propositional formula is in conjunctive normal form if it is a conjunction of disjunctions of literals.
A clause is a disjunction of literals,
so a CNF formula is a conjunction of clauses.
THEOREM Every propositional formula is logically equivalent to a propositional formula in CNF.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF: a conjunction of disjunctions of literals
THEOREM Every propositional formula is logically equivalent to a propositional formula in CNF.
PQR FFFT FFTF FTFT FTTT TFFF TFTT TTFT TTTT
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF: a conjunction of disjunctions of literals
Construct the DNF for the complement,
PQR
FFFTF
F F T F T
FTFTF
FTTTF
TFFFT P AND NOT(Q) AND NOT(R) TFTTF
TTFTF
TTTTF
[NOT(P) AND NOT(Q) AND R] OR [P AND NOT(Q) AND NOT(R)]
NOT(P) AND NOT(Q) AND R
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF: a conjunction of disjunctions of literals
Construct the DNF for the complement, negate it,
NOT( [NOT(P) AND NOT(Q) AND R] OR [P AND NOT(Q) AND NOT(R)] )
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF: a conjunction of disjunctions of literals
Construct the DNF for the complement, negate it, apply DeMorgan’s laws,
NOT( [NOT(P) AND NOT(Q) AND R] OR [P AND NOT(Q) AND NOT(R)] )
= NOT(NOT(P) AND NOT(Q) AND R) AND NOT(P AND NOT(Q) AND NOT(R))
= [NOT(NOT(P)) OR NOT(NOT(Q)) OR NOT(R)] AND [NOT(P) OR NOT(NOT(Q)) OR NOT(NOT(R))]
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF: a conjunction of disjunctions of literals
Construct the DNF for the complement, negate it, apply DeMorgan’s laws, and simplify.
NOT( [NOT(P) AND NOT(Q) AND R] OR [P AND NOT(Q) AND NOT(R)] )
= NOT(NOT(P) AND NOT(Q) AND R) AND NOT(P AND NOT(Q) AND NOT(R))
= [NOT(NOT(P)) OR NOT(NOT(Q)) OR NOT(R)] AND [NOT(P) OR NOT(NOT(Q)) OR NOT(NOT(R))]
= [P OR Q OR NOT(R)] AND [NOT(P) OR Q OR R]
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
CNF-SAT: decide whether a given propositional formula in CNF is satisfiable.
Input: a propositional formula in CNF
Output: YES if the formula is satisfiable, NO if it is unsatisfiable.
CNF-SAT is just as hard as SAT.
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
Lecture 4
Validity and Satisfiability of Predicate Logic Formulas
Prenex Normal Form
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Predicate Logic Formulas
A predicate logic formula is an expression built up from predicate symbols, each of which has a fixed number of arguments, using connectives and universal and existential quantifiers.
The arguments of predicate symbols are variables and constants from specific domains.
∀x ∈ D.[P(x,y,0) IMPLIES ∃y ∈ D.(S(x,y) AND G(y))] where 0 ∈ D
G : D → {T, F}
S : D × D → {T, F}
P : D × D × D → {T, F}
A constant symbol denotes one particular element in a domain,
whereas a variable can be used to denote any element in a domain.
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
An occurrence of a variable x is quantified
if it occurs within a subformula of the form ∀x ∈ D.E or ∃x ∈ D.E; otherwise it is unquantified or free.
Constants are never quantified.
∀x ∈ D.[P(x,x,z) IMPLIES ∃y ∈ D.(S(x,y) AND G(y))]
all occurrences of x and y are quantified the occurrence of z is free
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
An occurrence of a variable x is quantified
if it occurs within a subformula of the form ∀x ∈ D.E or ∃x ∈ D.E; otherwise it is unquantified or free.
∀x ∈ D.[P(x,y,z) IMPLIES ∃y ∈ D.(S(x,y) AND G(y))] the first occurrence of y is free
Better:
∀x ∈ D.[P(x,y,z) IMPLIES ∃w ∈ D.(S(x,w) AND G(w))]
DON’T use the same symbol for a free variable and a quantified variable in the same formula.
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
An occurrence of a variable x is quantified
if it occurs within a subformula of the form ∀x ∈ D.E or ∃x ∈ D.E; otherwise it is unquantified or free.
∀y ∈ D.[P(x,y,z) IMPLIES ∃y ∈ D.(S(x,y) AND G(y))] occurrences of x and z are free
the occurrences of y are quantified
Better:
∀y ∈ D.[P(x,y,z) IMPLIES ∃w ∈ D.(S(x,w) AND G(w))]
DON’T use the same symbol for nested quantified variables.
CSC 240 Enriched Introduction to Theory of Computation
The truth of a predicate logic formula depends on: what the predicate symbols mean,
what the domains are, and
what the constant symbols refer to.
p : D → {T, F}
∀x ∈ D.p(x)
TRUE if D = {1,3,5} and p(x) = ‘x is odd’ FALSE if D = {1,2,3} and p(x) = ‘x is odd’ FALSE if D = {1,3,5} and p(x) = ‘x is even’
Validity and Satisfiability
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
The truth of a predicate logic formula depends on: what the predicate symbols mean,
what the domains are, and
what the constant symbols refer to.
f:D×D→D id ∈ D
(∀x ∈ D .f (x , id ) = x ) IMPLIES (∀x ∈ D .∃y ∈ D .f (x , y ) = id ) FA L S E i f D = Z , f ( x , y ) = ‘ x × y ’ , a n d i d = 1
TRUE if D = Z, f (x , y ) = ‘x + y ’, and id = 0
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Interpretation
An interpretation of a predicate logic formula with no free variables consists of:
◮ a nonempty set for each domain in the formula,
◮ a function from the relevant domain to the relevant range for each function symbol in the formula, and
◮ a domain element for each constant symbol.
In particular, each predicate symbol in the formula must have a function from the
relevant domain to {T, F}.
If D = φ, then
∀x ∈ D.p(x) is always vacuously true ∃x ∈ D.p(x) is always false.
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Interpretation
An interpretation of a predicate logic formula consists of:
◮ a nonempty set for each domain in the formula,
◮ a function from the relevant domain to the relevant range for each function symbol in the formula,
◮ a domain element for each constant symbol, and
◮ an element of the relevant domain for each free variable. A valuation maps each free variable to a domain element.
∀x ∈ D.∃y ∈ D.(q(x,y) AND r(x,y,z))
TRUE if D = N, q(x,y) = ‘x ≥ y’, r(x,y,z) = ‘x ·y = z’, z = 0
FA L S E i f D = N , q ( x , y ) = ‘ x ≥ y ’ , r ( x , y , z ) = ‘ x · y = z ’ , z = 1
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Validity and Satisfiability
A predicate logic formula is valid or a tautology if it true for all interpretations. A predicate logic formula is satisfiable if it is true for some interpretation.
A predicate logic formula is unsatisfiable if it is false for all interpretations.
(∀x ∈ D.a(x)) IMPLIES ∃x ∈ D.a(x) VALID
(∀x ∈ D.a(x)) IMPLIES a(c) VALID
(∀x ∈ D.a(x)) IMPLIES a(y) VALID
(∃x ∈ D.a(x)) IMPLIES ∀x ∈ D.a(x) SATISFIABLE, not VALID
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
employee gender salary Andy M 0
Donna Leslie Ron Tom
(∃x ∈ D.a(x)) IMPLIES ∀x ∈ D.a(x)
F 3000 F 5000 M 5700 M 1800
FALSE if D = E and a(x) = ‘employee x is female’.
TRUE if D = E and a(x) = ‘employee x made more than 6000’. TRUE if |D| = 1.
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
employee gender salary Andy M 0
Donna Leslie Ron Tom
F 3000 F 5000 M 5700 M 1800
∃y ∈ D.∀x ∈ D.q(x,y)
Consider interpretations in which D = E .
TRUE if q(x,y) = ‘employee x made no less than employee y’. FALSE if q(x,y) = ‘employees x and y have the same gender’.
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
employee gender salary Andy M 0
Donna Leslie Ron Tom
F 3000 F 5000 M 5700 M 1800
∀x ∈ D.∃y ∈ D.q(x,y)
CSC 240
Enriched Introduction to Theory of Computation
Validity and Satisfiability
employee gender salary Andy M 0
Donna Leslie Ron Tom
∀x ∈ D.∃y ∈ D.q(x,y)
Consider interpretations in which D = E .
F 3000 F 5000 M 5700 M 1800
TRUE if q(x,y) = ‘employee x made no less than employee y’. TRUE if q(x,y) = ‘employees x and y have the same gender’. FALSE if q(x,y) = ‘employee x made less than employee y’.
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Logical Implication and Equivalence
E logically implies E′ means that E′ is true in every interpretation that makes E true. E and E′ are logically equivalent if E logically implies E′ and E′ logically implies E.
∃x ∈ D.(p(x) OR q(x)) is logically equivalent to (∃x ∈ D.p(x)) OR (∃x ∈ D.q(x))
∃x ∈ D.(p(x) AND q(x)) logically implies that (∃x ∈ D.p(x)) AND (∃x ∈ D.q(x))
If x does not occur in E, then
∃x ∈ D.(E AND q(x)) is logically equivalent to E AND (∃x ∈ D.q(x)).
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Logical Implication and Equivalence
E logically implies E′ means that E′ is true in every interpretation that makes E true. E and E′ are logically equivalent if E logically implies E′ and E′ logically implies E.
∀x ∈ D.(p(x) AND q(x)) is logically equivalent to (∀x ∈ D.p(x)) AND (∀x ∈ D.q(x))
(∀x ∈ D.p(x)) OR (∀x ∈ D.q(x)) logically implies that ∀x ∈ D.(p(x) OR q(x))
If x does not occur in E, then
∀x ∈ D.(E OR q(x)) is logically equivalent to E OR (∀x ∈ D.q(x)).
CSC 240 Enriched Introduction to Theory of Computation
If x does not occur in E, then
∃x ∈ D.(E IMPLIES q(x)) is logically equivalent to
E IMPLIES ∃x ∈ D.q(x).
∀x ∈ D.(E IMPLIES q(x)) is logically equivalent to
E IMPLIES ∀x ∈ D.q(x).
∃x ∈ D.(p(x) IMPLIES E) is logically equivalent to
(∀x ∈ D.p(x)) IMPLIES E
∀x ∈ D.(p(x) IMPLIES E) is logically equivalent to (∃x ∈ D.p(x)) IMPLIES E.
Validity and Satisfiability
Logical Implication and Equivalence
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Prenex Normal Form
A predicate logic formula is in prenex normal form if and only if it is of the form Q1x1 ∈ D1.Q2x2 ∈ D2.···Qkxk ∈ Dk.E(x1,...,xk),
where E(x1,...,xk) is a formula without quantifiers and,
foralli=1,...,k,Qi iseither∀or∃
Any predicate logic formula can be converted to prenex normal form by applying a sequence of transformations:
NOT(∃x ∈ D.p(x)) can be transformed to ∀x ∈ D.NOT(p(x)) NOT ( ∀x ∈ D.p(x)) can be transformed to ∃x ∈ D.NOT(p(x))
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Prenex Normal Form
(∃x ∈ D.p(x)) OR (∃x ∈ D.q(x)) can be transformed to ∃x ∈ D.(p(x) OR q(x)) (∀x ∈ D.p(x)) AND (∀x ∈ D.q(x)) can be transformed to ∀x ∈ D.(p(x) AND q(x))
(∃x ∈ D.p(x)) AND (∃x ∈ D.q(x)) CANNOT be transformed to ∃x ∈ D.(p(x) AND q(x))
(∀x ∈ D.p(x)) OR (∀x ∈ D.q(x)) CANNOT be transformed to ∀x ∈ D.(p(x) OR q(x))
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Prenex Normal Form
If x does not occur in E, then
E AND ∃x ∈ D.q(x) can be transformed to ∃x ∈ D.(E AND q(x)) (∃x ∈ D.p(x)) AND E can be transformed to ∃x ∈ D.(p(x) AND E) E AND ∀x ∈ D.q(x) can be transformed to ∀x ∈ D.(E AND q(x)) (∀x ∈ D.p(x)) AND E can be transformed to ∀x ∈ D.(p(x) AND E)
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Prenex Normal Form
If x does not occur in E, then
E OR ∃x ∈ D.q(x) can be transformed to ∃x ∈ D.(E OR q(x)) (∃x ∈ D.p(x)) OR E can be transformed to ∃x ∈ D.(p(x) OR E) E OR ∀x ∈ D.q(x) can be transformed to ∀x ∈ D.(E OR q(x)) (∀x ∈ D.p(x)) OR E can be transformed to ∀x ∈ D.(p(x) OR E)
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
If x does not occur in E, then
E IMPLIES ∃x ∈ D.q(x) can be transformed to ∃x ∈ D.(E IMPLIES q(x)) (∃x ∈ D.p(x)) IMPLIES E can be transformed to ∀x ∈ D.(p(x) IMPLIES E)
E IMPLIES ∀x ∈ D.q(x) can be transformed to ∀x ∈ D.(E IMPLIES q(x)) (∀x ∈ D.p(x)) IMPLIES E can be transformed to ∃x ∈ D.(p(x) IMPLIES E)
CSC 240 Enriched Introduction to Theory of Computation
Validity and Satisfiability
Example:
(f(x,c) OR ∃y ∈A.g(y)) IMPLIES ∀z ∈B.h(z)
is transformed to
(∃y∈A.(f(x,c)ORg(y))) IMPLIES∀z∈B.h(z) is transformed to
∀y ∈A.[(f(x,c) OR g(y)) IMPLIES ∀z ∈B.h(z)] is transformed to
∀y ∈A.∀z ∈B.[(f(x,c) OR g(y)) IMPLIES h(z)]
Another logically equivalent formula in prenex normal form: ∀z ∈B.∀y ∈A.[NOT(f(x,c) OR g(y)) OR h(z)]
CSC 240 Enriched Introduction to Theory of Computation
Problem 1
Determine whether each of these propositional formulas is valid, satisfiable but not valid, or unsatisfiable:
1. (P IMPLIES Q) IMPLIES P 2. P IMPLIES (Q IMPLIES P)
Problem 1
Determine whether each of these propositional formulas is valid, satisfiable but not valid, or unsatisfiable:
1. (P IMPLIES Q) IMPLIES P
This formula is satisfiable, but not valid.
The truth assignment P = Q = T makes it true. The truth assignment P = Q = F makes it false.
2. P IMPLIES (Q IMPLIES P)
Problem 1
Determine whether each of these propositional formulas is valid, satisfiable but not valid, or unsatisfiable:
1. (P IMPLIES Q) IMPLIES P
2. P IMPLIES (Q IMPLIES P)
if P = F, then the formula is vacuously true.
if P = T, then Q IMPLIES P is true, so the formula is true. Therefore, this formula is valid.
Problem Session 2
Problem 2
Consider the truth table for the Boolean predicate M(P, Q, R), which is true when exactly two of P, Q, and R are true.
PQRM TTTF TTFT TFTT TFFF FTTT FTFF FFTF FFFF
1. Give a propositional formula in DNF for M(P, Q, R). 2. Give a propositional formula in CNF for M(P, Q, R).
Problem Session 2
M(P,Q,R) is true when exactly two of P, Q, and R are true.
PQRM TTTF T T F T T F T T TFFF FTTT FTFF FFTF FFFF
PANDQAND(NOTR) P AND(NOTQ)ANDR
(NOT P) AND Q AND R
1. Give a propositional formula in DNF for M(P, Q, R). (P AND Q AND (NOT R)) OR
(P AND (NOT Q) AND R) OR
((NOT P) AND Q AND R)
Problem Session 2
M(P,Q,R) is true when exactly two of P, Q, and R are true.
PQRM TTTF TTFT TFTT TFFF FTTT FTFF FFTF FFFF
2. Give a propositional formula in CNF for M(P, Q, R). (P ORQ)AND(P ORR)AND(Q ORR)
AND ((NOT P) OR (NOT Q) OR (NOT R)) At least two of P, Q, and R are true.
At least one of P, Q, and R is false.
Problem Session 2
M(P,Q,R) is true when exactly two of P, Q, and R are true.
PQRM T T T F TTFT TFTT TFFF FTTT FTF F F F T F F F F F
PANDQANDR
P AND (NOT Q) AND (NOT R)
(NOT P) AND Q AND (NOT R) (NOTP)AND(NOTQ)ANDR (NOTP)AND(NOTQ)AND(NOTR)
Another approach.
NOT((P ANDQ ANDR)OR(P AND(NOTQ)AND(NOTR))OR ((NOT P) AND Q AND (NOT R)) OR
((NOT P) AND (NOT Q) AND R) OR
((NOT P) AND (NOT Q) AND (NOT R)))
Problem Session 2
2. Give a propositional formula in CNF for M(P, Q, R).
NOT ((P AND Q AND R) OR
(P AND (NOT Q) AND (NOT R)) OR ((NOT P) AND Q AND (NOT R)) OR ((NOT P) AND (NOT Q) AND R) OR ((NOT P) AND (NOT Q) AND (NOT R)))
= ((NOT P) OR (NOT Q) OR (NOT R)) AND ((NOT P) OR Q OR R) AND
(P OR (NOT Q) OR R) AND
(P OR Q OR (NOT R)) AND
(P OR Q OR R)
Problem Session 2
You can see that this answer can be transformed into the first answer.
((NOT P) OR (NOT Q) OR (NOT R)) AND
((NOT P) OR Q OR R) AND
(P OR (NOT Q) OR R) AND (P OR Q OR (NOT R)) AND (P OR Q OR R)
= ((NOT P) OR (NOT Q) OR (NOT R)) AND ((NOTP)ORQ ORR)AND(P ORQ ORR)AND (P OR(NOTQ)ORR)AND(P ORQ ORR)AND (P ORQ OR(NOTR))AND(P ORQ ORR)
= ((NOT P) OR (NOT Q) OR (NOT R)) AND (Q OR R) AND
(P OR R) AND
(P OR Q)
Problem Session 2
Problem 3
Consider a Boolean circuit with four Boolean inputs, x0, x1, y0, y1 and three Boolean outputs z0,z1, and e,
where x1x0, y1y0, and z1z0 are the binary representations of the numbers x, y, and z, respectively.
If y ̸= 0, then e = 0 and z is the quotient of x divided by y.
If y = 0, then e = 1 and z1 = z0 = 0.
The bit e is an error indicator.
For each of the three bits, e, z1 and z0, write a propositional formula in DNF or CNF (with variables x0, x1, y0 and y1) which expresses the value of that bit.
Problem Session 2
Problem 3
e = NOT (y1) AND NOT (y0) x =x1x0 y =y1y0 z =z1z0
0 if y = 0 z= ⌊x/y⌋ ify̸=0
The most significant bit of the quotient, z1, is 1 if and only if
z ≥ 2.
Since x ≤ 3, the quotient of x divided by y is at most 1 if y ≥ 2. Thus z ≥ 2 if and only if y = 1 and x ≥ 2.
Hence z1 = y0 AND NOT (y1) AND x1.
These two formulas are in both DNF and CNF.
Problem Session 2
Problem 3
x =x1x0 y =y1y0 z =z1z0 0 if y = 0
z= ⌊x/y⌋ ify̸=0
If y = 1 (i.e. y1 = 0 and y0 = 1), then z0 = x0.
If x < y then z = 0, so z0 = 0.
Otherwise 2 ≤ y ≤ x ≤ 3. In this case, z = 1, so z0 = 1. Note that if 2 ≤ y ≤ 3, then y1 = 1 = x1.
andeitherx0 =1ory0 =0.
Otherwise 2 ≤ y ≤ x ≤ 3. In this case, z = 1, so z0 = 1. Notethaty1 =1=x1,so
itisnotthecasethatx0 =0andy0 =1. Hence,eitherx0 =1ory0 =0.
Thus z0 = (NOT (y1) AND y0 AND x0) OR
(y1 AND x1 AND [x0 OR NOT (y0)]). However, this formula is not in DNF or CNF.
Problem Session 2
Problem 3
z0 = (NOT (y1) AND y0 AND x0)
OR (y1 AND x1 AND [x0 OR NOT (y0)]).
By distributivity,
y1 AND x1 AND [x0 OR NOT (y0)]
= (y1 AND x1 AND x0) OR (y1 AND x1 AND NOT (y0)). Hence z0 = (NOT (y1) AND y0 AND x0) OR
(y1 AND x1 AND x0) OR (y1 AND x1 AND NOT (y0)), which is in DNF.
Problem Session 2
Problem 3
A more tedious way to solve this problem is to use a truth table:
x1 x0 y1 y0 z1 z0 TTTT T TTTF T TTFT T TTFF F TFTT F TFTF T
TFFT
T F F F FTTT F FTTF F FTFT T FTFF F FFTT F FFTF F FFFT F FFFF F
z1 =
F (x1 AND NOT (x0) AND NOT (y1) AND y0) F OR
(x1 AND x0 AND NOT (y1) AND y0)
F F T F F F T F F F F F F F F F
Problem Session 2
Problem 3
A more tedious way to solve this problem is to use a truth table:
x1 x0 y1 y0 z1 z0 TTTT T TTTF T TTFT T TTFF F TFTT F TFTF T TFFT F TFFF F FTTT F FTTF F FTFT T FTFF F FFTT F FFTF F FFFT F FFFF F
z0 =
(NOT (x1) AND x0 AND NOT (y1) AND y0)
OR
(x1 AND NOT (x0) AND y1 AND NOT (y0))
OR
(x1 AND x0 AND NOT (y1) AND y0)
OR
(x1 AND x0 AND y1 AND NOT (y0))
OR
(x1 AND x0 AND y1 AND y0)
F F T F F F T F F F F F F F F F
Problem 4
Determine the free occurrences of each variable in the predicate logic formula
[∀x ∈ D.∃y ∈ D.(R(x,y,z) IMPLIES ∃w ∈ D.Q(w,x,y))] IMPLIES ∀y ∈ D.Q(w,w,y)
Problem 4
Determine the free occurrences of each variable in the predicate logic formula
[∀x ∈ D.∃y ∈ D.(R(x,y,z) IMPLIES ∃w ∈ D.Q(w,x,y))] IMPLIES ∀y ∈ D.Q(w,w,y)
Problem Session 2
Problem 5
Translate the formula
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀y ∈ D.(S(x,y) IMPLIES B(y))) IMPLIES NOT (S(y,x))]
into an English sentence, using an interpretation where D is a nonempty set of people,
G(y) = “person y is a girl”
B(y) = “person y is a boy” and
S(x,y) = “person x is a sibling of person y”.
Problem Session 2
Problem 5
Translate the formula
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀y ∈ D.(S(x,y) IMPLIES B(y))) IMPLIES NOT (S(y,x))]
into an English sentence, using an interpretation where D is a nonempty set of people,
G(y) = “person y is a girl”
B(y) = “person y is a boy” and
S(x,y) = “person x is a sibling of person y”.
G(y) and S(y,x) are bound to the first ∀y ∈ D
S(x,y) and B(y) are bound to the second ∀y ∈ D
If a variable is in the scope of multiple quantifiers, it is bound to the innermost quantifier applied to that variable.
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
Problem Session 2
Problem 5
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
The literal translation:
Forallpeoplex andy inD,ify isagirlandeverysiblingofx isa boy, then y is not a sibling of x.
Other correct translations:
Every girl (x) is not the sibling of anyone (y) whose siblings are all boys.
Every girl is not the sister of anyone who only has brothers.
This follows from the following facts:
Ifagirlx isasiblingofy,thenx isthesisterofy. If a sibling z is a boy, then z is a brother.
Everyone who only has brothers has no sisters.
Problem Session 2
Problem 5
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
The translation:
If a person has only brothers, they have no sisters.
is not as good, because it does not make the universal quantification clear. The universal quantification is indicated by the word ”a” and might be misunderstood by some people.
A similar problem applies to the translation:
If there is a girl and a person whose siblings are all boys, they are not siblings.
Problem Session 2
Problem 5
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
An incorrect translation: Girls don’t have brothers in this set D. Here is why this is incorrect. Consider the set D = {b,g,g′}, where g and g′ are girls, b is a boy, and all three are siblings of one another.
Note that every person x ∈ D has a sibling who is not a boy, so ∀z ∈ D.(S(x,z) IMPLIES B(z)) is false. Therefore (G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x)) is true. Hence the formula is true.
However, the English sentence is false, because both g and g′ have b as their brother.
Problem Session 2
Problem 5
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
The same counterexample applies to the incorrect translation:
Every girl is not a sibling of anyone who has a brother.
Consider the set D = {b,g,g′}, where g and g′ are girls, b is a boy, and all three are siblings of one another.
The English sentence is false, because g is a sibling of g′ and b is a brother of g′.
Problem Session 2
Problem 5
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
More generally, if the sets B and G are disjoint, the formula is true. Consider any people x and y such that
G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z)) is true. Then y is a girlandifx isasiblingofy,theny isaboyand,hence,notagirl. So this means that x is not a sibling of y and therefore y is not a sibling of x. Hence NOT S(y,x) is true. I
Problem Session 2
Problem 5
∀x ∈ D.∀y ∈ D.[(G(y) AND ∀z ∈ D.(S(x,z) IMPLIES B(z))) IMPLIES NOT (S(y,x))]
Another incorrect translation: If everyone is a girl and everyone with a sibling is a boy then no one has a sibling.
Consider the set D = {a,b}, where a is both a girl and a boy, b is a boy, and a and b are siblings.
Since a ∈ D is a girl and all siblings of a are boys, G(a) AND ∀z ∈ D.(S(a,z) IMPLIES B(z)) is true.
But a and b are siblings, so S(a,b) is true. Thus the formula is false.
However, the English sentence is vacuously true. Because b is not a girl, everyone is a girl is false.
Problem 6
Consider the predicate logic formula
∀A ∈ S.∀B ∈ S.∀C ∈ S.∀D ∈ S.[(A × B ⊆ C × D) IMPLIES ((A ⊆ C) AND (B ⊆ D))].
1. Give an interpretation which makes this formula true, where × denotes the Cartesian product of sets and ⊆ denotes subset.
2. Give an interpretation which makes this formula false, where × denotes the Cartesian product of sets and ⊆ denotes subset.
Consider the predicate logic formula
∀A ∈ S.∀B ∈ S.∀C ∈ S.∀D ∈ S.[(A × B ⊆ C × D) IMPLIES ((A ⊆ C) AND (B ⊆ D))].
1. Give an interpretation which makes this formula true, where × denotes the Cartesian product of sets and ⊆ denotes subset.
Let S = {{s}} consist of one set,
which contains a single element s.
The only choices for A, B, C, and D are A = B = C = D = {s}. Since A × B = {(s, s)} = C × D,
both the hypothesis and the conclusion are true.
Hence the implication is true.
Therefore the formula is true under this interpretation.
Consider the predicate logic formula
∀A ∈ S.∀B ∈ S.∀C ∈ S.∀D ∈ S.[(A × B ⊆ C × D) IMPLIES ((A ⊆ C) AND (B ⊆ D))].
2. Give an interpretation which makes this formula false, where × denotes the Cartesian product of sets and ⊆ denotes subset.
LetS={φ, {r}, {s}}.
Let A = φ, B = {r}, and C = D = {s}.
Since A × B = φ ⊆ {(s, s)} = C × D, the hypothesis is true. But B ̸⊆ D, so the conclusion is false.
Hence the implication is false and the formula is false under this interpretation.
Problem 1
Consider the predicate logic formula
∃y ∈ S.[(∀x ∈ S.A(x)) IMPLIES B(y)] IFF ∃y ∈ S.[∀x ∈ S.(A(x) IMPLIES B(y))].
1. What is the smallest possible size for the domain S in an interpretation so that the formula is true?
2. What is the smallest possible size for the domain S in an interpretation so that the formula is false?
Justify your answers.
Consider the predicate logic formula
∃y ∈ S.[(∀x ∈ S.A(x)) IMPLIES B(y)] IFF ∃y ∈ S.[∀x ∈ S.(A(x) IMPLIES B(y))].
1. What is the smallest possible size for the domain S in an interpretation so that the formula is true?
In any interpretation, |S| ≥ 1.
Suppose that |S| = 1. Let c be the only element of S.
Then ∀x ∈ S.A(x) is logically equivalent to A(c), so
(∀x ∈ S.A(x)) IMPLIES B(y) is logically equivalent to
A(c) IMPLIES B(y).
Also, ∀x ∈ S.(A(x) IMPLIES B(y)) is logically equivalent to A(c) IMPLIES B(y).
Hence ∃y ∈ S.[(∀x ∈ S.A(x)) IMPLIES B(y)] is logically equivalent to ∃y ∈ S.[∀x ∈ S.(A(x) IMPLIES B(y))].
Thus, every interpretation with |S| = 1 makes the formula true.
Consider the predicate logic formula
∃y ∈ S.[(∀x ∈ S.A(x)) IMPLIES B(y)] IFF ∃y ∈ S.[∀x ∈ S.(A(x) IMPLIES B(y))].
2. What is the smallest possible size for the domain S in an interpretation so that the formula is false?
Consider the interpretation in which S = {0, 1}, A(0) = F , A(1) = T, and B(0) = B(1) = F.
Then ∀x ∈ S.A(x) is false, so for every y ∈ {0,1},
(∀x ∈ S.A(x)) IMPLIES B(y).
Thus ∃y ∈ S.[(∀x ∈ S.A(x)) IMPLIES B(y)] is true.
However, since A(1) = T and B(0) = F, A(1) IMPLIES B(0) is F and, hence ∀x ∈ S.(A(x) IMPLIES B(0)) is F.
Similarly, ∀x ∈ S.(A(x) IMPLIES B(1)) is F.
Thus y ∈ S.[∀x ∈ S.(A(x) IMPLIES B(y))] is F.
Hence, the formula is false under this interpretation and the smallest possible size for S is 2.
Problem 2
Translate the formula
[∃x ∈ N.(x = y)] IMPLIES ∃x ∈ N.[x = 0 OR NOT (∃y ∈ N.(y < 0))]
into a logically equivalent formula in Prenex Normal Form. Use brackets where necessary to avoid ambiguity.
Problem 2
Translate the formula
[∃x ∈ N.(x = y)] IMPLIES ∃x ∈ N.[x = 0 OR NOT (∃y ∈ N.(y < 0))]
into a logically equivalent formula in Prenex Normal Form.
Use brackets where necessary to avoid ambiguity.
Substitute z for the second quantified x and w for the quantified y.
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0)))
Problem 2
Translate the formula
[∃x ∈ N.(x = y)] IMPLIES ∃x ∈ N.[x = 0 OR NOT (∃y ∈ N.(y < 0))]
into a logically equivalent formula in Prenex Normal Form.
Use brackets where necessary to avoid ambiguity.
Substitute z for the second quantified x and w for the quantified y.
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0)))
Then apply a sequence of transformations to get Prenex Normal Form.
Apply a sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0))
Apply a sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0))
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
Apply a sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
∀x ∈ N.[(x = y) IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))]
Apply a sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) ∀x ∈ N.[(x = y) IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))]
∀x ∈ N.∃z ∈ N.[(x = y) IMPLIES ∀w ∈ N.(z = 0 OR NOT (w < 0))]
Apply a sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) ∀x ∈ N.[(x = y) IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))] ∀x ∈ N.∃z ∈ N.[(x = y) IMPLIES ∀w ∈ N.(z = 0 OR NOT (w < 0))] ∀x ∈ N.∃z ∈ N.∀w ∈ N.[(x = y) IMPLIES (z = 0 OR NOT (w < 0))]
Apply an alternative sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
NOT [∃x ∈ N.(x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
Apply an alternative sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) NOT [∃x ∈ N.(x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
[∀x ∈ N.NOT (x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
Apply an alternative sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) NOT [∃x ∈ N.(x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) [∀x ∈ N.NOT (x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0))
∃z ∈ N.([∀x ∈ N.NOT (x = y)] OR ∀w ∈ N.(z = 0 OR NOT (w < 0)))
Apply an alternative sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) NOT [∃x ∈ N.(x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) [∀x ∈ N.NOT (x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) ∃z ∈ N.([∀x ∈ N.NOT (x = y)] OR ∀w ∈ N.(z = 0 OR NOT (w < 0)))
∃z ∈ N.∀w ∈ N.([∀x ∈ N.NOT (x = y)] OR (z = 0 OR NOT (w < 0)))
Apply an alternative sequence of transformations
[∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR NOT (∃w ∈ N.(w < 0))) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.(z = 0 OR ∀w ∈ N.NOT (w < 0)) [∃x ∈ N.(x = y)] IMPLIES ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) NOT [∃x ∈ N.(x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) [∀x ∈ N.NOT (x = y)] OR ∃z ∈ N.∀w ∈ N.(z = 0 OR NOT (w < 0)) ∃z ∈ N.([∀x ∈ N.NOT (x = y)] OR ∀w ∈ N.(z = 0 OR NOT (w < 0))) ∃z ∈ N.∀w ∈ N.([∀x ∈ N.NOT (x = y)] OR (z = 0 OR NOT (w < 0))) ∃z ∈ N.∀w ∈ N.∀x ∈ N.[NOT (x = y) OR (z = 0 OR NOT (w < 0))]
Complete Set of Connectives
CSC 240
Tutorial 2
January 20, 2021
CSC 240
Complete Set of Connectives
True/False?
Recall from online lectures: “A propositional formula is an expression built up from Boolean variables using connectives such as
AND, OR, NOT, IMPLIES, and XOR. It does not contain predicates or quantifiers.”
CSC 240
Complete Set of Connectives
True/False?
Recall from online lectures: “A propositional formula is an expression built up from Boolean variables using connectives such as
AND, OR, NOT, IMPLIES, and XOR. It does not contain predicates or quantifiers.”
Claim: Every propositional formula can be written using only the connectives AND, OR, NOT (and variables).
CSC 240
Complete Set of Connectives
True/False?
Recall from online lectures: “A propositional formula is an expression built up from Boolean variables using connectives such as
AND, OR, NOT, IMPLIES, and XOR. It does not contain predicates or quantifiers.”
Claim: Every propositional formula can be written using only the connectives AND, OR, NOT (and variables).
True/False?
CSC 240
Complete Set of Connectives
Complete Set of Connectives
Claim: Every propositional formula can be written using only the connectives AND , OR , NOT (and variables, and the constants T and F).
CSC 240
Complete Set of Connectives
Complete Set of Connectives
Claim: Every propositional formula can be written using only the connectives AND , OR , NOT (and variables, and the constants T and F).
The claim is true! DNF (and CNF) does exactly that.
CSC 240
Complete Set of Connectives
Complete Set of Connectives
Claim: Every propositional formula can be written using only the connectives AND , OR , NOT (and variables, and the constants T and F).
The claim is true! DNF (and CNF) does exactly that. Such a set of connectives is called complete.
CSC 240
Complete Set of Connectives
Complete Set of Connectives
Claim: Every propositional formula can be written using only the connectives AND , OR , NOT (and variables, and the constants T and F).
The claim is true! DNF (and CNF) does exactly that.
Such a set of connectives is called complete.
Formally: A set of connectives is complete if every propositional formula is logically equivalent to a propositional formula that only uses connectives from this set.
CSC 240
Complete Set of Connectives
True/False?
Is {AND, NOT} a complete set of connectives?
CSC 240
Complete Set of Connectives
True/False?
Is {AND, NOT} a complete set of connectives?
Yes!, because {AND, OR, NOT} is a complete set of connectives, and
P OR Q ≡ NOT(NOT(P) AND NOT(Q)).
CSC 240
Complete Set of Connectives
True/False?
Is {AND, NOT} a complete set of connectives?
Yes!, because {AND, OR, NOT} is a complete set of connectives,
and
P OR Q ≡ NOT(NOT(P) AND NOT(Q)). Is {OR, NOT} a complete set of connectives?
CSC 240
Complete Set of Connectives
True/False?
Is {AND, NOT} a complete set of connectives?
Yes!, because {AND, OR, NOT} is a complete set of connectives,
and
P OR Q ≡ NOT(NOT(P) AND NOT(Q)).
Is {OR, NOT} a complete set of connectives? Of course; dual argument!
CSC 240
Complete Set of Connectives
Can we do better?
Is {NOT} a complete set of connectives?
CSC 240
Complete Set of Connectives
Can we do better?
Is {NOT} a complete set of connectives?
Can’t express formulas with more than one propositional variable: for example, x AND y.
CSC 240
Complete Set of Connectives
Can we do better?
Is {NOT} a complete set of connectives?
Can’t express formulas with more than one propositional variable:
for example, x AND y.
Is {AND} a complete set of connectives?
CSC 240
Complete Set of Connectives
Can we do better?
Is {NOT} a complete set of connectives?
Can’t express formulas with more than one propositional variable:
for example, x AND y.
Is {AND} a complete set of connectives? Can’t express NOT(x). Why?
CSC 240
Complete Set of Connectives
Can we do better?
Is {NOT} a complete set of connectives?
Can’t express formulas with more than one propositional variable:
for example, x AND y.
Is {AND} a complete set of connectives?
Can’t express NOT(x). Why?
Suppose P is a propositional formula involving only propositional variables and the connective AND. Consider the truth assignment making all propositional variable T . Then P = T , but
NOT(x) = F.
CSC 240
Complete Set of Connectives
AND , OR
So we’ve seen {NOT, AND} and {NOT, OR} are each a complete set of connectives; while {NOT}, {AND}, {OR} are not.
CSC 240
Complete Set of Connectives
AND , OR
So we’ve seen {NOT, AND} and {NOT, OR} are each a complete set of connectives; while {NOT}, {AND}, {OR} are not.
What about {AND, OR}?
CSC 240
Complete Set of Connectives
AND , OR
So we’ve seen {NOT, AND} and {NOT, OR} are each a complete set of connectives; while {NOT}, {AND}, {OR} are not.
What about {AND, OR}? NO!
CSC 240
Complete Set of Connectives
AND , OR
So we’ve seen {NOT, AND} and {NOT, OR} are each a complete set of connectives; while {NOT}, {AND}, {OR} are not.
What about {AND, OR}?
NO! NOT(x) cannot be expressed. Why?
CSC 240
Complete Set of Connectives
AND , OR
So we’ve seen {NOT, AND} and {NOT, OR} are each a complete set of connectives; while {NOT}, {AND}, {OR} are not.
What about {AND, OR}?
NO! NOT(x) cannot be expressed. Why?Suppose P is a propositional formula involving only the propositional variables and the connectives AND and OR . Consider the truth assignment making all propositional variable T . Then P = T , but
NOT(x) = F.
CSC 240
Complete Set of Connectives
Can we do better?
Is {NAND} a complete set of connectives? NAND is defined by the following truth table:
P Q PNANDQ TTF TFT FTT FFT
CSC 240
Complete Set of Connectives
Can we do better?
Is {NAND} a complete set of connectives? NAND is defined by the following truth table:
P Q PNANDQ TTF TFT FTT FFT
Yes! Because {NOT, AND } is a complete set of connectives and P NAND P = NOT(P)
(P NAND Q) NAND (P NAND Q) ≡ NOT(P NAND Q) ≡ P AND Q.
CSC 240
Complete Set of Connectives
Ternary Connective
We introduce a new ternary connective: IF-THEN-ELSE(x,y,z) = “IF x THEN y ELSE z”.
CSC 240
Complete Set of Connectives
Ternary Connective
We introduce a new ternary connective: IF-THEN-ELSE(x,y,z) = “IF x THEN y ELSE z”.
You should be able to both: build a truth table directly from this informal description; and translate this informal description to a well-formed logical formula using only our familiar binary connectives.
CSC 240
Complete Set of Connectives
Ternary Connective
We introduce a new ternary connective: IF-THEN-ELSE(x,y,z) = “IF x THEN y ELSE z”.
You should be able to both: build a truth table directly from this informal description; and translate this informal description to a well-formed logical formula using only our familiar binary connectives.
{IF-THEN-ELSE} is not a complete set of connectives. But {IF-THEN-ELSE, T, F} is. We regard T and F is 0-ary connectives; i.e., constants.
CSC 240
Complete Set of Connectives
IF-THEN-ELSE
NOT(x ) ≡ IF-THEN-ELSE(x , F , T )
CSC 240
Complete Set of Connectives
IF-THEN-ELSE
NOT(x ) ≡ IF-THEN-ELSE(x , F , T ) AND(x, y) ≡ IF-THEN-ELSE(x, y, x)
CSC 240
Complete Set of Connectives
IF-THEN-ELSE
NOT(x ) ≡ IF-THEN-ELSE(x , F , T ) AND(x, y) ≡ IF-THEN-ELSE(x, y, x) OR(x, y) ≡ IF-THEN-ELSE(x, x, y)
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete?
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete? ◦ Is {F, IMPLIES} complete?
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete? ◦ Is {F, IMPLIES} complete?
◦ Is {AND , IMPLIES} complete?
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete?
◦ Is {F, IMPLIES} complete?
◦ Is {AND , IMPLIES} complete?
◦ Let MINORITY be a ternary connective disagreeing with the majority of truth-values (you should formalize this with a truth table!). Is {MINORITY, F} complete?
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete?
◦ Is {F, IMPLIES} complete?
◦ Is {AND , IMPLIES} complete?
◦ Let MINORITY be a ternary connective disagreeing with the majority of truth-values (you should formalize this with a truth table!). Is {MINORITY, F} complete?
◦ Is {XOR} complete? (Hint: parity!)
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete?
◦ Is {F, IMPLIES} complete?
◦ Is {AND , IMPLIES} complete?
◦ Let MINORITY be a ternary connective disagreeing with the majority of truth-values (you should formalize this with a truth table!). Is {MINORITY, F} complete?
◦ Is {XOR} complete? (Hint: parity!)
◦ Is {MINORITY} complete?
CSC 240
Complete Set of Connectives
Challenges
In ascending order of difficulty:
◦ Is {NOT, IMPLIES} complete?
◦ Is {F, IMPLIES} complete?
◦ Is {AND , IMPLIES} complete?
◦ Let MINORITY be a ternary connective disagreeing with the majority of truth-values (you should formalize this with a truth table!). Is {MINORITY, F} complete?
◦ Is {XOR} complete? (Hint: parity!)
◦ Is {MINORITY} complete?
◦ Show that {AND, IFF, XOR} is a minimal complete set of connectives (i.e., it is complete and no proper subset of it is complete).
CSC 240
1. (a)
Solutions to
CSC240 Winter 2021 Homework Assignment 2
Consider the truth table of any propositional formula G ∈ A. There are 8 different rows in the truth table. Each row for which G = T contributes a conjunction of 3 literals, which are all different, to the DNF of G. Hence, the DNF for G using the method described in Online Lecture 3 contains at most 24 occurrences of the variables X, Y , and Z.
To reduce the number of occurrences of variables, group the rows into pairs that agree onthevaluesofXandY,butdisagreeonthevalueofZ. IfG=Fonboththese rows, then they contribute nothing to the DNF. If G = T on exactly one of these rows, then that row contributes a total of three occurrences of variables. If G = T on both these rows, then together, they can contribute a conjunction of 2 literals, instead of two conjunctions of 3 literals each. For example, consider the two rows in which X and Y are both T. Then
(X ANDY ANDZ)OR(X ANDY ANDNOTZ) is logically equivalent to
(X AND Y ) AND (Z OR NOT Z), by distributivity, which is logically equivalent to
(X AND Y ) AND T,
which is logically equivalent to
(X AND Y ).
Since there are 4 pairs of rows in the truth table and each pair of rows either contributes no conjunction or contributes a conjunction with at most 3 literals, there is a logically equivalent formula P ∈ A with sz(P) ≤ 12.
(b) Consider the propositional formula X XOR Y XOR Z. Using the method from Online Lecture 3, a logically equivalent propositional formula in disjunctive normal form is
Q = “(X AND Y AND Z) OR (X AND NOT(Y) AND NOT(Z)) OR (NOT(X) AND Y AND NOT(Z)) OR (NOT(X) AND NOT(Y ) AND Z)”.
Note that sz(Q) = 12. Q is true when an odd number of the variables X, Y , and Z are true. This means that any conjunction of literals in a logically equivalent DNF formula must contain all 3 different variables. Otherwise, set the variables that occur in the conjunction so that it is true. Changing the truth value of the missing variable does not change the value of the conjunction to false. But then the DNF formula is true in at least one case when an even number of the variables are true. This means it is not logically equivalent to X XOR Y XOR Z.
Since there are four different truth assignments in which an odd number of variables are true and each conjunction of three literals is true for only one truth assignment, there must be four conjunctions of three literals in any logically equivalent DNF formula P. Hence sz(P ) ≥ 12.
(c) If G ∈ A, then so is NOT G. By part (a), there is a propositional formula P ∈ A in disjunctive normal form that is logically equivalent to NOT G such that sz(P) ≤
12. Applying DeMorgan’s Laws to NOT P gives a propositional formula Q ∈ A in conjunctive normal form that is logically equivalent to G and such that sz(Q) = sz(P).
2. (a) LetD=N,
p(x) = “x ≥ 0”, and
q(x) = “NOT p(x)”.
Every natural number x is at least 0, so p(x) is true and q(x) is false. Hence p(x) IMPLIES q(x)
is false, so ∃x ∈ D.(p(x) IMPLIES q(x)) is false. Thus, NOT ∃x ∈ D.(p(x) IMPLIES q(x)) is true, i.e. R is true.
For every natural number x, NOT q(x) is true, so p(x) IMPLIES NOT q(x) is true. Thus ∃x ∈ D.(p(x) IMPLIES NOT q(x)) is true, i.e. S is true.
(b) This is impossible. Consider any interpretation in which S is false. Then, for every x ∈ D, p(x) IMPLIES NOT q(x) is false, so p(x) is true and NOT q(x) is false.
Since D is nonempty, there is some element d ∈ D. Then p(d) is true and NOT q(d) is false, so q(d) is true. Thus p(d) IMPLIES q(d) is true. This implies that ∃x ∈ D.(p(x) IMPLIES q(x)) is true. Hence NOT ∃x ∈ D.(p(x) IMPLIES q(x)) is false, i.e. R is false.
(c) LetD=N,
p(x) = “x is even”, and
q(x) = “x is divisible by 4”.
Consider x = 1. Since p(1) is false, p(1) IMPLIES q(1) is true. Hence, ∃x ∈ D.(p(x) IMPLIES q(x)) is true and NOT ∃x ∈ D.(p(x) IMPLIES q(x)) is false, i.e. R is false.
Consider x = 2. Since q(2) is false, NOT q(2) is true, so p(2) IMPLIES NOT q(2) is
true. Thus ∃x ∈ D.(p(x) IMPLIES q(x)) is true, i.e. S is true.
(d) LetD={T,F}, p(x) = “T”, and
q(x) = “T”.
Hence, for all x ∈ D, p(x) IMPLIES q(x) is true and p(x) IMPLIES NOT q(x) is false.
Thus, ∃x ∈ D.(p(x) IMPLIES q(x)) is true, which implies that NOT ∃x ∈ D.(p(x) IMPLIES q(x)) is false, i.e. R is false. Furthermore, ∃x ∈ D.(p(x) IMPLIES NOT q(x)) is false, i.e. S
is false.
Proofs
Lecture 5
A proposition is a statement that is either true or false. An axiom is a proposition that we agree is true.
A proof is a convincing argument that a proposition is true.
It consists of a sequence of axioms, previously proved propositions, and logical deductions.
A logical deduction uses an inference rule to prove a new proposition from axioms and previously proved propositions.
CSC 240 Enriched Introduction to Theory of Computation
Let R be a tautology that contains propositional variable P. If R′ is the formula obtained by replacing
every occurrence of P in R by the formula (Q),
then R′ is a tautology.
Example:
R = (A OR P) IMPLIES (P OR A)
Q = C AND D
R′ =(AOR(CANDD))IMPLIES((CANDD)ORA)
Proofs
Substitution
CSC 240 Enriched Introduction to Theory of Computation
Let R be a tautology that contains propositional variable P. If R′ is the formula obtained by replacing
every occurrence of P in R by the formula (Q),
then R′ is a tautology.
Example:
R = (A OR P) IMPLIES (P OR A)
Q = C AND D
(A OR (C AND D)) IMPLIES (P OR A) is not a tautology
Proofs
Substitution
CSC 240 Enriched Introduction to Theory of Computation
Let R be a tautology that contains propositional variable P. If R′ is the formula obtained by replacing
every occurrence of P in R by the formula (Q),
then R′ is a tautology.
Example:
R = (A OR P) IMPLIES (P OR A)
Q = ∀e ∈ E.a(e)
R′ = (A OR (∀e ∈ E.a(e))) IMPLIES ((∀e ∈ E.a(e)) OR A)
Proofs
Substitution
CSC 240 Enriched Introduction to Theory of Computation
Substitution
Let S′ be a formula that is logically equivalent to S. If S is a subformula of R and
R′ is a formula obtained by replacing
some occurrences of S in R by S′,
then R′ is logically equivalent to R.
Example:
S = NOT(A) AND NOT(B)
S′ = NOT(A OR B)
R=
(NOT(A) AND NOT(B)) XOR (B IFF (NOT(A) AND NOT(B))
Proofs
CSC 240 Enriched Introduction to Theory of Computation
Substitution
Let S′ be a formula that is logically equivalent to S. If S is a subformula of R and
R′ is a formula obtained by replacing
some occurrences of S in R by S′,
then R′ is logically equivalent to R.
Example:
S = NOT(A) AND NOT(B)
S′ = NOT(A OR B)
R=
(NOT(A) AND NOT(B)) XOR (B IFF (NOT(A) AND NOT(B)) is logically equivalent to
R′ = NOT(A OR B) XOR (B IFF (NOT(A) AND NOT(B))
Proofs
CSC 240 Enriched Introduction to Theory of Computation
Substitution
Let S′ be a formula that is logically equivalent to S. If S is a subformula of R and
R′ is a formula obtained by replacing
some occurrences of S in R by S′,
then R′ is logically equivalent to R.
Example:
S = NOT(A) AND NOT(B)
S′ = NOT(A OR B)
R=
(NOT(A) AND NOT(B)) XOR (B IFF (NOT(A) AND NOT(B)) is logically equivalent to
R′ = (NOT(A) AND NOT(B)) XOR (B IFF (NOT(A OR B)))
Proofs
CSC 240 Enriched Introduction to Theory of Computation
Substitution
Let S′ be a formula that is logically equivalent to S. If S is a subformula of R and
R′ is a formula obtained by replacing
some occurrences of S in R by S′,
then R′ is logically equivalent to R.
Example:
S = NOT(A) AND NOT(B)
S′ = NOT(A OR B)
R=
(NOT(A) AND NOT(B)) XOR (B IFF (NOT(A) AND NOT(B)) is logically equivalent to
R′ = (NOT(A OR B)) XOR (B IFF (NOT(A OR B))
Proofs
CSC 240 Enriched Introduction to Theory of Computation
Proofs
Modus Ponens
If P and P IMPLIES Q are axioms or previously proved propositions, then Q is true.
Example:
1. ∀e ∈ E.l(e) axiom
2. (∀e ∈ E.l(e)) IMPLIES ∃e ∈ E.l(e) tautology 3. ∃e ∈ E.l(e) modus ponens 1,2
CSC 240 Enriched Introduction to Theory of Computation
Proofs
Modus Ponens
If P and P IMPLIES Q are axioms or previously proved propositions, then Q is true.
Example:
1. ∀e ∈ E.l(e) axiom
2. (∀e ∈ E.l(e)) IMPLIES ∃e ∈ E.l(e) tautology 3. ∃e ∈ E.l(e) modus ponens 1,2
CSC 240 Enriched Introduction to Theory of Computation
Proofs
Modus Ponens
If P and P IMPLIES Q are axioms or previously proved propositions, then Q is true.
Example:
1. ∀e ∈ E.l(e) axiom
2. (∀e ∈ E.l(e)) IMPLIES ∃e ∈ E.l(e) tautology 3. ∃e ∈ E.l(e) modus ponens 1,2
CSC 240 Enriched Introduction to Theory of Computation
Proofs
Modus Ponens
If P and P IMPLIES Q are axioms or previously proved propositions, then Q is true.
Example:
1. ∀e ∈ E.l(e) axiom
2. (∀e ∈ E.l(e)) IMPLIES ∃e ∈ E.l(e) tautology 3. ∃e ∈ E.l(e) modus ponens 1,2
CSC 240 Enriched Introduction to Theory of Computation
Proofs
Modus Ponens
If P and P IMPLIES Q are axioms or previously proved propositions, then Q is true.
Example:
1. ∀e ∈ E.l(e) axiom
2. (∀e ∈ E.l(e)) IMPLIES ∃e ∈ E.l(e) tautology 3. ∃e ∈ E.l(e) modus ponens 1,2
Formal Proof:
◮ Number each line.
◮ Write one proposition per line. ◮ Justify each line.
CSC 240
Enriched Introduction to Theory of Computation
If P and P IMPLIES Q are true propositions, then Q is a true proposition.
Not an example:
If he is a criminal, he has something to hide. He has something to hide.
Therefore he is a criminal.
From the axioms P IMPLIES Q and Q, you can’t conclude P.
Proofs
Modus Ponens
CSC 240 Enriched Introduction to Theory of Computation
If c ∈ D and
∀x ∈ D.a(x) is true, then a(c) is true.
Proofs
Specialization
CSC 240
Enriched Introduction to Theory of Computation
If c ∈ D and
∀x ∈ D.a(x) is true, then a(c) is true.
If c ∈ D, then (∀x ∈ D.a(x)) IMPLIES a(c) is a tautology. If ∀x ∈ D.a(x) is an axiom,
then a(c) follows by modus ponens.
Proofs
Specialization
CSC 240 Enriched Introduction to Theory of Computation
Proofs
Transitivity
If P IMPLIES Q and Q IMPLIES R are axioms or previously proved propositions, then P IMPLIES R is true.
Example:
If you study hard, you’ll learn the material.
If you learn the material, you’ll pass the course. Therefore, if you study hard, you’ll pass the course.
CSC 240 Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom 3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom 3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom
3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom 3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom 3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom 3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
Direct Proof of Implication
Assume P .
Q
Therefore P IMPLIES Q.
Example: Proof of Transitivity
1. Assume P
2. P IMPLIES Q axiom 3. Q modus ponens 1,2 4. Q IMPLIES R axiom 5. R modus ponens 3,4
6. Therefore P IMPLIES R direct proof 1,5
Proofs
CSC 240
Enriched Introduction to Theory of Computation
✓✏
P ✓✏
✒✑
Q
Proofs
✒✑
CSC 240 Enriched Introduction to Theory of Computation
✓✏
R
P ✓✏
✚✚❃✚✒✑ ✓✏
✚
✒✑
❩
Q
❩❩7❩✓✏
✒✑
S
✒✑
Proofs
CSC 240
Enriched Introduction to Theory of Computation
✚
✚ ❍❍✓✏ ❥❍
✯✟ ✒ ✑ ✓✏✟✟
✟ ❃✚✒❍✑
R
✓✏ U
✚ ✒✑
✓✏
T
P ✓✏
✒✑
❩
Q
❩❩7❩✓✏
✒✑
S
✒✑
Proofs
CSC 240
Enriched Introduction to Theory of Computation
✚
✚ ❍❍✓✏✓✏ ❥❍
✯✟ ✒ ✑ ✓✏✟✟
✟ ❃✚✒❍✑
R
✓✏ U W
✚
✒✑ ✒❍✑
✓✏
T
P ❍❍ ✓✏
✒✑ ❥❍
❩
❩ ✓ ✏ ✓ ✏✟ ✟
Q
❩
✯✟ ✒ ✑
7❩ ✟ SX
✒✑ ✒✑
Proofs
CSC 240 Enriched Introduction to Theory of Computation
✚
✒✑ ✒❍✑
✯✟ ✒ ✑ ✓✏✟✟
R
✟
✓✏
T
❃✚✒❍✑
✚ ❍❍✓✏✓✏
✚ ❥❍ ✲ ✓✏ U W
P ❍❍ ✓✏
✒✑ ❥❍
❩
Q
❩
✯✟ ✒ ✑ ❩ ✓ ✏ ✓ ✏ ✓ ✏✟ ✟
7❩S V✲X✟ ✒✑ ✒✑ ✒✑
Proofs
CSC 240 Enriched Introduction to Theory of Computation
P IMPLIES Q is logically equivalent to NOT(Q) IMPLIES NOT(P), so proving NOT(Q) IMPLIES NOT(P) proves P IMPLIES Q.
Assume NOT(Q) .
NOT(P)
Hence NOT(Q) IMPLIES NOT(P).
Therefore P IMPLIES Q.
Proofs
Indirect Proof of Implication
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: If x is even, then x2 is even.
Proof:
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Proofs
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: If x is even, then x2 is even.
Proof:
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Proofs
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: If x is even, then x2 is even.
Proof:
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Proofs
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: If x is even, then x2 is even.
Proof:
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Proofs
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: If x is even, then x2 is even.
Proof:
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x2 is even.
Then x2 = 2k for some integer k. ?
Proofs
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
LEMMA: If x2 is even, then x is even.
Proof:
Suppose x is not even.
Then x is odd,
so x = 2k + 1 for some integer k.
Hence x2 = (2k +1)2 = 4k2 +4k +1 = 2(2k2 +2k)+1, which is odd.
Therefore x2 is not even.
Proofs
CSC 240 Enriched Introduction to Theory of Computation
.
P
Therefore P OR Q.
Proofs
Proof of a Disjunction
CSC 240
Enriched Introduction to Theory of Computation
.
P.
Q
Therefore P AND Q.
Proofs
Proof of a Conjunction
CSC 240
Enriched Introduction to Theory of Computation
P AND Q
P
Proofs
Use of Conjunction
CSC 240 Enriched Introduction to Theory of Computation
P AND Q
(P AND Q) IMPLIES P tautology
P
Proofs
Use of Conjunction
CSC 240
Enriched Introduction to Theory of Computation
Proof by Contradiction
Q AND NOT(Q) is a contradiction,
so NOT(Q AND NOT(Q)) is a tautology.
Assume NOT(P) .
Q .
NOT(Q)
Q AND NOT(Q) proof of conjunction
NOT(Q AND NOT(Q)) IMPLIES P indirect proof NOT(Q AND NOT(Q)) tautology
Therefore P modus ponens
Proofs
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
THEOREM: √2 is irrational.
Proof: √
To obtain a contradiction,assume
Then there exist relatively prime positive integers x and y, such that √2 = x/y.
Since x2 = (√2y)2 = 2y2, x2 is even.
From the lemma, x is even.
Thus, there exists k ∈ Z+ such that x = 2k,
so2y2 =x2 =(2k)2 =4k2 andy2 =2k2.
Therefore y2 is even.
From the lemma, y is even.
Since 2 divides both x and y, they are not relatively prime. This is a contradiction. Hence √2 is irrational.
Proofs
2 is rational.
CSC 240 Enriched Introduction to Theory of Computation
Proof of Equivalences
P IFF Q is logically equivalent to
(P IMPLIES Q) AND (Q IMPLIES P)
Prove P IMPLIES Q and Q IMPLIES P separately.
To prove P IFF Q, Q IFF R, and P IFF R
it suffices to prove
P IMPLIES Q, Q IMPLIES R, and R IMPLIES P.
Proving P IMPLIES Q, Q IMPLIES R, and P IMPLIES R is not sufficent.
CSC 240
Enriched Introduction to Theory of Computation
Proof by Cases
.
P1 IMPLIES Q .
Pn IMPLIES Q
Therefore (P1 OR ··· OR Pn) IMPLIES Q
ThecasesP1,...,Pn canoverlap.
CSC 240
Enriched Introduction to Theory of Computation
Proof by Cases
P1 OR··· ORPn .
P1 IMPLIES Q .
Pn IMPLIES Q
Therefore (P1 OR ··· OR Pn) IMPLIES Q Hence Q.
CSC 240
Enriched Introduction to Theory of Computation
Proof by Cases
P IMPLIES (P1 OR ··· OR Pn) .
P1 IMPLIES Q .
Pn IMPLIES Q
Therefore (P1 OR ··· OR Pn) IMPLIES Q Hence P IMPLIES Q.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5 7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5 7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5 7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5
7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5
7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5 7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5
7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5
7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5 7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: P IMPLIES ((P AND C) OR (P AND NOT(C)))
1. Assume P
2. C OR NOT C tautology
3. Assume C
4. P AND C proof of conjunction 1,3
5. (P AND C) OR (P AND NOT(C)) proof of disjunction 4
6. C IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 3,5 7. Assume NOT(C)
8. P AND NOT(C) proof of conjunction 1,7
9. (P AND C) OR (P AND NOT(C)) proof of disjunction 8
10. NOT(C) IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 7,9
11. (P AND C) OR (P AND NOT(C)) proof by cases 2,6,10
12. P IMPLIES ((P AND C) OR (P AND NOT(C))) direct proof 1,11
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: ((P AND C) OR (P AND NOT(C))) IMPLIES P
1. Assume P AND C
2. P use of conjunction 1
3. (P AND C) IMPLIES P direct proof 1,2
4. Assume P AND NOT(C)
5. P use of conjunction 5
6. (P AND NOT(C)) IMPLIES P direct proof 4,5
7. ((P AND C) OR (P AND NOT(C))) IMPLIES P proof by cases 3,6
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: ⌊(n + 1)/2⌋ = ⌈n/2⌉.
Proof:
Suppose n is even. Then n = 2k for some integer k, so ⌊(n + 1)/2⌋ = ⌊(2k + 1)/2⌋ = ⌊k + 1/2⌋ = k
= ⌈k⌉ = ⌈2k/2⌉ = ⌈n/2⌉.
Then n is even IMPLIES ⌊(n + 1)/2⌋ = ⌈n/2⌉.
Supposenisodd. Thenn=2k+1forsomeintegerk,so ⌊(n + 1)/2⌋ = ⌊(2k + 2)/2⌋ = ⌊k + 1⌋ = k + 1
= ⌈k +1/2⌉ = ⌈(2k +1)/2⌉ = ⌈n/2⌉.
Then n is odd IMPLIES ⌊(n + 1)/2⌋ = ⌈n/2⌉.
Since n is even or n is odd, it follows that ⌊(n + 1)/2⌋ = ⌈n/2⌉.
CSC 240
Enriched Introduction to Theory of Computation
Generalization
Let x ∈ D .
p(x)
Since x is an arbitrary element of D, ∀x ∈ D.p(x)
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all integers x, if x is even, then x2 is even.
Proof:
Let x be an integer.
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Hence, x is even implies that x2 is even. Since x is an arbitrary integer,
for all integers x, if x is even, then x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all integers x, if x is even, then x2 is even.
Proof:
Let x be an integer. Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even. Hence, x is even implies that x2 is even.
Since x is an arbitrary integer,
for all integers x, if x is even, then x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all integers x, if x is even, then x2 is even.
Proof:
Let x be an integer.
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Hence, x is even implies that x2 is even. Since x is an arbitrary integer,
for all integers x, if x is even, then x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all integers x, if x is even, then x2 is even.
Proof:
Let x be an integer.
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Hence, x is even implies that x2 is even. Since x is an arbitrary integer,
for all integers x, if x is even, then x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all integers x, if x is even, then x2 is even.
Proof:
Let x be an integer.
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Hence, x is even implies that x2 is even. Since x is an arbitrary integer,
for all integers x, if x is even, then x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all integers x, if x is even, then x2 is even.
Proof:
Let x be an integer.
Assume x is even.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Hence, x is even implies that x2 is even. Since x is an arbitrary integer,
for all integers x, if x is even, then x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
LEMMA: For all even integers x, x2 is even.
Proof:
Let x be an even integer.
Then x = 2k for some integer k,
so x2 = (2k)2 = 2 × (2k2), which is even.
Since x is an arbitrary integer,
for all even integers x, x2 is even.
CSC 240
Enriched Introduction to Theory of Computation
Construction
Let x = .
Therefore x ∈ D. .
p(x)
∃x ∈ D.p(x)
CSC 240
Enriched Introduction to Theory of Computation
Instantiation
∃x ∈ D.p(x)
Let y ∈ D be such that p(y). .
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
For any integer y, let largest(y) = NOT(∃x ∈ Z.(x > y)) THEOREM: NOT(∃y ∈ Z.largest(y))
Proof:
1. Assume ∃y ∈ Z.largest(y).
2. Let y be an integer that satisfies largest(y). instantiation 1 3. NOT(∃x ∈ Z.(x > y)) definition 2
4. Let x = y + 1.
5. ∀z ∈ Z.(z + 1 is an integer) axiom.
6. x = y + 1 is an integer. specialization 5 7. ∀z ∈ Z.(z + 1 > z) axiom.
8. x = y + 1 > y specialization 7
9. ∃x ∈ Z.(x > y) construction 6,8
10. NOT(∃y ∈ Z.largest(y)) proof by contradiction 1,3,9
CSC 240
Enriched Introduction to Theory of Computation
Additional Reading
Proof Outlines
Mathematics for Computer Science, Section 1.9 Writing Mathematics
How to Write a 21st Century Proof
Generalized Logic
Proof techniques you shouldn’t use
CSC 240
Enriched Introduction to Theory of Computation
Problem Session 3
Problem 1
(a) Why is the following proof of 1/8 > 1/4 bogus?
3>2
3 log10(1/2) > 2 log10(1/2) log10(1/2)3 > log10(1/2)2 1/8 = (1/2)3 > (1/2)2 = 1/4
(b) Why is the following proof bogus? It claims to prove that if a and b are equal real numbers, then a = 0.
a=b
a2 = ab a2−b2 = ab−b2
(a−b)(a+b) = (a−b)b a+b=b
a=0
Problem Session 3
Problem 1
(a) Why is the following proof of 1/8 > 1/4 bogus?
3>2
3 log10(1/2) > 2 log10(1/2) log10(1/2)3 > log10(1/2)2 1/8 = (1/2)3 > (1/2)2 = 1/4
log10 x < 0 for 0 < x < 1.
Since the second line is obtained from the first by multiplying both sides by a negative number, the inequality needs to be reversed.
Problem Session 3
Problem 1
(b) Why is the following proof bogus? It claims to prove that if a and b are equal real numbers, then a = 0.
a=b
a2 = ab a2−b2 = ab−b2
(a−b)(a+b) = (a−b)b a+b=b
a=0
Since a − b = 0, you can’t divide both sides of the equation on line 4 to get the equation on line 5.
Problem Session 3
Problem 2
Formally prove
((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B
Problem Session 3
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption
9. B
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B
direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
5. NOT(A)
8. A
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
5. NOT(A)
8. A
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
4. NOT(B) IMPLIES NOT(A) contrapositive 3
5. NOT(A)
8. A
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
4. NOT(B) IMPLIES NOT(A) contrapositive 3
5. NOT(A) modus ponens 2,4
8. A
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
4. NOT(B) IMPLIES NOT(A) contrapositive 3
5. NOT(A) modus ponens 2,4
6. NOT(A) IMPLIES B use of conjunction 1
8. A
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
4. NOT(B) IMPLIES NOT(A) contrapositive 3
5. NOT(A) modus ponens 2,4
6. NOT(A) IMPLIES B use of conjunction 1 7. NOT(B) IMPLIES A contrapositive 6
8. A
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B
direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
4. NOT(B) IMPLIES NOT(A) contrapositive 3
5. NOT(A) modus ponens 2,4
6. NOT(A) IMPLIES B use of conjunction 1 7. NOT(B) IMPLIES A contrapositive 6
8. A modus ponens 2,7
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B
direct proof 1,9
Problem Session 3
1. (A IMPLIES B) AND (NOT(A) IMPLIES B) assumption 2. Assume NOT(B)
3. A IMPLIES B use of conjunction 1
4. NOT(B) IMPLIES NOT(A) contrapositive 3
5. NOT(A) modus ponens 2,4
6. NOT(A) IMPLIES B use of conjunction 1 7. NOT(B) IMPLIES A contrapositive 6
8. A modus ponens 2,7
9. B proof by contradiction 2,5,8
10. ((A IMPLIES B) AND (NOT(A) IMPLIES B)) IMPLIES B
direct proof 1,9
Note that we indent at lines 1 and 2, when we make assumptions.
Problem Session 3
Problem 3
Suppose that:
R is logically equivalent to S,
R′ is obtained from R by making a substitution,
S′ is obtained from S by making the same substitution, and R′ is true.
Prove S′ is true or give a counterexample.
Problem Session 3
Let
R = (P IMPLIES Q) IMPLIES P,
S = P AND P,
R′ = (P IMPLIES Q) IMPLIES U, and S′ = P AND U.
R is logically equivalent to S (check their truth tables), R′ is obtained from R by substituting U for the second P S′ is obtained from S by substituting U for the second P and,whenP=TandQ=U=F,R′ =TbutS′ =F.
Problem Session 3
Let
R = (P IMPLIES Q) IMPLIES P,
S = P AND P,
R′ = (P IMPLIES Q) IMPLIES U, and S′ = P AND U.
R is logically equivalent to S (check their truth tables), R′ is obtained from R by substituting U for the second P S′ is obtained from S by substituting U for the second P and,whenP=TandQ=U=F,R′ =TbutS′ =F.
Not all occurrences of P in R are replaced by U.
Problem Session 3
Let
R = (P OR Q) IMPLIES (P AND Q), S = P IFF ( Q OR (P AND Q)),
R′ = (P OR Q) IMPLIES U, and
S′ =PIFF(QORU).
R is logically equivalent to S (check their truth tables), R′ is obtained from R by substituting U for (P AND Q) S′ is obtained from S by substituting U for (P AND Q) and,whenP=Q=FandU=T,R′ =TbutS′ =F.
Problem Session 3
Let
R = (P OR Q) IMPLIES (P AND Q), S = P IFF ( Q OR (P AND Q)),
R′ = (P OR Q) IMPLIES U, and
S′ =PIFF(QORU).
R is logically equivalent to S (check their truth tables), R′ is obtained from R by substituting U for (P AND Q) S′ is obtained from S by substituting U for (P AND Q) and,whenP=Q=FandU=T,R′ =TbutS′ =F.
Substituting for a formula, rather than a variable.
Problem Session 3
Suppose that:
R is logically equivalent to S,
R′ is obtained from R by making a substitution,
S′ is obtained from S by making the same substitution, and R′ is true.
Prove S′ is true under more precise conditions.
Problem Session 3
Suppose that:
R is logically equivalent to S,
R′ is obtained from R by substituting all occurrences of some propositional variable P by a formula Q,
S′ is obtained from S by making the same substitution,
and R′ is true.
Then S is true.
Proof:
1. R′ assumption
2. R IFF S assumption
3. R IMPLIES S use of equivalence 2
4. R′ IMPLIES S′ substitution 3 (see lecture 5 slide 2) 5. S′ modus ponens 1,4
Problem Session 3
Problem 4
Give a formal proof of:
[∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]. Use a top down approach.
Problem Session 3
26 [∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
Problem Session 3
1 Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
25 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
26 [∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))] direct proof 1,25
Problem Session 3
1 Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y)) 3 (∃x ∈ D.R(x)) OR NOT(∃x ∈ D.R(x))
14 [∃x ∈ D.R(x)] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
24 [NOT(∃x ∈ D.R(x))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
25 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) proof by cases 3, 14, 24
26 [∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))] direct proof 1,25
Problem Session 3
1 Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
2 P OR NOT(P) tautology
3 (∃x ∈ D.R(x)) OR NOT(∃x ∈ D.R(x)) substitution 2
14 [∃x ∈ D.R(x)] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
24 [NOT(∃x ∈ D.R(x))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
25 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) proof by cases 3, 14, 24
26 [∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))] direct proof 1,25
Problem Session 3
1 Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
2 P OR NOT(P ) tautology
3 (∃x ∈ D.R(x)) OR NOT(∃x ∈ D.R(x)) substitution 2
4 Suppose ∃x ∈ D.R(x)
13 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
14 [∃x ∈ D.R(x)] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
direct proof 4,13
24 [NOT(∃x ∈ D .R (x ))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
25 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) proof by cases 3, 14, 24
26 [∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))] direct proof 1,25
Problem Session 3
1 2 3 4
13 14
15
23 24
25 26
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
P OR NOT(P ) tautology
(∃x ∈ D.R(x)) OR NOT(∃x ∈ D.R(x)) substitution 2
Suppose ∃x ∈ D.R(x)
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
[∃x ∈ D.R(x)] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))]
direct proof 4,13
Suppose NOT(∃x ∈ D.R(x))
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) [NOT(∃x ∈ D .R (x ))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))] direct proof 15, 23 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) proof by cases 3, 14, 24
[∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))] IMPLIES
[∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))] direct proof 1,25
Problem Session 3
1 4
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y)) Suppose ∃x ∈ D.R(x)
13
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
Problem Session 3
1
4 5
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y)) Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4
13
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
Problem Session 3
1
4 5 6
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d,y) specialization 1
13
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
Problem Session 3
1
4 5 6 7
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d,y), specialization 1 ∀y ∈ D.A(d,y) modus ponens 6,5
13
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
Problem Session 3
1
4 5 6 7
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d,y), specialization 1 ∀y ∈ D.A(d,y) modus ponens 6,5
12 13
∀y ∈ D.(R(y) IMPLIES A(d,y))
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 5,12
Problem Session 3
1
4 5 6 7 8
11 12 13
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d,y), specialization 1 ∀y ∈ D.A(d,y) modus ponens 6,5
Let y ∈ D be arbitrary.
R(y) IMPLIES A(d, y)
∀y ∈ D.(R(y) IMPLIES A(d,y)) generalization 8,11
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 5,12
Problem Session 3
1
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d,y), specialization 1 ∀y ∈ D.A(d,y) modus ponens 6,5
Let y ∈ D be arbitrary. Assume R(y).
4
5
6
7
8
9
10 A(d,y)
11 12 13
R(y) IMPLIES A(d,y) direct proof of implication 9,10 ∀y ∈ D.(R(y) IMPLIES A(d,y)) generalization 8,11
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 5,12
Problem Session 3
1
4
5
6
7
8
9
10
11
12
13
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x,y))
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d,y), specialization 1 ∀y ∈ D.A(d,y) modus ponens 6,5
Let y ∈ D be arbitrary. Assume R(y).
A(d,y) specialization 7
R(y) IMPLIES A(d,y) direct proof of implication 9,10 ∀y ∈ D.(R(y) IMPLIES A(d,y)) generalization 8,11
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 5,12
Problem Session 3
15 Suppose NOT(∃x ∈ D.R(x))
23 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
Problem Session 3
15 16
Suppose NOT(∃x ∈ D.R(x))
∀x ∈ D.NOT(R(x)) negation of quantifiers 15
23
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y))
Problem Session 3
15 16 17
Suppose NOT(∃x ∈ D.R(x))
∀x ∈ D.NOT(R(x)) negation of quantifiers 15
Let x ∈ D be arbitrary.
22 23
∀y ∈ D.(R(y) IMPLIES A(x,y))
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 17,22
Problem Session 3
15 16 17 18
21 22 23
Suppose NOT(∃x ∈ D.R(x))
∀x ∈ D.NOT(R(x)) negation of quantifiers 15
Let x ∈ D be arbitrary. Let y ∈ D be arbitrary.
R(y) IMPLIES A(x, y)
∀y ∈ D.(R(y) IMPLIES A(x,y)) generalization 18, 21
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 17,22
Problem Session 3
15
16
17
18
19
20
21
22
23
Suppose NOT(∃x ∈ D.R(x))
∀x ∈ D.NOT(R(x)) negation of quantifiers 15
Let x ∈ D be arbitrary. Let y ∈ D be arbitrary.
Assume NOT(A(x,y)).
NOT(R (y ))
R(y) IMPLIES A(x,y) indirect proof 19, 20
∀y ∈ D.(R(y) IMPLIES A(x,y)) generalization 18, 21 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 17,22
Problem Session 3
15
16
17
18
19
20
21
22
23
Suppose NOT(∃x ∈ D.R(x))
∀x ∈ D.NOT(R(x)) negation of quantifiers 15
Let x ∈ D be arbitrary. Let y ∈ D be arbitrary.
Assume NOT(A(x,y)).
NOT(R(y)) specialization 16
R(y) IMPLIES A(x,y) indirect proof 19, 20
∀y ∈ D.(R(y) IMPLIES A(x,y)) generalization 18, 21 ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x,y)) construction 17,22
Problem Session 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Assume ∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x, y)).
P OR NOT(P ) tautology
(∃x ∈ D.R(x)) OR NOT(∃x ∈ D.R(x)) substitution 2
Suppose ∃x ∈ D.R(x)
Let d ∈ D be such that R(d) instantiation 4 R(d) IFF ∀y ∈ D.A(d, y) specialization 1 ∀y ∈ D.A(d, y) modus ponens 6,5
Let y ∈ D be arbitrary. Assume R(y).
A(d,y) specialization 7
R(y) IMPLIES A(d, y) direct proof 9,10
∀y ∈ D.(R(y) IMPLIES A(d, y)) generalization 8,11
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x, y)) construction 5,12
[∃x ∈ D.R(x)] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x, y))] direct proof 4,13
Suppose NOT(∃x ∈ D.R(x)).
∀x ∈ D.NOT(R(x)) negation of quantifiers 15
Let x ∈ D be arbitrary. Let y ∈ D be arbitrary.
Assume NOT(A(x,y)).
NOT(R(y)) specialization 16
R(y) IMPLIES A(x, y) indirect proof 19, 20
∀y ∈ D.(R(y) IMPLIES A(x, y)) generalization 18,21
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x, y)) construction 17,22
[ NOT(∃x ∈ D.R(x))] IMPLIES ∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x, y))] direct proof 15,23
∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x, y)) proof by cases 3,14,24.
[∀x ∈ D.(R(x) IFF ∀y ∈ D.A(x, y))] IMPLIES [∃x ∈ D.∀y ∈ D.(R(y) IMPLIES A(x, y))] direct proof 1,25
Problem Session 3
Problem 5
Give a well structured informal proof of:
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)).
Problem Session 3
Problem 5
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)). Every real number is either irrational or rational.
log7 n is rational implies that log7 n is irrational or an integer.
log7 n is irrational also implies that log7 n is irrational or an integer. Using proof by cases, it follows that log7 n is irrational or an integer.
Problem Session 3
Problem 5
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)). Every real number is either irrational or rational.
Suppose log7 n is rational.
Hence log7 n is an integer.
Therefore log7 n is rational implies that log7 n is irrational or an integer. log7 n is irrational also implies that log7 n is irrational or an integer. Using proof by cases, it follows that log7 n is irrational or an integer.
Problem Session 3
Problem 5
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)).
Every real number is either irrational or rational.
Suppose log7 n is rational.
Then, by definition, there exist relatively prime non-negative integers
p and q ̸= 0 such that log7 n = p/q.
Multiplying both sides by q gives log7 nq = q log7 n = p,
so nq = 7log7nq = 7p.
Since the factorization of a positive integer into primes is unique
and 7 is prime, it follows that n = 7k , where k is a non-negative integer. Hence log7 n is an integer.
Therefore log7 n is rational implies that log7 n is irrational or an integer. log7 n is irrational also implies that log7 n is irrational or an integer. Using proof by cases, it follows that log7 n is irrational or an integer.
Problem Session 3
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)). Let n ∈ Z+ be arbitrary.
log7 n is irrational or an integer.
By generalization, the claim is true for all positive integers n.
Problem Session 3
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)). Let n ∈ Z+ be arbitrary.
Therefore log7 n is rational implies that log7 n is an integer. Since P IMPLIES Q is logically equivalent to NOT(P) OR Q, log7 n is irrational or an integer.
By generalization, the claim is true for all positive integers n.
Problem Session 3
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)). Let n ∈ Z+ be arbitrary.
Suppose log7 n is rational.
Hence log7 n is an integer.
Therefore log7 n is rational implies that log7 n is an integer. Since P IMPLIES Q is logically equivalent to NOT(P) OR Q, log7 n is irrational or an integer.
By generalization, the claim is true for all positive integers n.
Problem Session 3
Theorem ∀n ∈ Z+.((log7 n ̸∈ Q) OR (log7 n ∈ Z)).
Let n ∈ Z+ be arbitrary.
Suppose log7 n is rational.
Then, by definition, there exist relatively prime non-negative integers p and q ̸= 0 such that log7 n = p/q.
Multiplying both sides by q gives log7 nq = q log7 n = p,
so nq = 7q log7 n = 7p.
Since the factorization of a positive integer into primes is unique and 7 is prime, n = 7k , where k is a non-negative integer.
Hence log7 n is an integer.
Therefore log7 n is rational implies that log7 n is an integer. Since P IMPLIES Q is logically equivalent to NOT(P) OR Q, log7 n is irrational or an integer.
By generalization, the claim is true for all positive integers n.
Regular Tutorial 3 : Writing Formal Proofs
Logan Murphy
CSC 240
January 27th 2021
Contents
Quiz Solution
Proving Properties of Sets Problem Session
Quiz
Give a well structured, informal proof that, for all integers x and y, if xy is even, then x is even or y is even. Use proper indentation and state what proof techniques you are using.
Quiz Solution
Let x and y be integers.
Suppose that neither x nor y is even.
Then there exist integers u and v such that x = 2u + 1 and y = 2v + 1.
Since xy = (2u + 1)(2v + 1) = 4uv + 2u + 2v + 1 = 2(2uv +u+v)+1 , it follows that xy is not even.
Hence, by indirect proof, if xy is even then x is even or y is even.
By generalization, it follows that, for all integers x and y, if xy is even, then x is even or y is even.
Proving Properties of Sets: The Subset Relation
A ⊆ B means or equivalently,
.
∀x ∈A.x ∈B
∀x ∈U.x ∈A IMPLIES x ∈B
Proving Properties of Sets: The Subset Relation
In either case, to prove the A ⊆ B: Let x ∈ A be arbitrary
.
x∈B
x ∈ A IMPLIES x ∈ B
∀x ∈ A. x ∈ B generalization
direct proof
Proving Properties of Sets: Set Equality
Two sets are equal when they contain exactly the same elements. A=B
∀x∈U.x∈A IFF x∈B
∀x ∈U.(x ∈A IMPLIES x ∈B) AND (x ∈B IMPLIES x ∈A)
A ⊆ B AND B ⊆ A Set equality is mutual inclusion.
Proving Properties of Sets: Size Equality
The size (cardinality) of a set A, denoted |A|, is the number of elements in A.
So two sets are the same size if they contain the same number of elements.
Proving Properties of Sets: Size Equality
To prove |A| = |B|, prove there exists a bijective function from A to B.
A function f : A → B is bijective if and only if for every b ∈ B, there is exactly one a ∈ A such that f (a) = b.
Also called a one-to-one correspondence.
Proving Properties of Sets: Size Equality
Example.
Let A = {a0,a1,...,am−1} be a set of size m. Let B = {b0,b1,...,bn−1} be a set of size n.
Prove that |A × B| = mn by by defining a bijection from A × B to the nonnegative integers {0, ..., mn − 1}.
Proving Properties of Sets: Size Equality
Solution.
(A̸=∅ AND B ̸=∅) OR (A=∅ OR B =∅) tautology Assume A=∅ OR B =∅.
AssumeA=∅. Thenm=0,somn=0.
If A = ∅, then A × B = ∅, and thus |A × B| = 0 A=∅ IMPLIES |A×B|=mn directproof
B =∅ IMPLIES |A×B|=mn symmetry
(A=∅ OR B=∅) IMPLIES |A×B|=mn proofbycases
Assume A̸=∅ AND B ̸=∅
Letf :A×B→{0,...,mn−1}bedefinedby
f (ai , bj ) = (i · n) + j where 0 ≤ i < m and 0 ≤ j < n
Given any integer k and n ̸= 0, there exists a unique integer q (the quotient) and a unique integer r (the remainder) such that
0 ≤ r < n and k = q · n + r.
Since the quotient and remainder are unique, and we assumed B ̸= ∅, this function is indeed a bijection.
Proving Properties of Sets: Size Equality
1.(A̸=∅ AND B̸=∅) OR (A=∅ OR B=∅)tautology 2. Assume A=∅ OR B =∅.
3. AssumeA=∅. Thenm=0,somn=0.
4. IfA=∅,thenA×B=∅,andthus|A×B|=0 5. A=∅ IMPLIES |A×B|=mn directproof2,4 6. B=∅ IMPLIES |A×B|=mn symmetry4
7. (A=∅ OR B=∅) IMPLIES |A×B|=mn proofbycases5,6
8. Assume A̸=∅ AND B ̸=∅
9. Letf :A×B→{0,...,mn−1}bedefinedbyf(ai,bj)=(i·n)+j where 0 ≤ i < m and 0 ≤ j < n
10. Given any integer k and n ̸= 0, there exists a unique integer q (the quotient) and unique integer r (the remainder) such that 0 ≤ r < n and k = q · n + r.
11. B ̸= ∅ IMPLIES f is a bijection direct proof 8, 10
12. A̸=∅ AND B̸=∅ IMPLIES |A×B|=mn directproof8,11
13. (A̸=∅ AND B ̸=∅) OR (A=∅ OR B =∅) IMPLIES |A×B|=mn proof by cases 7, 12
14. |A×B|=mn modusponens1,13
Proving Properties of Sets: Size Equality
Usually it takes more work to prove a function is bijective!
A function f : A → B is bijective if and only if for every b ∈ B, there is exactly one a ∈ A such that f (a) = b.
I.e. f is bijective if and only if it is both injective and surjective.
Recall :
f is injective if and only if
∀a1 ∈A.∀a2 ∈A.f(a1)=f(a2) IMPLIES a1 =a2
f issurjectiveifandonlyif∀b∈B.∃a∈A.b=f(a)
Proving Properties of Sets: Size Equality
To prove |A| = |B|, prove there exists a bijective function from A to B
1. Letf :A→B bethefunctiondefinedbyf(a)= .
4. f is injective .
8. f is surjective
9. f is bijective 4,8
10. ∃f : A → B, such that f is bijective 11. Thus |A| = |B| direct proof
construction 1
Proving Properties of Sets: Size (In)equality
More generally, given sets A and B
|A| ≤ |B| if and only if there exists an injective function from
A to B
|A| ≥ |B| if an only if there exists a surjective function from A
to B
|A| = |B| if an only if there exists a bijective function from A to B
Problem 1
Give a well structured informal proof of:
THEOREM Let X be a set and let A,B,C ⊆ X. SupposethatA∩B=A∩C and(X−A)∩B=(X−A)∩C. Then B = C.
You may use use the following lemma without proof. LEMMAForallsetsU andV,U∩V ⊆U andU∩V ⊆V.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C .
Thus B = C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C .
B ⊆ C.
By symmetry, C ⊆ B. Thus B = C.
We can use symmetry, because the assumptions and statement do not change when all occurrences of B and C are interchanged.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Then b ∈ C
Hence B ⊆ C.
By symmetry, C ⊆ B. Thus B = C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Since B ⊆ X, it follows that b ∈ X.
Then b ∈ C
Hence B ⊆ C.
By symmetry, C ⊆ B. Thus B = C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Since B ⊆ X, it follows that b ∈ X. b ∈ A or b ∈ X − A.
Then b ∈ C
Hence B ⊆ C.
By symmetry, C ⊆ B. Thus B = C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Since B ⊆ X, it follows that b ∈ X. b ∈ A or b ∈ X − A.
Therefore b ∈ A IMPLIES b ∈ C.
Therefore b ∈ (X − A) IMPLIES b ∈ C .
Then b ∈ C, using proof by cases. Hence B ⊆ C.
By symmetry, C ⊆ B.
Thus B = C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Since B ⊆ X, it follows that b ∈ X. b ∈ A or b ∈ X − A.
Suppose b ∈ A.
Thus, b ∈ C.
Therefore b ∈ A IMPLIES b ∈ C.
Suppose b ∈ X − A.
Thus, b ∈ C.
Therefore b ∈ (X − A) IMPLIES b ∈ C . Then b ∈ C, using proof by cases.
Hence B ⊆ C.
By symmetry, C ⊆ B. Thus B = C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ A.
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ A. Then b ∈ A ∩ B.
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ A.
Then b ∈ A ∩ B. Since A ∩ B = A ∩ C ,
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ A.
Then b ∈ A ∩ B.
Since A ∩ B = A ∩ C ,
it follows that b ∈ A ∩ C .
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ A.
Then b ∈ A ∩ B.
Since A ∩ B = A ∩ C ,
it follows that b ∈ A ∩ C . By the lemma, A ∩ C ⊆ C . Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ X − A.
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ X − A. Then b ∈ (X − A) ∩ B.
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ X − A.
Then b ∈ (X − A) ∩ B.
Since (X − A) ∩ B = (X − A) ∩ C ,
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ X − A.
Then b ∈ (X − A) ∩ B.
Since (X − A) ∩ B = (X − A) ∩ C , it follows that b ∈ (X − A) ∩ C .
Thus, b ∈ C.
Assume A, B , C ⊆ X , A ∩ B = A ∩ C , and (X − A) ∩ B = (X − A) ∩ C . Let b ∈ B.
Suppose b ∈ X − A.
Then b ∈ (X − A) ∩ B.
Since (X − A) ∩ B = (X − A) ∩ C , it follows that b ∈ (X − A) ∩ C . By the lemma, (X − A) ∩ C ⊆ C . Thus, b ∈ C.
Assume A,B,C ⊆ X, A∩B = A∩C, and (X −A)∩B = (X −A)∩C. Let b ∈ B.
Since B ⊆ X, it follows that b ∈ X. b ∈ A or b ∈ X − A.
Suppose b ∈ A.
Then b ∈ A ∩ B.
Since A∩B = A∩C, it follows that b ∈ A∩C. By the lemma, A∩C ⊆ C.
Thus, b ∈ C.
Therefore b ∈ A IMPLIES b ∈ C.
Suppose b ∈ X − A.
Then b ∈ (X −A)∩B.
Since (X −A)∩B = (X −A)∩C, it follows that b ∈ (X −A)∩C. By the lemma, (X −A)∩C ⊆ C.
Thus, b ∈ C.
Therefore b ∈ (X − A) IMPLIES b ∈ C. Then b ∈ C using proof by cases.
Hence B ⊆ C.
By symmetry, C ⊆ B. Thus B = C.
Problem 2
(a) Indicate what is wrong with this solution and give suggestions for improvement, as if you are a TA for CSC240.
First, we show that B ⊆ C.
Letp∈A∩B. Thismeansthatp∈Aandp∈B.
Since A ∩ B = A ∩ C, A ∩ B ⊆ A ∩ C and A ∩ C ⊆ A ∩ B. Thatmeansthatp∈A∩B impliesp∈A∩C.
Since p ∈ A ∩ C , it follows that p ∈ C .
Becausep∈A∩B meansthatp∈B,p∈B impliesp∈C. Therefore B ⊆ C.
Second, we show that C ⊆ B.
Let p ∈ (X − A) ∩ C .
This means that p ∈ C.
Since (X − A) ∩ C = (X − A) ∩ B, we know that
(X −A)∩C ⊆(X −A)∩B. Thismeansthatp∈(X−A)∩C impliesp∈(X−A)∩B. Since p ∈ (X − A) ∩ B, it can be said that p ∈ B. Sincep∈(X−A)∩C meansp∈C,p∈C impliesp∈B. Therefore C ⊆ B.
We have shown both that B ⊆ C and C ⊆ B. Therefore, B = C.
Problem 2
Some problems
Use of the word “mean” is ambigous (sometimes used in place of IFF, other times used as IMPLIES)
Proof of subset relation is improper; should begin with p ∈ B.
What about the case if p ∈/ A?
From p ∈ A ∩ B IMPLIES p ∈ B and
p∈A∩B IMPLIES p∈C,wecannotinferB⊂C
(b) Indicate what is wrong with this solution and give suggestions for improvement, as if you are a TA for CSC240.
First, I will show that B ⊆ C.
Let x ∈ B. Considering A ∩ B = A ∩ C, x ∈ A ∩ B implies that x ∈ A ∩ C. From the lemma, A ∩ B ⊆ B and A ∩ C ⊆ C .
Since A∩B = A∩C, it can be said that A∩B ⊆ C.
Since x ∈ A ∩ B and therefore x ∈ B, and A ∩ B ⊆ C, x is therefore also an element of C in the case that A∩B = A∩C.
Likewise, (X −A)∩B = (X −A)∩C implies that a given element x exists in (X −A)∩B and (X −A)∩C.
Therefore x ̸∈ A and x ∈ B. Also, according to the lemma, (X − A) ∩ C ⊆ C. Since (X −A)∩C = (X −A)∩B, then (X −A)∩B ⊆ C.
This implies that there is an element x ∈ (X − A) ∩ B and x ∈ C .
The phrase x ∈ (X − A) ∩ B can be further broken down to x ̸∈ A and x ∈ B. Therefore B ⊆ C, regardless of whether x ∈ A or x ̸∈ A.
To prove that C ⊆ B, it suffices to show that element y ∈ C implies y ∈ B. Take (X − A) ∩ B = (X − A) ∩ C .
Then y ∈ (X − A) ∩ B, and thus y ∈ B and y ̸∈ A.
According to the lemma, (X − A) ∩ B ⊆ B.
Since (X −A)∩B = (X −A)∩C, then (X −A)∩C ⊆ B. This implies that y ̸∈ A and y ∈ C. Alsoy ∈ B.
Therefore, C ⊆ B. If B ⊆ C and C ⊆ B, then B = C.
Problem 2
Some problems
Proof by cases is incorrect. The proper case analysis would be on(x∈A∩B) OR (x∈(X−A)∩B),not
x ∈ A OR x ∈/ A
From the equality in line 6, you can’t infer an existential; what if all the sets are empty?
Paragraph 3 contains redundant information! E.g. y ∈ B is deduced twice.
(c) Indicate what is wrong with this solution and give suggestions for improvement, as if you are a TA for CSC240.
Let x ∈ A ∩ B.
Then x ∈ A and x ∈ B. Also let x ∈ A∩C, then x ∈ A and x ∈ C. This shows that x ∈ A, B and C.
Since(X−A)∩B=(X−A)∩C,thenx∈X andx̸∈Aand x ∈ B and x ∈ X and x ̸∈ A and x ∈ C are equivalent. Thereforex∈X,B,andC andx̸∈A.
By the lemma, A ∩ B ⊆ A and A ∩ B ⊆ B, and A ∩ C ⊆ A and A∩C ⊆C.
However, since x ̸∈ A, then B = C.
Problem 2
Some problems
x is used for two different “arbitrary” variables; each assumption needs a fresh name for the variables!
Line 5 does not follow from line 4.
Conclusion is not justified from previous sentences.
Solutions to
CSC240 Winter 2021 Homework Assignment 3
Let i ∈ Z+ be arbitrary.
1. (a) 1
2 (imod2=0)OR(imod4=1)OR(imod4=3),propertyofZ+.
3 Suppose i mod 2 = 0.
4 element(S′, i, 2), by definition of S′, 3.
5 Let j ∈ Z+ be arbitrary.
6 Let k = 2(⌈j/2⌉ + 1) ∈ Z+.
7 2⌈j/2⌉ ≥ j, property of Z+.
8 2(⌈j/2⌉ + 1) = 2⌈j/2⌉ + 2 > j, property of Z+, 7.
9 k > j, substitution 6, 8.
10 lt(j, k), by definition of lt, 9.
11 k mod 2 = 0, property of Z+, 6
12 element(S′, k, 2), by definition of S′.
13 lt(j, k) AND element(S′, k, 2), conjunction: 10,12.
14 ∃k ∈ Z+.(lt(j, k) AND element(S′, k, 2)), direct proof of existential quantification: 6,13.
15 ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, 2)), generalization: 5,14.
16 element(S′, i, 2) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, 2)), conjunction: 4,15.
17 ∃x ∈ Z.[element(S′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))],
direct proof of existential quantification: 16, since 2 ∈ Z.
18 (i mod 2 = 0) IMPLIES ∃x ∈ Z.[element(S′, i, x) AND
∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))], direct proof of implication: 3,17.
19 Suppose i mod 4 = 1.
20 element(S′, i, 1), by definition of S′, 19.
21 Let j ∈ Z+ be arbitrary.
22 Let k = 4⌈j/2⌉ + 1 ∈ Z+.
23 4⌈j/2⌉ ≥ j, property of Z+.
24 4⌈j/2⌉ + 1 > j, property of Z+, 23.
25 k > j, substitution 22, 24.
26 lt(j, k), by definition of lt, 25.
27 k mod 4 = 1, property of Z+, 22.
28 element(S′, k, 1), by definition of S′, 27.
29 lt(j, k) AND element(S′, k, 1), conjunction: 26,28.
30 ∃k ∈ Z+.(lt(j, k) AND element(S′, k, 1)), direct proof of existential quantification: 22,29.
31 ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, 1)), generalization: 21,30.
32 element(S′, i, 1) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, 1)), conjunction: 20,31.
33 ∃x ∈ Z.[element(S′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))],
direct proof of existential quantification: 32, since 1 ∈ Z.
34 (i mod 4 = 1) IMPLIES ∃x ∈ Z.[element(S′, i, x) AND
∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))], direct proof of implication: 19,33.
1
35 Suppose i mod 4 = 3.
36 element(S′, i, 3), by definition of S′, 35.
37 Let j ∈ Z+ be arbitrary.
38 Let k = 4⌈j/2⌉ + 3 ∈ Z+.
39 4⌈j/2⌉ ≥ j, property of Z+.
40 4⌈j/2⌉ + 1 > j, property of Z+, 39.
41 k > j, substitution 38, 40.
42 lt(j, k), by definition of lt, 41.
43 k mod 4 = 3, property of Z+, 38.
44 element(S′, k, 3),by definition of S′, 43.
45 lt(j, k) AND element(S′, k, 3), conjunction: 42,44.
46 ∃k ∈ Z+.(lt(j, k) AND element(S′, k, 3)), direct proof of existential quantification: 38,45.
47 ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, 3)), generalization: 37, 47.
48 element(S′, i, 3) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, 3)), conjunction: 36,47
49 ∃x ∈ Z.[element(S′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))],
direct proof of existential quantification: 49, since 3 ∈ Z.
50 (i mod 4 = 3) IMPLIES ∃x ∈ Z.[element(S′, i, x) AND
∀j ∈ Z+.∃k ∈ Z+, .(lt(j, k) AND element(S′, k, x))], direct proof of implication: 35,49.
51 ∃x ∈ Z.[element(S′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))],
proof by cases: 2,18,34,50.
52 ∀i ∈ Z+.∃x ∈ Z.[element(S′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′, k, x))],
generalization: 1,51.
53 io(S ′ ), by defintion of io, 52
2
(b) 1 2 3 4 5 6 7 8 9
10 11
12
13
14
15
16
17
18
19
20
21
22
23
24
Let i = 4 ∈ Z+.
Let x ∈ Z be arbitrary.
Suppose element(S′′, i, x).
x = 1, by definition of S′′ 1, 3.
Let j = i ∈ Z+.
Let k ∈ Z+ be arbitrary.
Suppose lt(j, k).
NOT(element(S′′, k, x)), definition of S′′ 1, 5, 7.
lt(j, k) IMPLIES NOT(element(S′′, k, x)), direct proof of implication 7, 8. (A IMPLIES NOT(B)) IMPLIES NOT(A AND B), tautology
[lt(j, k) IMPLIES NOT(element(S′′, k, x))] IMPLIES
[NOT(lt(j, k) AND element(S′′, k, x))], substitution 10.
NOT(lt(j, k) AND element(S′′, k, x)), modus ponens 11, 9.
∀k ∈ Z+.NOT(lt(j, k) AND element(S′′, k, x)), generalization 6, 12.
NOT[∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))], negation of quantifier 13 .
∃j ∈ Z+.NOT[∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))], construction 5, 14 NOT[∀j∈Z+.∃k∈Z+.(lt(j,k)ANDelement(S′′,k,x))], negationofquantifier15.
element(S′′, i, x) IMPLIES NOT[∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))],
direct proof of implication 3, 16.
(element(S′′, i, x) IMPLIES NOT[∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))]) IMPLIES NOT[(element(S′′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))], substitution 10
NOT[(element(S′′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))],
modus ponens 18, 17.
∀x ∈ Z.NOT[element(S′′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))] generalization 2, 19.
NOT[∃x ∈ Z.[(element(S′′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))], negation of quantifier 20.
∃i ∈ Z+.NOT[∃x ∈ Z.[(element(S′′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))], construction 1, 21
NOT(∀i ∈ Z+.∃x ∈ Z.[(element(S′′, i, x) AND ∀j ∈ Z+.∃k ∈ Z+.(lt(j, k) AND element(S′′, k, x))]), negation of quantifier 22.
NOT(io(S′′)), by defintion of io, 23
3
CSC 240 Lecture 4 Induction
Let p: N → {T,F} be a predicate. Suppose you want to prove ∀ n ∈ N. p(n)
⋮p(0) basis or base ⋮
∀ n ∈ N.[p(n) IMPLIES p(n+1)] ∀ n ∈ N. p(n) by induction
To prove ∀ n ∈ N.[p(n) IMPLIES p(n+1)]: Let n ∈ N be arbitrary
Assume p(n)
⋮
p(n+1)
p(n) IMPLIES p(n+1) direct proof
∀ n ∈ N.[p(n) IMPLIES p(n+1)] generalization
THEOREM 1. Consider any square chessboard whose sides have length which is a power of 2. If any one square is removed, then the resulting shape can be tiled using only 3-square L-shaped tiles.
A shape is tiled by a set of tiles means that you can fit the tiles together with no gaps or overlaps to fill the shape exactly. Another name for a tiling is a tessellation.
3-square L-shaped tiles
Let’s call these L-tiles
case
I
I
Proof:
Let P(n) = “any 2n x 2n chessboard with one square removed can be tiled using 3-square L-shaped tiles”.
Let C(n) denote the set of all 2n x 2n chessboards with one square removed. P(n) = “∀ c ∈ C(n). c can be tiled using only L-tiles”
N Pcn
Basis:
P(0) is true, since a 20 x 20 chessboard with one square removed has no squares and hence can be tiled with 0 L-tiles.
Let n ∈ N be arbitrary. Suppose that P(n) is true.
Let c in C(n+1) be arbitrary.
Divide c into 4 equal 2n x 2n chessboards
One of these has a square removed, so it is in C(n).
By the induction hypothesis, it can be tiled using L-tiles. Consider the other three 2n x 2n chessboards.
Each has 1 square that is in the centre of c.
With that square removed, the induction hypothesis says that
it can be tiled with L-tiles.
The 3 squares that we removed from the centre of c can be tiled
using one L-tile.
Hence c can be tiled using L -tiles.
∀ c ∈ C(n+1). c can be tiled using only L-tiles. by generalization
P(n+1) by definition of P(n+1)
P(n) IMPLIES P(n+1) by direct proof
∀ n ∈ N. (P(n) IMPLIES P(n+1)) by generalization ∀ n ∈ N. P(n) by induction
Prove
the
Example for n = 2
I
I
THEOREM 1. All square chessboards with sides whose length is a power of 2 and has one square removed can be tiled using only L-tiles.
THEOREM 2. All square chessboards with sides whose length is a power of 2 and has one square removed from the middle can be tiled using only L- tiles.
Let C'(n) denote the set of all 2n x 2n chessboards with one square removed from the middle
Let P'(n) = “∀ c ∈ C'(n). c can be tiled using only L-tiles” How can P'(n) be use to prove P'(n+1)? It can’t!
Proving a harder/more general result is easier here
because strengthening the induction hypothesis makes the proof of the induction step easier.
THEOREM 3 For all n ∈ N . 2n + 1 ≤ 2n. For all n ∈N,
let q(n) = ” 2n + 1 ≤ 2n ”
Base case:
2 x 0 + 1 = 1 ≤ 1 = 20 so q(0) is true.
Let n ∈ N be arbitrary. Assume q(n)
⋮
q(n+1)
DOESN’T WORK:
true for n = 0
false for n = 1: 2 x 1+ 1 = 3 > 2 = 21 false for n = 2: 2 x 2+ 1 = 5 > 4 = 22 true for n ≥ 3.
The actual theorem is
THEOREM 3 ∀ n ∈N. (n ≥ 3 IMPLIES q(n)) or, alternatively,
∀ m ∈ M. q(m),
where M = {m ∈ N | m ≥ 3}.
How can this be proved by induction?
IDEA 1
Let r(n) = “(n ≥ 3) IMPLIES q(n)”.
Then ∀ n ∈N. r(n) means the same as ∀ n ∈N. ((n ≥ 3) IMPLIES q(n))
base case: r(0)
vacuously true, since 0 ≥ 3 is false.
induction step:
Let n ∈ N be arbitrary.
Assume r(n) Assume (n ≥ 3) IMPLIES q(n) ⋮⋮
r(n+1) (n+1 ≥ 3) IMPLIES q(n+1) r(n) IMPLIES r(n+1)
∀ n ∈ N. (r(n) IMPLIES r(n+1)) by generalization ∀ n ∈ N. r(n)by induction
Assume (n ≥ 3) IMPLIES q(n) Assume n+1 ≥ 3
Then either n = 2 or n ≥ 3. Case 1: n = 2
7
Then2(n+1)+1=2×3+1=7≤23 =2^{n+1},soq(n+1)istrue
Case 2: n ≥ 3
q(n), modus ponens
2n + 1 ≤ 2n, by definition of q(n)
2 ≤ 8 = 23 ≤ 2n arithmetic
2(n+1) + 1 = 2n + 2 + 1 = (2n+1) + 2 ≤ 2n + 2n = 2^{n+1}
substitution
q(n+1), by definition of q(n+1) q(n+1) proof by cases
(n+1 ≥ 3) IMPLIES q(n+1), direct proof of implication
IDEA 2
Let p(n) = q(n+3).
Then ∀ n ∈ N. p(n) means the same as ∀ m ∈ M. q(m) and
∀ n ∈ N. (p(n) IMPLIES p(n+1)) means the same as
base case: p(0)
induction step:
Let n ∈ N be arbitrary.
∀ m ∈ M. (q(m) IMPLIES q(m+1)).
base case: q(3)
induction step:
Let m ∈ M be arbitrary
Assume p(n) ⋮⋮
p(n+1)
p(n) IMPLIES p(n+1)
∀ n ∈ N. (p(n) IMPLIES p(n+1)) by generalization
∀ n ∈ N. p(n) by induction
Assume q(m)
q(m+1)
q(m) IMPLIES q(m+1)
∀ m ∈ M. (q(m) IMPLIES q(m+1)) by generalization
∀ m ∈ M. q(m) by induction
to prove
∀ n ∈N. ((n ≥ b) IMPLIES p(n))
it suffices to prove
p(b)
and either
∀ n ∈ {m ∈N| m ≥ b}. (p(n) IMPLIES p(n+1)) or
∀ n ∈ N. (((n ≥ b) AND p(n)) IMPLIES p(n+1))
Suppose we want to prove that a predicate q is true only for all even natural numbers?
Let p(k) = q(2k)
Then ∀ k ∈N. p(k)
means the same as
∀ k ∈N. q(2k)
which means the same as ∀ n ∈ N. (n is even IMPLIES q(n)).
Base case: p(0) = q(0)
induction step is: p(k) IMPLIES p(k+1) which is q(2k) IMPLIES q(2k+2)
Therefore, it is sufficient to prove q(0) and
∀ n ∈ N. (q(n) IMPLIES q(n+2))
This isn’t necessary: we’re proving
q(0) IMPLIES q(2) q(1) IMPLIES q(3) q(2) IMPLIES q(4) q(3) IMPLIES q(5)
x
We don’t need half of these. In fact, they might not even be true. For example
n2 ≤ 2n is true for all even n ≥ 0 and for n = 1
but is false for n = 3
Thus q(1) IMPLIES q(3) is false.
To prove ∀ i ∈ {0,1,…,n}. p(i)
Base case:
⋮
p(0)
Induction step:
Let i ∈ {0,1,…,n-1} be arbitrary.
Assume p(i).
⋮
p(i+1)
p(i) IMPLIES p(i+1), direct proof
∀ i ∈ {0,1,…,n-1}. (p(i) IMPLIES p(i+1)) generalization ∀ i ∈ {0,1,…,n}. p(i) induction
arithmetic mean (a1 + … + a_n )/n = (∑{ai | 1 ≤ i ≤ n}) / n geometric mean (a1 … a_n) ^{1/n} = (∏{ai | 1 ≤ i ≤ n}) ^{1/n}
THEOREM 4 For all positive integers n and all positive real numbers
a1 ,…, a_n their geometric mean is less than or equal to their arithmetic mean.
For all n ∈Z+, let P(n) =
“∀ a ∈ (R+)^{1,…,n}. [(∏{a(i) | 1 ≤ i ≤ n}) ^{1/n} ≤ (∑{a(i) | 1 ≤ i ≤ n}) / n]”
THEOREM 4 ∀ n ∈ Z+. P(n)
Base case: n = 2
⋮
Induction steps:
Let n be an arbitrary integer ≥ 2.
Assume P(n)
⋮
P(n-1)
P(n) IMPLIES P(n-1)
Assume P(n)
⋮
P(2n)
P(n) IMPLIES P(2n)
∀ n ∈ Z+. P(n) by induction
Why?
To prove P(m), let k be the smallest power of 2 greater than or equal to m 2^{k-1} < m ≤ 2^k
Using the base case, prove P(2) Using the second induction step, prove P(4), P(8),..., P(2^k)
Using the first induction step, prove P(2^k - 1), P(2^k - 2),...,P(m)
Base case: n = 2
Let
arbitrary
o
a acRtbe
2a a t ai Ca a fz
ai
ai t ai
z2 itzazJZ_aftaz2t2qa4Z2ai9zf2q9z
By
azzla.aa generalization
PG
is true
y_aiqaitz
a
a
Let n be an arbitrary integer ≥ 2.
Assume P(n) arbitrary
Let ai an e E Rt be and Let bi ai for c I on l
let bn Cait i t an e kn 1 Then by specialization of Pcn
ELIE bi n ai bn In
II bi
bi 4
P(n-1)
P(n) IMPLIES P(n-1)
by
generalization
n
DbntbD1nJh_fnhnY
biThusIIiai
fIT.bi Ibn 2 BE Hn D
IITbi
Assume P(n)
t
be arbitrary zn and bz LEE
E IR bi thEnai
a aan
By specialization
Let Let
ai PEN
Itai ELLE aik
b.bz E Cbt b 12 IiiiailnJ Hence Itai efzha.hn
fnEiaIfi
a.ec ia
and by specialization of PCD
iii
cb.bdklbIh7
by generalization
P(2n)
P(n) IMPLIES P(2n)
xnI
of
and
STRONG or COMPLETE INDUCTION
to prove
∀ i ∈ N. p(i)
it suffices to prove
∀ i ∈ N. ( [ ∀ j ∈ N. ((j < i) IMPLIES p(j)) ] IMPLIES p(i) )
Let i ∈ N be arbitrary
Assume ∀ j ∈ N. ( (j < i) IMPLIES p(j ))
⋮
various cases
⋮
p(i)
[ ∀ j ∈ N. ( (j < i) IMPLIES p(j)) ] IMPLIES p(i) direct proof
∀ i ∈N. ( [ ∀ j ∈N. ((j < i) IMPLIES p(j)) ] IMPLIES p(i) ) generalization THESE 2 LINES ARE OPTIONAL
∀ i ∈ N. p(i) strong induction
Alternative:
Base Case:
⋮
p(0)
Induction Step:
Let i ∈ Z+ be arbitrary.
Assume ∀ j ∈ N. ( (j < i) IMPLIES p(j) ) ⋮
p(i)
∀ i ∈ N. p(i) strong induction
Theorem For all n ≥ 4, exactly $n can be made using only toonies and $5 bills.
Proof: For all n ∈ N,
let P(n) = "exactly $n can be made using only toonies and $5 bills." or,
let P(n) = "∃ f ∈ N. ∃ g ∈ N. (n = 2 f + 5 g)” Let n ∈ N be arbitrary.
Suppose n ≥ 4 and ∀j∈N.((4≤j
Then S = S′HS′′, where S′ = Tk for some 0 ≤ k < n and S′′ is the suffix of S following its
first occurrence of H. Note that S′′ contains an even number of H’s. Apply a step σ to the
first occurrence of H in S. Let S1 = S′ BS′′ be the resulting string, where |S′| = |S′ | = k
and |S′′| = |S′′| = n − 1 − k. 1
Ifk=0,thenS′ isanemptysequenceofB’sandS1′ =S′. Inthiscase,letσ′ betheempty sequence of steps. If k > 0, then S1′ = Tk−1H. By the induction hypothesis, there exists a sequence of steps σ′ that converts S1′ to Bk. Since there is a B following S1′ in S1, none of these steps affect S′′.
If n−k−1 = 0, then S′′ is an empty sequence of B’s and S′′ = S′′, so σσ′ converts S to 1
Bn. Otherwise, S′′ ∈ {H,T}n−k−1. It contains an odd number of H’s, since step σ changed 1
the first letter of S′′ from T to H or from H to T. By the induction hypothesis, there exists a sequence of steps σ′′ that converts S′′ to Bn−k−1, since n − 1 − k < n. Then σσ′σ′′ is a
2
1
1
111
sequence of steps that converts S to Bn, because when σ′′ is applied, the rest of the string consists of B’s, which are not affected by any steps.
Hence, if S contains an odd number of H’s, there exists a sequence of steps that converts S to Bn.
Now suppose there is a sequence of steps τ that converts S to Bn. Let 0 ≤ i ≤ n−1 be
the number of H’s and T’s that precede the H to which the first step of τ is applied, so
S = S′HS′′, where |S′| = k < n and |S′′| = n−1−k < n. Let S1 = S′BS′′ be the resulting
string, where |S′| = |S′ | and |S′′| = |S′′|. 11
If k ≥ 1, then the number of H’s in S1′ differs from the number of H’s in S′ by 1. Likewise, if n−1−k ≥ 1, the number of H’s in S′′ differs from the number of H’s in S′′ by 1. Let
τ′ be the subsequence of steps in τ that are applied to positions 1 ≤ i ≤ k and let τ′′ be the
subsequence of steps in τ that are applied to positions k + 1 ≤ i ≤ n. Since there is a B in
position k of S1, the steps in τ′ do not affect S′′ and the steps in τ′′ do not affect S′ . Thus 11
τ′ converts S′ to Bk−1 and τ′′ converts S′′ to Bn−1−k. 11
Ifk−1≥1,then,bytheinductionhypothesis,S1′ containsanoddnumberofH’sand,hence S′ contains an even number of H’s. If k − 1 = 0, then S′ = S1′ contains zero H’s which is an even number.
Likewise, if n − 1 − k ≥ 1 then, by the induction hypothesis, S′′ contains an odd number 1
of H’s and, hence S′′ contains an even number of H’s, and if n−1−k = 0, then S′′ = S′′ 1
contains zero H’s which is an even number. Since S = S′HS′′, it follows that S contains an odd number of H’s.
Hence, if there exists a sequence of steps that converts S to Bn, then S contains an odd number of H’s,
Therefore, (there exists a sequence of steps that converts S to Bn) IFF (S contains an odd number of H’s. By generalization, q(n) is true. Finally, by strong induction, ∀n ∈ Z+.q(n) is true.
1
3
11
CSC 240 Lecture 4 Induction STRONG INDUCTION
Let i ∈ N be arbitrary
Assume ∀ j ∈ N. ( (j < i) IMPLIES p(j )
⋮
various cases
⋮
p(i)
optional: [ ∀ j ∈ N. ( (j < i) IMPLIES p(j)) ] IMPLIES p(i) direct proof
optional: ∀ i ∈ N. ( [ ∀ j ∈ N. ((j < i) IMPLIES p(j)) ] IMPLIES p(i) ) generalization ∀ i ∈ N. p(i) strong induction
THEOREM Every integer greater than 1 is a product of primes.
Proof:
Let M = { n ∈ N | n > 1}.
For all n ∈ M, let p(n) = “n is a product of primes”
Let n ∈ M be arbitrary.
Suppose ∀ i ∈ M. ((i < n) IMPLIES p(i))
If n is prime, then n is a product of 1 prime.
Otherwise, by definition of prime,
∃ k in M. ∃ m in M. (n = mk)
Since k < n and m < n, it follows by the induction hypothesis, that k is a product of primes and m is a product of primes.
Thus n = km is a product of primes, i.e. p(n). By strong induction, ∀ n ∈ M. p(n)
Proofs by weak induction can be easily transformed into proofs by strong induction by using the strong induction template instead of the ordinary induction template.
When proving P(n+1), there is no harm in assuming P(0),...,P(n-1) in addition to P(n).
Proofs by strong induction can also be transformed into proofs by weak induction. This was discussed in tutorial.
Recursively Defined Sets
Such definitions have 2 parts:
a base case, that doesn't depend on anything else, and a constructor case, that depends on previous cases.
Examples
1. {0,1}* = set of all finite strings of bits Base case:
the empty string, λ, of length 0, is in {0,1}* Constructor case:
if s ∈ {0,1}* then s0 and s1 are in {0,1}*
More generally, if 𝝨 is any finite set of letters,
then 𝝨* is the set of all finite strings of letter from 𝝨. For example 𝝨 = {[,]}
2. Brkts = set of finite strings of matched brackets Base case:
the empty string, λ, of length 0, is in Brkts Constructor cases:
if s,t ∈ Brkts then [s] ∈ Brkts and st ∈ Brkts Alternative constructor case:
if s,t ∈ Brkts then [s]t ∈ Brkts
3. S = syntactically correct formulas of propositional logic Base case:
propositional variables are in S
constructor cases:
If f, f' ∈ S, then NOT(f) ∈ S
(f OR f') ∈ S
(f AND f') ∈ S
(f IMPLIES f') ∈ S (f IFF f') ∈ S
(f XOR f') ∈ S
4. M = syntactically correct monotone formulas of propositional logic Base case:
propositional variables are in M
Constructor cases:
If f, f' ∈ M, then (f OR f') ∈ M
(f AND f') ∈ M
M is the smallest set of strings containing all the propositional variables that is closed under AND and OR.
• There can be many sets that satisfy a definition, for example S also satisfies the definition for M
• We define a set recursively, we mean (but may not say explicitly) that we are defining the smallest such set.
5. A = arithmetic expressions involving natural numbers Base case: N ⊆ A
Constructor cases:
if e,f ∈ A then
e + f ∈ A and e x f∈A
When a recursive definition allows an element to be constructed
in more than one way, the definition is ambiguous.
For example, 3 x 2 + 1
can be obtained by combining 3 x 2 and 1 with the first constructor case or by combining 3 and 2 + 1 with the second constructor case
Notice:
• We are defining a set of finite strings
• In the base case(s), we explicitly define the smallest or simplest elements
in the set.
• In the constructor case(s), we define the ways in which larger or more
complex elements in the
set can be constructed out of smaller or simpler elements
Structural induction
a form of induction used to prove properties about recursively defined sets.
Let S be a recursively defined set.
To prove ∀ x ∈ S. p(x), where p:S→{T,F} is a predicate, prove:
p(x) for all base cases of the definition
p(x) for the constructor cases of the definition,
assuming it is true for the components of x Example:
Let M be the set of syntactically correct monotone formulas of propositional logic.
For all f ∈ M,
let Nv(f) = “the number of occurrences of propositional variables in f”,
let Nc(f) = “the number of occurrences of connectives in f”, and let p(f) = “Nv(f) = 1 + Nc(f)”.
Base case:
If f is a propositional variable, then Nv(f) =1 and Nc(f) = 0, so p(f) is true.
Constructor cases:
Let f' and f" in M be arbitrary.
Assume p(f') and p(f") are true.
Consider f = (f' OR f").
Nv(f) = Nv(f') + Nv(f")
= (1 + Nc(f')) +(1 + Nc(f")) by the induction hypothesis = 1 + (Nc(f') + Nc(f") + 1)
= 1 + Nc(f).
Hence p(f) is true.
Similarly, if f = (f' AND f"), then
Nv(f) = Nv(f') + Nv(f")
= (1 + Nc(f')) +(1 + Nc(f")) by the induction hypothesis
= 1 + (Nc(f') + Nc(f") + 1) = 1 + Nc(f).
so p(f) is true.
E
By structural induction, ∀ f ∈ M. p(f).
Proving universally quantified predicates of two or more variables: ∀m ∈N.∀ n ∈N. p(m,n)
N x N can also be defined recursively: Base case: (0,0) ∈ N x N
Constructor case: if (m,n) ∈ N x N, then (m,n+1) ∈NxNand (m+1,n) ∈NxN.
To prove ∀m ∈ N.∀ n ∈ N. p(m,n) using structural induction:
Base case:
Prove p(0,0) Constructor case:
Let (m,n) ∈ N x N be arbitrary.
Assume p(m,n).
Prove p(m,n+1) and p(m+1,n)
n g
m
Strong induction alternative: Let (m,n) ∈ N x N be arbitrary.
Assume
o
∀i ∈ N.∀ j ∈ N. ([(i ≤ m) AND (j ≤ n) AND ((i
Quiz Solution
Give a recursive definition of the function min : R+R so that for every sequence S ∈ Rn, min(S) is the smallest real number that occurs in S.
Solution:
Base case:
if x ∈ R, then min(x) = x Constructor case:
if (S , x ) ∈ R n × R , where n ∈ Z + , then:
min(S,x)=
x if x < min(S); min(S) if x ≥ min(S)
Quiz Solution
Prove by structural induction that max(−S) = −min(S) for every sequence S ∈ Rn.
Solution:
For all S ∈ Rn, let P(S) = “max(−S) = −min(S)”.
Base Case: If S ∈ R, then, by definition of max, max(−S) = −S and, by the definition of min, min(S) = S, so
max(−S) = −S = −min(S). Thus P(S) is true.
Constructor Case: Consider S = (S′,x), where S′ ∈ Rn and
x ∈ R. Note, that −S = (−S′,−x). By the induction hypothesis, max(−S′) = −min(S′).
Quiz Solution
Solution:
For all S ∈ Rn, let P(S) = “max(−S) = −min(S)”.
Constructor Case: Consider S = (S′,x), where S′ ∈ Rn and
x ∈ R. Note, that −S = (−S′,x). By the induction hypothesis, max(−S′) = −min(S′).
Case 1: −x > max(−S′).
By definition of max, max(−S) = −x. In this case
−x > −min(S′), so x < min(S′). By definition of min, min(S) = x. Thus max(−S) = −x = −min(S).
Case 2: −x ≤ max(−S′).
Quiz Solution
Solution:
For all S ∈ Rn, let P(S) = “max(−S) = −min(S)”.
Constructor Case: Consider S = (S′,x), where S′ ∈ Rn and
x ∈ R. Note, that −S = (−S′,x). By the induction hypothesis, max(−S′) = min(S′).
Case 1: −x > max(−S′). Case 2: −x ≤ max(−S′).
By definition of max, max(−S) = max(−S′). Since max(−S′) = −min(S′) it follows that −x ≤ −min(S′), so
x ≥ min(S′). By definition of min, min(S) = min(S′). Thus max(−S) = −min(S) = −min(S).
Since one of these two cases holds, max(−S) = −min(S). Thus P(S) is true.
By structural induction, ∀S ∈ Rn.P(S).
Problem session
1. Strict binary tree is a binary tree in which every node that is not a leaf has exactly 2 children. Give a recursive definition of the set S of strict binary trees.(Recall that a leaf is a node with no children.)
Problem session
a. Strict binary tree is a binary tree in which every node that is not a leaf has exactly 2 children. Give a recursive definition of the set S of strict binary trees.(Recall that a leaf is a node with no children.)
Solution:
Base Case:
A node is in S.
Constructor Case:
Ift1 andt2 areinS andifr isanode,then:
Problem session
b. Link in the chat, discuss in the breakout rooms
Solution:
Problem session
b. Link in the chat, discuss in the breakout rooms Solution: counterexample. Consider a tree:
Problem session
b. Link in the chat, discuss in the breakout rooms
The mistake is that we cannot apply the induction hypothesis to t′, since it is not a strict binary tree. In particular, the node v′ has 1 child.
Problem session
c. Give a recursive definition of the depth of a strict binary tree.
Problem session
c. Give a recursive definition of the depth of a strict binary tree.
For our strict binary tree t, we have: left(t) and right(t) are children of t. We will define d(t) as the depth of a strict binary tree.
Base case:
ift isanode,thend(t)=0.
Constructor case:
if t is not a node, then d(t) = 1 + max{d(left(t)), d(right(t))}
Problem session
d. Prove by structural induction that, for all strict binary trees t, N(t) ≤ 2d(t)+1 − 1
Problem session
d. Prove by structural induction that, for all strict binary trees t, N(t) ≤ 2d(t)+1 − 1
For all strict binary trees t, let P(t) = ”N(t) ≤ 2d(t)+1 − 1”.
Base case: if t is a node, then d(t) = 0, N(t) = 1. Therefore, 2d(t)+1 − 1 = 1 and N(t) ≤ 2d(t)+1. Thus, P(t) is true. Constructor case: consider a strict binary tree t s.t node r is its root and t1 and t2 are its left and right children respectively. Without loss of generality, assume that d(t1) ≥ d(t2). There are two things to notice here:
1. 2d(t1)+2 = 2d(t1)+1 + 2d(t1)+1 ≥ 2d(t2)+1 + 2d(t1)+1.
Problem session
d. Prove by structural induction that, for all strict binary trees t, N(t) ≤ 2d(t)+1 − 1
Constructor case: consider a strict binary tree t s.t node r is its root and t1 and t2 are its left and right children respectively. Without loss of generality, assume that d(t1) ≥ d(t2). There are two things to notice here:
1. 2d(t1)+2 = 2d(t1)+1 + 2d(t1)+1 ≥ 2d(t2)+1 + 2d(t1)+1. 2. By definition of d(t), d(t) = d(t1) + 1. Therefore,
d(t1)+2 = d(t)+1
We know that N(t) = N(t1) + N(t2) + 1. By induction hypothesis,
N(t) ≤ 2d(t1)+1 −1+2d(t2)+1 −1+1 ≤ 2d(t1)+2 −1 = 2d(t)+1 −1.
Therefore, N(t) ≤ 2d(t)+1 − 1, which means that P(t) is true. By structural induction, ∀ strict binary trees t. P(t).
Solutions to
CSC240 Winter 2021 Homework Assignment 5
1. Consider H(2,1). Line 1 cannot be applied since 1 ̸= 0. Applying line 2 or line 3 gives H(2,1) = H(1,2). Line 1 cannot be applied to H(1,2), since 2 ̸= 0. Line 3 cannot be applied to H(1, 2), since 1 < 2. Therefore, only line 2 can be applied to H(1, 2), resulting in H(1,2) = H(2,1). Thus, there is no way to get a value for H(2,1) from the definition.
2. For all natural numbers a and b, let P (a, b) = “G(a, b) has one and only one value.”
Note that, for b > a, neither the first line or the third line can be applied to G(a, b), so the only way to define it is by applying the second line and defining it to be the same as G(b, a). Therefore, it suffices to prove (b ≤ a) IMPLIES P (a, b)
We will prove ∀a ∈ N.∀b ∈ N.[(b ≤ a) IMPLIES P (a, b)] by double induction on a and b. Let Q(a) denote the predicate ∀b ∈ N.[(b ≤ a) IMPLIES P (a, b)].
We will prove ∀a ∈ N.Q(a) by induction on a.
Let a ∈ N be arbitrary. Suppose that Q(a′) is true for all a′ ∈ N such that a′ < a.
Let b ∈ N be arbitrary and suppose that b ≤ a. Furthermore, suppose that P(a,b′) is true forallb′ ∈Nsuchthatb′
Case3: a>0andb>0. Byline3,G(a,b)=G(a−b,b). Sinceb>0,line1cannotbe applied. Applying line 2 to G(a, b) results in G(b, a). Since a > 0, line 1 cannot be applied to G(b, a) and, since a ≥ b, line 3 cannot be applied to G(b, a). Thus, only line 2 can be applied to G(b, a), which results in G(a, b). Therefore applying line 2 to G(a, b) is not useful. Hence only line 3 can be applied.
Sinceb>0anda≥b,itfollowsthata−b∈Nanda−b
Let m’0 = m0 / p ∈ Z+ and n’0 = n0 / p ∈ Z+.
Since m’0 / n’0 = m0 /n0, it cannot be expressed in reduced form. Thus m’0 ∈ C.
But m’0 < m0.
This contradicts the fact that m0 is the smallest element of C.
Hence C = 𝜙 and every rational number can be expressed in reduced form. ---------------
For every positive integer i
let E(i) denote the subsets of {1,...,i } which contain an even number of elements and
let U(i) denote the subsets of {1,...,i } which contain an odd number of elements.
Theorem For all positive integers i, |E(i)| = |U(i)| = 2i−1. Proof (using the well ordering principle):
For every positive integer i, let P(i) = "|E(i)| = |U(i)| = 2i−1 ".
Let C = {i ∈Z+ | NOT(P(i)) }.
To obtain a contradiction, suppose that C ≠ 𝜙 .
Then, by the well ordering principle, C has a smallest element, x.
Note that x ≠ 1, since {1} has 1 = 2x−1 subset which contains an even number of elements, namely 𝜙, and
1 subset which contains an odd number of elements, namely {1}. Thus x > 1 and P(x-1) is true, so |E(x-1)| = |U(x-1)| = 2x−2.
Let E'(x) ={ S ∈ E(x) | x ∈ S }.
Since the sets in E(x) that don’t contain x are the sets in E(x-1),
it follows that E(x) = E'(x) U E(x-1) and |E(x)| = |E'(x)| + |E(x-1)|. There is a one-to-one correspondence between E'(x) and U(x-1): adding x to a set in U(x-1) gives a set in E'(x)
and deleting x from a set in E'(x) gives a set in U(x-1).
Thus |E'(x)| = |U(x-1)|.
Hence |E(x)| = |U(x-1)| + |E(x-1)| = 2x−2 + 2x−2 = 2x−1.
Thus P(x) so x ∉ C. This is a contradiction. Hence C = 𝜙 and ∀ i ∈ Z+.P(i) is true.
COUNTABLE AND UNCOUNTABLE SETS Afunctionf:A→Bissurjectiveorontoifandonlyif∀y∈ B.∃x∈ A.f(x)=y.
Each element of B is mapped to by some element of A.
From the existence of a surjective function f:A→B,
where A and B are finite sets, we can conclude that |A| ≥ |B|
A nonempty set C is called countable if there is a surjective function from N to C.
Every nonempty finite set is countable.
Suppose C is a finite set.
Arrange the elements in some order: c0 c1,…, cx − 1
Define f:N → C as follows: f(i) = ci for i =0,…,x-1
cx − 1 for i ≥ x
Problem: what if C is empty? There is no such function f, since there is no place to map to.
We also define the empty set to be countable.
Z is countable 0,-1,1,-2,2
f(n) = n/2 if n is even -(n+1)/2 if n is odd
More generally,
if A and B are countable, then so is A U B.
If A is countable and B ⊆ A, then B is countable. Example: the set of odd integers is countable.
If A and B are countable, then A x B = {(a,b) | (a ∈ A) AND (b∈ B)} is countable.
For example, N x N is countable.
f 0 1 2 3
0123…
9
0136 247
58
⋮
f(k) = (x,y) if location (x,y) of this infinite array contains the number k. Lemma If A is nonempty and countable and there is a surjective function
f:A →B, then B is countable.
Proof:
Since A is countable, there is a surjective function g:N → A. Then there is a surjective function h:N →B
defined by h(i) = f(g(i)) for all i ∈ N.
Q+ is countable f:Z+ xZ+→Q+
f(a,b) = a/b
Note that f is not 1 to 1: every element of Q+ has an infinite number of pairs that are mapped to it by f.
For example, (1,2), (2,4), (3,6) all map to 1/2
{0,1}* = the set of all finite binary sequences is countable: λ, 0, 1, 00, 01, 10, 11, 000, …
Consider the surjective function g: N x N → {0,1}* where
g(i,j) = j’th lexicographically smallest string of length i if 1 ≤ j ≤ 2i
λ, otherwise.
There are 2i binary strings of length i.
The set of all finite strings of ASCII characters is countable.
The set of all syntactically correct Python programs is countable.
For any set A, the power set of A is the set of all subsets of A i.e. 𝒫(A) = { S | S ⊆ A }.
If A has size n, what is the size of 𝒫(A)? 2n Theorem 𝒫(N) is uncountable.
(MIT text Chapter 8, Corollary 8.1.13, section 8.1.4)
Proof: Suppose 𝒫(N) is countable.
Then there is a surjective function f:N →𝒫(N).
LetD={i∈N|i∉ f(i)}∈𝒫(N).
Since f is surjective, there exists j ∈ N such that f(j) = D.
Then, for all i ∈ N,
i ∈ f(j) IFF i ∈ D, since f(j) = D
IFF i ∉ f(i), by definition of D.
Since j ∈ N, by specialization, j ∈ f(j) IFF j ∉ f(j).
This is a contradiction.
Therefore 𝒫(N) is uncountable.
This is an example of a proof by diagonalization.
Given any S ⊆ {1,2,3,4}
we can represent it by the binary sequence S1, S2, S3, S4 of length 4, where
Si= 1ifi∈S
0 if i ∉ S. for example
0,1,1,0 denotes the set {2,3}
0,0,0,0 denotes the empty set.
This sequence is called the characteristic vector of the set.
Likewise, given any S ⊆ N ,
we can represent it by the infinite binary sequence S0, S1, S2, …
where
Si= 1ifi∈S
0 if i ∉ S.
If f is surjective, then f(0),
f(1),
⋮
is a list of all subsets of N, possibly with duplications.
Consider the characteristic vectors of all of these sets. f(0)0, f(0)1,…
f(1)0, f(1)1,…
⋮
This is an infinite 2 dimensional Boolean array M
where M[i,j] = f(i)j In other words, M[i,j]= 1if j∈f(i)
0if j∉f(i)
M0 1 2 3… 01000 10000 21010 30000
⋮
The rows and columns are indexed by the natural numbers.
Row i represents the i’th set in our enumeration.
Note that every set is guaranteed to occur in the list,
but the same set can occur in the list f(0), f(1), f(2),… many times, since f is surjective (onto), but not necessarily injective (1-to-1).
For example,
f(0) could be {0},
f(1) could be the empty set
f(2) could be the set of all even natural numbers f(3) could be the empty set
Consider the set D = { i ∈ N | i ∉ f(i) } ∈ 𝒫(N) Note that the characteristic vector of D is
the complement of the diagonal of M.
The set D can be constructed by going along the diagonal: put i in D if and only if M[i,i] = 0.
By doing so, we ensure that D ≠ f(i) for all i ∈N.
More generally,
THEOREM 8.1.12 Cantor’s theorem
For any set A, there is no surjective function from A to 𝒫(A).
Another example of a diagonalization proof Halting problem (MIT book Section 8.2)
There is a compiler (which is a program) G that determines whether a given ASCII string P is a syntactically correct Python function that takes a string as input
i.e. it that takes a single ASCII string P as input,
outputs True if P is a syntactically correct Python function that takes a string as input
and, outputs False if P is not a syntactically correct Python function.
It is easy to modify a Python compiler to do this.
It would be nice to have a Python program
H that takes as input two strings, P and x, and decides whether
P is a syntactically correct Python function that takes one string as input
and eventually returns (i.e.halts) on input x.
i.e. H(P,x) returns True if
P is a syntactically correct Python function that takes one string as input and returns on input x
and H(P,x) returns False otherwise, i.e. if P is not syntactically correct, or P doesn’t take one string as its input, or if P runs forever (gets into an infinite loop) on input x.
def H(P:str, x:str):
⋮
>>> justreturn = ‘def j(s: str): return s’ >>> H(justreturn, ‘hello’)
True
>>> goforever = ‘def g(s: str): while True: pass’ >>> H(goforever, ‘hello’)
False
The halting problem is to construct such a program H. Unfortunately, the halting problem is unsolvable.
To obtain a contradiction, suppose that such a program H exists.
Consider the syntactically correct Python function D that takes one string as input:
def D(x:str): if H(x,x):
while True: pass else: return True
>>> d = ‘def D(x):\n if H(x,x): \n\t while True: pass\n else: return True’
What happens when D runs on input d? >>> D(d)
from the code of D:
if H(d,d) = False then D(d) returns
if H(d,d) = True then D(d) goes into an infinite loop
from the definition of H:
if D(d) returns, then H(d,d) = True
if D(d) goes into an infinite loop, then H(d,d) = False
There is a contradiction, no matter which case occurs:
if H(d,d) = False then D(d) returns, so H(d,d) = True
if H(d,d) = True then D(d) goes into an infinite loop, so H(d,d) = False. Thus the halting problem is unsolvable.
Pictorially, we can view the function H(P,x) using an infinite matrix whose rows and columns are indexed by the set of all ASCII strings, which is countable.
x
H λ a b c…
λTFFF P aFFFF bTFTF
cFFFF
⋮
If H(x,x) = False then D(x) halts, so H(d,x) = True
If H(x,x) = True then D(x) runs forever, so H(d,x) = False
Thus row d is the complement of the diagonal of the matrix H.
In particular, element d of row d is the complement of element d of the diagonal.
This is a contradiction, since this is the same element.
Reductions
THEOREM There is no Python program A that takes as input a string P
and decides whether P is a syntactically correct Python function
that takes one string as input and eventually returns (i.e.halts) on every input. i.e. A(P) returns True if P is syntactically correct, takes 1 string as input, and returns on all inputs and
A(P) returns False otherwise.
Proof:
To obtain a contradiction, suppose there is such a program A.
Let 𝒞 be the set of all syntactically syntactically correct Python functions that take one string as input.
Let H’ be the Python program that takes two strings P and x as input and behaves as follows:
if P ∉ 𝒞, then return False.
Otherwise, let Q be constructed from P by
adding a new first line
s=x
to its program, where s is the input variable for program P and x is the other input to H’.
output (A(Q))
For example, recall the string justreturn = ‘def j(s: str): return s’
Then H'(justreturn,’hi’) determines that justreturn ∈ 𝒞,
it constructs Q = ‘def j(s:str):\n s = ‘hi’ \n return s’, it runs A on input Q, which returns True,
and returns True.
Similarly, if
goforever = ‘def g(s: str): while True: pass’ Then H'(goforever,’hi’)
determines that goforever ∈ 𝒞,
it constructs Q = ‘def g(s:str):\n s = ‘hi’ \n while True: pass’, it runs A on input Q, which returns False,
and returns False.
Claim: H’ solves the halting problem: Proof:
If P ∉ 𝒞, then H'(P,x) outputs False = H(P,x). So suppose P ∈ 𝒞.
If P halts on input x,
then Q halts on all inputs, so A(Q) returns True and hence H'(P,x) returns True = H(P,x).
If P doesn’t halt on input x,
then, on all inputs, Q doesn’t halt, so A(Q) returns False and hence H'(P,x) returns False = H(P,x).
Hence H’ solves the halting problem. But the halting problem is unsolvable. Hence there is no such program A.
H
EG
true
P X
Fal se Q
A
True1 False
Asymptotic Notation
Let F denote the set of all functions from N to R+ ⋃ {0} , from the natural numbers to the nonnegative real numbers. For any function f ∈ F , let
O(f)={g∈F |∃c∈R+.∃b∈N.∀n∈N. [(n≥b)IMPLIES (g(n)≤cf(n))]}. g ∈ O(f) means that,
for all n sufficiently large (i.e. for all but finitely many n ∈ N), g(n) is at most a constant factor times f(n).
Example:
6n+4isinO(3n)since6n+4 ≤3x 3nforalln≥2. Here c=3 and b=2.
We could also have chosen c=4 and b=1.
If there is one choice for c and b that work,
then there are an infinite number of choices that work.
It is customary in computer science to write O(n2) instead of
O(f), where f(n) = n2 for all n ∈ N.
In other words, we consider n2 to be a function from N to N.
Ω(f)={g∈F |∃c∈R+.∃b∈N.∀n∈N. [(n≥b)IMPLIES (g(n)≥cf(n))]} g ∈ Ω(f) means that,
for all n sufficiently large (i.e. for all but finitely many n ∈ N), g(n) is at least a constant factor times f(n).
(g ∈ Ω(f)) IFF (f ∈ O(g))
θ(f)={g∈F |∃c∈R+.∃c’∈R+.∃b∈N.∀n∈N.
[(n ≥ b) IMPLIES (cf(n) ≤ g(n) ≤ c’f(n))]}
= O(f) ⋂ Ω(f)
PROPERTIES OF O NOTATION
(see summary in Course Materials.)
THEOREM The set of all functions from N to N is uncountable.
Let F be the set of all functions from N to N.
To obtain a contradiction, assume F is countable. Then there is a surjective function f from N to F.
THEOREM The set of all functions from N to N is uncountable.
Let F be the set of all functions from N to N.
To obtain a contradiction, assume F is countable. Then there is a surjective function f from N to F.
Letg bedefinedsothat,foralln∈N,g(n)=fn(n)+1. Since fn : N → N, it follows that fn(n) ∈ N.
Since N is closed under addition, g(n) = fn(n) + 1 ∈ N. Thus g ∈ F.
THEOREM The set of all functions from N to N is uncountable.
Let F be the set of all functions from N to N.
To obtain a contradiction, assume F is countable. Then there is a surjective function f from N to F.
Letg bedefinedsothat,foralln∈N,g(n)=fn(n)+1. Since fn : N → N, it follows that fn(n) ∈ N.
Since N is closed under addition, g(n) = fn(n) + 1 ∈ N. Thus g ∈ F.
Since f is surjective, there exists n ∈ N such that g = fn. By definition, g(n) = fn(n) + 1 ̸= fn(n) = g(n).
This is a contradiction. Thus F is uncountable.
THEOREM The set of all functions from N to N is uncountable.
Let F be the set of all functions from N to N.
To obtain a contradiction, assume F is countable. Then there is a surjective function f from N to F.
Letg bedefinedsothat,foralln∈N,g(n)=fn(n)+1. Since fn : N → N, it follows that fn(n) ∈ N.
Since N is closed under addition, g(n) = fn(n) + 1 ∈ N. Thus g ∈ F.
Since f is surjective, there exists n ∈ N such that g = fn. By definition, g(n) = fn(n) + 1 ̸= fn(n) = g(n).
This is a contradiction. Thus F is uncountable.
012···
f0 f0 (0)
f1 f1 (0)
f2 f2 (0)
.
f0 (1) f1 (1) f2 (1)
f0 (2) f1 (2) f2 (2)
Solutions to
CSC240 Winter 2021 Homework Assignment 6
1. This is known as Kraft’s Inequality.
Let P : B → {T, F} be the predicate such that, for every binary tree T ∈ B,
P(T) = “ 2−depth(T,x) ≤ 1”. x∈leaves(T )
To obtain a contradiction, assume that ∀T ∈ B.P (T ) is false.
Let C = {T ∈ B | NOT (P(T))} be the set of counterexamples to P.
By assumption, C ̸= φ. Since ≼ is a well ordering of B, the well ordering principle implies that C has a smallest element, T .
If T is the empty binary tree, then it has no leaves, so
x∈leaves(T ) Thus T is not the empty binary tree.
2−depth(T,x) = 0 ≤ 1.
If T consists of a single node, then it has one leaf of depth 0, so
2−depth(T,x) = 2−0 = 1. Therefore T contains at least two nodes.
Let L = T.left and R = T.right be the left and right subtrees of T. If P(L) and P(R) are both true, then
2−depth(L,x) ≤ 1 and 2−depth(R,x) ≤ 1. x∈leaves(L) x∈leaves(R)
Note that, for every node x in L, depth(T, x) = depth(L, x) + 1, since the unique path from x to the root of T consists of the unique path from x to the root of L followed by the edge from the root of L to the root of T. Similarly, for every node x in R, depth(T,x) = depth(R,x)+1.
Since the root of T is not a leaf, leaves(T) is the disjoint union of leaves(L) and leaves(R). It follows that
x∈leaves(T )
2−depth(T ,x)
= 2−depth(T,x) + 2−depth(T,x) x∈leaves(L) x∈leaves(R)
x∈leaves(T )
= 2−depth(L,x)−1 + x∈leaves(L) x∈leaves(R)
= 1 2−depth(L,x) + 1
2−depth(R,x)−1 2−depth(R,x)
22
x∈leaves(R)
x∈leaves(L) ≤ 1·1+1·1
22 = 1.
1
Thus P(T) is true. This is a contradiction. Hence, at least one of P(L) and P(R) is false and at least one of L and R is in C.
ButL≼T andR≼T,contradictingthedefinitionofT. ThusC=φand∀T ∈B.P(T)is true.
2. To obtain a contradiction, suppose there is such a program E.
Let C be the set of all syntactically correct Python functions that takes one string as input.
Let H′ be the Python program that takes two strings P and x as input and behaves as follows: if P ∈ C , then return False. Otherwise, let P′ be constructed from P by adding a new first line s = x to its program, where s is the input variable for function P and x is the other input to H′, and changing all the return statements of P to return True. Let Q = ′def j(s: str): return True′. Finally, H′ runs E(P′,Q) and outputs the result.
Note that Q halts and returns True on every input y. If P ̸∈ C, then H′(P, x) outputs False.
If P halts on input x, then P ′ halts and returns True on every input y. Thus E(P ′, Q) returns True and H′(P,x) returns True.
If P doesn’t halt on input x, then P′ doesn’t halt on any input y. Thus E(P′,Q) returns False and H′(P,x) returns False.
Hence H′(P,x) solves the halting problem. This is impossible. Therefore, there is no such program E.
2
Proof Outlines
LINE NUMBERS: Only lines that are referred to have labels (for example, L1) in this document. For a formal proof, all lines are numbered. Line numbers appear at the beginning of a line. You can indent line numbers together with the lines they are numbering or all line numbers can be unindented, provided you are consistent.
INDENTATION: Indent when you make an assumption or define a variable. Unindent when this assumption or variable is no longer being used.
1. Implication: Direct proof of A IMPLIES B.
L1. Assume A.
.
L2. B
A IMPLIES B; direct proof: L1, L2
2. Implication: Indirect proof of A IMPLIES B.
L1. Assume NOT(B).
.
L2. NOT(A)
A IMPLIES B; indirect proof: L1, L2
3. Equivalence: Proof of A IFF B.
L1. Assume A.
.
L2. B
L3. A IMPLIES B; direct proof: L1, L2
L4. Assume B.
.
L5. A
L6. B IMPLIES A; direct proof: L4, L5 A IFF B; equivalence: L3, L6
4. Proof by contradiction of A.
L1. To obtain a contradiction, assume NOT(A). .
L2. B .
L3. NOT(B)
L4. This is a contradiction: L2, L3
Therefore A; proof by contradiction: L1, L4
1
5. Modus Ponens.
.
L1. A
.
L2. A IMPLIES B
B; modus ponens: L1, L2
6. Conjunction: Proof of A AND B:
.
L1. A
.
L2. B
A AND B; proof of conjunction; L1, 2
7. Use of Conjunction: .
L1. A AND B
A; use of conjunction: L1 B; use of conjunction: L1
8. Implication with Conjunction: Proof of (A1 AND A2) IMPLIES B.
L1. Assume A1 AND A2. A1; use of conjunction, L1 A2; use of conjunction, L1
.
L2. B
(A1 AND A2) IMPLIES B; direct proof, L1, L2
9. Implication with Conjunction: Proof of A IMPLIES (B1 AND B2).
L1. Assume A. .
L2. B1
.
L3. B2
L4. B1 AND B2; proof of conjunction: L2, L3 A IMPLIES (B1 AND B2); direct proof: L1, L4
10. Disjunction: Proof of A OR B and B OR A. .
L1. A
A OR B; proof of disjunction: L1 B OR A; proof of disjunction: L1
2
11. Proof by cases.
L1. C OR NOT(C) tautology
L2. Case 1: Assume C. .
L3. A
L4. C IMPLIES A; direct proof: L2, L3
L5. Case 2: Assume NOT(C). .
L6. A
L7. NOT(C) IMPLIES A; direct proof: L5, L6
A proof by cases: L1, L4, L7 12. Proof by cases of A OR B.
L1. C OR NOT(C) tautology L2. Case 1: Assume C.
.
L3. A
L4. A OR B; proof of disjunction, L3 L5. C IMPLIES (A OR B); direct proof, L2, L4
L6. Case 2: Assume NOT(C). .
L7. B
L8. A OR B; proof of disjunction, L7
L9. NOT(C) IMPLIES (A OR B); direct proof: L6, L8 A OR B; proof by cases: L1, L5, L9
13. Implication with Disjunction: Proof by cases of (A1 OR A2) IMPLIES B.
L1. Case 1: Assume A1. .
L2. B
L3. A1 IMPLIES B; direct proof: L1,L2
L4. Case 2: Assume A2. .
L5. B
L6. A2 IMPLIES B; direct proof: L4, L5
(A1 OR A2) IMPLIES B; proof by cases: L3, L6
3
14. Implication with Disjunction: Proof by cases of A IMPLIES (B1 OR B2).
L1. Assume A.
L2. C OR NOT(C) tautology L3. Case 1: Assume C.
.
L4. B1
L5. B1 OR B2; disjunction: L4
L6. C IMPLIES (B1 OR B2); direct proof: L3, L5 L7. Case 2: AssumeNOT(C).
.
L8. B2
L9. B1 OR B2; disjunction: L8
L10. NOT(C) IMPLIES (B1 OR B2); direct proof: L7, L9 L11. B1 OR B2; proof by cases: L2, L6, L10
A IMPLIES (B1 OR B2): direct proof. L1, L11
15. Substitution of a Variable in a Tautology:
Suppose P is a propositional variable, Q is a formula, and R′ is obtained from R by replacing every occurrence of P by (Q).
L1. R tautology
R′; substitution of all P by Q: L1
16. Substitution of a Formula by a Logically Equivalent Formula:
Suppose S is a subformula of R and R′ is obtained from R by replacing some occurrence of S by S′.
L1. R
L2. S IFF S′
L3. R′; substitution of an occurrence of S by S′: L1, L2
17. Specialization:
L1. c ∈ D
L2. ∀x∈D.P(x)
P(c); specialization: L1, L2
18. Generalization: Proof of ∀x ∈ D.P (x).
L1. Let x be an arbitrary element of D.
.
L2. P(x)
Since x is an arbitrary element of D, ∀x ∈ D.P (x); generalization: L1, L2
4
19. Universal Quantification with Implication: Proof of ∀x ∈ D.(P (x) IMPLIES Q(x)). L1. Let x be an arbitrary element of D.
L2. Assume P(x)
.
L3. Q(x)
L4. P(x) IMPLIES Q(x); direct proof: L2, L3
Since x is an arbitrary element of D,
∀x ∈ D.(P (x) IMPLIES Q(x)); generalization: L1, L4
20. Implication with Universal Quantification: Proof of (∀x ∈ D.P (x)) IMPLIES A.
L1. Assume ∀x ∈ D.P (x). .
L2. a ∈ D
P(a); specialization: L1, L2
.
L3. A
Therefore (∀x ∈ D.P (x)) IMPLIES A; direct proof: L1, L3
21. Implication with Universal Quantification: Proof of A IMPLIES (∀x ∈ D.P (x)).
L1. Assume A.
L2. Let x be an arbitrary element of D.
.
L3. P(x)
Since x is an arbitrary element of D, L4. ∀x ∈ D.P (x); generalization, L2, L3
A IMPLIES (∀x ∈ D.P (x)); direct proof: L1, L4
22. Instantiation:
L1. ∃x∈D.P(x)
Let c ∈ D be such that P (c); instantiation: L1
.
23. Construction: Proof of ∃x ∈ D.P (x).
L1. Let a = · · · .
L2. a ∈ D
.
L3. P(a)
∃x ∈ D.P (x); construction: L1, L2, L3
5
24. Existential Quantification with Implication: Proof of ∃x ∈ D.(P (x) IMPLIES Q(x)).
L1. Let a = · · ·
.
L2. a ∈ D
L3. Suppose P(a).
.
L4. Q(a)
L5. P(a) IMPLIES Q(a); direct proof: L3, L4
∃x ∈ D.(P (x) IMPLIES Q(x)); construction: L1, L2, L5
25. Implication with Existential Quantification: Proof of (∃x ∈ D.P (x)) IMPLIES A.
L1. Assume ∃x ∈ D.P (x).
Let a ∈ D be such that P (a); instantiation: L1
.
L2. A
(∃x ∈ D.P (x)) IMPLIES A; direct proof: L1, L2
26. Implication with Existential Quantification: Proof of A IMPLIES (∃x ∈ D.P (x)).
L1. Assume A.
L2. Let a = · · ·
.
L3. a ∈ D .
L4. P(a)
L5. ∃x ∈ D.P (x); construction: L2, L3, L4
A IMPLIES (∃x ∈ D.P (x)); direct proof: L1, L5 27. Subset: Proof of A ⊆ B.
L1. Let x ∈ A be arbitrary. .
L2. x ∈ B
The following line is optional:
L3. x ∈ A IMPLIES x ∈ B; direct proof: L1, L2
A ⊆ B; definition of subset: L3 (or L1, L2, if the optional line is missing)
6
28. Weak Induction: Proof of ∀n ∈ N.P(n)
Base Case:
.
L1. P(0)
L2. Let n ∈ N be arbitrary.
L3. Assume P(n).
.
L4. P(n+1)
The following two lines are optional:
L5. P (n) IMPLIES (P (n + 1); direct proof of implication: L3, L4
L6. ∀n ∈ N.(P (n) IMPLIES P (n + 1)); generalization L2, L5
∀n ∈ N.P(n) induction; L1, L6 (or L1, L2, L3, L4, if the optional lines are missing)
29. Strong Induction: Proof of ∀n ∈ N.P(n) L1. Let n ∈ N be arbitrary.
L2. Assume ∀j ∈ N.(j < n IMPLIES P(j))
.
L3. P(n)
The following two lines are optional:
L4. ∀j ∈ N.(j < n IMPLIES P(j)) IMPLIES P(n); direct proof of implication: L2, L3
L5. ∀n ∈ N.[∀j ∈ N.(j < n IMPLIES P(j)) IMPLIES P(n)]; generalization: L1, L4 ∀n ∈ N.P(n); strong induction: L5 (or L1, L2, L3, if the optional lines are missing)
30. Structural Induction: Proof of ∀e ∈ S.P (e), where S is a recursively defined set
Base case(s):
L1. For each base case e in the definition of S L2. P(e).
Constructor case(s):
L3. For each constructor case e of the definition of S,
L4. assume P(e′) for all components e′ of e.
.
L5. P(e)
∀e ∈ S.P (e); structural induction: L1, L2, L3, L4, L5
7
31. Well Ordering Principle: Proof of ∀e ∈ S.P (e), where S is a well ordered set, i.e. every nonempty subset of S has a smallest element.
L1. To obtain a contradiction, suppose that ∀e ∈ S.P (e) is false.
L2. Let C = {e ∈ S | P(e) is false} be the set of counterexamples to P. L3. C ̸= φ; definition: L1, L2
L4. Let e be the smallest element of C; well ordering principle: L2, L3 Let e′ = · · ·
.
L5. e′ ∈C .
L6. e′ < e.
L7. This is a contradiction: L4, L5, L6
∀e ∈ S.P (e); proof by contradiction: L1, L7
8