Write all answers legibly on the paper provided. If you need extra paper, raise your hand and request a blank paper - you must put your name on and hand-in any paper you receive. 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 2 hours to complete this exam. You may not use calculators, textbooks or any other aids during this exam.

1. [9 pnts.] For each of the following English sentences, translate the meaning into formal notation using the logic symbols ($\exists$, $\forall$, $\wedge$, $\vee$, $\sim$, and $\rightarrow$). In addition to these, you may also use mathematical, grouping and set notations symbols as needed. On the next line write the negation of the original statement using formal notation. The ``$\sim$'' (not) must be carried completely through to the smallest unit of the expression. These statements may be true or may be false - that is not important since all you are to do is to translate them to formal notation.

   For every real number there is exactly one integer which is equal to it.

   Domain: $R$ = {all reals},$Z$ = {all integers}

   Predicate: E(x,y) = ``real number x equals integer y''

   statement:

   negation:

   There is a real number which is greater than all of the integers.

   Domains: $R$ = {all reals} and $Z$={all integers}

   Predicate: G(x,y)= ``real x is greater than integer y''

   statement:

   negation:

   No integer has another integer which is its additive inverse.

   Domains: $Z$ = {all integers}

   Predicate: $A(x,y) =$``$x+y=0$'' (or in less symbolic terms):

   $A(x,y) =$'' y is the additive inverse of x''.

   statement:

   negation:

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

   

   
   
2. [10 pnts.] Use only those rules given on the ``formula sheet'' to prove that the following is a valid argument. It is a Valid Argument - you only need to prove that it is.

   P1	$\forall x \in P,\,\,\, A(x) \vee (B(x) \wedge C(x))$
   P2	$\forall y \in P,\,\,\, B(y) \rightarrow \sim C(y)$
   P3	$\forall z \in P,\,\,\, A(z) \rightarrow (D(z) \vee E(z))$
   P4	$\sim (D(fred) \vee \sim C(fred))$ where fred $\in P$
   	Therefore $\exists w \in P, \,\,\, E(w) \wedge A(w)$

   line	Statement	Reason	Line #s
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

3. [10 pnts.] Prove the following true or give a counter example to show that it is false. You may assume that $n(X)$ indicates the size of the set X, $P(X)$ indicates the powerset of the set X, and $X \times X$ indicates the cartesian product of X with itself: $\forall A \in \{$sets with more than 4 elements}, $n(A\times A) < n(P(A))$
4. [10 pnts.] Assume you are dealing with a group of 20 people. 12 of the people are male and 8 of the people are female. 4 of the people are wearing blue shirts, 5 people are wearing red, 2 people are wearing yellow, and 9 people are wearing black. Answer the following questions about those people. You do not have to do the arithmetic, but you do have to get each answer into a form that includes addition, subtraction, multiplication, division, factorials and/or exponents: (Be sure to clearly label each of your answers and be sure to show and explain your work for any partial credit.)
   1. How many ways can you select a team of 5 people?
      
      
      
      
      
      
      
   2. How many ways can you select a team of 5 people if you must have at least one with each color of shirt on the team?
      
      
      
      
      
      
      
   3. How many different ways can you select a team of 5 people if you must have at least three females on the team?
      
      
      
      
      
      
      
   4. If you select two people at random from the group, what is the probability that they will have the same color shirt?
      
      
      
      
      
      
      
   5. If you select three people at random from the group, what is the probability that they will all be the same gender?
5. [11 pnts.] Either prove or find a specific counter example to the statement that
   
   $$\forall n \in Z^{odd}, 8\vert(n^2-1)$$
   
   
   .
