MAT 140Dr. S. Epp
Discrete Mathematics I
Review Guide (Tentative)
1. What does it mean for two statement forms to be logically equivalent? Be able to do examples where you test to see whether two statement forms are logically equivalent and explain why they are or are not equivalent.
2. What are De Morgan's laws? Be able to work with examples of De Morgan’s laws in ordinary English.
3. What is the negation of “If p then q”? Be able to express negations of if-then statements in ordinary English.
4. What are the converse, inverse, and contrapositive of a statement of the form “If p then q”? What are the converse, inverse, and contrapositive of a statement of the form “x, if P(x) then Q(x)”? Be able to express converses, inverses, and contrapositives in ordinary English.
5. What does it mean to say that one thing is a necessary condition for another thing? That one thing is a sufficient condition for another thing? What does it mean to say that one thing is true only if another thing is true? Be able to translate statements about necessary and sufficient conditions and only-if statements into if-then form.
6. What does it mean for a form of argument to be valid? Be able to do examples where you test to see whether a given form of argument is valid and explain why it is or is not valid. Can a valid argument have a false conclusion? (Answer: yes) Can an invalid argument have a true conclusion? (Answer: yes)
7. What are modus ponens, modus tollens, converse error, and inverse error? Which are valid and which are invalid? What are the “universal” versions of these forms of argument?
8. What are the negations of the following statements? Be able to express them in ordinary English as well as formally.
x, Q(x)
x such that Q(x)
x, if P(x) then Q(x)
x, y such that P(x,y)
x such that yP(x,y)
9. Given a digital logic circuit, be able to a) find the output for a given set of input signals, b) construct an input/output table, c) find the corresponding Boolean expression.
10. Given a Boolean expression, be able to draw the corresponding digital logic circuit.
11. Given an input/output table, be able to draw the corresponding digital logic circuit.
12. Be able to transform positive integers from decimal to binary notation and the reverse, from decimal to hexadecimal notation and the reverse, and from binary to hexadecimal notation and the reverse.
13. Be able to add and subtract integers using binary notation.
14. How do you generally determine the truth of an existential statement (that is, a statement of the form “x such that Q(x)”)? (Answer: Give an example; that is, find a value of x for which Q(x) is true.)
15. How are the following defined: odd integer, even integer, prime number, composite number, rational number, irrational number, divisibility of one integer by another?
16. How do you generally establish the falsity of a universal statement “x, Q(x)”? (Answer: Show that its negation is true.) What is its negation? (Answer: “ x such that ~Q(x)”) This is an existential statement. How do you show it is true? (Answer: As indicated in #14 above, you give an example. Since this example is used to show something is false, it is called a counterexample. To be specific, a counterexample describes a value of x for which Q(x) is false.)
17. What does it mean to “disprove” a statement? (Answer: It means to show that the statement is false. So to disprove a universal statements, we generally find a counterexample.) Be able to find counterexamples to disprove universal statements involving real numbers, odd and even integers, prime and composite numbers, rational and irrational numbers, divisibility of integers, and the quotient-remainder theorem.
18. How do you use the method of exhaustion to prove the truth of a universal statement that is defined over a small, finite domain?
19. How do you use the method of direct proof to show the truth of a statement of the form “x, if P(x) then Q(x)”? Be able to apply this method to “outline” a proof of a statement (that is, to state what one supposes and what one has to show in order to prove the statement). Be able to apply the method of direct proof to prove statements about odd and even integers, prime numbers, rational numbers, divisibility of integers, and the floor and ceiling functions.
20. How do you disprove an existential statement “x such that Q(x)”? That is, how to do establish its falsity? (Answer: Show that its negation is true.) What is its negation? (Answer: “ x, ~Q(x)”) This is a universal statement. How do you show it is true? (Answer: Use a direct proof or a proof by contradiction or a proof by contraposition.)
21. What is the unique factorization theorem for integers? (This theorem is also called the fundamental theorem of arithmetic.)
22. What is the quotient-remainder theorem? Be able to apply it to specific situations.
23. What is the method of proof by division into cases? Be able to apply it in specific situations.
TIPS FOR SUCCESS WITH PROOFS AND DISPROOFS
Make sure your proofs are genuinely convincing. Express yourself carefully and completely – but concisely! Write in complete sentences, but don’t use an unnecessary number of words.
Disproof by Counterexample
- To disprove a universal statement, give a counterexample.
- Write the word "Counterexample" at the beginning of a counterexample.
- Write counterexamples in complete sentences.
- Give values of the variables that you believe show the property is false.
- Include the computations that prove beyond any doubt that these values really do make the property false.
Proof of a Universal Statement
- Write the word “Proof” at the beginning of a proof.
- Write proofs in complete sentences.
- Start each sentence with a capital letter and finish with a period.
Direct Proof
- Begin each direct proof with the word "Suppose."
- In the "Suppose" sentence:
a. Introduce a variable or variables (indicating the general set they belong to - e.g., integers, real numbers etc.), and
b. Include the hypothesis that the variables satisfy.
3. Identify the conclusion that you will need to show in order to complete the proof.
4. Reason carefully from the “suppose” to the “conclusion to be shown.”
5. Include the little words (like “Then,” “Thus,” “So,” “It follows that”) that make your
reasoning clear.
6. Give a reason to support each statement you make in your proof.\
Proof by Contradiction
- Begin each proof by contradiction by writing “Suppose not. That is, suppose...,” and continue this sentence by carefully writing the negation of the statement to be proved.
- After you have written the “suppose,” you need to show that this supposition leads logically to a contradiction.
- Once you have derived a contradiction, you can conclude that the think you supposed is false. Since you supposed that the given statement was false, you now know that the given statement is true.