%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Note to students! %
% %
% This source file is provided to give example LaTeX code. We do not recommend %
% trying to compile it, since it has some advanced LaTeX dependencies. %
% Specifically, this file depends on the cse311-common.cls file (link below) %
% and LuaLaTeX. The course staff will not be able to help much with %
% configuring your system for LuaLaTeX. %
% https://courses.cs.washington.edu/courses/cse311/21sp/section/cse311-common.cls
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[section,problems]{../../latex-common/cse311-common}
\sectionnumber{01}
\topic{Propositional Logic Translation}
\begin{document}
\maketitle
\section{Warm-Up}
Translate the English sentences below into symbolic logic.
\begin{enumeratequestions}
\item If I am lifting weights this afternoon, then I do a warm-up exercise.
\begin{solution}
Since we're in ``if...then...'' form, the sentence is an implication. \\
$a$: I am lifting weights\\
$b$: I do a warm-up exercise
$$a\rightarrow b$$
\end{solution}
\item If I am cold and going to bed or I am two-years old, then I carry a blanket.
\begin{solution}
$a$: I am cold\\
$b$: I am going to bed\\
$c$: I am two-years old\\
$d$: I carry a blanket
$$[(a\wedge b) \vee c]\rightarrow d$$
How did we know the translation wasn't $[a \wedge (b \vee c)] \rightarrow d]$? Two hints were available: first, omitted words (``going to bed'' instead of ``I am going to bed'' indicates $b$ should be closer to the ``and'' than the ``or''), second the interpretation of the sentence -- two-year olds more commonly carry blankets during the day than warm adults.
\end{solution}
\end{enumeratequestions}
\section{Truth Tables}
Write a truth table for each of the following:
\begin{enumeratequestions}
\item
$(r \oplus q) \vee (r \oplus \neg q)$
\begin{solution}
\begin{truth-table}{5}{$r$ & $q$ & $r \oplus q$ & $r \oplus \neg q$ & $(r \oplus q) \vee (r \oplus \neg q)$}
T & T & F & T & T\\\hline
T & F & T & F & T\\\hline
F & T & T & F & T\\\hline
F & F & F & T & T\\\hline
\end{truth-table}
\end{solution}
\item
$(r \vee q) \rightarrow (r \oplus q)$
\begin{solution}
\begin{truth-table}{5}{$r$ & $q$ & $r \vee q$ & $r \oplus q$ & $(r \vee q) \rightarrow (r \oplus q)$}
T & T & T & F & F\\\hline
T & F & T & T & T\\\hline
F & T & T & T & T\\\hline
F & F & F & F & T\\\hline
\end{truth-table}
\end{solution}
\item
$p \leftrightarrow \neg p$
\begin{solution}
\begin{truth-table}{4}{$p$ & $\neg p$ & $p \leftrightarrow \neg p$}
T & F & F\\\hline
F & T & F\\\hline
\end{truth-table}
\end{solution}
\end{enumeratequestions}
\section{If I can translate, then...}
For each of the following more obscure English ways to write an implication, define atomic propositions and write a symbolic representation of the sentence.
\begin{enumeratequestions}
\item whenever I walk my dog, I make new friends.
\begin{solution}
$p$: I walk my dog\\
$r$: I make new friends
$$p \rightarrow r$$
The promise is that we will definitely make new friends on the condition of walking our dog.
\end{solution}
\item I will drink coffee, if Starbucks is open or my coffeemaker works.
\begin{solution}
$a$: I will drink coffee\\
$b$: Starbucks is open\\
$c$: my coffeemaker works
$$(b \vee c) \rightarrow a$$
\end{solution}
\item Being a U.S. citizen and over 18 is sufficient to be eligible to vote.
\begin{solution}
$a$: One is a U.S. citizen\\
$b$: One is over 18\\
$c$: One is eligible to vote
$$(a \wedge b)\rightarrow c$$
The original sentence omits a subject. We introduced a dummy subject ``one'' to the propositions, you might have said ``someone'' or ``a person'' instead (among other options).
\end{solution}
\item I can go home only if I have finished my homework.
\begin{solution}
$p$: I can go home.\\
$r$: I have finished my homework.
$$p \rightarrow r$$
The promise here is that if I can go home then I must have finished my homework. It can sometimes help to imagine when the sentence is broken. Is it broken if my homework is finished, but I cannot go home? No, perhaps I also have to say bye to my friends before I leave. But if I can go home with unfinished homework, then the promise is broken.
``Only if'' is one of the more confusing arrangements -- the consequence (``the then part'') is adjacent to the ``only if.''
\end{solution}
\item Having an internet connection is necessary to log onto zoom.
\begin{solution}
$p$: One has an internet connection\\
$r$: One can log onto zoom
$$r \rightarrow p$$
The internet connection is not enough (what if you don't have the meeting link?) but certainly if you are in the meeting then you have a connection.
\end{solution}
\end{enumeratequestions}
\section{I can rewrite these formulas in English, only if...}
Given propositions and a logical formula, write \textbf{two} potential English translations. The meanings of the sentences will be the same (They represent the same formula!), but they can still look quite different.
\begin{enumeratequestions}
\item $p$: The sun is out\\
$r$: We have class outside
$$p\rightarrow r$$
\begin{solution}
If the sun is out, then we have class outside.\\
Whenever the sun is out, we have class outside.
\end{solution}
\item $a$: the book has been out for a week.\\
$b$: I don't have homework.\\
$c$: I have finished reading the book.
$$(a \wedge b) \rightarrow c$$
\begin{solution}
I have finished reading the book, if it has been out for a week and I don't have homework.\\
The book being out for a week and me not having homework is sufficient for me to have finished reading the book.
\end{solution}
\item $p$: I have read the manual\\
$r$: I operate the machine
$$r \rightarrow p$$
\begin{solution}
I operate the machine only if I have read the manual. \\
Operating the machine implies that I have read the manual.
\end{solution}
\end{enumeratequestions}
\section{Translation}
For each of the following, define propositional variables and translate
the sentences into logical notation.
\begin{enumeratequestions}
\item
I will remember to send you the address only if you send me an
e-mail message.
\begin{solution}
\begin{align*}
p:\; &\text{I will remember to send you the address}\\
r:\; & \text{You send me an e-mail message}
\end{align*}
\begin{center}
\fbox{$p \rightarrow r$}
\end{center}
\end{solution}
\item If berries are ripe along the trail, hiking is safe if and
only if grizzly bears have not been seen in the area.
\begin{solution}
\begin{align*}
a:\; & \text{Berries are ripe along the trail}\\
b:\; & \text{Hiking is safe}\\
c:\; & \text{Grizzly bears have not been seen in the area}
\end{align*}
\begin{center}
\fbox{$a \rightarrow (b \leftrightarrow c)$}
\end{center}
\end{solution}
\item Unless I am trying to type something, my cat is either eating or sleeping.
\begin{solution}
\begin{align*}
a:\; & \text{My cat is eating}\\
b:\; & \text{My cat is sleeping}\\
c:\; & \text{I'm trying to type }\\
\end{align*}
\begin{center}
\fbox{$\neg c \rightarrow (a \oplus b)$}
\end{center}
\end{solution}
\end{enumeratequestions}
\section{Tea Time}
Consider the following sentence:
\vspace{1em}
\begin{center}
If I am drinking tea then I am eating a cookie, or, if I am eating a cookie then I am drinking tea.
\end{center}
\begin{enumeratequestions}
\item
Define propositional variables and translate the sentence into an expression in logical notation.
\begin{solution}
\begin{align*}
p:\; & \text{I am drinking tea}\\
r:\; & \text{I am eating a cookie}\\
\end{align*}
\begin{center}
\fbox{$(p \rightarrow r) \vee (r \rightarrow p)$}
\end{center}
\end{solution}
\item Fill out a truth table for your expression.
\begin{solution}
\begin{truth-table}{5}{$p$ &$r$ &$(p \rightarrow r)$ &$(r \rightarrow p)$ &$(p \rightarrow r) \vee (r \rightarrow p)$}
T & T & T & T & T\\\hline
T & F & F & T & T\\\hline
F & T & T & F & T\\\hline
F & F & T & T & T\\\hline
\end{truth-table}
\end{solution}
% \item Based on your truth table, classify the original sentence as a contingency, tautology, or contradiction.
% \begin{solution}
% Tautology
% \end{solution}
\end{enumeratequestions}
\section{??clusive Or}
Exclusive or ($\oplus$) and inclusive or ($\vee$) both can be translated as ``or'' in English. For each of the following ambiguous phrases, decide which type of ``or'' is likely meant and why.
\begin{enumeratequestions}
\item Experience with C or Java is required.
\begin{solution}
Inclusive or. Experience with both is usually not a bad thing.
\end{solution}
\item Lunch includes soup or salad.
\begin{solution}
Exclusive or. Most restaurants charge you more for both.
\end{solution}
\item Publish or perish.
\begin{solution}
This phrase is a common one among researchers -- it means publish papers or your career will perish. Exclusive or is meant; i.e. if you do indeed publish you should avoid the loss of your career.
\end{solution}
\item To enter the country, you need a passport or voter registration card.
\begin{solution}
Inclusive or -- if you have both, they won't kick you out!
\end{solution}
\end{enumeratequestions}
\section{Non-equivalence}
Prove that the following pairs of propositional formulae are not equivalent by finding inputs they differ on.
\begin{enumeratequestions}
\item
$p \rightarrow r$ vs. $r \rightarrow p$
\begin{solution}
When $p = \textsf{T}$ and $r = \textsf{F}$, then $p \rightarrow r \equiv \textsf{F}$, but $r \rightarrow p \equiv \textsf{T}$.
\end{solution}
\item $a \rightarrow (b \land c)$ vs. $(a \rightarrow b) \land c$
\begin{solution}
When $a = \textsf{F}$ and $c = \textsf{F}$, then $a \rightarrow (b \land c) \equiv \textsf{T}$ (by vacuous truth), but $(a \rightarrow b) \land c \equiv \textsf{F}$ (because $c$ is false).
\end{solution}
\end{enumeratequestions}
\newpage
\section{They mean the same thing}
In the activity from lecture 2, we showed the following.
\[ \neg(q \to r) \equiv \neg (\neg q \vee r) \]
Use the \href{https://courses.cs.washington.edu/courses/cse311/21sp/resources/logicalConnectPoster.pdf}{elementary equivalences} presented at the end of lecture 2 to argue that the following pairs are equivalent.
\begin{eqnarray}
\neg (\neg q \vee r) &\equiv& \neg (\neg q) \wedge \neg r
\\ \neg (\neg q) \wedge \neg r &\equiv& q \wedge \neg r
\\ q \wedge \neg r &\equiv& \neg r \wedge q
\end{eqnarray}
Your friend says this means that $\neg(q \to r) \equiv \neg r \wedge q$. Is that true?
\begin{solution}
\begin{eqnarray*}
\neg(q \to r) &\equiv& \neg (\neg q \vee r) \quad \textrm{(Activity in Lecture 2)} \\
&\equiv& \neg (\neg q) \wedge \neg r \quad \textrm{(De Morgan)} \\
&\equiv& q \wedge \neg r \quad \textrm{(Double negation)} \\
&\equiv& \neg r \wedge q \quad (\textrm{Commutativity})
\end{eqnarray*}
For any statements $A$, $B$, and $C$, if $A$ and $B$ agree on all possible truth assignments and $B$ and $C$ do too, then $A$ and $C$ agree on all possible truth assignments, so the above chain of equivalences shows that $\neg(q \to r) \equiv \neg r \wedge q$.
\end{solution}
\section{Equivalent Translations}
Prove that the following English statements are equivalent.\\
(i) Unless it isn't raining or I don't have an umbrella, I buy a book.\\
(ii) It isn't raining or I don't have an umbrella or I buy a book.
\begin{solution}
$$a: \text{It is raining.}$$
$$b: \text{I have an umbrella.}$$
$$c: \text{I buy a book.}$$
When we say unless a, b, this suggests that as long as a is not true, b will be true. Then, we can rewrite (i) as follows:
$$\neg (\neg a \vee \neg b) \rightarrow c$$
With the same propositional variables, we can rewrite (ii) as:
$$\neg a \vee \neg b \vee c$$
If these two compound propositions are equivalent, then the English statements are equivalent. Starting with the left-hand side
\begin{align*}
\neg (\neg a \vee \neg b) \rightarrow c & \equiv (\neg \neg a \land \neg \neg b) \rightarrow c && \text{[DeMorgan's Laws]} \\
& \equiv (a \land b) \rightarrow c && \text{[Double Negation]} \\
& \equiv \neg (a \land b) \vee c && \text{[Law of Implication]} \\
& \equiv (\neg a \vee \neg b) \vee c && \text{[DeMorgan's Laws]} \\
\end{align*}
Therefore, we've shown that the two English statements are equivalent.
\end{solution}
\section{Circuitous}
Translate the following circuit into a logical expression.
\vspace{1em}
\begin{center}
\begin{circuitikz} \draw
(0,0) node (r) {$r$}
(0,2) node (p) {$p$}
(2,2) node[not port] (notp) {\hspace{-1.1em}\tiny NOT}
(1.5,0) node[not port] (notr) {\hspace{-1.1em}\tiny NOT}
(4,0) node[and port] (and) {\hspace{-0.8em}\tiny AND}
(6,1) node[or port](or) {\hspace{-0.5em}\tiny OR}
(8,1) node[not port] (not) {\hspace{-1.1em}\tiny NOT}
(9.5,1) node (out) {\tiny\textsc{OUT}}
(p) -- (notp.in)
(p) -- (and.in 1)
(notp.out) -- (or.in 1)
(r) -- (notr.in)
(notr.out) -- (and.in 2)
(and.out) -- (or.in 2)
(or.out) -- (not.in)
(not.out) -- (out);
\end{circuitikz}
\end{center}
\begin{solution}
$\neg(\lnot p \vee (p \land \neg r))$
\end{solution}
\end{document}