6. [10 pnts.] Prove or give a counter example to the fact that $\sqrt[7]{5}$ is not rational. Note: you can use any facts given on the ``formula sheet''.
7. [8 pnts.] Assume you have a set of X elements and that you have 40 computers. Each of these computers can handle up to 100 requests per day. In one day, you want to submit one request for each of the elements in the powerset of X. Answer the following questions about this scenerio. Answer each of the following - you must justify your answer by showing the sizes and how known principles were applied.
   1. What is the largest size that the set X can be. Note: You can not go over the limits set above.
      
      
      
      
      
      
      
      
      
      
      
      
      
   2. Assume (for this subpart) that there are 7 elements in the set X. If all requests (for each of the elements in the powerset of X) must be made, give the number of machines that must handle at least 10 requests. If all requests can not be made, tell how many must be ignored.
      
      
      
      
      
      
      
      
      
      
      
      
      
   3. Assume (for this subpart) that there are 10 elements in set X. If all requests (for each of the elements in the powerset of X) must be made, give the number of machines that must handle at least 20 requests. If all requests can not be made, tell how many must be ignored.
      
      
      
      
      
      
      
      
      
      
      
      
      
   4. Assume (for this subpart) that there are 15 elements in set X. If all requests (for each of the elements in the powerset of X) must be made, give the number of machines that must handle at least 30 requests. If all requests can not be made, tell how many must be ignored.
8. [8 pnts.] Let $A=\{a,b,c,d,e,f,g\}.$ Let $P$ be a partial order relation on $A$ defined by:
   
   $$\{(a,a),(a,c),(a,e),(b,b),(b,c),(b,d),(b,e),(c,c),(d,d),(d,c),(d,e),(e,e),(e,c)\}$$
   
   
   1. Draw the directed graph for $P$.
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
   2. Draw the Hasse diagram for $P$.
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
   3. Fill in the following for the relation $P$. If no elements of that type exist, write NONE next to that word.
      • Least =
        
      • Greatest =
        
      • Minimal =
        
      • Maximal =
9. [10 pnts.] Either give a counter example to dispove (giving specific members for the sets A, B, C and D) or use only the rules provided on any of the ``Formula Sheets'' along with any definitions from the textbook and/or class to prove the following statement.
   Be sure to give the name of the reason which justifies each step you give. You may assume that $\times$ represents Cartesian Product, that $X-Y$ indicates set difference, and that $X'$ indicates the complement of the set $X$. $\forall A,B,C,D \in \{sets\}, \,\,\, (A-B) \times (C-D) \subseteq (A\times C)\cup (B'\times D')$
10. [14 pnts.] Assuming relation R is defined as follows: $\forall p \in Z^{prime}, \,\, \forall x,y \in Z, \,\, xRy \leftrightarrow p\vert x-y$
    Prove that $R$ is an equivalence relation.

Theorem	Theorem
Number
E1	Z is closed during +, - and *
E2	Q is closed during +, - and *
E3	R is closed during +, -, * and /
E4	Every integer is a rational number.
E5	Every integer greater than 1 has a prime that divies it.
	$\forall x \in Z^{>1} \exists p \in Z^{prime}, p\vert x$
E6	Transitivity of Divides
	$\forall a,b,c \in Z^+, a \vert b \wedge b \vert c \rightarrow a \vert c$
E7	Quotient-Remainder Theorem
	$\forall n \in Z \forall d \in Z^+ \exists q,r \mbox{ unique } \in Z , n = dq+r \wedge 0 \leq r < d$
E8	Any two consecutive integers have opposite parity.
E9	Every integer is either even or odd but not both.
E10	$\forall n \in Z, n^2 \in Z^{even} \rightarrow n \in Z^{even}$
E11	$\forall n \in Z \forall x \in Z^+ \forall p \in Z^{prime}, p \vert n^x \rightarrow p \vert n$
E12	$\sqrt{2} \not \in Q$
E13	Every pair of integers has a greatest common factor.
	$\forall a,b \in Z, \exists q \in Z,$ q is the greatest common factor of a and b.
E14	No prime divides two consecutive integers.
	$\forall a \in Z \forall p \in Z^{prime}, p \vert a \rightarrow p \not \vert (a+1)$
E15	The set of primes is infinite.
E16	The Definition of Cartesian Product
	$\forall A,B \in \{sets\}, \,\, (a,b) \in A \times B \leftrightarrow a \in A \wedge b \in B$

Nothing on this paper will be graded.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.61)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode finalc

The translation was initiated by Fawzi Emad on 2003-05-13

Web Accessibility