Name (PRINTED):
Student ID #:
Section # (or Lab Time:
name and time)

CMSC 250

Exam #1 - VER A

Thurs., March 9, 2006

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 120, and you will have exactly 70 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; it should not be submitted with your exam.

1. [12 pnts.] Use a COMPLETE truth table to determine if the argument expressed represents a valid argument. You must use 1 for true and 0 for false to represent the truth values.

   $p \vee q$

   $p \vee (\sim p \wedge q)$

   $q \vee (p \wedge q)$

   $p$	$q$	$p \vee q$	$\sim p$	$\sim p \wedge q$	$p \vee (\sim p \wedge q)$	$p \wedge q$	$q \vee (p \wedge q)$
   1	1	1	0	0	1	1	1
   1	0	1	0	0	1	0	0
   0	1	1	1	1	1	0	1
   0	0	0	1	0	0	0	0

   
   
   
   NO    (Yes or No) This is a valid argument form.
   
   Explain why you selected this answer concerning the vality - indicate how specific rows/columns indicated this answer to you. The third and sixth columns are the premises. In the first, second, and third rows the premises are both true. These are called the critical rows. All critical rows must have a true conclusion in a valid argument. The second row does not.
2. [19 pnts.] Use only those rules given on the ``cheatsheet'' to prove that the following is a valid argument. It is a Valid Argument - you only need to prove that it is. You may assume that the domain D is not empty. You may combine double negation, commutativity and associativity with any other statement as long as you acknowledge that you have done that. All other statements must be directly from the ``cheat sheet.''

   P1	$\forall x \in D, F(x) \rightarrow (M(x) \vee \sim N(x))$
   P2	$\forall y \in D, \sim (\sim M(y) \vee \sim Y(y)) \rightarrow \sim N(y)$
   P3	$\exists z \in D, Y(z) \wedge Z(z)$
   P4	$\forall x \in D, \sim Z(x) \vee N(x)$
   	Therefore $\exists m \in D, \sim F(m) \wedge Z(m)$

   line	Statement	Reason	Stmt # or
   			premise #
   1	$Y(a) \wedge Z(a)$	$\exists$ instance	P3
   2	$\sim Z(a) \vee N(a)$	$\forall$ instance	P4
   3	$Z(a)$	Conjunctive simplification	1
   4	$N(a)$	Dbl Neg & Disjunctive simplification	2, 3
   5	$\sim M(a) \vee \sim Y(a)$	Universal Modus Tollens & Dbl Neg	4, P2
   6	$Y(a)$	Conjunctive simplification	1
   7	$\sim M(a)$	Dbl Neg & Disjunctive syllogism	5,6
   8	$\sim M(a) \wedge N(a)$	Conjunctive addition	7, 4
   9	$\sim (M(a) \wedge \sim N(a))$	Dbl Neg & DeMorgan	8
   10	$\sim F(a)$	Universal Modus Tollens	9, P1
   11	$\sim F(a) \wedge Z(a)$	Conjunctive addition	10, 3
   12	$\exists m \in D, \sim F(m) \wedge Z(m)$	Existential generalization	11

3. [16 pnts.] Translate each of the following to quantified predicate calculous notation. You may only use the domains and predicates given for that question. The NOT (``$\sim$``) may only appear immediately before a predicate - it may not appear immediately before a parenthesis or before a quantifier.

   There is a student who enjoys the taking of at least one test while in college.

   Domain: A = {all tests}, P= {all people}

   Predicates: S(x) = ``x is currently a student in college'' , L(x,y) = ``x enjoys test y''

   
   

   $$\exists p \in P \, \exists m \in A, \,\, S(p) \wedge L(p,m)$$

   
   

   There is exactly one dog who likes to eat celery.

   Domain: A = {all animals}

   Predicate: D(x) = ``x is a dog'' and L(x)= ``x likes to eat celery''

   
   

   $$\exists d \in A, \,\, D(d) \wedge L(d) \wedge \forall x \in A \,\, (D(x) \wedge L(x)) \rightarrow x = d$$

   
   

   Every dog likes to play with each and every child.

   (note: Each and every child is either a boy child or a girl child.)

   Domain: A = {all animals (except people)}, P = {all people}

   Predicates: L(x,y) = ``x likes to play with y'', D(x)= ``x is a dog'',

   B(x) = ``x is a boy child'', G(x) = ``x is a girl child''

   
   

   $$\forall x \in A \, \forall p \in P, \,\, D(x) \wedge (B(p) \vee G(p)) \rightarrow L(x,p)$$

   
   

   There is a male politician who trusts himself but doesn't trust any other male politician.

   Domain: P = {All people}

   Predicate: M(x) = ``x is male'', P(x) = ``x is a politician'', T(x,y) = ``x trusts y''

   
   

   $$\exists p \in P, \,\, M(p) \wedge P(p) \wedge T(p,p) \wedge... ... P \,\, (M(x) \wedge P(x)) \rightarrow (\sim T(p,x) \vee p=x)$$

   
   

