\documentclass[11pt]{exam}
\usepackage{graphicx}
\usepackage{anysize}
\usepackage{dsfont}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol}
\usepackage{placeins}

\printanswers
%\noprintanswers

\begin{document}

\title{ EECS 203: Discrete Mathematics \\
        Individual Homework 2 (Winter 2016)}
\date{Due: May 12, 2016}
\author{Answer Key}

\maketitle

\begin{questions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf \item[] Textbook Questions:}
\question[3] Section 1.3 Problem 50\\
%%
\begin{solution}
\begin{enumerate}[a)]
\item From the definition (or as seen in the truth table constructed in Exercise 48), $p\downarrow p$ is false when p is true and true when p is false, exactly as $\neg p$ is; thus the two are logically equivalent.
\item The proposition $(p\downarrow q) \downarrow (p\downarrow q)$ is equivalent, by part (a), to $\neg (p \downarrow q)$, which from the definition (or truth table or Exercise 49) is clearly equivalent to $p \vee q$.
\item By Exercise 45, every compound proposition is logically equivalent to one that uses only $\neg$ and $\vee$. But by parts (a) and (b) of the present exercise, we can get rid of all the negations and disjunctions by using NOR's. Thus every compound proposition can be converted into a logically equivalent compound proposition involving only NOR's.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.4 Problem 24 (c,d,e)\\
%%
\begin{solution}
\begin{enumerate}[a)]
\addtocounter{enumi}{2}
\item Let $S(x)$ be "x can swim." Then we have $\exists x\neg S(x)$ the first way, or $\exists x(C(x) \wedge \neg S(x))$ the second way.
\item Let $Q(x)$ be "x can solve quadratic equations." Then we have $\forall x Q(x)$ the first way, or $\forall x(C(x) \rightarrow Q(x))$ the second way.
\item Let $R(x)$ be "x wants to be rich." Then we have $\exists x\neg R(x)$ the first way, or $\exists x(C(x)\wedge \neg R(x))$ the second way.
\end{enumerate}

\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.4 Problem 36\\
%%
\begin{solution}
\begin{enumerate}
\item Since $1^2 = 1$, this statement is false; $x = 1$ is a counterexample. So is $x = 0$ (these are the only two counterexamples).
\item There are two counterexamples: $x = \sqrt2$ and $x = -\sqrt 2$
\item There is one counterexample: $x = 0$.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.5 Problem 14 (a,c,f)\\
%%
\begin{solution}
The answers to this exercise are not unique; there are many ways of expressing the same propositions symbolically. Our domain of discourse for persons here consists of people in this class. We need to make up a predicate in each case.
\begin{enumerate}[a)]
\item Let $S(x, y)$ mean that person $x$ can speak language $y$. Then our statement is $\exists x S(x, Hindi)$.
\addtocounter{enumi}{1}
\item Let $V(x, y)$ mean that person $x$ has visited state $y$. Then our statement is \\
$\exists x(V(x, Alaska) \wedge \neg V(x, Hawaii))$.
\addtocounter{enumi}{2}
\item Let $G(x, y)$ mean that persons $x$ and $y$ grew up in the same town. Then our statement is $\exists x\exists y(x \neq y \wedge G(x, y) \wedge \forall z(G(x, z) \rightarrow (x = y \vee x = z)))$.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 1.5 Problem 28 (b,h)\\
%%
\begin{solution}
\begin{enumerate}[a)]
\addtocounter{enumi}{1}
\item false (no such y exists if x is negative) 
\addtocounter{enumi}{5}
\item false (this system of equations is inconsistent)
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 1.5 Problem 38\\
%%
\begin{solution}
\begin{enumerate}[a)]
\item In English, the negation is "Some student in this class does not like mathematics." With the obvious propositional function, this is $\exists x\neg L(x)$.
\item In English, the negation is "Every student in this class has seen a computer." With the obvious propositional function, this is $\forall xS(x)$.
\item In English, the negation is "For every student in this class, there is a mathematics course that this student has not taken." With the obvious propositional function, this is $\forall x\exists c\neg T(x, c)$.
\item As in Exercise 15f, let $P(z, y)$ be "Room z is in building y ," and let $Q(x, z)$ be "Student x has been in room z ." Then the original statement is $\exists x\forall y\exists z (P(z, y) \wedge Q(x, z))$. To form the negation, we change all the quantifiers and put the negation on the inside, then apply De Morgan’s law. The negation is therefore $\forall x\exists y\forall z (\neg P(z, y)\vee \neg Q(x, z))$, which is also equivalent to $\forall x\exists y\forall z (P(z, y) \rightarrow \neg Q(x, z))$. In English, this could be read, “For every student there is a building such that for every room in that building, the student has not been in that room.”
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.6 Problem 4\\
%%
\begin{solution}
\begin{enumerate}[a)]
\item We have taken the conjunction of two propositions and asserted one of them. This is, according to Table 1, simplification.
\item We have taken the disjunction of two propositions and the negation of one of them, and asserted the other. This is, according to Table 1, disjunctive syllogism. See Table 1 for the other parts of this exercise as well.
\item modus ponens 
\item addition 
\item hypothetical syllogism
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 1.6 Problem 24\\
%%
\begin{solution}
Steps 3 and 5 are incorrect; simplification applies to conjunctions, not disjunctions.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.6 Problem 30\\
%%
\begin{solution}
Let a be "Allen is a good boy"; let h be "Hillary is a good girl"; let d be "David is happy." Then our assumptions are $\neg a \vee h$ and $a \vee d$. Using resolution gives us $h \vee d$, as desired.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.7 Problem 12
%%
\begin{solution}
This is true. Suppose that $a/b$ is a nonzero rational number and that $x$ is an irrational number. We must prove that the product $xa/b$ is also irrational. We give a proof by contradiction. Suppose that $xa/b$ were rational. Since $a/b\neq 0$, we know that $a\neq 0$, so $b/a$ is also a rational number. Let us multiply this rational number $b/a$ by the assumed rational number $xa/b$. By Exercise 26, the product is rational. But the product is $(b/a)(xa/b) = x$, which is irrational by hypothesis. This is a contradiction, so in fact $xa/b$ must be irrational, as desired.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[3] Section 1.7 Problem 18
%%
\begin{solution}
\begin{enumerate}[a)]
\item We must prove the contrapositive: If $n$ is odd, then $3n + 2$ is odd. Assume that $n$ is odd. Then we can write $n = 2k + 1$ for some integer $k$. Then $3n + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 2) + 1$. Thus $3n + 2$ is two times some integer plus 1, so it is odd.
\item Suppose that $3n + 2$ is even and that $n$ is odd. Since $3n + 2$ is even, so is $3n$. If we add or subtract an odd number from an even number, we get an odd number, so $3n − n = 2n$ is odd. But this is obviously not true. Therefore our supposition was wrong, and the proof by contradiction is complete.
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[2] Section 1.7 Problem 20
%%
\begin{solution}
We need to prove the proposition "If $1$ is a positive integer, then $1^2 \geq 1$." The conclusion is the true statement $1 \geq 1$. Therefore the conditional statement is true. This is an example of a trivial proof, since we merely showed that the conclusion was true.
\end{solution}


\end{questions}

\end{document}