\documentclass[12pt]{article} \oddsidemargin .25in \evensidemargin .25in \topmargin -0.25in \textwidth 6.0in \textheight 9.5in \sloppy \newcommand{\R}{\mathbb{R}} \usepackage{url, amsmath, amsthm, enumerate, multicol} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{eucal} %\usepackage{boxproof} \usepackage{verbatim} \usepackage{fullpage} \usepackage{soul} \usepackage{color} \definecolor{Light}{gray}{.90} \sethlcolor{Light} \newcounter{bar} \newcommand{\probheadernum}[1]{% \stepcounter{bar}% \noindent{\large\bf Problem \arabic{bar}. {\small (#1 points)}} \smallskip} \newcounter{scantron} \newcommand{\scantronlabelnocount}{{\texttt{{\large\hl{{\small Scantron} XX{}}}}}} \newcommand{\scantronlabel}{ \stepcounter{scantron} {\texttt{{\large\hl{{\small Question} \thescantron{\small }}}}} } \newcommand{\tfproblem}{ \vspace{0.2in} \noindent \hspace{0.4in} {\texttt{\scantronlabel (A) True (B) False}} \vspace{0.2in} } \newcommand{\multchoice}{\vspace{0.3in}\noindent\scantronlabel } \pagenumbering{arabic} \def\infer#1#2{\raisebox{.5ex}{\rule{0pt}{2.5ex}$#1$} \over\raisebox{.5ex}{\rule{0pt}{2.5ex}$#2$}} \def\encl#1#2{\fbox{\parbox{.3em}{$#1$ $\vdots$ $#2$}}} \def\bigencl#1#2{\fbox{\parbox{1em}{$#1$ $~\,\vdots$ $~~#2$}}} \def\bbigencl#1#2{\fbox{\parbox{5em}{$#1$ \hspace{4em} $~~~~~~\vdots~~~$ $~~~~~~~#2$}}} \def\low#1{{\parbox{2em}{$~~~~~~$ $~~~~~~$ $~~~~~~$ $#1$}}} \mathchardef\hyph="2D \newcommand{\premise}{\mathrm{premise}} \newcommand{\assump}{\mathrm{assumption}} \newcommand{\intr}{\mathrm{\hyph intro\ }} \newcommand{\eli}{\mathrm{\hyph elim\ }} \newcommand{\fal}{{\tt F}} \newcommand{\mt}{\mathrm{Modus Tollens\ }} \newcommand{\pbc}{\mathrm{PBC\ }} \newcommand{\romanlist}{(\roman{enumi})} \newcommand{\countlist}{\usecounter{enumi}} \newcommand{\se}{\subseteq} \newcommand{\nat}{{\Bbb N}} \newcommand{\zahl}{{\Bbb Z}} \newcommand{\real}{{\Bbb R}} \newcommand{\rat}{{\Bbb Q}} \thispagestyle{empty} \pagestyle{empty} \begin{document} \section*{ \begin{center} Group assignment 3 -- A practice exam\\ EECS 203\\ Spring 2016 \end{center}} \vspace{0.2in} \noindent {\bf Name (Print): }\hrulefill \vspace{0.3in} \noindent {\bf uniqname (Print): }\hrulefill \vspace{0.4in} \noindent {\bf Name (Print): }\hrulefill \vspace{0.3in} \noindent {\bf uniqname (Print): }\hrulefill \vspace{0.4in} \noindent {\bf Name (Print): }\hrulefill \vspace{0.3in} \noindent {\bf uniqname (Print): }\hrulefill \vspace{1.3in} \noindent {\large \bf General Instructions} \noindent This is a group assignment that is posted as a LaTeX file. You are to answer the questions using LaTeX. The ``exam'' is worth 100 points. Your grade on the assignment is out of 30. For every point you lose on the exam, you lose one on the group assignment (so a 90 exam score would be a 20 group assignment score). \bigskip \newpage \noindent {\large \bf True/False Questions. 2 pts each. \bigskip \noindent\scantronlabel For all sets $A$ and $B$, $A\cup(B\cap\emptyset)=A$. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel For all sets $A$, $\overline{(\overline{A}) \cup A}=A$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \bigskip\bigskip \noindent\scantronlabel $\{\emptyset,\{1\}, \{2\}\}$ is the power set of some set. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel Let $a$ and $b$ be distinct elements. Then $\{\emptyset, \{a\},\{b\},\{a,b\}\}$ is the power set of some set. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel For all sets $A$, $B$ and $C$, if $A\cap C\subseteq B\cap C$, then $A\subseteq B$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel $(p \oplus q) \vee (\lnot p \rightarrow (q \wedge p))$ is a tautology. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \newpage \noindent\scantronlabel $(p \vee r) \wedge (\lnot q \vee r) \wedge (\lnot p \wedge \lnot r)$ is a contradiction. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel $(\lnot q \vee p) \wedge (p \oplus q)$ is satisfiable. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{.5in} \newpage \noindent For problems 9, 10, and 11 below, we define the following propositions. \begin{itemize} \item $s$: We will go swimming this afternoon. \item $t$: There is a thunderstorm today. \end{itemize} Consider the following sentence. \begin{quote} We will not go swimming this afternoon if there is a thunderstorm today. \end{quote} \vspace*{0.5in} \noindent\scantronlabel The sentence above is equivalent to the proposition $\lnot t \rightarrow \lnot s$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel The sentence above is equivalent to the proposition $s\rightarrow \lnot t$. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel The sentence above is equivalent to the proposition $s \lor t$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \newpage \vspace*{0.5in} \noindent\scantronlabel Determine whether the argument given is valid or invalid: \\ Everyone enrolled in the university has eaten at a dining hall. Ralph has not eaten at a dining hall. Therefore, Ralph is not enrolled in the university. \begin{quote} \fbox{(A) Valid}\quad (B) Invalid \end{quote} \vspace*{0.5in} \noindent\scantronlabel $\forall x\exists y (Q(x)\land\lnot P(y))$ is equivalent to $\lnot\exists x \forall y(Q(x)\rightarrow P(y))$. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel $\exists x\forall y Q(x,y)\rightarrow \lnot\exists y\forall x \lnot Q(x,y)$ is a tautology. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \newpage \noindent For problems 16, 17, and 18 below, we define the following predicates. \begin{itemize} \item $C(x)$: $x$ is a child \item $A(x)$: $x$ grew up in Ann Arbor \item $F(x)$: $x$ likes Michigan football \item $B(x)$: $x$ likes barbecues. \end{itemize} Consider the sentence \begin{quote} Every child who grew up in Ann Arbor likes Michigan football and barbecues. \end{quote} \vspace*{0.5in} \noindent\scantronlabel The sentence above is equivalent to $\forall x (C(x) \rightarrow A(x) \land (F(x) \land B(x)))$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{.5in} \noindent\scantronlabel The sentence above is equivalent to $\forall x (C(x) \land A(x) \land (F(x) \land B(x)))$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel The sentence above is equivalent to $$\forall x (((C(x) \land A(x)) \rightarrow F(x)) \land ((C(x) \land A(x)) \rightarrow B(x))).$$ \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \newpage \noindent\scantronlabel The function $f$ from $\zahl^+$ to $\zahl^+$ defined by $f(x)=\left\lfloor 2.5x\right\rfloor$ is onto. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel The function $f$ from $\mathbb{N}$ to $\mathbb{N}$ defined by $f(x)=x^2$ is one-to-one. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel The function $f$ from $\real$ to $\real$ defined by $f(x)=4x^3-7$ is a bijection (one-to-one correspondence). \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel The function $f$ from $\real$ to $\{-1,1\}$ defined by \[f(x) = \begin{cases} -1 & \text{if }x\in \rat\\ 1 & \text{if }x\notin\rat \end{cases}\] is one-to-one. \begin{quote} (A) True \quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \newpage \noindent\scantronlabel The function $f$ from $\real-\{0\}$ to $\real-\{0\}$ given by $f(x)=1/x$ has an inverse. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \vspace*{0.5in} \noindent\scantronlabel The value of the sum \[ \sum_{k=0}^{15} (2e^{k+1} - 2e^k)\] is $2e^{16}$. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel If $A \subseteq B$ and both $A$ and $B$ are countably infinite, then $B - A$ is finite. \begin{quote} (A) True\quad \fbox{(B) False} \end{quote} \vspace*{0.5in} \noindent\scantronlabel The set $\mathbb{Z}^- \cup \mathbb{Q}^+$ is countable. \begin{quote} \fbox{(A) True}\quad (B) False \end{quote} \newpage \noindent{\large\bf Problem 26. 10 points.} \bigskip \noindent Given the premise \[ \forall x P(x) \wedge \exists x Q(x),\] prove \[ \exists x (P(x) \wedge Q(x)) \] using a deductive argument. \vspace*{1in} Solution: \begin{align*} &1) \; \forall x P(x) \wedge \exists x Q(x) && \text{premise}\\ &2) \; \exists x Q(x) && \text{simplification (1)}\\ &3) \; Q(c) && \text{existential instantiation (2)}\\ &4) \; \forall x P(x) && \text{simplification (1)}\\ &5) \; P(c) && \text{universal instantiation (4)}\\ &6) \; P(c) \wedge Q(c) && \text{conjunction (3,5)}\\ &7) \; \exists x (P(x) \wedge Q(x)) && \text{existential generalization (6)} \end{align*} \newpage \noindent{\large\bf Problem 27. 10 points.} \bigskip \noindent (a) Show that if $f:A\rightarrow B$ and $S,T \subseteq A$, then \[(f(S) - f(T))\subseteq f(S - T).\] \vspace*{.5in} Solution: \\ Let $x \in f(S) - f(T)$. Then $x \in f(S)$ and $x \not\in f(T)$. Since $x \in f(S)$, there exists some $y \in S$ such that $f(y) = x$. Furthermore, since $x \not\in f(T)$, it must be the case that $y \not\in T$. Therefore, $y \in S - T$ and so $x \in f(S - T)$. Thus, $(f(S) - f(T))\subseteq f(S - T)$. \vspace*{1in} \noindent (b) Is it also true that $f(S - T)\subseteq (f(S) - f(T))$? Circle one: $$ \mbox{\bf Yes}\qquad \fbox{\mbox{\bf No}} $$ Prove your answer. \vspace*{.5in} Solution: \\ There are many counterexamples that could work here. One is given below. Consider the function $f : \R \to \R$ given by $f(x) = x^2$. Let $S = \R$ and let $T = \R^-$. Then $S - T = \R^+ \cup \{0\}$. Note that in this case, \[ f(S - T) = \R^+ \cup \{0\}.\] However, we have that \[ f(S) = \R^+ \cup \{0\}\] and \[ f(T) = \R^+\] and therefore $f(S) - f(T) = \{0\}$ and so $f(S - T)\not\subseteq (f(S) - f(T))$. \newpage \noindent \bigskip \noindent{\large\bf Problem 28. 10 points.} \bigskip \noindent Let $m$ and $n$ be positive integers. Prove by contraposition that if $m\cdot n + 4$ is odd, then $m$ is odd and $n$ is odd. \vspace*{0.5in} Solution: \\ By means of contraposition, assume that it is not the case that $m$ is odd and $n$ is odd. This means that either $m$ or $n$ is even. Without loss of generality, we may assume that $m$ is even. Therefore, we can write $m = 2k$ for some integer $k$. But then $m\cdot n + 4 = 2k \cdot n + 4 = 2(k \cdot n + 2)$ and therefore we see that $m \cdot n$ is even. \newpage \noindent \bigskip \noindent{\large\bf Problem 29. 10 points.} \bigskip \noindent Let $L(x, y)$ be the statement ``x loves y'', and let $M(x, y)$ be the statement ``x is the mother of y'' where the domain discourse consists of all the people on earth. Use quantifiers to formally express the following statements. \bigskip \noindent (a) Everybody loves their mother. \vspace*{0.2in} \[ \forall x \forall y (M(x,y) \rightarrow L(y,x)) \] \vspace*{0.2in} \noindent (b)Nobody loves everybody. \vspace*{0.2in} \[ \forall x \exists y (\lnot L(x,y)) \] \vspace*{0.2in} \noindent (c) All mothers love all of their children. \vspace*{0.2in} \[ \forall x \forall y (M(x,y) \rightarrow L(x,y)) \] \vspace*{0.2in} \noindent (d) Everyone loves exactly one person. \vspace*{0.2in} \[ \forall x \exists y (L(x,y) \wedge \forall z((y \neq z) \rightarrow \lnot L(x,z)))\] \vspace*{0.2in} \noindent (e) There is someone who loves no one except himself or herself. \vspace*{0.2in} \[ \exists x \forall y ((x \neq y) \rightarrow \lnot L(x,y))\] \vspace*{0.2in} \newpage \noindent \bigskip \noindent{\large\bf Problem 30. 10 points. } \bigskip \noindent \noindent Use the rules of logic to prove that $(\lnot p \wedge (p \vee q)) \rightarrow q$ is a tautology. \vspace*{.5in} Solution: \\ \begin{align*} (\lnot p \wedge (p \vee q)) \rightarrow q &\equiv \lnot(\lnot p \wedge (p \vee q)) \vee q & \text{definition of implication}\\ &\equiv \lnot(\lnot p) \vee \lnot (p \vee q) \vee q & \text{DeMorgan's}\\ &\equiv p \vee \lnot (p \vee q) \vee q & \text{double negation}\\ &\equiv p \vee (\lnot p \wedge \lnot q) \vee q & \text{DeMorgan's}\\ &\equiv (( p \vee \lnot p) \wedge (p \vee \lnot q)) \vee q & \text{distribution}\\ &\equiv (T \wedge (p \vee \lnot q)) \vee q & \text{negation}\\ &\equiv (p \vee \lnot q) \vee q & \text{identity}\\ &\equiv p \vee (\lnot q \vee q) & \text{associative}\\ &\equiv p \vee T & \text{negation}\\ &\equiv T & \text{domination} \end{align*} \end{document}