Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Exam #2

Friday, Oct. 29, 2004

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the exam is 100, and you will have exactly 50 minutes to complete this exam. You may not use calculators, textbooks or any other aids during this exam. If you need more space for any answer, ask for an extra paper - these extra papers must be turned in and you must mark so we can find the answer corresponding to a question. The ``cheatsheet'' (which is the last page of the exam) can be ripped off and used during the exam, and the back of the cheat sheet can be used for scratch paper. Note: The short answer questions are at the end of the exam so that you have the two facing pages for each of the proof questions. If you need more than those two pages DO NOT continue on the page from another problem, raise you hand and we will bring you additional sheets of paper. Note: The points for the individual non-short answer questions for this exam are not indicated. This would give too much indication as to which are true and which are false. Statements that are true will receive more points than ones that are false. Proving something true that is false or false that is true will result is a loss of all credit. Induction problems will be worth slightly more that deduction. Leave the paper closed this side up on your desk until you are told to start. Make sure you are in your assigned seat with all celphones and pagers turned off. Make sure you have writing instruments and your picture ID out on your desk.

**** This area is for grading purposes (points lost per problem)- Do not write below this line ****

1. If you believe the following statement is True, you must use INDUCTION to prove that it is indeed true. If you believe the following statement is False, you must give and justify a specific counter example.:
   

   $\forall n \in Z^{\geq 0}, \,\,\,\, 9 \vert (12^n-3^n)$	This is:
   	TRUE
   Hints - if you are using a formal proof	FALSE
   for this you may want to consider:
   definition of division and quotient remainder theorem

   This page for the continuation of question number 1
2. Prove True or False:
   

   $\exists n \in Z, n^2 \equiv_3 2$	This is:
   	TRUE
   Hints - if you are using a formal proof	FALSE
   for this you may want to consider:
   definition of equivalence in a mod
   and definition of divides
   and division into cases
   and quotient remainder theorem
   the fact that something can only be equivalent to one value r where $0 \leq r < d$

   This page for the continuation of question number 2
3. Prove true or false:

   $\forall n,p,r \in Z, \,\,\, n \vert pr \rightarrow n\vert p \vee n\vert r$	This is:
   	TRUE
   Hints - if you are using a formal proof	FALSE
   for this you may want to consider:
   conditional worlds
   and definition of divides
   and prime factorization

   This page for the continuation of question number 3
4. Assuming you have the recurrence relation defined as
   
   $$a_0 = 1 \,\,\, a_1 = 2 \,\,\, \mbox{and} \,\, \forall n \in Z^{\geq 2}, a_n = a_{n-2} + 4$$
   
   
   Use Induction to prove the following fact about the elements of that series:
   
   $$\forall k \in Z^{\geq 0}, a_k \equiv_2 (k+1)$$
   
   
   This page for the continuation of question number 4
5. [20 pnts] Short Answer Questions:
   1. Based on the Unique Prime Factorization theorem circle the most appropriate answer based on the statement that $2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot m = 7 \cdot 8 \cdot 9 \cdot 10$

      			Can't Tell
      $2 \vert m$	Definately	Definately	Need more
      	TRUE	FALSE	Information
      			Can't Tell
      $7\vert m$	Definately	Definately	Need more
      	TRUE	FALSE	Information
      			Can't Tell
      $21 \vert m$	Definately	Definately	Need more
      	TRUE	FALSE	Information
      			Can't Tell
      $5 \vert m$	Definately	Definately	Need more
      	TRUE	FALSE	Information

   2. For each of the following fill in the limits on the $\sum$ or $\prod$ as requested to cover as many terms as possible. For any additional terms, not covered by the summation or product, give the value of X required by that one problem to maintain the equality - do not use any summation or product notation when giving the value of X, only individual operands.
      1. 
         
         $$\sum_{i=k}^n a_i + \sum_{i = k+2}^{n+3} b_i = \left ( \sum (a_i + b_i)\right) + X$$
         
         
         
         Lower Limit = Upper Limit =
         
         X =
      2. 
         
         $$\sum_{i=k-1}^{n+2} a_i= \left ( \sum_{i=k+1}^{n} a_i \right )+ X$$
         
         
         
         X =
      3. 
         
         $$\prod_{i=k-1}^{n}a_i \cdot \prod_{i=k+2}^{n-1} b_i= \left ( \prod a_ib_i \right ) \cdot X$$
         
         
         
         Lower Limit = Upper Limit =
         
         X =
      4. 
         
         $$\prod_{i=k}^n a_ib_i = \left (\prod_{i=k+2}^{n-1} a_i \cdot \prod_{j=k}^{n-2} b_j \right) \cdot X$$
         
         
         
         X =
   3. Answer TRUE or FALSE (complete word) for each of the following. (No justification is needed - just the correct whole word answer.):
      1. $\forall n \in Z, \exists q \in Q, \exists m \in Z, q = \frac{m}{n}$
      2. $\forall n, m \in Z, n < m \rightarrow \exists k \in Z, n < k< m$
      3. $\forall n, m \in Q, n < m \rightarrow \exists k \in Q, n < k< m$

Theorem 1.1.1 - Epp Textbook p. 14

Given any statement variables $p$, $q$, and $r$, a tautology $t$ and a contradiction $c$,
the following logical equivalences hold:
1. Commutative laws:	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
2. Associative laws:	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
3. Distributive laws:	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
4. Identity laws:	$p \wedge t \equiv p$	$p \vee c \equiv p$
5. Negation laws:	$p \vee \sim p \equiv t$	$p \wedge \sim p \equiv c$
6. Double Negative law:	$\sim (\sim p) \equiv p$
7. Idempotent laws:	$p \wedge p \equiv p$	$p \vee p \equiv p$
8. DeMorgan's laws:	$\sim (p \wedge q) \equiv \sim p \vee \sim q$	$\sim (p \vee q) \equiv \sim p \wedge \sim q$
9. Universal bounds laws:	$p \vee t \equiv t$	$p \wedge c \equiv c$
10. Absorption laws:	$p \vee (p \wedge q) \equiv p$	$p \wedge (p \vee q) \equiv p$
11. Negations of t and c:	$\sim t \equiv c$	$\sim c \equiv t$

Table 1.3.1 - Epp Textbook p. 40

Modus Ponens	Modus Tollens		Disjunctive	$p \vee q$	$p \vee q$
$p \rightarrow q$	$p \rightarrow q$		Syllogism	$\sim q$	$\sim p$
$p$	$\sim q$			Therefore $p$	Therefore $q$
Therefore $q$	Therefore $\sim p$
Conjunctive	$p$		Hypothetical	$p \rightarrow q$
Addition	$q$		Syllogism	$q \rightarrow r$
	Therefore $p \wedge q$			Therefore $p \rightarrow r$
Disjunctive	$p$	$q$	Dilemma:	$p \vee q$
Addition	Therefore $p \vee q$	Therefore $p \vee q$	Poof by	$p \rightarrow r$
			Division	$q \rightarrow r$
			into Cases	Therefore $r$
Conjunctive	$p \wedge q$	$p \wedge q$	Rule of	$\sim p \rightarrow c$
Simplification	Therefore $p$	Therefore $q$	Contradiction	Therefore $p$
Closing C.W.	$\vert p$ Assumed		Closing C.W.	$\vert p$ Assumed
without	$\vert q$ derived		with	$\vert x \wedge \sim x$ derived
contradiction	Therefore $p \rightarrow q$		contradiction	Therefore $\sim p$

Other Equivalences and Other Rules of Inference

Definition	$p \rightarrow q$	$\equiv$	$\sim p \vee q$
of Implication	$\sim (p \rightarrow q)$	$\equiv$	$p \wedge \sim q$
Definition of	$A \leftrightarrow B$	$\equiv$	$(A \rightarrow B) \wedge (B \rightarrow A)$
Biconditional	$\sim (A \leftrightarrow B)$	$\equiv$	$(A \wedge \sim B) \vee (B \wedge \sim A)$
Negation of	$\sim \forall x\,\, P(x)$	$\equiv$	$\exists x \,\, \sim P(x)$
Quantifiers	$\sim \exists x\,\, P(x)$	$\equiv$	$\forall x \,\, \sim P(x)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Ponens	$P(a)$	$\rightarrow$	$Q(a)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Tollens	$\sim Q(a)$	$\rightarrow$	$\sim P(a)$
Universal Instantiation	$\forall x \in D, P(x)$	$\rightarrow$	$P(a)$
Existential Generalization	$P(a)$ where $a \in D$	$\rightarrow$	$\exists x \in D, P(x)$
Universal Generalization**	$P(a)$ where $a \in D$	$\rightarrow$	$\forall x \in D, P(x)$
Existential Instantiation **	$\exists x \in D, P(x)$	$\rightarrow$	$P(a)$ where $a \in D$

** NOTE: Remember the special circumstances required for the rules marked by the stars.

This Page Intentionally Blank
Absolutely NOTHING on this page will be graded

Web Accessibility