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

CMSC 250	Exam #1 ANSWERS	Tuesday, Oct. 11, 2005
(0201 & 0202)

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 110, 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, and the back of the cheat sheet can be used for scratch paper.

1. [20 pnts.] Use a COMPLETE truth table to determine if the following represents a logically valid argument. Use 1 for ``true'' and 0 for ``false'' to create the complete truth table.

   $p \vee (q \rightarrow \sim r)$

   $\sim q \rightarrow \sim p$

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

   					A			B		C
   p	q	r	$\sim r$	$q \rightarrow \sim r$	$p \vee (q \rightarrow \sim r)$	$\sim q$	$\sim p$	$\sim q \rightarrow \sim p$	$A \wedge B$	$q \vee \sim p$	$C \wedge r$
   0	0	0	1	1	1	1	1	1	1	1	0*
   0	0	1	0	1	1	1	1	1	1	1	1
   0	1	0	1	1	1	0	1	1	1	1	0*
   0	1	1	0	0	0	0	1	1	0	1	1
   1	0	0	1	1	1	1	0	0	0	0	0
   1	0	1	0	1	1	1	0	0	0	0	0
   1	1	0	1	1	1	0	0	1	1	1	0*
   1	1	1	0	0	1	0	0	1	1	1	1

   
   
   
   NO (Yes or No) This is a valid argument form.
   
   Explain why you selected this answer for the valid argument form question - indicate how specific rows/columns indicated this answer to you.
   
   
   

   I looked at the rows marked with the stars. These are the critical rows. The premises are both true in these rows. The premises are the columns labeled A and B. The premises are both true in these rows but the conclusion is false, therefore the argument is not valid.

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

   

   
   
2. [24 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.

   P1	$\forall z \in D, ((P(z) \rightarrow Q(z)) \rightarrow M(z)$
   P2	$\exists x \in D, \sim P(x) \vee (M(x) \wedge \sim Q(x))$
   P3	$\forall x \in D, R(x) \vee (M(x) \rightarrow Z(x))$
   P4	$\exists x \in D, \sim Z(x) \wedge \sim R(x)$
   	Therefore $\exists y \in D, P(y) \wedge \sim Q(y)$

   line	Statement	Reason	Line #s
   1	$\sim Z(a) \wedge \sim R(a)$	$\exists$ instantiation	P4
   2	$\sim R(a)$	conj simplification	1
   3	$R(a) \vee (M(a) \rightarrow Z(a))$	$\forall$ instantiation	P3
   4	$M(a) \rightarrow Z(a)$	disj syllogism	2,3
   5	$\sim Z(a)$	conj simplification	1
   6	$\sim M(a)$	MT	4,5
   7	$\sim (P(a) \rightarrow Q(a))$	$\forall$ MT	P1,6
   8	$\sim (\sim P(a) \vee Q(a))$	def of impl	7
   9	$\sim \sim P(a) \wedge \sim Q(a)$	DeMorgan's	8
   10	$P(a) \wedge \sim Q(a)$	Double Neg	9
   11	$\exists y \in D, P(y) \wedge \sim Q(y)$	$\exists$ Gen	10

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 exactly one teddy bear that is sitting in a chair.

   Domain: U = {all stuffed animals}, C={all chairs}

   Predicate: S(x,y) = ``x is sitting in y'', B(x) = ``x is a bear''

   $\exists x \in U, \exists c \in C, B(x) \wedge S(x,c) \wedge (\forall p \in U, \forall q \in C, (S(p,q) \wedge B(p)) \rightarrow p = x)$

   Every teddy bear has either a boy or a girl (child) who loves it.

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

   Domain: T = {all teddy bears}, C = {all children}

   Predicates: L(x,y) = ``x loves y'', B(x) = ``x is a boy'', G(x) = ``x is a girl''

   $\forall x \in T, \exists c \in C, L(c,x)$

   No teddy bear is taller than a CMSC 250 instructor.

   Domain: U = {all suffed animals}, P= {all people}

   Predicates: B(x) = ``x is a teddy bear'', I(x) = ``x is a CMSC 250 instructor'', T(x,y) = ``x is taller than y''

   $\forall c \in T, \forall p \in P, \sim B(t) \vee \sim I(p) \vee \sim T(c,p)$

   All white fluffy teddy bears are light and cuddly.

   Domain: Z = {all teddy bears}

   Predicate: W(x) = ``x is white'', F(x) = ``x is fluffy'', L(x) = ``x is light'', C(x) = ``x is cuddly''

   $\forall x \in Z, (W(x) \wedge F(x)) \rightarrow (L(x) \wedge C(x))$

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

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

   1. Write the simplest logical expressiion that represents the truth table shown above. You may only use $\wedge$, $\vee$ and $\sim$ as your logical operators.
      
      
      $(q \wedge r) \vee \sim (p \vee q)$
      
      
      
   2. Draw the circuit that represents your 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.
5. [30 pnts.] For each of the following: State if you believe the statement to be true or state that you believe it to be false and then prove it. The proof must be complete and convincing.
   1. If a, b and c are positive integers and m is a positive integer greater than or equal to 2 where $a \equiv_m b$, then $ac \equiv_{mc} bc$. $\forall a,b,c \in Z^+, \forall m \in Z^{\geq 2}, a \equiv_m b \rightarrow ac \equiv_{mc} bc$ Proof:
      Let a,b and c be arbitrary in $Z^+$
      Let m be arbitrary in $Z^{\geq 2}$
      $\vert$ Assume $a \equiv_m b$
      $\vert m \vert (a-b)$ by definition of equiv in a mod
      $\vert \exists k \in Z, a-b = mk$ by definition of divides
      $\vert c(a-b) = c(mk)$ by multiplying both sides by c
      $\vert ac-bc = (mc)k$ by algebra
      $\vert$ Since $k \in Z$ as defined above, $mc \vert (ac-bc)$ by def of divides
      $\vert ac \equiv_{mc} bc$ by definition of equiv in a mod
      
      $a \equiv_m b \rightarrow ac\equiv_{mc} bc$ by closing the conditional world without a contradiction
      
      $\forall a,b,c \in Z^+, \forall m \in Z^{\geq 2}, a \equiv_m b \rightarrow ac \equiv_{mc} bc$ by generalizing from the generic particular
      
   2. The sum of two consecutive integers is always odd. proof:
      Let a be arbitrary in Z
      a+1 is the next consecutive integer after a
      Consider a+(a+1)
      This is equivalent to $2a +1$ by algebra
      Since $a \in Z$ as defined above $2a+1 \in Z^{odd}$ by definition of odd
      
   3. For all positive even integers (a, b and c), if $a\vert bc$, then $a\vert b$ or $a\vert c$. This is false.
      
      Counter Example: Let a = 4, b = 2, and c = 2.
      It is true that $4 \vert (2)(2)$ because $4 \vert 4$ which makes the antecedent true.
      It is false that $4\vert 2 \vee 4 \vert 2$ so the consequent is false
      When the antecedent is true and the consequent false, the implication is false.
      
6. [14 pnts.] Use an Euler diagram to determine if each of the following represents a valid argument form. Make sure to label the parts of the diagram. If it is invalid, you must draw a diagram that is not supportive of the conclusion. If it is a valid argument, draw a diagram that does support the conclusion (since you can't draw one that doesn't).

   No cats like dogs.

   Nothing that likes a dog can play at the park.

   -----

   therefore: No cats can play at the park.

   Circle One: Valid Invalid

   The ``cat'' circle and the ``likes dogs'' circle must be not touching.

   The ``likes dogs'' and ``can play in the park'' circle must also be not touching.

   The ``cat'' circle and the ``can play in the park'' circle must be overlapping.

   Some horses like dogs.

   Flicka is a horse.

   -----

   therefore: Flicka does like dogs.

   Circle One: Valid Invalid

   The ``horse'' circle and the ``likes dogs'' circle must be overlapping.

   The ``Flicka'' point must be inside of the horse circle.

   The ``Flicka'' point must be outside of the ``likes dogs'' circle.

Web Accessibility