6.042/18.062J Mathematics for Computer Science February 1,2005
Srini Devadas and Eric Lehman
Problem Set 1 Solutions
Due,Monday,February 7 at 9 PM
Problem 1,The connectives ∧(and),∨(or),and?(implies) come often not only in com-
puter programs,but also everyday speech,But devices that compute the nand operation
are preferable in computer chip designs,Here is the truth table for nand,
P Q
T T F
T F T
F T T
F F T
P nand Q
For each of the following expressions,?nd an equivalent expression using only nand and
(not),
(a) A∧B
Solution,?(A nand B)
(b) A∨B
Solution,(?A) nand (?B)
(c) A B?
Solution,A nand (?B)
Problem 2,A self-proclaimed,great logician” has invented a new quanti?er,on par with
(“there exists”) and?(“for all”),The new quanti?er is symbolized by U and read,there
exists a unique”,The proposition UxP(x) is true iff there is exactly one xfor which P(x) is
true,The logician has noted,“There used to be two quanti?ers,but now there are three! I
have extended the whole?eld of mathematics by 50%!”
(a) Write a proposition equivalent to Ux P(x) using only the? quanti?er,=,and
logical connectives,
Solution,
x (P(x)∧?(?y (?(x = y)∧P(y)))?
2 Problem Set 1
(b) Write a proposition equivalent to Ux P(x) using only the? quanti?er,=,and
logical connectives,
Solution,
= y ∨?P(y)))x (?P(x)∨y (x
Problem 3,A media tycoon has an idea for an all-news television network called LNN,
The Logic News Network,Each segment will begin with the de?nition of some relevant
sets and predicates,The day’s happenings can then be communicated concisely in logic
notation,For example,a broadcast might begin as follows,
“THIS IS LNN,Let S be the set {Bill,Monica,Ken,Linda,Betty},Let D(x) be
a predicate that is true if x is deceitful,Let L(x,y) be a predicate that is true if
x likes y,Let G(x,y) be a predicate that is true if x gave gifts to y.”
Complete the broadcast by translating the following statements into logic notation,
(a) If neither Monica nor Linda is deceitful,then Bill and Monica like each other,
Solution,
(?(D(Monica)∨D(Linda)))? (L(Bill,Monica)∧L(Monica,Bill))
(b) Everyone except for Ken likes Betty,and no one except Linda likes Ken,
Solution,
x ∈ S (x = Ken ∧?L(x,Betty)) ∨(x = Ken ∧L(x,Betty)) ∧? ?
x ∈ S (x = Linda ∧L(x,Ken)) ∨(x = Linda ∧?L(x,Ken))? ?
(c) If Ken is not deceitful,then Bill gave gifts to Monica,and Monica gave gifts to
someone,
Solution,
D(Ken)? (G(Bill,Monica)∧?x ∈ S G(Monica,x))
(d) Everyone likes someone and dislikes someone else.
Solution.
= z)∧L(x,y)∧?L(x,z)x ∈ S?y ∈ S?z ∈ S (y? ?
The remaining problems will be graded primarily on the clarity of
your proofs— not on whether you have the right idea,In fact,if you
can’t?gure out the right idea,we’ll give it to you– just ask your TA!
3 Problem Set 1
Problem 4,Let n be a postive integer,Prove that log
2
n is rational if and only if n is
a power of 2,Assume any basic facts about divisibility that you need; just state your
assumptions explicitly,
Solution,Assumption,If n
b
is a power of 2,then n is a power of 2,
Proof,We prove that if n is a power of 2,then log
2
n is rational and vice-versa,
First,we prove that if n is a power of 2,then log
2
n is rational,Assume that n is a power
of 2,Then n = 2
k
for some integer k ≥ 0,Thus,log
2
n = log
2
2
k
= k,which is a rational
number,
Next,we prove that if log
2
n is rational,then n is a power of 2,Assume that log
2
n is
rational,That means there exist integers a and b such that,
a
log
2
n =
b
We can rewrite this equation as follows,
n = 2
a/b
(Take 2 to power of each side.)
n
b
= 2
a
(Take the b-th power of each side.)
Thus,n
b
is a power of 2,By our assumption,n is a power of 2,
Problem 5,A triangle is a set of three people such that either every pair has shaken hands
or no pair has shaken hands,Prove that among every six people there is a triangle,Sug-
gestion,Initially,break the problem into two cases,
1,There exist at least three people who shook hands with person X,
2,There exist at least three people didn’t shake hands with X
(Why must at least one of these conditions hold?)
Solution,
Proof,We use case analysis,Let X denote one of the six people,There are two possibili-
ties,
1,There exist three people who shook hands with person X,Now there are two fur-
ther possibilities,
(a) Among these three,some pair shook hands. Then these two and X form a
triangle,
(b) Among these three,no pair shook hands,Then these three form a triangle,
4 Problem Set 1
2,Otherwise,at most two people shook hands with person X,Thus,there exist three
people who didn’t shake hands with X,Again,there are two further possibilities,
(a) Among these three,every pair shook hands,Then these three form a triangle,
(b) Among these three,some pair didn’t shake hands,Then these two and X for a
triangle,
Problem 6,Let x and y be nonnegative real numbers,The arithmetic mean of x and y
is de?ned to be (x + y)/2,and the geometric mean is de?ned to be
√
xy,Prove that the
arithmetic mean is equal to the geometric mean if and only if x = y,
Solution,
Proof,We construct a chain of if-and-only-if implications,The arithmetic mean is equal
to the geometric mean if and only if,
x + y
=
√
xy x + y = 2
√
xy
2
(x + y)
2
= 4xy?
2
x
2
+ 2xy + y = 4xy?
2
x? 2xy + y
2
= 0
(x? y)
2
= 0
x? y = 0
x = y
Problem 7,Use case analysis to prove that all integral solutions to the equation
1 1 1 1
+ = +
m n e 2
subject to these constraints
e > 0m ≥ 3 n ≥ 3
are in this table,
m n e
3 3 6
3 4 12
3 5 30
4 3 12
5 3 30
These equations reveal something fundamental about the geometry of our three-dimensional
world; we’ll revisit them in about three weeks,
5 Problem Set 1
Solution,
Proof,We use case analysis,Since m ≥ 3,one of four cases must hold,
1,m = 3,There are now four subcases,
(a) n = 3,Rewriting the equation in the form
1
e =
1
+
1
nm
1
2
and subtituting in m = n = 3 implies that e = 6,which is the?rst solution,
(b) n = 4,Substituting the values of m and n into the equation show that e = 12,
which is the second solution,
(c) n = 5,Substituting into the equation shows that e = 30,which is the third
solution,
(d) n ≥ 6,This implies,
1 1 1 1 1
m
+
n
≤
3
+
6
=
2
Thus,the left side of the equation is strictly less than the right for all e > 0,so
there are no solutions in this case,
2,m = 4,There are two subcases,
(a) n = 3,Subsituting gives e = 12,which is the fourth solution,
(b) n ≥ 4,This implies,
1 1 1 1 1
+ =
m
+
n
≤
4 4 2
Again,the left side of the equation is strictly less than the right for all e > 0,so
there are no solutions in this case,
3,m = 5,There are two subcases,
(a) n = 3,Subsituting gives e = 30,which is the?fth solution,
(b) n ≥ 4,This implies,
1 1 1 1 1
+ <
m
+
n
≤
5 4 2
Again,the equation can not hold,so there are no solutions in this case,
4,m ≥ 6,This implies,
1 1 1 1 1
+ =
m
+
n
≤
6 3 2
Once more,the equation can not hold,so there are no solutions in this case,
Srini Devadas and Eric Lehman
Problem Set 1 Solutions
Due,Monday,February 7 at 9 PM
Problem 1,The connectives ∧(and),∨(or),and?(implies) come often not only in com-
puter programs,but also everyday speech,But devices that compute the nand operation
are preferable in computer chip designs,Here is the truth table for nand,
P Q
T T F
T F T
F T T
F F T
P nand Q
For each of the following expressions,?nd an equivalent expression using only nand and
(not),
(a) A∧B
Solution,?(A nand B)
(b) A∨B
Solution,(?A) nand (?B)
(c) A B?
Solution,A nand (?B)
Problem 2,A self-proclaimed,great logician” has invented a new quanti?er,on par with
(“there exists”) and?(“for all”),The new quanti?er is symbolized by U and read,there
exists a unique”,The proposition UxP(x) is true iff there is exactly one xfor which P(x) is
true,The logician has noted,“There used to be two quanti?ers,but now there are three! I
have extended the whole?eld of mathematics by 50%!”
(a) Write a proposition equivalent to Ux P(x) using only the? quanti?er,=,and
logical connectives,
Solution,
x (P(x)∧?(?y (?(x = y)∧P(y)))?
2 Problem Set 1
(b) Write a proposition equivalent to Ux P(x) using only the? quanti?er,=,and
logical connectives,
Solution,
= y ∨?P(y)))x (?P(x)∨y (x
Problem 3,A media tycoon has an idea for an all-news television network called LNN,
The Logic News Network,Each segment will begin with the de?nition of some relevant
sets and predicates,The day’s happenings can then be communicated concisely in logic
notation,For example,a broadcast might begin as follows,
“THIS IS LNN,Let S be the set {Bill,Monica,Ken,Linda,Betty},Let D(x) be
a predicate that is true if x is deceitful,Let L(x,y) be a predicate that is true if
x likes y,Let G(x,y) be a predicate that is true if x gave gifts to y.”
Complete the broadcast by translating the following statements into logic notation,
(a) If neither Monica nor Linda is deceitful,then Bill and Monica like each other,
Solution,
(?(D(Monica)∨D(Linda)))? (L(Bill,Monica)∧L(Monica,Bill))
(b) Everyone except for Ken likes Betty,and no one except Linda likes Ken,
Solution,
x ∈ S (x = Ken ∧?L(x,Betty)) ∨(x = Ken ∧L(x,Betty)) ∧? ?
x ∈ S (x = Linda ∧L(x,Ken)) ∨(x = Linda ∧?L(x,Ken))? ?
(c) If Ken is not deceitful,then Bill gave gifts to Monica,and Monica gave gifts to
someone,
Solution,
D(Ken)? (G(Bill,Monica)∧?x ∈ S G(Monica,x))
(d) Everyone likes someone and dislikes someone else.
Solution.
= z)∧L(x,y)∧?L(x,z)x ∈ S?y ∈ S?z ∈ S (y? ?
The remaining problems will be graded primarily on the clarity of
your proofs— not on whether you have the right idea,In fact,if you
can’t?gure out the right idea,we’ll give it to you– just ask your TA!
3 Problem Set 1
Problem 4,Let n be a postive integer,Prove that log
2
n is rational if and only if n is
a power of 2,Assume any basic facts about divisibility that you need; just state your
assumptions explicitly,
Solution,Assumption,If n
b
is a power of 2,then n is a power of 2,
Proof,We prove that if n is a power of 2,then log
2
n is rational and vice-versa,
First,we prove that if n is a power of 2,then log
2
n is rational,Assume that n is a power
of 2,Then n = 2
k
for some integer k ≥ 0,Thus,log
2
n = log
2
2
k
= k,which is a rational
number,
Next,we prove that if log
2
n is rational,then n is a power of 2,Assume that log
2
n is
rational,That means there exist integers a and b such that,
a
log
2
n =
b
We can rewrite this equation as follows,
n = 2
a/b
(Take 2 to power of each side.)
n
b
= 2
a
(Take the b-th power of each side.)
Thus,n
b
is a power of 2,By our assumption,n is a power of 2,
Problem 5,A triangle is a set of three people such that either every pair has shaken hands
or no pair has shaken hands,Prove that among every six people there is a triangle,Sug-
gestion,Initially,break the problem into two cases,
1,There exist at least three people who shook hands with person X,
2,There exist at least three people didn’t shake hands with X
(Why must at least one of these conditions hold?)
Solution,
Proof,We use case analysis,Let X denote one of the six people,There are two possibili-
ties,
1,There exist three people who shook hands with person X,Now there are two fur-
ther possibilities,
(a) Among these three,some pair shook hands. Then these two and X form a
triangle,
(b) Among these three,no pair shook hands,Then these three form a triangle,
4 Problem Set 1
2,Otherwise,at most two people shook hands with person X,Thus,there exist three
people who didn’t shake hands with X,Again,there are two further possibilities,
(a) Among these three,every pair shook hands,Then these three form a triangle,
(b) Among these three,some pair didn’t shake hands,Then these two and X for a
triangle,
Problem 6,Let x and y be nonnegative real numbers,The arithmetic mean of x and y
is de?ned to be (x + y)/2,and the geometric mean is de?ned to be
√
xy,Prove that the
arithmetic mean is equal to the geometric mean if and only if x = y,
Solution,
Proof,We construct a chain of if-and-only-if implications,The arithmetic mean is equal
to the geometric mean if and only if,
x + y
=
√
xy x + y = 2
√
xy
2
(x + y)
2
= 4xy?
2
x
2
+ 2xy + y = 4xy?
2
x? 2xy + y
2
= 0
(x? y)
2
= 0
x? y = 0
x = y
Problem 7,Use case analysis to prove that all integral solutions to the equation
1 1 1 1
+ = +
m n e 2
subject to these constraints
e > 0m ≥ 3 n ≥ 3
are in this table,
m n e
3 3 6
3 4 12
3 5 30
4 3 12
5 3 30
These equations reveal something fundamental about the geometry of our three-dimensional
world; we’ll revisit them in about three weeks,
5 Problem Set 1
Solution,
Proof,We use case analysis,Since m ≥ 3,one of four cases must hold,
1,m = 3,There are now four subcases,
(a) n = 3,Rewriting the equation in the form
1
e =
1
+
1
nm
1
2
and subtituting in m = n = 3 implies that e = 6,which is the?rst solution,
(b) n = 4,Substituting the values of m and n into the equation show that e = 12,
which is the second solution,
(c) n = 5,Substituting into the equation shows that e = 30,which is the third
solution,
(d) n ≥ 6,This implies,
1 1 1 1 1
m
+
n
≤
3
+
6
=
2
Thus,the left side of the equation is strictly less than the right for all e > 0,so
there are no solutions in this case,
2,m = 4,There are two subcases,
(a) n = 3,Subsituting gives e = 12,which is the fourth solution,
(b) n ≥ 4,This implies,
1 1 1 1 1
+ =
m
+
n
≤
4 4 2
Again,the left side of the equation is strictly less than the right for all e > 0,so
there are no solutions in this case,
3,m = 5,There are two subcases,
(a) n = 3,Subsituting gives e = 30,which is the?fth solution,
(b) n ≥ 4,This implies,
1 1 1 1 1
+ <
m
+
n
≤
5 4 2
Again,the equation can not hold,so there are no solutions in this case,
4,m ≥ 6,This implies,
1 1 1 1 1
+ =
m
+
n
≤
6 3 2
Once more,the equation can not hold,so there are no solutions in this case,
