% Homework 1, CSCE 235, spring 2007 % Assigned 17 January 2007; due 24 January 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~1} (70~points)} \centerline{Assigned Wednesday, January~17, 2007} \centerline{Due 12:30~p.m., Wednesday, January~24, 2007} \centerline{(Homework five minutes late will {\it not\/} be accepted.)} \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (4~points) Consider the following propositions. $$\matrix{ p\to q,&\lnot p\to\lnot q,&q\to p,&\lnot q\to\lnot p,\cr \noalign{\smallskip} p\land q,&p\land\lnot q,&\lnot p\land q,&\lnot p\land\lnot q,\cr \noalign{\smallskip} p\lor q,&p\lor\lnot q,&\lnot p\lor q,&\lnot p\lor\lnot q.\cr }$$ \smallskip \item{(a)} Which proposition is the converse of $p\to q$? \item{(b)} Which proposition is the contrapositive of $p\to q$? \item{(c)} Which proposition is the inverse of $p\to q$? \item{(c)} Which propositions are logically equivalent to $p\to q$? \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (4~points) Suppose that the truth value of $\lnot p\to\lnot q$ is known to be false. Give the truth values for \smallskip \item{(a)} $p\land q$, \item{(b)} $p\lor q$, \item{(c)} $p\to q$, \item{(d)} $q\to p$. \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (8~points) Show that each of these implications is a tautology by using truth tables. \smallskip \item{(a)} $[p\land(p\to q)]\to q$ \item{(b)} $[(p\to q)\land\lnot q]\to\lnot p$ \item{(c)} $(p\to q)\to[(q\to r)\to(p\to r)]$ \item{(d)} $p\to[q\to(p\land q)]$ \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Prove or disprove the following. (Hint: Only one line of the truth table is needed to show that a proposition is {\it not\/} a tautology.) \smallskip \item{(a)} $\lnot(p\lor q)\iff(\lnot p\land\lnot q)$ \item{(b)} $[(p\to q)\land\lnot p]\implies\lnot q$ \item{(c)} $[(p\land q)\to r]\iff[p\to(q\to r)]$ \item{(d)} $(p\to q)\iff(\lnot p\to\lnot q)$ \item{(e)} $(p\lor q)\land q\iff\lnot(p\land q)$ \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (4~points) Recall that the ``exclusive~or'' connective is denoted by the symbol~$\oplus$ (see page~5 of the textbook). \smallskip \item{(a)} Show that $(p\oplus q)\iff[(p\lor q)\land\lnot(p\land q)]$. \item{(b)} Show that $(p\oplus q)\iff\lnot(p\leftrightarrow q)$. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (8~points) Every compound proposition can be written using only the connectives $\lnot$ and~$\lor$. This fact follows from the equivalences $(p\to q)\iff(\lnot p\lor q)$, $(p\land q)\iff\lnot(\lnot p\lor\lnot q)$, and $(p\leftrightarrow q)\iff[(p\to q)\land(q\to p)]$. Find propositions logically equivalent to the following, using only the connectives $\lnot$ and~$\lor$. \smallskip \item{(a)} $p\leftrightarrow q$ \item{(b)} $(p\land q)\to(\lnot q\land r)$ \item{(c)} $(p\to q)\land(q\lor r)$ \item{(d)} $p\oplus q$\qquad[Hint: See Problem~5(b).] \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (12~points) The {\it Sheffer stroke\/} is a logical connective written~$\mid$ and defined by the following truth table. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\quad\hfil#\hfil\quad\cr height2pt&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\mid q$&\cr height2pt&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&\cr &T&&T&&F&\cr &T&&F&&T&\cr &F&&T&&T&\cr &F&&F&&T&\cr height2pt&\omit&&\omit&&\omit&\cr} \hrule}$$ This connective is interesting because Henry~M. Sheffer (for whom it is named) proved in~1913 that all compound propositions can be written using only this single connective. You may prove logically or use a truth table (or a combination of both) for the following. \smallskip \item{(a)} Show that $\lnot p\iff p\mid p$. \item{(b)} Show that $(p\lor q)\iff(p\mid p)\mid(q\mid q)$. \item{(c)} Find a proposition equivalent to $p\land q$ using only the Sheffer stroke. \item{(d)} Find a proposition equivalent to $p\to q$ using only the Sheffer stroke. \item{(e)} For {\bf three bonus points}, find a proposition equivalent to $p\leftrightarrow q$ using only the Sheffer stroke. What is the minimum number of Sheffer strokes required? \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Complete the following formal proofs by supplying an explanation for each step. \smallskip \item{(a)} If $p\to(q\lor\lnot r)$, $\lnot(r\to q)$, and $p\lor s$, then~$s$. \smallskip \item{} {\bf Proof:} \itemitem{1.} $p\to(q\lor\lnot r)$ \itemitem{2.} $\lnot(r\to q)$ \itemitem{3.} $p\lor s$ \itemitem{4.} $\lnot(\lnot r\lor q)$ \itemitem{5.} $\lnot(q\lor\lnot r)$ \itemitem{6.} $\lnot p$ \itemitem{7.} $s$ \vfill\eject \item{(b)} If $p\to(q\to r)$, $p\lor\lnot s$, and $q$, then $s\to r$. \smallskip \item{} {\bf Proof:} \itemitem{1.} $p\to(q\to r)$ \itemitem{2.} $p\lor\lnot s$ \itemitem{3.} $q$ \itemitem{4.} $\lnot s\lor p$ \itemitem{5.} $s\to p$ \itemitem{6.} $s\to(q\to r)$ \itemitem{7.} $(s\land q)\to r$ \itemitem{8.} $q\to[s\to(q\land s)]$ \itemitem{9.} $s\to(q\land s)$ \itemitem{10.} $s\to(s\land q)$ \itemitem{11.} $s\to r$ \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Complete the following proofs by contradiction by supplying an explanation for each step. \smallskip \item{(a)} If $p\to(\lnot q\land r)$, $q$,~and $p\lor s$, then~$s$. \smallskip \item{} {\bf Proof:} \itemitem{1.} $p\to(\lnot q\land r)$ \itemitem{2.} $q$ \itemitem{3.} $p\lor s$ \itemitem{4.} $\lnot s$ \itemitem{5.} $s\lor p$ \itemitem{6.} $\lnot(\lnot s)\lor p$ \itemitem{7.} $\lnot s\to p$ \itemitem{8.} $p$ \itemitem{9.} $\lnot q\land r$ \itemitem{10.} $\lnot q$ \itemitem{11.} $q\land(\lnot q)$ \itemitem{12.} contradiction \medskip \item{(b)} If $q\land(r\land p)$, $t\to v$, and $v\to\lnot p$, then $\lnot t\land r$. \smallskip \item{} {\bf Proof:} \itemitem{1.} $q\land(r\land p)$ \itemitem{2.} $t\to v$ \itemitem{3.} $v\to\lnot p$ \itemitem{4.} $\lnot(\lnot t\land r)$ \itemitem{5.} $t\lor\lnot r$ \itemitem{6.} $\lnot r\lor t$ \itemitem{7.} $r\to t$ \itemitem{8.} $r\to v$ \itemitem{9.} $r\to\lnot p$ \itemitem{10.} $q$ \itemitem{11.} $r\land p$ \itemitem{12.} $r$ \itemitem{13.} $p$ \itemitem{14.} $\lnot p$ \itemitem{15.} $\lnot p\land p$ \itemitem{16.} contradiction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye