Texas A&M University-Corpus Christi / Dept. of Computing and Mathematical Sciences

MATH 2305 §002 -- Discrete Mathematics I -- Spring 2003

Test 1 Review

Section Topic Examples Comment
1.1 Construct truth tables for compound wffs. 1.1 # 2,14 How many rows are there in a truth table? Each row must be evaluated correctly.
  Recognize tautologies and contradictions 1.1 #17,18 You are not responsible for the algorithm 'Tautology Test.'
  Translate between symbolic representation and English language statements 1.1 # 4-13 See Table 1.5, Use DeMorgan's Laws to negate compound statements
  Definitions: wffs, truth values, connectives, tautologies, contradictions    
1.2 Justify equivalences and derivation rules for propositional logic. Show that modus ponens is a tautology. Assuming m.p. and DeMorgan's laws, prove disjunctive syllogism The equivalences and rules in Tables 1.12 and 1.13 are best justified by truth tables.
1.2 Apply derivation rules for propositional logic 1.2 #9-20 All proof sequences in this class must have justifications for each step. See Tables 1.12, 1.13, 1.14
  Use propositional logic to prove validity of verbal arguments 1.2 #38-44 This involves both translation and proof.
  Definitions: valid arguments, proof sequence.    
.13 Determine truth value of a predicate wff in a given interpretation 1.3 #1-3 This depends on knowledge of the interpretation. Common domain: the integers, positive real numbers.
  Translate English language statements into predicate wffs, and vice-versa 1.3 #6-17 Remember the general rule, universal statements are implications, existential statements are conjunctions (ands).
  Recognize a valid wff and explain why it is valid   We will only use derivation rules to decide if given prepositional arguments are valid.
  Definitions: predicates, interpretations    
1.4 Apply derivation rules for predicate logic 1.4 # 6-7,10-14,25 Use tables as in Section 1.2 together with instantiation (existential before universal) and generalization.
  Use predicate logic to prove validity of a verbal argument 1.4 # 1-5,26-32 This involves both translation and proof.
2.1 Look for a counterexample. 2.1 #3,4 (37-51) Finding a counterexample depends on knowledge of the domain. Sometimes you may not know if there is a counterexample or if you will be able to write a proof
  Construct direct proofs, proofs by contraposition, and proofs by contradiction. 2.1 #1, 5-36, 37-51, 52-54
  • Proofs by exhaustion work if there is a finite (and reasonable) number of cases to check.
  • Direct proofs work well if the hypotheses and conclusion are 'positive' statements allowing translation of the statements. Examples: Two integers are even (x =2j and y = 2k for integers x and k), or an integer is a perfect square (x = j^2) or an integer is not prime (x = a*b for integers a,b with neither a nor b = x).
  • Proofs by contraposition work well if both the hypothesis and conclusion are 'negative' statements that cannot be translated. Examples: An integer is not a perfect square ( x /= j^2), an integer is prime (x /=a*b for any integers a,b with neither a nor b = x).
  • Proofs by contradiction work well if the hypothesis is positive and the conclusion is negative. Taking the negation of the conclusion as a hypothesis gives more to work with.
  Definitions: inductive reasoning, deductive reasoning    
2.2 Use the first principle of induction in proofs 2.2 #1-22 (closed forms for sums), 27-38 (inequalities) and 41-52 (divisibility problems)
  • Start with the basis statement. The basis need not be for n = 1
  • Clearly state the inductive hypothesis, P(k), in mathematical terms. Example: 2.2 #50, P(k) is n^k - n = 3*j for some integer j.
  • Prove the inductive conclusion, P(k+1) using the inductive hypothesis. Be sure to look for some part of the statement of P(k) in the statement of P(k+1) and make a substitution.
  Use the second principle of induction in proofs 2.2 #66-70 (combining unequal values)
  • As above, but the inductive hypothesis is that P(j) is true for every integer less than or equal to k.
  • Works well if the object of size k+1 (polygon in #64, value in #66-70, etc) breaks down into pieces that are not size k and size 1.
  Definitions: properties of positive integers, basis step, induction step    
2.4 Generate values in a sequence defined recursively. 2.4 #1-10, Fibonacci sequence, 36-37 This is fairly mechanical. But it has many applications.
  Prove properties of the Fibonacci sequence. 2.4 #11-23 Apply the definition or either principle of induction.
  Recognize objects in a recursively defined collection of objects 2.4 #38-41  
  Give recursive definitions for particular sets of objects. 2.4 #42-49  
  Give recursive definitions for certain operations on objects 2.4 #50-52  
  Write recursive algorithms to generate sequences defined recursively. 2.4 #62-71 At least you should be able to follow a recursive algorithm to find the value at for a given input.
  Solve linear, first order recurrence relations with constant coefficients by using a solution formula The function S(n)=2^n is a solution to S(1)=2 and S(n)=2*S(n-1)
The function f(n)=3+2n is a solution to f(0)=3 and f(n)=f(n-1)+2.		 We didn't have time to look at the techniques for solving them. However, you should be able to verify solutions as in the example.
  Solve recurrence relations by the expand, guess and verify technique. 2.4 #73-78 Just try it as in the bottom of p.131 or Example 42.
  Definitions: Basis, recursive step, recurrence relations.