Write all answers legibly in the answer space provided. The answer for each problem must be on the page with that problem. If you need extra pages - we have blank ones, but you must hand in all papers in the correct order when you are finished. The number of points possible for each question is indicated in square brackets - the total number of points on the exam is 185, 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. [20 pnts.] Using only the ``Logical Equivalence Rules'' and the ``Rules of Inference'' from the cheat sheet and the definitions presented in class, prove that the following premises necessarily lead to the conclusion stated. It is a Valid Argument - you only need to prove that it is. You may also assume that $a$ is a member of the domain named $D$.
    P1 $ (S(a) \wedge M(a))\rightarrow P(a)$
    P2 $\forall x \in D, \sim P(x) \vee Q(x)$
    P3 $\forall y \in D, \sim (D(y) \vee \sim M(y)) $
    P4 $\sim S(a) \rightarrow D(a) $
      $ --------------$
      therefore $\exists w \in D, R(w) \rightarrow Q(w)$
    line Statement Reason Line #s
    1      
           
    2      
           
    3      
           
    4      
           
    5      
           
    6      
           
    7      
           
    8      
           
    9      
           
    10      
           
    11      
           
    12      
           
    13      
           
    14      
           
    15      
           
    16      
           
    17      
           
    18      
           
  2. [20 pnts] Let $p$ be a prime number and let $k\geq 2\in \bf Z$. Prove that $\sqrt[k]{p}$ is irrational.
  3. [15 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 negation should be in its simplest form - no parentheses grouping logical operators.
    For every integer there is both a real number that is greater than it and a real number that is less than it.
    Domains: Z = {all integers}, R = {all reals}
    Predicate: G(x,y) = ``x is greater than y''
    statement:
     
    negation:
     
     
    There is an integer that divides no other integer than itself.
    Domain: Z = {all integers}
    Predicate: D(x,y) = ``x divides y''
    statement:
     
    negation:
     
     
    Every house has a cat that lives in it.
    Domains: H = {all houses}, C = {all cats}
    Predicate: L(c,h) = ``cat c lives in house h''
    statement:
     
    negation:
     
     
  4. [20 pnts] Using only rules provided on the cheat sheet and definitions given in class, prove that $(A-B)\times B = (A\times B)-(B\times B)$. You may assume that $A$ and $B$ are both non-empty sets over the same domain. Make sure you justify each step you write with the name of the rule as given on the ``cheat sheet''.
  5. [20 pnts] Let $p \in R^+$ where $p > 0$ and let $a_{1} < p$, $a_{2}<p^{2}$, and $a_{3} < p^{3}$. For all $n\geq 4$, let $a_{n}=a_{n-1}+ba_{n-2}+ca_{n-3}.$ If $1+\frac{1}{p}b+\frac{1}{p^{2}}c< p$, prove that $a_{n}<p^{n}$ for all $n\geq 1.$
  6. [20 pnts] Tell if the following functions with the given domain and co-domain have the stated properties. You must give reasons for your answers.
    Function Property Does the function have the stated property? (Yes/No)
         
         
         
    $f(x) = x^{2}+\frac{1}{\pi}$    
    $f(x):\bf R\rightarrow\bf R$ 1 to 1  
         
         
         
         
         
         
    $g(x) = x^{3}-4$    
    $g(x):\bf R\rightarrow\bf R$ onto  
         
         
         
         
         
         
    $h(x)= x+2$    
    $h(x):\bf R^{+}\rightarrow\bf R^{+}$ onto  
         
         
         
         
         
         
    $k(x) = x^{3}+2$    
    $k(x):\bf Z\rightarrow\bf Z$ 1 to 1  
         
         
         
         
         
         
    $m(x) = x^{2}+1$    
    $m(x):\bf Z^{+}\rightarrow\bf Z^{+}$ onto  
         
         
         
  7. [35 pnts] Let $R$ be a relation on the set $A=\{a,b,c,d,e,f,g,h\}$ represented by the following matrix (assume the vertical is from and the horizontal is to):
      a b c d e f g h
    a 1 1 1 1 1 1 1 1
    b 0 1 0 0 0 0 0 0
    c 0 1 1 1 1 1 0 0
    d 0 0 0 1 1 1 0 0
    e 0 0 0 0 1 1 0 0
    f 0 0 0 0 0 1 0 0
    g 0 0 0 0 1 1 1 0
    h 0 0 0 0 0 0 0 1
    1. Draw the directed graph (digraph) representing $R$.
    2. Redraw the digraph from part a as a Hasse Diagram (it does represent a Partial Order Set).
    3. Give the maximal, minimal, greatest and least values by either saying that it doesn't exist or giving the exact values.
      Maximal  
         
      Minimal  
         
      Greatest  
         
      Least  
         
      Assume the Hasse Diagram represents a different relation - call it T. (Notice: it is no longer a digraph, so assume each of the edges represents both directions. It is then a symmetric and irreflexive relation which is not transitive.)


    4. Determine if T has an Euler Circuit. Either give a path (list of vertices) that makes that Euler Circuit or tell why it does not contain an Euler Circuit. (NOTE: THIS IS THE RELATION T from the previous part of this question - not the original R.)












    5. Determine if T has a Hamiltonian Circuit. Either give a path (list of vertices) that make that Hamiltonian Circuit or tell why it does not contain a Hamiltonian Circuit. (NOTE: THIS IS THE RELATION T from the previous part of this question - not the original R.)
  8. [35 pnts] Let $\Sigma$ be an alphabet with $k$ elements in it where $ k \geq 2$.
    1. Find the number of elements in $\Sigma^{i}$ for all $i\geq 0$. Hint: $n(\Sigma^i) $ will be a formula in terms of both $i$ and $k$.
    2. For all $i\geq 0$, Let

      \begin{displaymath}S_{i}=\cup_{j=0}^{i}\Sigma^{j}.\end{displaymath}

      Use induction to prove that $n(S_{i})= \frac{k^{i+1}-1}{k-1}$, for all $i\geq 0$. (Where the function $n$ tells the size of the set.) Hint: This will be induction on $i$ where the formula is given in terms of the variable $k$.
    3. For all $i\geq 1$, prove that any function $f:\Sigma^{i}\rightarrow S_{i-1}$ must map at least $k$ elements to one of the elements in $S_{i}$.

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 finala

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

Fawzi Emad 2003-05-11

Web Accessibility