% Homework 2, 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\;} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{{\bf Homework assignment~2} (143~points)} \centerline{Assigned Friday, January~26, 2007} \centerline{Due 12:30~p.m., Monday, February~5, 2007} \centerline{(Homework five minutes late will {\it not\/} be accepted.)} \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)$ \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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)$ \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. \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)$. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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. \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$.) \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$.) \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$. \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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.) \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Prove or disprove that the product of two irrational numbers is irrational. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye