ICS 6D – Discrete Mathematics
– Winter 2009
Homework Assignments
Unless
otherwise indicated, all exercises from Rosen’s textbook.
Make
sure that your full name and student
number is on the first page of your homework and that all pages are stapled securely. Deliver the homework to the TA either during
the lecture or before your discussion session.
Take photocopies of your submissions if you want to compare your
solutions to the solutions we will distribute on the day the homework is
due. Remember that homework is by
default graded for completeness, but answers
which are obviously sloppily written or obviously incorrect will receive zero
points. We will mark questions which
will be graded in detail with an asterisk.
The homework score is made in 80% of the homework grade for completeness
of answers to questions without an asterisk, and 20% of the homework grade for
correctness of answers questions with asterisks.
- Homework #1, due Monday,
January 12.
Here you can download: the scan of the
homework questions, and the scan of
solutions to odd-numbered quetsions.
- Section 1.1: 2, 6, 8, 10, 12, 14, 16 [explanation
required!], 18 [your answer, in each case, should be a definition of what
are propositions p and q so that the given statement is indeed expressed
as “p -> q”], 24 [just a and b, state each as an English sentence],
28, 44, 46, 56, 58*, 62.
(Solutions to
Even-Numbered Exercises in Section 1.1)
- Section 1.2: 6, 8, 10 [also, think a little bit
*why* each of these statements is a tautology…], 12 [but only for 10b],
20, 26, 40 [try to find a compound proposition which expresses the same
statement in a shortest way, i.e. “a -> b” is preferable from “(a and
b) or (not a)” because both statements are equivalent but the first one
is shorter], 44*, 60
(Solutions to
Even-Numbered Exercises in Section 1.2)
- Section 1.3: Postponed till next week (see below).
- Homework #2, due Wednesday,
January 21 (Not Monday, 1/19, because it's the MLK Holiday!)
- Section 1.3: 2, 4, 8, 10, 12, 14, 18 [assume the domain
includes just 0, 1, and 2], 22, 24, 26 [in your answers to 24 and 26
define any prepositional variables or predicates or sets you use!], 32,
36, 42, 50, 60*
(Solutions to
Even-Numbered Exercises in Section 1.3)
- Section 1.4: 4 [just
use the words "some" and "all"..., e.g. 4a can be
"some student has taken some class"], 6, 8 [by "logical
connectives" they mean logical operations like and, or, not, ...],
10, 12 [you can use "J" for "Jerry", "R"
for "Rachel", etc], 16 [assume an implicit domain for any
variable is either the set of students in this class or the set of
majors, and define the predicates you use, e.g. J(x) = "x is a
junior"], 20, 26*, 28, 30 [use DeMorgan's low for quantified formulas
(and for conjunctions and disjunctions)], 38 [when using quantifiers you
can use implicitely defined predicates, e.g. the statement "All
students hate some homework problems" using quantifiers can be
stated as "\forall(student) \exists(hmw) hate(student,hmw)",
where "\forall" and "\exists" stand for respectively
the universal and the existential quantifier (it's hard to render those
in html...), and so the negation of that statement can be stated with
quantifiers as "\exists(student) \forall(hmw) \not
hate(student,hmw)", where "\not" stands for a negation
sign, and then in English this can be stated as "Some students like
all homework".], 40, 52*
(Solutions to
Even-Numbered Exercises in Section 1.4)
- Section 1.5: 4, 10
[please do exercise 10 as follows: First label each elementary variable,
then label the given premises as p1,p2,..., and express these premises as
logical formulas on these variables, and then for each conclusion (or
intermediary premise) you draw state which law of inference you used on
which premises. For example, in 10(a) if you label a="I play
hockey", b="I'm sore the next day", c="I use the
whirlpool", then you should should express the three given premises
as p1 = (a -> b), p2 = (b -> c), and p3 = (not c). Then the first
derivation you can make is that p4 = (not b), i.e. "I wasn't
sore", by using modus tollens on p2 and p3, and the second one is p5
= (not a), i.e. "I haven't played hockey", by using modus
tollens this time on p1 and p4.], 14*, 16, 18, 22, 24 [but there's a typo
in step 7: It should be \forall_x P(x) \conjunction \forall_x Q(x), i.e.
a conjunction of (4) and (6)], 34
(Solutions to Even-Numbered
Exercises in Section 1.5)
- Homework #3, due Monday,
January 26:
- Section 2.1: 6, 8, 12, 14, 16, 18, 20 [argue why],
22, 24, 36, 38
(Solutions to
Even-Numbered Exercises in Section 2.1)
- Section 2.2: 2, 4, 8, 12, 16 [give a proof for each statement:
each proof should be very short!], 18 [give proofs: each proof should be
very short], 20 [give a proof], 24 [give a proof], 26, 30 [just say yes
or no], 36 [read up the definition of symmetric difference between sets,
and give a proof], 46, 48
(Solutions to
Even-Numbered Exercises in Section 2.2)
- Homework #4, due Monday, Feb
2:
- Section 2.3: 2, 6, 8, 10, 12, 14, 18, 22*, 26, 28,
32, 36, 52, 68, 70
(Solutions to
Even-Numbered Exercises in Section 2.3)
- Homework #5, due Monday, Feb
9:
- Section 3.4:
6, 8, 10, 16, 18, 24 (hint: let n=8*q+r where q is the quotient and r the remainder, and then consider different cases for r...), 28, 32
(Solutions to
Even-Numbered Exercises in Section 3.4)
- Section 3.5:
2, 4, 6, 10, 12, 20, 22, 24, 26 (and what are these two numbers?), 32, 36
(Solutions to
Even-Numbered Exercises in Section 3.5)
- Section
3.6: 2, 4, 6, 8, 12
(don't show it: just convince yourself it's true), 24 (a-c), 26,
28, 32, 34, 36 (use 34 and 35..), 38, 40, 42 (use 40 and 41...),
(Solutions to
Even-Numbered Exercises in Section 3.6)