% Homework 2 solutions, CSCE 235, spring 2007 % Assigned 26 January 2007; due 5 February 2007 \pdfpagewidth=8.5truein \pdfpageheight=11truein \hsize=5.5truein \vsize=8.5truein \pdfhorigin=1.5truein \pdfvorigin=1.25truein \headline={\hfil} \footline={\hfil Page~\folio\hfil} \newcount\pno \pno=0 \def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} } \def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} } \def\solution{\nobreak\medskip\noindent{\bf Solution.} } \def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces} \def\mathpart#1#2\par{{% \abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox % \abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox % \part{#1}#2\par}} \def\implies{\;\Longrightarrow\;} % Pilfered from an example on page 106 of the TeXbook \def\qed{{\unskip\nobreak\hfil\penalty50 \hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule} \parfillskip=0pt \finalhyphendemerits=0 \par}} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{{\bf Homework assignment~2} (solutions)} \centerline{Assigned Friday, January~26, 2007} \centerline{Due 12:30~p.m., Monday, February~5, 2007} \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (15~points) Let the domain of discourse consist of all integers. Determine {\it with justification\/} whether each statement below is true or false. \smallskip \item{(a)} $\forall x\;(x-3n)$ \item{(d)} $\exists b\;(42b-5678=15b+667)$ \item{(e)} $\forall k\ge0\;(\sqrt k\le k)$ \item{(f)} $\exists t\not=5\;(t^2-2t-15=0)$ \item{(g)} $\exists!u\;\forall n>0\;(u^n=u)$ \item{(h)} $\exists!c\;(\sqrt31\;\exists q>1\;(pq=377)$ \item{(o)} $\forall m\;\exists!n\;(m+n=0)$ \solution \part{(a)} True; subtracting~3 from any integer results in a smaller (lesser) integer. \part{(b)} False; any integer with absolute value less than~10 will have a square less than~100. \part{(c)} False; $0+|0|\not>0$. \part{(d)} True; $42(235)-5678=15(235)+667$. \part{(e)} True; $\sqrt0=0$, $\sqrt1=1$, and for $k>1$ we have $\sqrt k0$, we have $0^n=0$ and also $1^n=1$. So the {\it existence\/} part is true, but the {\it uniqueness\/} part is false. \part{(h)} True; $1<\sqrt3<2<\sqrt7<3$, so 2 is the unique integer between $\sqrt3$ and~$\sqrt7$. \part{(i)} False; $3^2=9$ and $(-3)^2=9$. As in part~(g), the {\it existence\/} part is true, but the {\it uniqueness\/} part is false. \part{(j)} True; for any~$x$, take $y=-x^2$, and then $x^2+y=0$. \part{(k)} False; no single integer is the additive inverse of every square. \part{(l)} False; if $r=0$ and $s=1$, then $r+s$ is not even, so no $t$ exists such that $2t=r+s$. \part{(m)} True; take $a=1$, then for any~$b$ let $c=b$, so $b/c=a$. \part{(n)} True; $13\cdot29=377$. \part{(o)} True; additive inverses of integers exist and are unique. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) For each of the following statements, give a domain of discourse in which the statement is true and another domain of discourse in which the statement is false. \smallskip \item{(a)} $\exists x\;(5x=8)$ \item{(b)} $\forall y\;\bigl(\sin(\pi y)=0\bigr)$ \item{(c)} $\exists z\;(z^2=-3)$ \item{(d)} $\forall s\;\exists t\;(st=1)$ \item{(e)} $\exists a\;\forall b\;(a+b=0)$ \solution \part{(a)} This statement is true if the domain consists of all rational numbers (or all real numbers, or all complex numbers). It is false if the domain consists of all integers (or all natural numbers, or if the domain is the empty set). \part{(b)} This statement is true if the domain consists of all integers (or all natural numbers, or if the domain is the empty set). It is false if the domain consists of all real numbers (or all rational numbers, or all complex numbers). \part{(c)} This statement is true if the domain consists of all complex numbers (or all imaginary numbers). It is false if the domain consists of all real numbers (or all rational numbers, or all integers, or all natural numbers, or if the domain is the empty set). \part{(d)} This statement is true if the domain consists of all rationals except~0 (or all real numbers except~0, or all complex numbers except~0, or if the domain is the empty set, or if the domain is the set~$\{\pm1\}$, or if the domain is the set of all $n$th roots of unity for some integer~$n$). It is false if the domain consists of all integers (or all natural numbers, or if the domain is any set of numbers containing~0). \part{(e)} This statement is true if the domain consists only of the number~0. It is false if the domain consists of all integers (or if the domain is just about anything else). \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (15~points) For each of the following statements, give the negation of the statement in English, and define and use one or more propositional functions to express the statement and its negation as logical expressions. Be sure to specify the domain of discourse. \smallskip \item{(a)} Every book can be found in the Library of Congress. \item{(b)} Some U.S. president was born in January. \item{(c)} No planet other than Earth is known to support life. \solution \part{(a)} The negation of this statement is the statement ``Not every book can be found in the Library of Congress'' (or ``There exists a book that is not found in the Library of Congress''). Let $P(x)$ be the statement ``$x$~can be found in the Library of Congress'', where the domain consists of all books. Then the original statement can be expressed as $\forall x\;P(x)$ [or $\lnot\exists x\;\lnot P(x)$], and its negation can be expressed as $\exists x\;\lnot P(x)$ [or $\lnot\forall x\;P(x)$]. \part{(b)} The negation of this statement is the statement ``No U.S. president was born in January''. Let $Q(x)$ be the statement ``$x$~was born in January'', where the domain consists of all U.S. presidents. Then the original statement can be expressed as $\exists x\;Q(x)$ [or $\lnot\forall x\;\lnot Q(x)$], and its negation can be expressed as $\forall x\;\lnot Q(x)$ [or $\lnot\exists x\;Q(x)$]. \part{(c)} The negation of this statement is the statement ``Some planet other than Earth is known to support life'' (or ``There exists a planet other than Earth that is known to support life''; but {\bf not} ``All planets other than Earth are known to support life''). Let $R(x)$ be the statement ``$x$~is known to support life'', where the domain consists of all planets. Then the original statement can be expressed as $\lnot\exists x\not={\rm Earth}\;\bigl(R(x)\bigr)$ $\bigl[$or $\forall x\not={\rm Earth}\;\bigl(\lnot R(x)\bigr)$$\bigr]$, and its negation can be expressed as $\exists x\not={\rm Earth}\;\bigl(R(x)\bigr)$ $\bigl[$or $\lnot\forall x\not={\rm Earth}\;\bigl(\lnot R(x)\bigr)$$\bigr]$. Alternatively, define $R(x)$ as above, and let $S(x)$ be the statement ``$x$~is Earth'', again with the domain consisting of all planets. Then the original statement can be expressed as $\forall x\;\bigl(\lnot S(x)\to\lnot R(x)\bigr)$ $\bigl[$or $\lnot\exists x\;\bigl(\lnot S(x)\land R(x)\bigr)$$\bigr]$, and its negation can be expressed as $\exists x\;\bigl(\lnot S(x)\land R(x)\bigl)$ $\bigl[$or $\lnot\forall x\;\bigl(\lnot S(x)\to\lnot R(x)\bigr)$$\bigr]$. \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (33~points) Prove the following statements. You may use any of the logical equivalences and implications given on the handout from class. \smallskip \item{(a)} (8~points) If $(p\to\lnot q)\to r$ and $\lnot r$, then $p\land q$. \item{(b)} (10~points) If $p\to(q\land r)$ and $r\to\lnot(p\land q)$, then~$\lnot p$. \item{(c)} (15~points) If $p\to(\lnot q\to\lnot r)$, $q\to s$, and $p\lor q$, then $\lnot(r\land\lnot s)$. \solution \item{(a)} Here is a direct proof of this statement. \smallskip \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$(p\to\lnot q)\to r$&Given\cr 2.&$\lnot r$&Given\cr 3.&$[(p\to\lnot q)\to r]\land\lnot r$&1,~2: conjunction\cr 4.&$\lnot(p\to\lnot q)$&3: modus tollens\cr 5.&$\lnot(\lnot p\lor\lnot q)$&4: implication\cr 6.&$\lnot[\lnot(p\land q)]$&5: De~Morgan's law\cr 7.&$p\land q$&6: double negation\cr } \medskip \item{(b)} We shall prove this statement using a proof by contradiction. \smallskip \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$p\to(q\land r)$&Given\cr 2.&$r\to\lnot(p\land q)$&Given\cr 3.&$p$&Negation of conclusion\cr 4.&$p\land[p\to(q\land r)]$&1,~3: conjunction\cr 5.&$q\land r$&4: modus ponens\cr 6.&$r$&5: simplification\cr 7.&$r\land[r\to\lnot(p\land q)]$&2,~6: conjunction\cr 8.&$\lnot(p\land q)$&7: modus ponens\cr 9.&$q$&5: simplification\cr 10.&$p\land q$&3,~9: conjunction\cr 11.&$(p\land q)\land\lnot(p\land q)$&8,~10: conjunction\cr 12.&$c$&11: negation law\cr } \vfill\eject \item{(c)} We can use a direct proof to prove this statement. \smallskip \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$p\to(\lnot q\to\lnot r)$&Given\cr 2.&$q\to s$&Given\cr 3.&$p\lor q$&Given\cr 4.&$p\to(r\to q)$&1: contrapositive\cr 5.&$[p\to(r\to q)]\land(p\lor q)$&3,~4: conjunction\cr 6.&$\bigl([p\to(r\to q)]\land p\bigr)\lor\bigl([p\to(r\to q)]\land q\bigr)$&5: distributive law\cr 7.&$\bigl([p\to(r\to q)]\land p\bigr)\lor q$&6: simplification\cr 8.&$\bigl(p\land[p\to(r\to q)]\bigr)\lor q$&7: commutativity\cr 9.&$(r\to q)\lor q$&8: modus ponens\cr 10.&$(r\to q)\lor(q\lor\lnot r)$&9: addition\cr 11.&$(r\to q)\lor(\lnot r\lor q)$&10: commutativity\cr 12.&$(r\to q)\lor(r\to q)$&11: implication\cr 13.&$r\to q$&12: idempotent law\cr 14.&$(r\to q)\land(q\to s)$&2,~13: conjunction\cr 15.&$r\to s$&14: hypothetical syllogism\cr 16.&$\lnot(r\land\lnot s)$&15: implication\cr } \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (20~points) For each of the following arguments, determine {\it with justification\/} whether the {\bf form} of the argument is valid or invalid. If the form of the argument is valid, state which rule of inference it uses. \smallskip \item{(a)} If Michael studies past 3:00~a.m., then he will be tired when he takes the tes. If he is tired when he takes the test, then he will do poorly. Therefore, if Michael studies past 3:00~a.m., he will do poorly on the test. \item{(b)} Boise is the capital of Idaho, and Jackson is the capital of Mississippi. Therefore, Jackson is the capital of Mississippi. \item{(c)} The leaves of my maple tree are not green. If my maple tree is alive, then its leaves are green. Therefore, my maple tree is not alive. \item{(d)} If I won the lottery, I can quit my job. I did not win the lottery. Therefore, I cannot quit my job. \item{(e)} Everyone who lives in Canada loves poutine. The prime minister of Canada lives in Canada. Therefore, the prime minister of Canada loves poutine. \item{(f)} Rhenium is a metal. If rhenium is a metal, then it conducts electricity. Therefore, rhenium conducts electricity. \item{(g)} Unicorns have eight legs. Therefore, unicorns have eight legs, and earthworms migrate south each winter. \item{(h)} If Susan is a truthful person, then every statement Susan makes is true. Susan makes the statement that she is a truthful person. Therefore, Susan is a truthful person. \item{(i)} If the number~$x$ is even, then the number~$x^2$ is even. The number~$x^2$ is even. Therefore, the number~$x$ is even. \item{(j)} The Volta River is in Africa. Therefore, the Volga River is in Russia, or the Volta River is in Africa. \solution \part{(a)} Valid: hypothetical syllogism. \part{(b)} Valid: simplification. \part{(c)} Valid: modus tollens. \part{(d)} Invalid: fallacy of denying the hypothesis. \part{(e)} Valid: universal instantiation. \part{(f)} Valid: modus ponens. \part{(g)} Invalid: $p\to(p\land q)$ is not a tautology. \part{(h)} Invalid: circular reasoning (begging the question). Our conclusion is that Susan is a truthful person. This argument proves the truth of the conclusion by implicitly assuming the truth of the conclusion in the argument itself. \part{(i)} Invalid: fallacy of affirming the conclusion. \part{(j)} Valid: addition. \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Use a direct proof to show that the product of two odd numbers is odd. (Recall that a number~$n$ is odd if and only~if there exists an integer~$k$ such that $n=2k+1$.) \solution Let $x$ and~$y$ be two odd numbers. Then there exists an integer~$k$ such that $x=2k+1$, and there exists an integer~$\ell$ such that $y=2\ell+1$. So the product of $x$ and~$y$ is $$\eqalign{ xy&=(2k+1)(2\ell+1)\cr &=4k\ell+2k+2\ell+1\cr &=2(2k\ell+k+\ell)+1.\cr }$$ Letting $m=2k\ell+k+\ell$, we have $xy=2m+1$. Since $k$ and~$\ell$ are integers, $m$~is an integer. Therefore $xy$ is odd, since it can be written as $2m+1$ for some integer~$m$. \qed \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Use a direct proof to show that the product of two rational numbers is rational. (Recall that a number~$n$ is rational if and only~if there exists an integer~$a$ and there exists an integer~$b$ such that $b\not=0$ and $n=a/b$.) \solution Let $x$ and~$y$ be two rational numbers. Then there exist integers $a$ and~$b$, with $b\not=0$, such that $x=a/b$; and there exist integers $c$ and~$d$, with $d\not=0$, such that $y=c/d$. So the product of $x$ and~$y$ is $$xy=\left(a\over b\right)\left(c\over d\right)={ac\over bd}.$$ Since $a$ and~$c$ are integers, $ac$~is an integer. Since $b$ and~$d$ are nonzero integers, $bd$~is a nonzero integers. So there exist integers $p$ and~$q$, with $q\not=0$, such that $xy=p/q$, namely, $p=ac$ and $q=bd$. Therefore, $xy$~is a rational number. \qed \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Use a proof by contraposition to prove that if $x+y\ge2$, where $x$ and~$y$ are real numbers, then $x\ge1$ or $y\ge1$. \solution Assume that $x<1$ and $y<1$. Then $$x+y<1+1=2,$$ so $x+y\not\ge2$. This proves the contrapositive, namely, if $x<1$ and $y<1$, then $x+y\not\ge2$. Therefore, if $x+y\ge2$, then $x\ge1$ or $y\ge1$. \qed \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Use a proof by contradiction to prove that the sum of a rational number and an irrational number is irrational. (Recall that a number is irrational if and only~if it is not rational.) \solution Let $x$ be a rational number, so that there exist integers $a$ and~$b$, with $b\not=0$, such that $x=a/b$. Let $y$ be an irrational number, so that there do not exist integers $c$ and~$d$ such that $y=c/d$. Assume that $x+y$ is rational. Then there exist integers $m$ and~$n$, with $n\not=0$, such that $x+y=m/n$. So $$y=(x+y)-x={m\over n}-{a\over b}={mb-an\over nb}.$$ Let $c=mb-an$. Since each of $m$,~$b$, $a$, and~$n$ is an integer, $mb-an$~is an integer, so $c$ is an integer. Let $d=nb$. Since $n$ and~$b$ are nonzero integers, $nb$~is a nonzero integer, so $d$ is a nonzero integer. So we have $y=c/d$, where $c$ and~$d$ are integers, with $d\not=0$. This means that $y$ is rational. But this is a contradiction. Hence the sum of a rational number and an irrational number must be irrational. \qed \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Prove or disprove that the product of two irrational numbers is irrational. \solution This statement is false. For example, we know $\sqrt2$ to be irrational (we proved this in class); but $(\sqrt2)(\sqrt2)=2$, which is clearly rational, since we can write $2=2/1$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye