\documentclass{article}
\usepackage{hyperref}
\usepackage{enumerate}
\pagenumbering{gobble}
\begin{document}
\vspace*{-1.4in}
\flushleft \underline{Homework 2 -- MATH 2510 Spring 2019}\\
\vspace{0.1in}
\begin{enumerate}[1.]
\item Determine whether the statement is a tautology, a contradiction, or neither by constructing a truth table.
\begin{enumerate}[a.]
\item $(\neg P \vee Q) \vee (P \wedge Q)$ \\
\textit{Solution}:  \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
$P$ & $Q$ & $\neg P$ & $\neg P \vee Q$ & $P \wedge Q$ & $(\neg P \vee Q) \vee (P \wedge Q)$ \\
T & T &F&T&T&T \\
T & F &F&F&F&F \\
F & T &T&T&F&T \\
F & F &T&T&F&T \\
\hline
\end{tabular} \\
Therefore, the formula $(\neg P \vee Q) \vee (P \wedge Q)$ is neither a tautology nor a contradiction.

\item $(\neg P \vee \neg Q) \vee (P \wedge Q)$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline 
$P$ & $Q$ & $\neg P$ & $\neg Q$ & $\neg P \vee \neg Q$ & $P \wedge Q$ & $(\neg P \vee \neg Q) \vee (P \wedge Q)$ \\
T &T&F&F&F&T&T \\
T &F&F&T&T&F&T \\
F &T&T&F&T&F&T \\
F &F&T&T&T&F&T \\
\hline
\end{tabular}  \\
Therefore, the formula $(\neg P \vee \neg Q) \vee (P \wedge Q)$ is a tautology.

\item $P \rightarrow (P \vee Q)$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$P$ & $Q$ & $P \vee Q$ & $P \rightarrow (P \vee Q)$ \\
T &T&T&T \\
T &F&T&T \\
F &T&T&T \\
F &F&F&T \\
\hline
\end{tabular} \\
Therefore $P \rightarrow (P \vee Q)$ is a tautology.
\item $Q \leftrightarrow (P \wedge Q)$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$P$ & $Q$ & $P \wedge Q$ & $Q \leftrightarrow (P \wedge Q)$ \\ 
T &T&T&T \\
T &F&F&F \\
F &T&F&T \\
F &F&F&T \\
\hline
\end{tabular}\\
Therefore, the formula $Q \leftrightarrow (P \wedge Q)$ is neither a tautology nor a contradiction.
\end{enumerate}

\item Determine whether the two statements are propositionally equivalent or not by constructing a truth table.
\begin{enumerate}[a.]
\item $P$ and $P \rightarrow P$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$P$ & $P \rightarrow P$ & $P \leftrightarrow (P \rightarrow P)$ \\
T & T & T\\
F & T & T \\
\end{tabular} \\
Since $P \leftrightarrow (P \rightarrow P)$ is a tautology, we may conclude that $P \rightarrow P$ is propositionally equivalent to $P$.

\item $P \rightarrow Q$ and $\neg P \rightarrow \neg Q$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline 
$P$ & $Q$ & $\neg P$ & $\neg Q$ & $P \rightarrow Q$ & $\neg P \rightarrow \neg Q$ & $(P \rightarrow Q) \leftrightarrow (\neg P \rightarrow \neg Q)$ \\
T&T&F&F&T&T&T \\ 
T&F&F&T&F&T&F \\
F&T&T&F&T&F&F \\
F&F&T&T&T&T&T \\
\hline
\end{tabular} \\
Since $(P \rightarrow Q) \leftrightarrow (\neg P \rightarrow \neg Q)$ is not a tautology, we conclude that $P \rightarrow Q$ is \textbf{not} propositionally equivalent to $\neg P \rightarrow \neg Q$.
\item $P$ and $P \vee \neg P$  \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$P$ & $Q$ & $\neg P$ & $P \vee \neg P$ & $P \leftrightarrow (P \vee \neg P)$ \\
T&T&F&T&T \\
T&F&F&T&T \\
F&T&T&T&F \\
F&F&T&T&F \\
\hline
\end{tabular} \\
Since $P \leftrightarrow (P \vee \neg P)$ is not a tautology, we conclude that $P$ is \textbf{not} propositionally equivalent to $P \vee \neg P$.
\end{enumerate}

