unit09.tex

\providecommand{\main}{..}
\documentclass[\main/notes.tex]{subfiles}

\begin{document}
	\ifSubfilesClassLoaded{\setcounter{chapter}{8}}{}
	\chapter{Logic: Truth Tables}
		\section{Declarative Statements}
			A declarative statement is a statement that conveys information.
			\begin{description}
				\item[Declarative Statements] Some examples are:
					\begin{itemize}[nosep]
						\item The capital of France is Paris
						\item 3 is an even integer
						\item This sentence is false
					\end{itemize}
				\item[Non-Declarative Statements] Some examples are:
					\begin{itemize}[nosep]
						\item Is 3 an even integer? (\emph{Question}: acquire information, not convey information)
						\item Add 3 to 5! (\emph{Command}: induce behaviour, not convey information)
					\end{itemize}
			\end{description}
			\begin{sidenote}{Not all declarative statements are usable}
				A declarative statement is not necessarily true or false, as there can be a contradiction in the statement.\\
				However, when dealing with proofs, declarative statements are restricted to those that can be either \emph{true} or \emph{false}.
			\end{sidenote}
			A declarative statement can either be
			\begin{itemize}[nosep]
				\item \concept{atomic}, (or simple) meaning they convey a single fact, or
				\item \concept{compound}, meaning they combine multiple atomic statements.
			\end{itemize}
		\section{Combining Statements}
			Statements can be combined using different \concept{logical connectives}. Below is a list of the possible connectives.
			\begin{center}
				\begin{tblr}{colspec={l c l}, stretch=0}
					and & $\land$ & conjunction\\
					or & $\lor$ & disjunction\\
					not & $\lnot $ & negation\\
					if and only if & $\leftrightarrow$ & biconditional\\
					if \ldots, then \ldots & $\rightarrow$ & conditional/implication
				\end{tblr}
			\end{center}
			\subsection[Conjunction]{Conjunction (AND)}
				\begin{definition}{Conjunction}
					If $p$ and $q$ represent declarative statements, then $p \land q$ represents the statement ``$p$ and $q$'', and is called the \concept{conjunction} of $p$ and $q$.
				\end{definition}
				\nopagebreak
				\begin{center}
					\begin{tblr}{colspec={|c c | c|}, row{1}={font=\bfseries}, row{even}={definition color}}
						\toprule
						$p$ & $q$ & $p \land q$\\
						\midrule
						T & T & T\\
						T & F & F\\
						F & T & F\\
						F & F & F\\
						\bottomrule
					\end{tblr}	
				\end{center}
			\subsection[Disjunction]{Disjunction (OR)}
				\begin{definition}{Disjunction}
					If $p$ and $q$ represent declarative statements, then $p \lor q$ represents the statement ``$p$ or $q$'', and is called the \concept{disjunction} of $p$ and $q$.
				\end{definition}
				\nopagebreak
				\begin{center}
					\begin{tblr}{colspec={|c c | c|}, row{1}={font=\bfseries}, row{even}={definition color}}
						\toprule
						$p$ & $q$ & $p \lor q$\\
						\midrule
						T & T & T\\
						T & F & T\\
						F & T & T\\
						F & F & F\\
						\bottomrule
					\end{tblr}
				\end{center}
			\subsection{Negation}
				\begin{definition}{Negation}
					If $p$ is some declarative statement, then $\lnot p$ represents the statement ``not $p$''. This is called the \concept{negation} of a given statement.
				\end{definition}
				\nopagebreak
				\begin{center}
					\begin{tblr}{colspec={| c | c |}, row{1}={font=\bfseries}, row{even}={definition color}}
						\toprule
						$p$ & $\lnot p$\\
						\midrule
						T & F\\
						F & T\\
						\bottomrule
					\end{tblr}
				\end{center}
			\pagebreak
			\subsection{Biconditional}
				\begin{definition}{Biconditional}
					If $p$ and $q$ represent declarative statements, then $p \leftrightarrow q$ represents the statement $p$ if and only if $q$, which can also be written $p$ iff $q$. This is called the \concept{biconditional}.
				\end{definition}
				\nopagebreak
				\begin{center}
					\begin{tblr}{colspec={|c c | c|}, row{1}={font=\bfseries}, row{even}={definition color}}
						\toprule
						$p$ & $q$ & $p \leftrightarrow q$\\
						\midrule
						T & T & T\\
						T & F & F\\
						F & T & F\\
						F & F & T\\
						\bottomrule
					\end{tblr}
				\end{center}
			\subsection[Conditional]{Conditional/Implication}
				\begin{definition}{Implication}
					If $p$ and $q$ represent declarative statements, then $p \rightarrow q$ represents the statement ``If $p$, then $q$'', and is called a \concept{conditional statement} or \concept{implication}. $p$ is called the \concept{hypothesis} or the \concept{antecedent} and $q$ is called the \concept{conclusion} or \concept{consequent}.
				\end{definition}
				\nopagebreak
				\begin{center}
					\begin{tblr}{colspec={|c c | c|}, row{1}={font=\bfseries}, row{even}={definition color}}
						\toprule
						$p$ & $q$ & $p \rightarrow q$\\
						\midrule
						T & T & T\\
						T & F & F\\
						F & T & T\\
						F & F & T\\
						\bottomrule
					\end{tblr}	
				\end{center}
				\nopagebreak
				\begin{sidenote}{If the hypothesis is false, then the statement is true}
					This can be quite confusing. The idea is that if the original statement is false, we can't say that the next statement is not true.
					\begin{example}
						Consider a statement ``If you read books, you are smart''.
						\begin{indentparagraph}
							If someone reads books and is smart, this is true.\\
							If someone reads books and is not smart, this is false.\\
							If someone does not read books, we cannot say the statement is false, but we also cannot say it is true. So the statement would be vacuously true.
						\end{indentparagraph}
					\end{example} 
				\end{sidenote}
		\pagebreak
		\section{Constructing Truth Tables}
			\begin{enumerate}
				\item List the statements at the top.
				\item For the first column, fill half of the rows with T and half with F.
				\item For the second column, for the rows that have T, write T for the upper half, and F for the lower half. Do the same for F.
				\item Continue doing that until the base statements are filled.
				\item Then apply the rules to the columns left to right.
			\end{enumerate}
			\begin{example}[width=0.6\textwidth]
				Construct a truth table for $p \land (\lnot q)$.
					\begin{center}
						\begin{tblr}{colspec={| c c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
							\toprule
							$p$ & $q$\\
							\midrule
							T & T\\
							T & F\\
							F & T\\
							F & F\\
							\bottomrule
						\end{tblr} \hspace{0.25cm}
						\begin{tblr}{colspec={| c c | c|}, row{1}={font=\bfseries}, row{odd[3]}={white}}
							\toprule
							$p$ & $q$ & $\lnot q$\\
							\midrule
							T & T & F\\
							T & F & T\\
							F & T & F\\
							F & F & T\\
							\bottomrule
						\end{tblr} \hspace{0.25cm}
						\begin{tblr}{colspec={| c c | c | c|}, row{1}={font=\bfseries}, row{odd[3]}={white}}
							\toprule
							$p$ & $q$ & $\lnot q$ & $p \land (\lnot q)$\\
							\midrule
							T & T & F & F\\
							T & F & T & T\\
							F & T & F & F\\
							F & F & T & F\\
							\bottomrule
						\end{tblr}
					\end{center}
			\end{example}
			\begin{exercise}{Activity \thechapter.4}
				\begin{questions}
					\item Construct a truth table for $\bigl[\lnot p \rightarrow (q \land r)\bigr] \lor r$
						\begin{answer}
							\begin{center}
								\begin{tblr}{colspec={| c c c | c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
									\toprule
									$p$ & $q$ & $r$ & $\lnot p$ & $q \land r$ & $\lnot p \rightarrow (q \land r)$ & $[\lnot p \rightarrow (q \land r)] \lor r$\\
									\midrule
									T & T & T & F & T & T & T\\
									T & T & F & F & F & T & T\\
									T & F & T & F & F & T & T\\
									T & F & F & F & F & T & T\\
									F & T & T & T & T & T & T\\
									F & T & F & T & F & F & F\\
									F & F & T & T & F & F & T\\
									F & F & F & T & F & F & F\\
									\bottomrule
								\end{tblr}
							\end{center}
						\end{answer}
				\end{questions}
			\end{exercise}
			\pagebreak
			\begin{exercise}{Self Assessment Exercise \thechapter.5}
				\begin{questions}
					\item Suppose that $p$ represents the statement ``It is sunny'', and $q$ represents the statement ``It is humid''. Write each of the following in abbreviated form.
						\begin{questions}
							\item It is sunny, and it is not humid {\answer $p \land \lnot q$}
							\item It is humid, or it is sunny {\answer $p \lor q$}
							\item It is false that it is humid {\answer $\lnot q$}
							\item It is false that it is sunny and humid {\answer $\lnot (p \land q)$}
							\item It is neither sunny nor humid {\answer $\lnot p \land \lnot q$}
							\item It is not the case that if it is sunny then it is humid {\answer $\lnot (p \rightarrow q)$}
							\item It is humid if it is sunny {\answer $p \rightarrow q$}
							\item It is humid only if it is sunny {\answer $q \rightarrow p$}
							\item It is sunny if and only if it is humid {\answer $p \leftrightarrow q$}
							\item If it is false that it is either sunny or humid (but not both), then it is not sunny {\answer $\lnot \bigl[(p \lor q) \land \lnot (p \land q)\bigr]\rightarrow \lnot p$}
						\end{questions}
					\item Construct truth tables for the following compound statements:
						\begin{questions}
							\item $[(\lnot q) \rightarrow (\lnot p)] \rightarrow (p \rightarrow q)$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={| c c | c c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $q$ & $\lnot p$ & $\lnot q$ & $(\lnot q) \rightarrow (\lnot p)$ & $p \rightarrow q$ & $\bigl[(\lnot q) \rightarrow (\lnot p)\bigr] \rightarrow (p \rightarrow q)$\\
											\midrule
											T & T & F & F & T & T & T\\
											T & F & F & T & F & F & T\\
											F & T & T & F & T & T & T\\
											F & F & T & T & T & T & T\\
											\bottomrule
										\end{tblr}
									\end{center}
								\end{answer}
							\item $\Bigl[\lnot p \rightarrow \bigl(q \land (\lnot q)\bigr)\Bigr] \rightarrow p$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={|c c | c  c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $q$ & $\lnot p$ & $\lnot q$ & $q \land \lnot q$ & $ \lnot p \rightarrow (q \land \lnot q)$ & $[\lnot p \rightarrow (q \land \lnot q)] \rightarrow p$\\
											\midrule
											T & T & F & F & F & T & T\\
											T & F & F & T & F & T & T\\
											F & T & T & F & F & F & T\\
											F & F & T & T & F & F & T\\
											\bottomrule
										\end{tblr}
									\end{center}
								\end{answer}
							\item $p \lor (\lnot p)$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={| c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $\lnot p$ & $p \lor \lnot p$\\
											\midrule
											T & F & T\\
											F & T & T\\
											\bottomrule
										\end{tblr}
									\end{center}
								\end{answer}
							\pagebreak
							\item $\bigl[p \land (p \rightarrow q)\bigr] \rightarrow q$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={| c c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $q$ & $p \rightarrow q$ & $p \land (p \rightarrow q)$ & $[p \land (p \rightarrow q)] \rightarrow q$\\
											\midrule
											T & T & T & T & T\\
											T & F & F & F & T\\
											F & T & T & F & T\\
											F & F & T & F & T\\
											\bottomrule
										\end{tblr}
									\end{center}
								\end{answer}
							\item $(p \lor q) \land (\lnot p \lor \lnot q)$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={|c c | c c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $q$ & $\lnot p$ & $\lnot q$ & $p \lor q$ & $\lnot p \lor \lnot q$ & $(p \lor q) \land (\lnot p \lor \lnot q)$\\
											\midrule
											T & T & F & F & T & F & F\\
											T & F & F & T & T & T & T\\
											F & T & T & F & T & T & T\\
											F & F & T & T & F & T & F\\
											\bottomrule
										\end{tblr}
									\end{center}
								\end{answer}
							\item $\bigl(\lnot p \rightarrow [q \land r]\bigr) \lor r$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={|c c c | c | c | c | c|}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $q$ & $r$ & $\lnot p$ & $q \land r$ & $\lnot p \rightarrow (q \land r)$ & $[\lnot p \rightarrow (q \land r)] \lor r$\\
											\midrule
											T & T & T & F & T & T & T\\
											T & T & F & F & F & T & T\\
											T & F & T & F & F & T & T\\
											T & F & F & F & F & T & T\\
											F & T & T & T & T & T & T\\
											F & T & F & T & F & F & F\\
											F & F & T & T & F & F & T\\
											F & F & F & T & F & F & F\\
											\bottomrule
										\end{tblr}
									\end{center}
								\end{answer}
							\item $\bigl(p \rightarrow [q \land r]\bigr) \leftrightarrow \bigl([p \rightarrow q] \lor [p \rightarrow r]\bigr)$
								\begin{answer}
									\begin{center}
										\begin{tblr}{colspec={| c c c | c | c | c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
											\toprule
											$p$ & $q$ & $r$ & $q \land r$ & $p \rightarrow q$ & $p \rightarrow r$ & $p \rightarrow (q \land r)$ & $(p \rightarrow q) \lor (p \rightarrow r)$ & $S$\\
											\midrule
											T & T & T & T & T & T & T & T & T\\
											T & T & F & F & T & F & F & T & F\\
											T & F & T & F & F & T & F & T & F\\
											T & F & F & F & F & F & F & F & T\\
											F & T & T & T & T & T & T & T & T\\
											F & T & F & F & T & T & T & T & T\\
											F & F & T & F & T & T & T & T & T\\
											F & F & F & F & T & T & T & T & T\\
											\bottomrule
										\end{tblr}
									\end{center}
									$S$ is the statement.
								\end{answer}
						\end{questions}
				\end{questions}
			\end{exercise}
			\pagebreak
		\section{Relationships Between Statements}
			\subsection{Tautology}
				\begin{definition}[width=0.7\textwidth]{Tautology}
					A compound statement that is always true is called a \concept{tautology}.
				\end{definition}
				\begin{example}[width=0.55\textwidth]
					The statement $p \lor \lnot p$ is always true.
					\begin{center}
						\begin{tblr}{colspec={| c c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
							\toprule
							$p$ & $\lnot p$ & $p \lor \lnot p$\\
							\midrule
							T & F & T\\
							F & T & T\\
							\bottomrule
						\end{tblr}
					\end{center}
				\end{example}
			\subsection{Contradiction}
				\begin{definition}[width=0.75\textwidth]{Contradiction}
					A compound statement that is always false is called a \concept{contradiction}.
				\end{definition}
				\begin{example}[width=0.55\textwidth]
					The statement $p \land \lnot p$ is always false.
					\begin{center}
						\begin{tblr}{colspec={| c c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
							\toprule
							$p$ & $\lnot p$ & $p \land \lnot p$\\
							\midrule
							T & F & F\\
							F & T & F\\
							\bottomrule
						\end{tblr}
					\end{center}
				\end{example}
			\subsection{Logical Equivalence}
				\begin{definition}{Logical Equivalence}
					Two declarative statements $a$ and $b$ are \concept{logically equivalent}, written $a \equiv b$, if and only if the statement $a \rightarrow b$ is a tautology.
				\end{definition}
				\begin{example}[width=0.8\textwidth]
					Take the declarative statement $(p \lor q) \leftrightarrow (q \lor p)$.
					\begin{center}
						\begin{tblr}{colspec={| c c | c | c | c |}, row{1}={font=\bfseries}, row{odd[3]}={white}}
							\toprule
							$p$ & $q$ & $p \lor q$ & $q \lor p$ & $(p \lor q) \leftrightarrow (q \lor p)$\\
							\midrule
							T & T & T & T & T \\
							T & F & T & T & T \\
							F & T & T & T & T \\
							F & F & F & F & T \\
							\bottomrule
						\end{tblr}
					\end{center}
					As $(p \lor q) \leftrightarrow (q \lor p)$ is a tautology, the statements are logically equivalent. That is:
						\begin{align*}
							p \lor q \equiv q \lor p
						\end{align*}
				\end{example}
			\pagebreak
			\begin{sidenote}{Important Logical Equivalences (Identities)}
				Let $T_{0}$ be a tautology, and $F_{0}$ be a contradiction.
				\begin{enumerate}[label=(\alph*), labelsep=2.5em, leftmargin=*]
					\item $p \lor q \equiv q \lor p$\\
						$p \land q \equiv q \land p$ \hfill (commutative laws)
					\item $p \lor (q \lor r) \equiv (p \lor q) \lor r$\\
						$p \land (q \land r) \equiv (p \land q) \land r$ \hfill (associative laws)
					\item $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$\\
						$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ \hfill (distributive laws)
					\item $p \lor p \equiv p$\\
						$ p \land p \equiv p$ \hfill (idempotent laws)
					\item $\lnot (\lnot p) \equiv p$ \hfill (double negation laws)
					\item $\lnot (p \lor q) \equiv \lnot p \land \lnot q$ \\
						$ \lnot (p \land q) \equiv \lnot p \lor \lnot q$ \hfill(De Morgan's laws)
					\item $p \lor \lnot p \equiv T_{0}$\\
						$p \land \lnot p \equiv F_{0} $ \hfill (inverse laws)
					\item $\lnot F_{0} \equiv T_{0}$\\
						$\lnot T_{0} \equiv F_{0} $ \hfill (negation laws)
					\item $p \lor F_{0} \equiv p$\\
						$p \land T_{0} \equiv p$ \hfill (identity laws)
					\item $p \lor T_{0} \equiv T_{0}$\\
						$p \land F_{0} \equiv F_{0}$ \hfill (domination laws/universal bound)
				\end{enumerate}
			\end{sidenote}
			\begin{sidenote}{Other Useful Logical Eqiuivalences}
				\begin{enumerate}[label=(\alph*), labelsep=2.5em, leftmargin=*]
					\item $(p \rightarrow q) \equiv (\lnot q \rightarrow \lnot p)$ \hfill (contrapositive equivalence)
					\item $p \rightarrow q \equiv \lnot p \lor q$ \hfill (implication equivalence)
					\item $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ \hfill (biconditional equivalence)
					\item $\lnot (p \rightarrow q) \equiv p \land \lnot q$ \hfill (negation of implication)
				\end{enumerate}
			\end{sidenote}
			\pagebreak
			\begin{exercise}{Self Assessment Exercise \thechapter.9}
				\begin{questions}
					\item Rewrite $p \leftrightarrow q$ as a statement built up using only $\lnot$, $\lor$ and $\land$.
						\begin{answer}
							\begin{align*}
								p \leftrightarrow q &\equiv (p \rightarrow q) \land (q \rightarrow p)\\
								&\equiv (\lnot p \lor q) \land (\lnot q \lor p)
							\end{align*}
						\end{answer}
					\item Show that $\equiv$ is an equivalence relation on statements.
						\begin{answer}
							\begin{proof}
								For $\equiv$ to be an equivalence relation, $\equiv$ needs to be reflexive, symmetric and transitive.\\
								Let $p$ and $q$ be two statements, where $p \equiv q$.
								\begin{questions}[label=(\roman*)]
									\item
										\begin{subproof}[Reflexivity]
											Is it the case that $p \equiv p$ for all statements? Yes.\\
											If $p$ is a statement, then $p \leftrightarrow p$ is always true. So $p \leftrightarrow p$ is a tautology.\\
											So $p \leftrightarrow p$ is logically equivalent.\\
											So $p \equiv p$ is part of the relation for all statements $p$.\\
											So $\equiv$ is a reflexive relation.
										\end{subproof}
									\item
										\begin{subproof}[Symmetry]
											Is it the case that, if $p \equiv q$, then $q \equiv p$ for all statements $p$ and $q$? Yes.\\
											Suppose $p \equiv q$. Then that means that $p \leftrightarrow q$ is always true.\\
											If $p \leftrightarrow q$ is always true, that means that $p \rightarrow q$ is always true, and $q \rightarrow p$ is always true.\\
											If $q \rightarrow p$ is always true, and $p \rightarrow q$ is always true, then $q \leftrightarrow p$ is always true.\\
											If $q \leftrightarrow p$ is always true, then $q \leftrightarrow p$ is a tautology.\\
											So $q \equiv p$.\\
											So $\equiv$ is a symmetric relation.
										\end{subproof}
									\item
										\begin{subproof}[Transitivity]
											Is it the case that, if $p \equiv q$ and $q \equiv r$, then $p \equiv r$ for all statements $p$, $q$ and $r$? Yes.\\
											Suppose $p \equiv q$ and $q \equiv r$.\\
											Then $p \leftrightarrow q$ is always true, and $q \leftrightarrow r$ is always true.\\
											So $p \rightarrow q$ and $q \rightarrow r$ are both always true. So $p \rightarrow r$ is always true.\\
											And $r \rightarrow q$ and $q \rightarrow p$ are both always true. So $r \rightarrow p$ is always true.\\
											So $p \leftrightarrow r$ is always true.\\
											So $p \equiv r$\\
											So $\equiv$ is a transitive relation.
										\end{subproof}
								\end{questions}
								As $\equiv$ is reflexive, symmetric, and transitive, $\equiv$ is an equivalence relation.
							\end{proof}
						\end{answer}
					\item Suppose we want to define a new connective, the \emph{exclusive disjunction}, also called the \emph{``exclusive or''}, which will be written $+$. By $p + q$, we denote ``$p$ or $q$, but not both''. Construct a truth table for this connective.
						\begin{answer}
							\begin{center}
								\begin{tblr}{colspec={|c c | c|}, row{1}={font=\bfseries}, row{odd[3]}={white}}
									\toprule
									$p$ & $q$ & $p + q$\\
									\midrule
									T & T & F\\
									T & F & T\\
									F & T & T\\
									F & F & F\\
									\bottomrule
								\end{tblr}
							\end{center}
						\end{answer}
					\pagebreak
					\item Find a statement that is logically equivalent to $\lnot (p \lor \lnot q)$
						\begin{answer}
							\begin{align*}
								\lnot (p \lor \lnot q) &\equiv \lnot p \land \lnot (\lnot q) \tag*{De Morgan's law}\\
								&\equiv \lnot p \land q \tag*{Double Negation}
							\end{align*}
						\end{answer}
					\item Use the law of double negation and De Morgan's laws to rewrite the following statements so that the not symbol ($\lnot$) does not appear outside parentheses.
						\begin{questions}
							\item $\lnot \bigl[(p \lor q \lor \lnot q) \land (q \land \lnot p)\bigr]$
								\begin{answer}
									\begin{align*}
										\lnot \bigl[(p \lor q \lor \lnot q) \land (q \land \lnot p)\bigr] &\equiv \lnot(p \lor q \lor \lnot q) \lor \lnot(q \land \lnot p) \tag*{De Morgan's law}\\
										& \equiv \bigl(\lnot p \land \lnot q \land \lnot (\lnot q)\bigr) \lor \bigl(\lnot q \lor \lnot (\lnot p)\bigr) \tag*{De Morgan's law}\\
										& \equiv (\lnot p \land \lnot q \land q) \lor (\lnot q \lor p) \tag*{Double Negation}
									\end{align*}
								\end{answer}
							\item $\lnot \Bigl[\bigl(p \lor (p \rightarrow q)\bigr) \lor (p \land q)\Bigr]$
								\begin{answer}
									\begin{align*}
										\lnot \Bigl[\bigl(p \lor (p \rightarrow q)\bigr) \lor (p \land q)\Bigr] &\equiv \lnot \Bigl[\bigl(p \lor (\lnot p \lor q)\bigr) \lor (p \land q)\Bigr] \tag*{Implication}\\
										& \equiv \lnot \bigl(p \lor (\lnot p \lor q)\bigr) \land \lnot (p \land q) \tag*{De Morgan's law}\\
										& \equiv \bigl(\lnot p \land \lnot (\lnot p \lor q)\bigr) \land (\lnot p \lor \lnot q) \tag*{De Morgan's law}\\
										& \equiv \bigl(\lnot p \land (\lnot \lnot p \land \lnot q)\bigr) \land (\lnot p \lor \lnot q) \tag*{De Morgan's law}\\
										& \equiv \bigl(\lnot p \land (p \land \lnot q)\bigr) \land (\lnot p \lor \lnot q) \tag*{Double Negation}
									\end{align*}
								\end{answer}
						\end{questions}
					\item Determine whether the following statements are equivalent:\\ $\lnot p \land (p \land \lnot q)$ and $\lnot \bigl(p \lor (p \rightarrow q)\bigr)$
						\begin{answer}
							\begin{align*}
								\lnot \bigl(p \lor (p \rightarrow q)\bigr) &\equiv \lnot \bigl(p \lor (\lnot p \lor q)\bigr) \tag*{Implication}\\
								& \equiv \lnot p \land \lnot(\lnot p \lor q) \tag*{De Morgan's law}\\
								& \equiv \lnot p \land (\lnot \lnot p \land \lnot q) \tag*{De Morgan's law}\\
								& \equiv \lnot p \land (p \land \lnot q) \tag*{Double Negation}
							\end{align*}
							Therefore the two expressions are equivalent.
						\end{answer}
				\end{questions}
			\end{exercise}
	\rulechapterend
\end{document}