MAT 140: Discrete Mathematics I Dr. S. Epp

Review Guide for the Final Exam

Logical Equivalence: 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.

Negations: What are negations for the following statement forms? Be able to express them in ordinary English as well as formally.

p Ú q

p Ù q

p ® q (if p then q)

" 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 " y P(x,y)

Converse, Inverse, Contrapositive: 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.

Necessary and Sufficient Conditions: 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.

Validity and Invalidity: 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)

Special Valid and Invalid Argument Forms: 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?

Digital Logic Circuits and Boolean Expressions: Given a digital logic circuit, how do you a) find the output for a given set of input signals, b) construct an input/output table, c) find the corresponding Boolean expression? Given a Boolean expression, how do you draw the corresponding digital logic circuit? Given an input/output table, how do you draw the corresponding digital logic circuit?

Binary and Hexadecimal Notation: How do you 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? How do you add and subtract integers using binary notation?

Definitions: How are the following defined: logical equivalence, validity, odd integer, even integer, prime number, rational number, divisibility of one integer by another, the floor of a number, the ceiling of a number? (Be able to write definitions for these terms without using any books or notes.)

Truth of an Existential Statement/Falsity of a Universal Statement:

· 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.)

· 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 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.)

· What does it mean to “disprove” a statement? (Answer: It means to show that the statement is false. So to disprove a universal statement, you 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.

Proving a Universal Statement/Disproving an Existential Statement

· Method of exhaustion: How do you use the method of exhaustion to prove the truth of a universal statement that is defined over a small, finite domain?

· Generalizing from the generic particular and direct proof: How do you use the method of generalizing from the generic particular and 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.

· Proof by division into cases: What is the method of proof by division into cases? Be able to apply it in specific situations.

· Proof by contraposition: What is the method of proof by contraposition? (Be sure you can apply it to construct proofs.)

· Disproving an existential statement: 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.)

· Proof by mathematical induction: What are the two parts of a proof by mathematical induction? (Be sure you can use mathematical induction to construct proofs involving formulas and divisibility properties.)

Sequences and summations: What is a method to help find an explicit formula for a sequence whose first few terms are given (provided a nice explicit formula exists!)? What is the summation notation for a sum given in expanded form? What is the expanded form for a sum that is given in summation notation? What is factorial notation? How do you make a change of variable in a summation?

Some important theorems and algorithms: What is the unique factorization theorem for integers? (This theorem is also called the fundamental theorem of arithmetic.) What is the quotient-remainder theorem? Be able to apply it to specific situations. What are the theorems about the irrationality of the square root of 2 and the infinitude of the prime numbers? You should know the proofs of these theorems. What are the division algorithm and the Euclidean algorithm? How do you use the Euclidean algorithm to compute the greatest common divisor of two positive integers? How do you apply the formulas for the sum of the first n integers and the sum of the successive powers of a number in new situations?

Proof by contradiction: What is the structure of a proof by contradiction? What do you suppose and what do you have to show in a proof by contradiction? Be able to apply it in specific situations.

Probability: What is the sample space of an experiment? an event in the sample space? the probability of an event when all the outcomes are equally likely?

Counting: How do you find the number of elements in a segment of an array? What are the multiplication rule and the addition rule? (Be sure you can apply them in a variety of different situations.) When should you use the multiplication rule and when should you use the addition rule? What is the inclusion/exclusion formula? (Be sure you can apply it in various situations.) What is an r-permutation? What is P(n,r)? How does the multiplication rule give rise to P(n,r)? What is (n choose r)? (Answer: The number of subsets of size r that can be formed from a set of n elements.) What is an r-combination? (Answer: A subset of size r formed from a set of n elements.) What is the formula for computing (n choose r) by hand? (Be sure you can apply this knowledge in various situations.)

Pascal's theorem and the binomial theorem: What is Pascal's theorem? (Be sure you can apply it in various situations.) What is the binomial theorem? (Be sure you can apply it in various situations.)