\item Determine whether or not the second statement is a propositional consequence of the first statement by constructing a truth table.
\begin{enumerate}[a.]
\item $P \wedge (P \rightarrow Q)$ and $Q$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline 
$P$ & $Q$ & $P \rightarrow Q$ & $P \wedge (P \rightarrow Q)$ & $(P \wedge (P \rightarrow Q)) \rightarrow Q$ \\
T &T&T&T&T \\
T &F&F&F&T \\
F &T&T&F&T \\
F &F&T&F&T \\
\hline
\end{tabular} \\
Since $(P \wedge (P \rightarrow Q)) \rightarrow Q$ is a tautology, we conclude that $Q$ is a propositional consequence of $(P \wedge (P \rightarrow Q))$.
\item $\neg P \wedge (P \rightarrow Q)$ and $P$ \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$P$ & $Q$ & $\neg P$ & $P \rightarrow Q$ & $\neg P \wedge (P \rightarrow Q)$ & $(\neg P \wedge (P \rightarrow Q)) \rightarrow P$  \\
T &T&F&T&F&T \\
T &F&F&F&F&T \\
F &T&T&T&T&F \\
F &F&T&T&T&F \\
\hline
\end{tabular} \\
Since $(\neg P \wedge (P \rightarrow Q)) \rightarrow P$ is not a tautology, we conclude that $P$ is \textbf{not} a propositional consequence of $\neg P \wedge (P \rightarrow Q)$.
\end{enumerate}

\item Show that $D$ is a propositional consequence of $(D \vee O) \wedge \neg O$. \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$D$ & $O$ & $\neg O$ & $D \vee O$ & $(D \vee O) \wedge \neg O$ & $((D \vee O) \wedge \neg O) \rightarrow D$ \\ 
T&T&F&T&F&T \\
T&F&T&T&T&T \\
F&T&F&T&F&T \\
F&F&T&F&F&T \\
\hline
\end{tabular} 

\item Show that $\neg C$ is a propositional consequence of $(C \rightarrow \neg D) \wedge D)$. \\
\textit{Solution}: \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|} 
\hline
$C$ & $D$ & $\neg D$ & $C \rightarrow \neg D$ & $(C \rightarrow \neg D) \wedge D$ & $((C \rightarrow \neg D) \wedge D) \rightarrow D$ \\
T&T&F&F&F&T \\
T&F&T&T&F&T \\
F&T&F&T&T&T \\
F&F&T&T&F&T \\
\hline
\end{tabular}

\iffalse
\item Verbally explain why the statement $\exists x [P(x) \wedge \forall y (P(y) \rightarrow y=x)]$ says there is exactly one object for which $P$ is true. (What's intended is an intuitive verbal explanation only).

\item Write a symbolic statement expressing$\ldots$
\begin{enumerate}[a.]
\item ``There are at least three different objects such that $P$."
\item ``
There are exactly two different objects such that $P$."
\end{enumerate}

\item Translate into symbols using using appropriate quantifiers and the given predicates.
\begin{enumerate}[a.]
\item Express
\begin{center}
``All differentiable functions are continuous."
\end{center}
with predicates $D(f)$ for ``$f$ is differentiable" and $C(f)$ for ``$f$ is continuous".
\item Express
\begin{center} 
``There is a complex number that is an integer."
\end{center}
with predicates $C(x)$ for ``$x$ is a complex number" and $N(x)$ for ``$x$ is a natural number". 
\item Express 
\begin{center}
``All Lipschitz functions with compact support are absolutely continuous and of bounded variation."
\end{center}
with predicates $L(f)$ for ``$f$ is Lipschitz", $C(f)$ for ``$f$ has compact support", $A(f)$ for ``$f$ is absolutely continuous", and $B(f)$ for ``$f$ is of bounded variation".
\end{enumerate}
\fi

\end{enumerate}

\end{document}