Rachel W. Hall
Department of Math and CS
St. Joseph's University
5600 City Ave.
Philadelphia, PA 19131
Homework Help for my Discrete Structures class
Here's how it works: any student in my class can e-mail
me for help with the homework. I'll write back to the student individually,
and also post the student's question anonymously, along with my answer.
Question. I am not sure how to answer #4 in section 5.2, i dont know what kind of answers are need to answer the problem correctly.
Answer. I would compare the proof with p. 245 and
the proof on p. 250
to get an idea of the language typically used in these proofs.
Question. Regarding #4 in section 3.6, what is the best way to prove by contradiction that there is no least positive raional number?
Answer. There is a similar example in the book (proving
there is no greatest integer) and also one we did in class (there
is no least real number). Basically you just need to tweak these
a little.
Question. Regarding #21 in section 3.6, I suppose that there exists some pair of irrational numbers x and y such that xy is rational. Then, xy=a/b for some integers a and b with b not equal to 0. But because x and y irrational, I don't know what substitutions I can make in order to find a contradiction.
Answer. Try thinking about how we found a contradiction
to "the sum of any two irrational numbers is irrational"---the
idea is to choose irrational numbers like (1 - pi) and (3 + pi) so
that when you add them, the irrational part cancels.
Can you see how to divide two irrational numbers so that the irrational part cancels? Can you write this as a product?
Question. Regarding #13 in section 3.8. once I find that gcd(1001, 544) = gcd(22, 21), do I just conclude that they do not have a common divisor?
Answer. To complete the algorithm,
gcd(22, 21) = gcd(21, 1) = gcd(1,0) = 1
The algorithm does not terminate until the remainder is 0.
Question. Regarding #36 in Section 3.3 part b, what is the best way to determine how many zeros are at the end of (20!)?
Answer. The number of zeros at the end of a number is equal to the number of factors of 10 it has. For example
102 x 20 x 15 x 4 = 102 x 10 x 2 x 5 x 3 x 4 = 104 x 12
so 102 x 20 x 15 x 4
has 4 zeros at the end.
Question. I was working on question #25 in section 1.3 and attempted to check my answer through a truth table, as we did in class on one of the questions. However, after filling in the truth table, I did not really know what to look for to see if my answer was correct. I completed the truth table as follows:
| p | q | r | p->q | q->r | ~p->~r |
| T | T | T | T | T | T |
| T | T | F | T | F | T |
| T | F | T | F | T | T |
| T | F | F | F | T | T |
| F | T | T | T | T | F |
| F | T | F | T | F | T |
| F | F | T | T | T | F |
| F | F | F | T | T | T |
My work for # 25 was:
p->q
q ->r
.: ~p->~r
My question is : How would I use this truth table to prove my answer to #25?
Answer. I've got a few comments on what you've done so far:
--To answer your question, first you need to identify all the critical rows (that is, rows where all the premises are true). If the conclusion is true in ALL the critical rows, then the argument is valid. If the conclusion is false in ONE OR MORE critical rows, then the argument is invalid. According to the truth table you have now, the argument is invalid. Can you see which row is the problem?
--You made an error in the conclusion ~p -> ~r. Do you see what it should be?
--The book actually only asks you to identify the rule of inference (or type of error) used in the argument. Although making a truth table is great practice, you didn't have to do it here.
I hope this helps....
Question. i saw on the help page that someone had asked about #25 of Section 1.3 do i have to use a truth table to solve the problem, or can i use the hypothetical syllogism inverse error???
Answer. The problem only asks you to identify the rule or error, not make a truth table. Be careful... this argument IS valid. Can you see why?
Question. i'm really frustrated with Section 1.2, #14...i've
walked away from it and came back about five different times in the past
three or four days. this is what i have so far...
| p | q | r | qVr | p^~q | p^~r | p->qVr | p^~q->r | p^~r->q |
| T | T | T | T | F | F | T | F | F |
| T | T | F | T | F | T | T | F | T |
| T | F | T | T | T | F | T | T | F |
| T | F | F | F | T | T | F | F | F |
| F | F | F | F | F | F | F | F | F |
| F | T | F | T | F | F | F | F | F |
| F | F | T | T | F | F | F | F | F |
| F | T | T | T | F | F | F | F | F |
i can't prove that they are logically equivalent because from my work they aren't. can you give me any tips as to what i have done wrong because obviously they are log. eq because the book says so.
Answer. One hint is that an if/then (p->q) statement is always
true when its hypothesis is false. This changes your answers in the p ->qVr
column. This column should be
T
T
T
F
T
T
T
T
I see similar errors in the other columns. Can you find them?
Question. if i staple all my work that is due tomorrow together, is that ok?? or should i staple the discussion problems from last week together and the problems to hand in together...therefore two different stapled "packets"??
Answer. Just staple the whole thing together.
Question. I handed in both the practice problems and the discussion problems for section 1.1. I wasnt sure when the discussion problems were due and it made sense for me to put both on the same paper (to save paper). I hope this isnt a problem. If it is, im sorry and i wont do it in the future. If it's ok with you, then ill keep doing it in the future.
Answer. For my own peace of mind, I'd rather that you keep the problems to hand in separate from the ones that aren't due yet. It's fine to put last week's discussion problems with this week's problems to hand in, though.