% Homework 1 solutions, 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\;} \def\[{[\thinspace} \def\]{\thinspace]} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{{\bf Homework assignment~1} (solutions)} \centerline{Assigned Wednesday, January~17, 2007} \centerline{Due 12:30~p.m., Wednesday, January~24, 2007} \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{(d)} Which propositions are logically equivalent to $p\to q$? \solution \part{(a)} $q\to p$. \part{(b)} $\lnot q\to\lnot p$. \part{(c)} $\lnot p\to\lnot q$. \part{(d)} All of the following are logically equivalent to $p\to q$: $\lnot q\to\lnot p$, $\lnot p\lor q$, and of course $p\to q$ itself. \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$. \solution Consider the truth table for $\lnot p\to\lnot q$, shown below. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$\lnot p$&&$\lnot q$&&$\lnot p\to\lnot q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&F&&F&&T&\cr &T&&F&&F&&T&&T&\cr &F&&T&&T&&F&&F&\cr &F&&F&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ The only row where $\lnot p\to\lnot q$ is false is the third row, so we must have $p=\rm F$ and $q=\rm T$. With the truth values of $p$ and~$q$ determined, we can find the truth values of each of the four compound propositions in the problem. \part{(a)} $p\land q=\rm F$. \part{(b)} $p\lor q=\rm T$. \part{(c)} $p\to q=\rm T$. \part{(c)} $q\to p=\rm F$. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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)]$ \solution \mathpart{(a)} $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\to q$&&$p\land(p\to q)$&&$[p\land(p\to q)]\to q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&T&&T&\cr &T&&F&&F&&F&&T&\cr &F&&T&&T&&F&&T&\cr &F&&F&&T&&F&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Since $[p\land(p\to q)]\to q$ is true no matter what truth values are assigned to $p$ and~$q$, we see that $[p\land(p\to q)]\to q$ is a tautology. \medskip \mathpart{(b)} $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\to q$&&$\lnot q$&&$(p\to q)\land\lnot q$&&$\lnot p$&&$[(p\to q)\land\lnot q]\to\lnot p$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&F&&F&&F&&T&\cr &T&&F&&F&&T&&F&&F&&T&\cr &F&&T&&T&&F&&F&&T&&T&\cr &F&&F&&T&&T&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Again, since $[(p\to q)\land\lnot q]\to\lnot p$ is true no matter what truth values are assigned to $p$ and~$q$, we see that $[(p\to q)\land\lnot q]\to\lnot p$ is a tautology. \medskip \mathpart{(c)} $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$r$&&$p{\to}q$&&$q{\to}r$&&$p{\to}r$&&$(q{\to}r){\to}(p{\to}r)$&&$(p{\to}q){\to}[(q{\to}r){\to}(p{\to}r)]$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&T&&T&&T&&T&&T&\cr &T&&T&&F&&T&&F&&F&&T&&T&\cr &T&&F&&T&&F&&T&&T&&T&&T&\cr &T&&F&&F&&F&&T&&F&&F&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &F&&T&&T&&T&&T&&T&&T&&T&\cr &F&&T&&F&&T&&F&&T&&T&&T&\cr &F&&F&&T&&T&&T&&T&&T&&T&\cr &F&&F&&F&&T&&T&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ We see that no matter what truth values are assigned to $p$,~$q$, and~$r$, the compound proposition $(p\to q)\to[(q\to r)\to(p\to r)]$ is true, so $(p\to q)\to[(q\to r)\to(p\to r)]$ is a tautology. \medskip \mathpart{(d)} $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\land q$&&$q\to(p\land q)$&&$p\to[q\to(p\land q)]$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&T&&T&\cr &T&&F&&F&&T&&T&\cr &F&&T&&F&&F&&T&\cr &F&&F&&F&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ The compound proposition $p\to[q\to(p\land q)]$ is always true, no matter what truth values are assigned to $p$ and~$q$, so it is a tautology. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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)$ \solution \part{(a)} We construct a truth table for the two propositions $\lnot(p\lor q)$ and $\lnot p\land\lnot q$. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\lor q$&&$\lnot(p\lor q)$&&$\lnot p$&&$\lnot q$&&$\lnot p\land\lnot q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&F&&F&&F&&F&\cr &T&&F&&T&&F&&F&&T&&F&\cr &F&&T&&T&&F&&T&&F&&F&\cr &F&&F&&F&&T&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ We see that the column for $\lnot(p\lor q)$ and the column for $\lnot p\land\lnot q$ are identical; in other words, $\lnot(p\lor q)$ always has the same truth value as $\lnot p\land\lnot q$, no matter what truth values are assigned to $p$ and~$q$. Therefore, $\lnot(p\lor q)$ and $\lnot p\land\lnot q$ are logically equivalent, so the statement $\lnot(p\lor q)\iff(\lnot p\land\lnot q)$ is true. \part{(b)} In constructing the truth table for the proposition $[(p\to q)\land\lnot p]\to\lnot q$, we discover the following row of the table. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\to q$&&$\lnot p$&&$(p\to q)\land\lnot p$&&$\lnot q$&&$[(p\to q)\land\lnot p]\to\lnot q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &F&&T&&T&&T&&T&&F&&F&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Hence, when $p=\rm F$ and $q=\rm T$, we have $(p\to q)\land\lnot p=\rm T$ but $\lnot q=\rm F$. For these truth values of $p$ and~$q$ the proposition $[(p\to q)\land\lnot p]\to\lnot q$ is false, so this latter proposition is not a tautology. Therefore the statement $[(p\to q)\land\lnot p]\implies\lnot q$ is false. \part{(c)} We make a truth table for the two propositions $(p\land q)\to r$ and $p\to(q\to r)$. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$r$&&$p\land q$&&$(p\land q)\to r$&&$q\to r$&&$p\to(q\to r)$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&T&&T&&T&&T&\cr &T&&T&&F&&T&&F&&F&&F&\cr &T&&F&&T&&F&&T&&T&&T&\cr &T&&F&&F&&F&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &F&&T&&T&&F&&T&&T&&T&\cr &F&&T&&F&&F&&T&&F&&T&\cr &F&&F&&T&&F&&T&&T&&T&\cr &F&&F&&F&&F&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Since the columns for $(p\land q)\to r$ and $p\to(q\to r)$ are identical, we see that the truth values of $(p\land q)\to r$ and $p\to(q\to r)$ are always the same, no matter what truth values are assigned to $p$,~$q$, and~$r$; in other words, these two compound propositions are logically equivalent. Therefore, the statement $\lnot(p\lor q)\iff(\lnot p\land\lnot q)$ is true. \part{(d)} In the truth table for $p\to q$ and $\lnot p\to\lnot q$, we find the following two rows. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\to q$&&$\lnot p$&&$\lnot q$&&$\lnot p\to\lnot q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&F&&F&&F&&T&&T&\cr &F&&T&&T&&T&&F&&F&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ We see that in these two rows, the truth values of $p\to q$ and $\lnot p\to\lnot q$ differ, which means that the truth values of $p\to q$ and $\lnot p\to\lnot q$ are not always the same. Thus $p\to q$ and $\lnot p\to\lnot q$ are not logically equivalent, and the statement $(p\to q)\iff(\lnot p\to\lnot q)$ is false. \part{(e)} Again, we construct a truth table for $(p\lor q)\land q$ and $\lnot(p\land q)$. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\lor q$&&$(p\lor q)\land q$&&$p\land q$&&$\lnot(p\land q)$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&T&&T&&F&\cr &T&&F&&T&&F&&F&&T&\cr &F&&T&&T&&T&&F&&T&\cr &F&&F&&F&&F&&F&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Notice that in this truth table, the truth values of $(p\lor q)\land q$ and $\lnot(p\land q)$ are the same in only one row out of four! Therefore, these two propositions are not logically equivalent, so the statement $(p\lor q)\land q\iff\lnot(p\land q)$ is false. \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)$. \solution \part{(a)} We make a truth table for $p\oplus q$ and $(p\lor q)\land\lnot(p\land q)$. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\oplus q$&&$p\lor q$&&$p\land q$&&$\lnot(p\land q)$&&$(p\lor q)\land\lnot(p\land q)$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&F&&T&&T&&F&&F&\cr &T&&F&&T&&T&&F&&T&&T&\cr &F&&T&&T&&T&&F&&T&&T&\cr &F&&F&&F&&F&&F&&T&&F&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Since the columns for $p\oplus q$ and $(p\lor q)\land\lnot(p\land q)$ are identical, we see that these two compound propositions are logically equivalent, that~is, $(p\oplus q)\iff[(p\lor q)\land\lnot(p\land q)]$. \part{(b)} Shown below is the truth table for $p\oplus q$ and $\lnot(p\leftrightarrow q)$. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\oplus q$&&$p\leftrightarrow q$&&$\lnot(p\leftrightarrow q)$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&F&&T&&F&\cr &T&&F&&T&&F&&T&\cr &F&&T&&T&&F&&T&\cr &F&&F&&F&&T&&F&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ The columns for $p\oplus q$ and $\lnot(p\leftrightarrow q)$ are the same, so these two compound propositions are logically equivalent. Thus, $(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).] \solution \part{(a)} We will use the three logical equivalences given in the problem description to transform the compound proposition $p\leftrightarrow q$ into a logically equivalent proposition that uses only $\lnot$ and~$\lor$. $$\eqalignno{ p\leftrightarrow q &\iff[(p\to q)\land(q\to p)]&\hbox{\[third equivalence\]}\cr &\iff[(\lnot p\lor q)\land(\lnot q\lor p)]&\hbox{\[first equivalence\]}\cr &\iff\lnot[\lnot(\lnot p\lor q)\lor\lnot(\lnot q\lor p)]. &\hbox{\[second equivalence\]}\cr }$$ [Another logically equivalent proposition is $\lnot(p\lor q)\lor\lnot(\lnot p\lor\lnot q)$. The proof that this proposition is logically equivalent to $p\leftrightarrow q$ is left as an exercise.] \part{(b)} As in part~(a), we will use the three logical equivalences to transform the compound proposition $(p\land q)\to(\lnot q\land r)$ into a logically equivalent proposition that uses only $\lnot$ and~$\lor$, one step at a time. $$\eqalignno{ [(p\land q)\to(\lnot q\land r)] &\iff[\lnot(p\land q)\lor(\lnot q\land r)]&\hbox{\[1st equiv.\]}\cr &\iff\bigl(\lnot[\lnot(\lnot p\lor\lnot q)]\lor\lnot(\lnot\lnot q\lor\lnot r)\bigr) &\hbox{\[2nd equiv.\]}\cr &\iff[(\lnot p\lor\lnot q)\lor\lnot(q\lor\lnot r)].&\hbox{\[double negation\]}\cr }$$ The last step was a simplification step, and was not strictly necessary to arrive at a correct answer for this problem (the second-to-last proposition above is perfectly correct, just awkward). (As it turns out, another logically equivalent proposition is simply $\lnot p\lor\lnot q$; again, the proof that this is indeed logically equivalent is left as an exercise.) \part{(c)} Once again, we use the three given equivalences to transform the proposition $[(p\to q)\land(q\lor r)]$ into a logically equivalent proposition. $$\eqalignno{ [(p\to q)\land(q\lor r)] &\iff[(\lnot p\lor q)\land(q\lor r)]&\hbox{\[1st equiv.\]}\cr &\iff\bigl(\lnot[\lnot(\lnot p\lor q)\lor\lnot(q\lor r)]\bigr). &\hbox{\[2nd equiv.\]}\cr }$$ At first glance, this last proposition seems like it should be able to be simplified by double negation; however, upon closer inspection, we see that no single part of this proposition is being negated twice, so no such simplification is possible. \part{(d)} To save us some work, we will use the results of previous problems here. $$\eqalignno{ p\oplus q&\iff\lnot(p\leftrightarrow q)&\hbox{\[by Problem~5(b)\]}\cr &\iff\lnot\bigl(\lnot[\lnot(\lnot p\lor q)\lor\lnot(\lnot q\lor p)]\bigr) &\hbox{\[using part~(a)\]}\cr &\iff[\lnot(\lnot p\lor q)\lor\lnot(\lnot q\lor p)]. &\hbox{\[double negation\]}\cr }$$ As in part~(b), the last step is just simplification, to make our answer less awkward; such simplification is not strictly necessary for a correct answer. $\bigl[$Another logically equivalent proposition is $\lnot[\lnot(\lnot p\lor\lnot q)\lor\lnot(p\lor q)]$. The proof that this is logically equivalent is again left as an exercise.$\bigr]$ \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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? \solution \part{(a)} This is easiest to show with a small truth table. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\quad\hfil#\hfil\quad\cr height2pt&\omit&&\omit&&\omit&\cr &$p$&&$\lnot p$&&$p\mid p$&\cr height2pt&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&\cr &T&&F&&F&\cr &F&&T&&T&\cr height2pt&\omit&&\omit&&\omit&\cr} \hrule}$$ Since the columns for $\lnot p$ and~$p\mid p$ are identical, we see that $\lnot p\iff p\mid p$. (Notice that we only needed two rows in this truth table to cover all possible assignments of truth values to the one variable in our expressions.) \part{(b)} We shall again use a truth table to prove this logical equivalence. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\lor q$&&$p\mid p$&&$q\mid q$&&$(p\mid p)\mid(q\mid q)$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&T&&F&&F&&T&\cr &T&&F&&T&&F&&T&&T&\cr &F&&T&&T&&T&&F&&T&\cr &F&&F&&F&&T&&T&&F&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ The columns for $p\lor q$ and $(p\mid p)\mid(q\mid q)$ are the same, so $(p\lor q)\iff(p\mid p)\mid(q\mid q)$. \part{(c)} After experimenting with various possibilities, we find that $(p\mid q)\mid(p\mid q)$ is logically equivalent to $p\land q$. To prove this, we can use a truth table. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\mid q$&&$(p\mid q)\mid(p\mid q)$&&$p\land q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&F&&T&&T&\cr &T&&F&&T&&F&&F&\cr &F&&T&&T&&F&&F&\cr &F&&F&&T&&F&&F&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ Since the columns for $(p\mid q)\mid(p\mid q)$ and $p\land q$ are identical, we have shown that the two propositions $(p\mid q)\mid(p\mid q)$ and $p\land q$ are logically equivalent. \part{(d)} As in part~(c), we do some experimentation, and discover that $p\mid(q\mid q)$ is logically equivalent to $p\to q$, as shown by the fact that the columns for $p\mid(q\mid q)$ and $p\to q$ are identical in the truth table below. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$q\mid q$&&$p\mid(q\mid q)$&&$p\to q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&F&&T&&T&\cr &T&&F&&T&&F&&F&\cr &F&&T&&F&&T&&T&\cr &F&&F&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ $\bigl[$Another logically equivalent proposition is $p\mid(p\mid q)$, and a third is the more complicated proposition $[(p\mid p)\mid(q\mid q)]\mid(q\mid q)$. As an exercise, show that these really are logically equivalent to $p\to q$.$\bigr]$ \part{(e)} It is possible to use the logical equivalence $(p\leftrightarrow q)\iff(p\to q)\land(q\to p)$ and the results from parts (a),~(c), and~(d) to formulate a proposition that is logically equivalent to $p\leftrightarrow q$, but doing this turns out to be a lot of work and gets very confusing (because the resulting proposition is very long). Instead, we can turn to our favorite technique of {\it ad~hoc\/} experimentation to find that $[(p\mid p)\mid(q\mid q)]\mid(p\mid q)$ is logically equivalent to $p\leftrightarrow q$. The truth table that proves this is shown below. $$\vbox{\offinterlineskip \hrule \halign{&\vrule#&\strut\enspace\hfil#\hfil\enspace\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &$p$&&$q$&&$p\mid p$&&$q\mid q$&&$(p\mid p)\mid(q\mid q)$&&$p\mid q$&&$\bigl((p\mid p)\mid(q\mid q)\bigr)\mid(p\mid q)$&&$p\leftrightarrow q$&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr \noalign{\hrule} height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr &T&&T&&F&&F&&T&&F&&T&&T&\cr &T&&F&&F&&T&&T&&T&&F&&F&\cr &F&&T&&T&&F&&T&&T&&F&&F&\cr &F&&F&&T&&T&&F&&T&&T&&T&\cr height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr} \hrule}$$ I believe that five is the minimum number of Sheffer strokes required. The reason for this belief comes from a result in the field of logic circuits. The Sheffer stroke is equivalent to the logic gate called NAND, and the expression $p\leftrightarrow q$ (called XNOR in logic circuits) requires no fewer than five NAND gates to implement (if no other gates are allowed). You weren't expected to know about logic circuits, but this gives some sort of justification for the claim that at least five Sheffer strokes are needed to produce a logical proposition equivalent to $p\leftrightarrow q$. If you are interested in this, find out more about logic gates, logic circuits, and in particular how to build XNOR using only NAND gates. $\bigl[$The logically equivalent proposition that results from using the logical equivalence $(p\leftrightarrow q)\iff(p\to q)\land(q\to p)$ and the results from parts (a),~(c) and~(d) is $$\bigl([p\mid(q\mid q)]\mid[q\mid(p\mid p)]\bigr)\bigm|\bigl([p\mid(q\mid q)]\mid[q\mid(p\mid p)]\bigr).$$ Another logically equivalent proposition is $$[(p\mid p)\mid p]\bigm|\bigl([(p\mid p)\mid q]\mid[(q\mid q)\mid p]\bigr).$$ As exercises, show that these are both logically equivalent to $p\leftrightarrow q$. An interesting aspect of the second of these is that the first part, $[(p\mid p)\mid p]$, turns out to be a tautology. Why is this useful? What is its role in the compound proposition?$\bigr]$ \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (10~points) Complete the following formal proofs by supplying an explanation for each step. \solution \part{(a)} If $p\to(q\lor\lnot r)$, $\lnot(r\to q)$, and $p\lor s$, then~$s$. \smallskip \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$p\to(q\lor\lnot r)$&Given\cr 2.&$\lnot(r\to q)$&Given\cr 3.&$p\lor s$&Given\cr 4.&$\lnot(\lnot r\lor q)$&2: implication (rule~10.a)\cr 5.&$\lnot(q\lor\lnot r)$&4: commutativity (rule~2.a)\cr 6.&$\lnot p$&1,~5: [conjunction and] modus tollens (rule~20)\cr 7.&$s$&3,~6: [conjunction and] disjunctive syllogism (rule~21)\cr } \part{(b)} If $p\to(q\to r)$, $p\lor\lnot s$, and $q$, then $s\to r$. \smallskip \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$p\to(q\to r)$&Given\cr 2.&$p\lor\lnot s$&Given\cr 3.&$q$&Given\cr 4.&$\lnot s\lor p$&2: commutativity (rule~2.a)\cr 5.&$s\to p$&4: implication (rule~10.a)\cr 6.&$s\to(q\to r)$&2,~5: transitivity of~$\to$ or hypothetical syllogism (rule~24)\cr 7.&$(s\land q)\to r$&6: exportation (rule~14)\cr 8.&$q\to[s\to(q\land s)]$&statement of rule~22\cr 9.&$s\to(q\land s)$&3,~8: modus ponens (rule~19)\cr 10.&$s\to(s\land q)$&9: commutativity (rule~2.b)\cr 11.&$s\to r$&7,~10: transitivity of~$\to$ or hypothetical syllogism (rule~24)\cr } \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 \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$p\to(\lnot q\land r)$&Given\cr 2.&$q$&Given\cr 3.&$p\lor s$&Given\cr 4.&$\lnot s$&Negation of conclusion\cr 5.&$s\lor p$&3: commutativity (rule~2.a)\cr 6.&$\lnot(\lnot s)\lor p$&double negation (rule~1)\cr 7.&$\lnot s\to p$&implication (rule~10.a)\cr 8.&$p$&4,~7: modus ponens (rule~19)\cr 9.&$\lnot q\land r$&1,~8: modus ponens (rule~19)\cr 10.&$\lnot q$&9: simplification (rule~17)\cr 11.&$q\land(\lnot q)$&2,~10: conjunction\cr 12.&contradiction&11: negation law (rule~7.b)\cr } \vfill\eject \item{(b)} If $q\land(r\land p)$, $t\to v$, and $v\to\lnot p$, then $\lnot t\land r$. \smallskip \halign{\indent\llap{#}&\strut\enspace#\hfil\hskip4em&#\hfil\cr &{\bf Proof:}&{\bf Explanation:}\cr 1.&$q\land(r\land p)$&Given\cr 2.&$t\to v$&Given\cr 3.&$v\to\lnot p$&Given\cr 4.&$\lnot(\lnot t\land r)$&Negation of conclusion\cr 5.&$t\lor\lnot r$&4: De~Morgan's law (rule~8)\cr 6.&$\lnot r\lor t$&5: commutativity (rule~2.a)\cr 7.&$r\to t$&6: implication (rule~10.a)\cr 8.&$r\to v$&2,~7: transitivity of~$\to$ or hypothetical syllogism (rule~24)\cr 9.&$r\to\lnot p$&8,~3: transitivity of~$\to$ or hypothetical syllogism (rule~24)\cr 10.&$q$&1: simplification (rule~17)\cr 11.&$r\land p$&1: simplification (rule~17)\cr 12.&$r$&11: simplification (rule~17)\cr 13.&$p$&11: simplification (rule~17)\cr 14.&$\lnot p$&9,~12: modus ponens (rule~19)\cr 15.&$\lnot p\land p$&13,~14: conjunction\cr 16.&contradiction&15: negation law (rule~7.b)\cr } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye