\documentclass{article}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage{amssymb}
\usepackage[normalem]{ulem}
\renewcommand*{\arraystretch}{2}

\begin{document}
\flushleft \underline{Homework 2 (solution) -- MATH 2510 Spring 2018} \\
\vspace{1mm}
\# 1.1: Show that $\neg$ and $\vee$ can be taken as primitive symbols in propositional logic. That is, show that each of the symbols $\wedge, \rightarrow$, and $\leftrightarrow$ can be defined in terms of $\neg$ and $\vee$. \\
\textit{Solution}: We can define $A \wedge B$ as $\neg (\neg A \vee \neg B)$. To see this, consider the following truth table: \\
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$\neg A$&$\neg B$&$\neg A \vee \neg B$&$\neg(\neg A \vee \neg B)$&$A \wedge B$ \\
\hline
1&1&0&0&0&1&1 \\
1&0&0&1&1&0&0 \\
0&1&1&0&1&0&0 \\
0&0&1&1&1&0&0 \\
\hline 
\end{tabular} \\
\vspace{1mm}
We can define $A \rightarrow B$ as $B \vee \neg A$. To see this, consider the following truth table: \\
\begin{tabular}{|l|l|l|l|l|}
\hline
$A$&$B$&$\neg A$&$B \vee \neg A$&$A \rightarrow B$ \\
\hline
1&1&0&1&1 \\
1&0&0&0&0 \\
0&1&1&1&1 \\
0&0&1&1&1 \\
\hline 
\end{tabular} \\
\vspace{1mm}
The symbol $\leftrightarrow$ is normally defined as $(A \rightarrow B) \wedge (B \rightarrow A)$, meaning we can define it as $\neg (\neg(A \rightarrow B) \vee \neg(B \rightarrow A))$, in other words, as $\neg(\neg(B \vee \neg A) \vee \neg(A \vee \neg B) )$. To see this, consider the following truth table: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$\neg A$&$\neg B$&$B \vee \neg A$&$A \vee \neg B$&$\neg(B \vee \neg A)$&$\neg(A \vee \neg B)$&$\neg(B \vee \neg A) \vee \neg(A \vee \neg B)$\\
\hline
1&1&0&0&1&1&0&0&0 \\
1&0&0&1&0&1&1&0&1 \\
0&1&1&0&1&0&0&1&1 \\
0&0&1&1&1&1&0&0&0 \\
\hline 
\end{tabular} \\
\textit{(continued below)} \\
\begin{tabular}{|l|l|l|l|l|}
\hline
$\neg(\neg(B \vee \neg A) \vee \neg(A \vee \neg B))$ & $A \leftrightarrow B$ \\
\hline
1&1 \\
0&0 \\
0&0 \\
1&1 \\
\hline
\end{tabular} \\
\vspace{1mm} 
\# 1.3: Find the truth tables for each of the following formulas. State whether each is a tautology, a contradiction, or neither. \\
\begin{enumerate}[(a)]
\item $(\neg A \rightarrow B) \vee ((A \wedge \neg C) \leftrightarrow B)$ \\
\textit{Solution}: Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$C$&$\neg A$&$\neg C$&$\neg A \rightarrow B$&$A \wedge \neg C$&$(A \wedge \neg C) \leftrightarrow B$&$(\neg A \rightarrow B) \vee ((A \wedge \neg C) \leftrightarrow B)$ \\
\hline
1&1&1&0&0&1&0&0&1 \\
1&1&0&0&1&1&1&1&1 \\
1&0&1&0&0&1&0&1&1 \\
1&0&0&0&1&1&1&0&1 \\
0&1&1&1&0&1&0&0&1 \\
0&1&0&1&1&1&0&0&1 \\
0&0&1&1&0&0&0&1&1 \\
0&0&0&1&1&0&0&1&1 \\
\hline 
\end{tabular} \\
\vspace{1mm}
Therefore we see that $(\neg A \rightarrow B) \vee ((A \wedge \neg C) \leftrightarrow B)$ is a tautology.
\newpage
\item $(A \rightarrow B) \wedge (A \rightarrow \neg B)$ \\
\textit{Solution}: Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$\neg B$&$A \rightarrow B$&$A \rightarrow \neg B$&$(A \rightarrow B) \wedge (A \rightarrow \neg B)$ \\
\hline
1&1&0&1&0&0 \\
1&0&1&0&1&0 \\
0&1&0&1&1&1 \\
0&0&1&1&1&1 \\
\hline 
\end{tabular} \\
\vspace{1mm}
Therefore we see that $(A \rightarrow B) \wedge (A \rightarrow \neg B)$ is neither a tautology nor a contradiction.
\item $(A \rightarrow (B \vee C)) \vee (C \rightarrow \neg A)$ \\
\textit{Solution}: Calculate \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$C$&$B \vee C$ & $A \rightarrow (B \vee C)$& $\neg A$ & $C \rightarrow \neg A$ & $(A \rightarrow (B \vee C)) \vee (C \rightarrow \neg A)$ \\
\hline
1&1&1&1&1&0&0&1 \\
1&1&0&1&1&0&1&1 \\
1&0&1&1&1&0&0&1 \\
1&0&0&0&0&0&1&1 \\
0&1&1&1&1&1&1&1 \\
0&1&0&1&1&1&1&1 \\
0&0&1&1&1&1&1&1 \\
0&0&0&0&1&1&1&1 \\
\hline 
\end{tabular} \\
\newpage
\item $((A \rightarrow B) \wedge C) \vee (A \wedge D)$ \\
\textit{Solution}: Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$C$&$D$&$A \rightarrow B$&$(A \rightarrow B) \wedge C$&$A \wedge D$&$((A \rightarrow B) \wedge C) \vee (A \wedge D)$ \\ 
\hline
1&1&1&1&1&1&1&1 \\
1&1&1&0&1&1&0&1 \\
1&1&0&1&1&0&1&1 \\ 
1&1&0&0&1&0&0&0 \\
1&0&1&1&0&0&1&1 \\ 
1&0&1&0&0&0&0&0 \\ 
1&0&0&1&0&0&1&1 \\ 
1&0&0&0&0&0&0&0 \\ 
0&1&1&1&1&1&0&1 \\ 
0&1&1&0&1&1&0&1 \\ 
0&1&0&1&1&0&0&0 \\ 
0&1&0&0&1&0&0&0 \\ 
0&0&1&1&1&1&0&1 \\ 
0&0&1&0&1&1&0&1 \\ 
0&0&0&1&1&0&0&0 \\ 
0&0&0&0&1&0&0&0 \\
\hline
\end{tabular} \\
From this we see that it is neither a tautology nor a contradiction.
\end{enumerate} 
\newpage
\# 1.4: In each of the following, determine whether the two formulas are equivalent.
\begin{enumerate}[(a)]
\item $(A \wedge B) \vee C$ and $(A \rightarrow \neg B) \rightarrow C$ \\
\textit{Solution}: It is sufficient to check if $((A \wedge B) \vee C) \leftrightarrow ((A \rightarrow \neg B) \rightarrow C)$ is a tautology. So, compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline 
$A$ & $B$ & $C$ & $A \wedge B$ & $(A \wedge B) \vee C$ & $\neg B$ & $A \rightarrow \neg B$& $(A \rightarrow \neg B) \rightarrow C$ \\
\hline
1&1&1&1&1&0&0&1 \\
1&1&0&1&1&0&0&1 \\
1&0&1&0&1&1&1&1 \\
1&0&0&0&0&1&1&0 \\
0&1&1&0&1&0&1&1 \\ 
0&1&0&0&0&0&1&0 \\
0&0&1&1&1&1&1&1 \\ 
0&0&0&0&0&1&1&0 \\
\hline
\end{tabular}
Since the columns for $(A \wedge B) \vee C$ and $(A \rightarrow \neg B) \rightarrow C$ have the same values, we see that $((A \wedge B) \vee C) \leftrightarrow ((A \rightarrow \neg B) \rightarrow C)$ is a tautology (\textit{note: I could have made this a column in the truth table itself, but I didn't have room to fit it in nicely!})
\item $(((A \rightarrow B) \rightarrow B) \rightarrow B)$ and $(A \rightarrow B)$ \\
\textit{Solution}: It is sufficient to check if $((((A \rightarrow B) \rightarrow B) \rightarrow B)) \leftrightarrow (A \rightarrow B)$ is a tautology. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$A$ & $B$ & $A \rightarrow B$ & $(A \rightarrow B) \rightarrow B$ & $((A \rightarrow B) \rightarrow B) \rightarrow B$ \\
\hline
1&1&1&1&1 \\
1&0&0&1&0 \\
0&1&1&1&1 \\ 
0&0&1&0&1 \\
\hline
\end{tabular} \\
\vspace{1mm}
Since the columns for $A \rightarrow B$ and $((A \rightarrow B) \rightarrow B) \rightarrow B$ are the same, we see that $((((A \rightarrow B) \rightarrow B) \rightarrow B)) \leftrightarrow (A \rightarrow B)$ is a tautology.
\newpage
\item $(((A \rightarrow B) \rightarrow A) \rightarrow A)$ and $(C \rightarrow D) \vee C$ \\
\textit{Solution}: It is sufficient to check if $(((A \rightarrow B) \rightarrow A) \rightarrow A) \leftrightarrow ((C \rightarrow D) \vee C)$ is a tautology. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$C$&$D$&$A \rightarrow B$& $(A \rightarrow B) \rightarrow A$ & $((A \rightarrow B) \rightarrow A) \rightarrow A$&$C \rightarrow D$ & $(C \rightarrow D) \vee C$ \\ 
\hline
1&1&1&1&1&1&1&1&1 \\
1&1&1&0&1&1&1&0&1 \\
1&1&0&1&1&1&1&1&1 \\ 
1&1&0&0&1&1&1&1&1 \\
1&0&1&1&0&1&1&1&1 \\ 
1&0&1&0&0&1&1&0&1 \\ 
1&0&0&1&0&1&1&1&1 \\ 
1&0&0&0&0&1&1&1&1 \\ 
0&1&1&1&1&0&1&1&1 \\ 
0&1&1&0&1&0&1&0&1 \\ 
0&1&0&1&1&0&1&1&1 \\ 
0&1&0&0&1&0&1&1&1 \\ 
0&0&1&1&1&0&1&1&1 \\ 
0&0&1&0&1&0&1&0&1 \\ 
0&0&0&1&1&0&1&1&1 \\ 
0&0&0&0&1&0&1&1&1 \\
\hline
\end{tabular} \\
\vspace{1mm}
Since the column for $((A \rightarrow B) \rightarrow A) \rightarrow A$ and the column for $(C \rightarrow C) \vee C$ are the same, the formula $(((A \rightarrow B) \rightarrow A) \rightarrow A) \leftrightarrow ((C \rightarrow C) \vee C)$ is a tautology.
\newpage
\item $A \leftrightarrow ((\neg A \wedge B) \vee (A \wedge \neg B))$ and $\neg B$ \\
\textit{Solution}: It is sufficent to check if $(A \leftrightarrow ((\neg A \wedge B) \vee (A \wedge \neg B))) \leftrightarrow \neg B$ is a tautology. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$A$&$B$&$\neg A$&$\neg B$&$\neg A \wedge B$&$A \wedge \neg B$&$(\neg A \wedge B) \vee (A \wedge \neg B)$& $A \leftrightarrow ((\neg A \wedge B) \vee (A \wedge \neg B))$\\
\hline
1&1&0&0&0&0&0&0 \\
1&0&0&1&0&1&1&1 \\
0&1&1&0&1&0&1&0 \\ 
0&0&1&1&0&0&0&1 \\
\hline
\end{tabular} \\
Since the columns for $A \leftrightarrow ((\neg A \wedge B) \vee (A \wedge \neg B))$ and for $\neg B$ are the same, $(A \leftrightarrow ((\neg A \wedge B) \vee (A \wedge \neg B))) \leftrightarrow \neg B$ is a tautology.
\end{enumerate} 

\# 1.5: Show that the following statements are equivalent. 
\begin{enumerate}[(a)]
\item $F \vDash G$,
\item $\vDash F \rightarrow G$, 
\item $F \wedge \neg G$ is unsatifiable, and
\item $F \equiv F \wedge G$.
\end{enumerate}
\textit{Solution}: First we show ``if $(a)$ holds, then $(b)$ holds": if $F \vDash G$ is true, it means in any row where there is a ``$1$" below $F$, then there is a ``$1$" below $G$. We are trying to show that, in that circumstance, that $\vDash F \rightarrow G$, i.e. that $F \rightarrow G$ is a tautology. (\textit{note: below, the second row is struck out because it does not satisfy that $F \vDash G$ since a $1$ in the first column has a $0$ in the second column...it is not under consideration!}) \\
\begin{tabular}{|l|l|l|l|l|}
\hline
$F$&$G$&$F \rightarrow G$  \\
\hline
1&1&1 \\
\sout{1}&\sout{0}&\sout{0} \\
0&1&1 \\
0&0&1 \\
\hline
\end{tabular} \\
Notice that in all the rows under consideration that $F \rightarrow G$ is true, hence it is a tautology (in the circumstance in question, not in general!). 

Now we show that ``if $(b)$ holds, then $(c)$ holds": if $\vDash F \rightarrow G$, it means that the only rows under $F \rightarrow G$ under consideration are those with a $1$ in them and $F \wedge \neg G$ being unsatisfiable means that the relevant rows in that column are all false. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$F$&$G$&$F \rightarrow G$&$\neg G$&$F \wedge \neg G$  \\
\hline
1&1&1&0&0 \\
\sout{1}&\sout{0}&\sout{0}&\sout{1}&\sout{1} \\
0&1&1&0&0 \\
0&0&1&1&0 \\
\hline
\end{tabular} \\
Notice that in all the rows under consideration that $F \wedge \neg G$ is false, hence it is unsatisfiable (in the circumstance in question!). 

Now we show that ``if $(c)$ holds, then $(d)$ holds": we must show that in the situation where $F \wedge \neg G$ is unsatisfiable, it follows that $F \equiv F \wedge G$, i.e. we must show that $F \leftrightarrow (F \wedge G)$ is a tautology. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$F$&$G$&$\neg G$&$F \wedge \neg G$&$F \wedge G$&$F \leftrightarrow (F \wedge G)$  \\
\hline
1&1&0&0&1&1 \\
\sout{1}&\sout{0}&\sout{1}&\sout{1}&\sout{0}&\sout{0} \\
0&1&0&0&0&1 \\
0&0&1&0&0&1 \\
\hline
\end{tabular} \\
Notice that in all of the rows under consideration that $F \leftrightarrow (F \wedge G)$ is true, hence a tautology (in the circumstance in question!). 

Finally, we show that ``if $(d)$ holds, then $(a)$ holds". It is sufficient to show that in the sitaution where $F \leftrightarrow (F \wedge G)$ is a tautology, it follows that $F \vDash G$, i.e. that $F \rightarrow G$ is a tautology. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$F$&$G$&$F \wedge G$&$F \leftrightarrow (F \wedge G)$&$F \rightarrow G$  \\
\hline
1&1&1&1&1 \\
\sout{1}&\sout{0}&\sout{0}&\sout{0}&\sout{0} \\
0&1&0&1&1 \\
0&0&0&1&1 \\
\hline
\end{tabular} \\
Notice that in all rows under consideration that $F \rightarrow G$ is true, hence a tautology (in the circumstance in question!). 

This completes the problem.

\newpage 
Prolog exercise. Consider the Prolog code \texttt{logicops.pl} at \\
\href{https://github.com/tomcuchta/math2510spring2018/blob/master/logicops.pl}{https://github.com/tomcuchta/math2510spring2018/blob/master/logicops.pl}. Copy this code to \href{https://swish.swi-prolog.org/}{SWISH}. 

The fact \texttt{p(a)} is given in the code. To write the conjunction ``$A \wedge B$" in Prolog, we write \texttt{A,B} -- this is why \texttt{conj} is defined as it is in the code. The negation symbol $\neg$ is written as \texttt{\textbackslash +}. Definition 1.6 in the text defines the disjunction $\vee$ as in $P \vee Q$ as $\neg ( \neg P \wedge \neg Q)$. This justifies the defintion of \texttt{disj} in the code.
\begin{enumerate}
\item Run the query \texttt{p(a)}. What is the result? \\
\textit{Solution}: \texttt{True}
\item Run the query \texttt{\textbackslash + p(a)}. What is the result?  \\
\textit{Solution}: \texttt{False}
\item Run the query \texttt{p(b)}. What is the result? \\
\textit{Solution}: \texttt{False}
\item Run the query \texttt{\textbackslash + p(b)}. What is the result?  \\
\textit{Solution}: \texttt{True}
\item Define \texttt{impl} to encode the symbol $\rightarrow$ as in $P \rightarrow Q$ in terms of \texttt{disj}. \\
\textit{Solution}: \texttt{impl(X,Y) :- disj(Y,\textbackslash + X).} \\
\item Define \texttt{iff} to encode the symbol $\leftrightarrow$ as in $P \longleftrightarrow Q$ in terms of \texttt{impl}. \\
\textit{Solution}: \texttt{iff(X,Y) :- conj(impl(X,Y),impl(Y,X)).}
\item Run \texttt{impl(p(a),p(b))}. What is the result? \\
\textit{Solution}: \texttt{False}
\item Run \texttt{impl(\textbackslash + p(a),p(b))}. What is the result?  \\
\textit{Solution}: \texttt{True}
\item Run \texttt{iff(p(a),p(b))}. What is the result? \\
\textit{Solution}: \texttt{False}
\item Run \texttt{iff(p(b),p(a))}. What is the result? \\
\textit{Solution}: \texttt{False}
\end{enumerate}
\end{document}