CMSC 250

Quiz #4 ANSWERS

Wed., Sept. 22, 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 quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [10 pnts] For each of the following, write the formal notation representation of each of the following English Statements. You may only use the Domains of A = ``All Animals''. You may only use the predicates listed for that question.
   1. No pigs fly. F(x) = ``x can fly'' and P(x) = ``x is a pig'' $\forall a \in A, P(a) \rightarrow \sim F(a)$
      $\forall a \in A, F(a) \rightarrow \sim P(a)$
      $\forall a \in A, \sim F(a) \vee \sim P(a)$
      $\forall a \in A, \sim P(a) \vee \sim F(a)$
      
   2. All horses have feathers.
      H(x) = ``x is a horse'' and F(x) = ``x has feathers'' $\forall a \in A, H(a) \rightarrow F(a)$
      $\forall a \in A, \sim F(a) \rightarrow \sim H(a)$
      $\forall a \in A, \sim H(a) \vee F(a)$
      $\forall a \in A, F(a) \vee \sim H(a)$
      
   3. Some horses are small.
      H(x) = ``x is a horse'' and S(x) = ``x is small'' $\exists a \in A, H(a) \wedge S(a)$
      $\exists a \in A, S(a) \wedge H(a)$
   4. Some pigs are big and fat.
      P(x) = ``x is a pig'' and F(x) = ``x is fat'' and B(x) = ``x is big'' $\exists a \in A, P(a) \wedge B(a) \wedge F(a)$
   5. All horses and pigs have owners.
      H(x) = ``x is a horse'' and P(x) = ``x is a pig'' and O(x) = ``x has an owner'' $\forall a \in A, (H(a) \vee P(a)) \rightarrow O(a)$
2. [6 pnts] Convert each of the following to the base indicated.
   
   
   1. $10111_{2} =$ $23$$_{10}$
      
      
   2. $245_{10} =$ $365$$_{8}$
      
      
   3. $314_{10} =$ $13A$$_{16}$
   Turn Over
   
   
3. [14 pnts.] Use the handout of the ``Logical Equivalence Rules'' and the ``Rules of Inference'' to prove the following. It is a Valid Argument - you need to prove it without using a truth table.

   P1	$(S \rightarrow \sim P) \wedge (\sim S \rightarrow D)$
   P2	$R \vee (G \wedge N)$
   P3	$\sim G \vee \sim N$
   	$--------------$
   	therefore $(\sim P \vee D) \wedge (R \vee M)$

   Line #	Logical Statement	Name of Rule	Line Numbers Used
   1	$\sim (G \wedge N)$	DeMorgan's	P3
   2	$R$	Disj. Syll.	1,P2
   3	$R \vee M$	Disj. Add.	2
   4	$S \rightarrow \sim P$	Conj. Simp	P1
   5	$\sim S \vee \sim P$	Def of Impl.	4
   6	$\sim P \vee \sim S$	Comm	5
   7	$P \rightarrow \sim S$	Def of Impl.	6
   8	$\sim S \rightarrow D$	Conj. Simp.	P1
   9	$P \rightarrow D$	Hypo. Syll.	7,8
   10	$\sim P \vee D$	Def of Impl.	9
   11	( $\sim P \vee D) \wedge (R \vee M)$	Conj. Add	10,3

Web Accessibility