4. [12 pnts.] Based on the following truth table, answer the questions.

   p	q	r	output
   1	1	1	0
   1	1	0	1
   1	0	1	0
   1	0	0	1
   0	1	1	0
   0	1	0	1
   0	0	1	0
   0	0	0	0

   1. Write the complete logic statement in its most expanded form (the truth table that directly represents the truth table given) - one element of the disjunction for each line which is true in the truth table.
      
      
      
      
      $$(p \wedge q \wedge \sim r) \vee (p \wedge \sim q \wedge \sim r) \vee (\sim p \wedge q \wedge \sim r)$$
      
      
      
      
      
      
   2. This is equivalent to $(p \vee q) \wedge \sim r$. Do the following tasks related to that statement.
      1. Draw the circuit that represents the reduced form of the logical expression. Label all gates as ``AND,'' ``OR'' or ``NOT''. Each AND gate and each OR gate can only have two inputs and one output. EACH NOT gate can only have one input and one output. You may only use ``AND,'' ``OR'' and ``NOT'' gates - you can not use gates of any other type.
         =4.0in
      2. Draw an equivalent circuit that does not use any ``AND'' gates. (``OR'' and ``NOT'' gates are all that can be used and must be as described above.
         $\sim \sim ( (p \vee q) \wedge \sim r )$
         $\sim (\sim (p \vee q) \vee r)$
         =5.5in
5. [35 pnts.] For each of the following: State if you believe the statement to be TRUE or state that you believe it to be FALSE. Then convince us that your truth value assessment is correct. The proof must be complete and convincing. You may use only the definitions from the text (and lecture) along with facts stated here. Something is odd if and only if it is not even. Consecutive integers have opposite parity. The Quotient Remainder Theorem. The Unique Prime Factorization Theorem. If you would like to use any lemma (or subproof) along the way, that is fine; just be sure to clearly label it and include its proof on these papers. If you need more space for any answer, page 10 is blank; YOU MUST MARK BOTH AT THE PLACE WHERE YOU ARE CONTINUING FROM AND THE PLACE YOU ARE CONTINUING TO.
   1. For all integers, if $n^2$ is odd, then $n$ is odd. TRUE. $\forall n \in Z,~n^2 \in Z^{odd} \rightarrow n \in Z^{odd}$
      $\forall n \in Z,~n \not\in Z^{odd} \rightarrow n^2 \not\in Z^{odd}$     Contrapositive.
      $\forall n \in Z,~n \in Z^{even} \rightarrow n^2 \in Z^{even}$      even iff not odd. Proof.
      

      Let $n$ be arbitrary in $Z$.

      $\vert$Assume $n$ is even.

      $\vert$Then $\exists k \in Z, n = 2k$, by definition of even.

      $\vert$ $n^2 ~=~ (2k)^2$ by substitution.

      $\vert$ $~~~~=~ 2(2k^2)$ by algebra.

      $\vert$$2k^2 \in Z$ by closure of $Z$ under multiplication.

      $\vert$ $2(2k^2) \in Z^{even}$ by definition of even.

      $\vert$ $n^2 \in Z^{even}$ by substitution.

      $n \in Z^{even} \rightarrow n^2 \in Z^{even}$ by CCW without contradiction.

      $\forall n \in Z,~n \in Z^{even} \rightarrow n^2 \in Z^{even}$, by universal generalization.

      QED

   2. There is a rational number and an irrational number whose sum is rational. $\exists m \in Q \, \exists n \not \in Q, \,\,\, m + n \in Q$
      FALSE.
      Its negation is
      $\sim (\exists m \in Q \, \exists n \not \in Q, \,\,\, m + n \in Q)$
      $\forall m \in Q \, \forall n \not \in Q, \,\,\, m + n \not\in Q$
      Proof (by contradiction).
      

      Let $m$ be an arbitrary rational.

      Let $n$ be an arbitrary irrational.

      $\exists a,b \in Z, \,\,\, m = \frac{a}{b} ~\wedge ~ b \neq 0$, by definition of rational.

      $\vert$Assume $m+n \in Q$.

      $\vert$ $\exists c,d \in Z, \,\,\, m+n = \frac{c}{d} ~\wedge ~ d \neq 0$, by definition of rational.

      $\vert$ $\frac{a}{b} + n ~=~ \frac{c}{d}$, by substitution.

      $\vert$ $n ~=~ \frac{c}{d} - \frac{a}{b} ~=~ \frac{cb-ad}{bd}$, by algebra.

      $\vert$$cb-ab \in Z$ by closure of $Z$ under multiplication and subtraction.

      $\vert$$bd \in Z$ by closure of $Z$ under multiplication.

      $\vert$$bd \neq 0$ by algebraic properties of multiplication.

      $\vert$ $\frac{cb-ad}{bd} \in Q$, by definition of rational.

      $\vert$$n \in Q$, by substitution.

      $\vert$$n \not\in Q$, as defined above.

      $\vert$Contradiction since a number cannot be both rational and irrational.

      $m+n \not\in Q$, by CCW with contradiction.

      $\forall m \in Q \, \forall n \not \in Q, \,\,\, m + n \not\in Q$, by universal generalization.

      QED

   3. $\forall a, b, c \in Z^{>1}, \,\,\, c \vert ab \rightarrow (c \vert a \vee c \vert b)$ FALSE. Let $a = 2$, $b = 2$, $c = 4$.
      Consider the antecedent $c \vert ab$. By substitution it is $4 \vert 2*2$, and by algebra it is $4 \vert 4$.
      So the antecedent is true.
      Consider the consequent $c \vert a \vee c \vert b$.
      By substitution it is $4 \vert 2 \vee 4 \vert 2$.
      So the consequent is false. Since the antecedent is true and the consequent is false, the implication is false. So this is a valid counterexample.
      
      
      
   4. $\forall a,b,c \in Z^{>1}, \,\,\, c^2 \vert ab \rightarrow (c \vert a \vee c \vert b)$ FALSE. Let $a = 4$, $b = 9$, $c = 6$.
      Consider the antecedent $c^2 \vert ab$. By substitution it is $6^2 \vert 4*9$, and by algebra it is $36 \vert 36$.
      So the antecedent is true.
      Consider the consequent $c \vert a \vee c \vert b$.
      By substitution it is $6 \vert 4 \vee 6 \vert 9$.
      So the consequent is false. Since the antecedent is true and the consequent is false, the implication is false. So this is a valid counterexample.
6. [12 pnts.] For each of the questions in the short answer section - write the answer in the space provided. You do not need to show your work.
   1. For all of the following, give the equivalent value in the base indicated. For the values in this set assume they are all unsigned integers.
      
      
      
      1. $1001101_{2} ~=~ 115_{8}$
         
         
         
      2. $1AB_{16} ~=~ 427_{10}$
         
         
         
      3. $47_{10} ~=~ 101111_{2}$
      
      
      
      
   2. For all of the following, give the equivalent value in the base indicated. For the values in this set assume negative values must be/are represented using 8-bit 2's complement.
      
      
      
      1. $11001101_{2} ~=~ -51_{10}$
         
         
         
      2. $00010010_{2} ~=~ 18_{10}$
         
         
         
      3. $-60_{10} ~=~ 11000100_{2}$
7. [14 pnts.] Use an Euler diagram to determine if each of the following represents a valid argument form. If it is invalid, you must select ``invalid'' and draw a diagram that convinces the grader that the argument is indeed invalid. Make sure to label the parts of the diagram, and be sure to show where the counter example would be if it is a universal statement. If it is a valid argument, mark it as valid, but then do not draw any diagram since an Euler diagram cannot be used to prove an argument valid.

   No Flibbits are Gloopers

   No Gloopers are Higgiters.

   -----

   therefore: No Flibbits are Higgiters.

   INVALID

   =4.5in

   

   Some hookitees are jambers.

   Bompa is a jamber.

   -----

   therefore: Bompa is a hookitee.

   INVALID

   =4.5in

   

Web Accessibility