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)$

   
   
   
   (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.
   
   
   
   
   
   
   **** This area is for grading purposes (points lost per page)- Do not write below this line ****
   
   
   
   
   
   
   

   

   
   
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
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

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''

   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''

   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''

   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''

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.
      
      
      
      
      
      
      
   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.
         
         
         
         
         
         
         
         
         
         
         
         
         
         
      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.
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.
   2. There is a rational number and an irrational number whose sum is rational.
   3. $\forall a, b, c \in Z^{>1}, \,\,\, c \vert ab \rightarrow (c \vert a \vee c \vert b)$
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
   4. $\forall a,b,c \in Z^{>1}, \,\,\, c^2 \vert ab \rightarrow (c \vert a \vee c \vert b)$
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}$ = $_{8}$
         
         
         
      2. $1AB_{16}$ = $_{10}$
         
         
         
      3. $47_{10}$ = $_{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}$ = $_{10}$
         
         
         
      2. $00010010_{2}$ = $_{10}$
         
         
         
      3. $-60_{10}$ = $_{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.

   Circle One: Valid Invalid

   Some hookitees are jambers.

   Bompa is a jamber.

   -----

   therefore: Bompa is a hookitee.

   Circle One: Valid Invalid

This page is intentionally blank
It is space to continue any proof that would not fit into the space provided.
Only one problem can be continued onto this page.
It must state here what problem number it is.
And it must state by that problem number where it is continued to.
If you need more paper, raise your hand and we will come to you.
All paper you receive must have your name on it, and it must be submitted with your exam.

Web Accessibility