% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}

\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 03 --- Solutions}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


\problem [5pts] Let $P(x)$ be the statement ``$\frac{1}{x} = x$.'' If the domain consists of real numbers, then what are these truth values?

a. $P(2)$. 

False. $\frac{1}{2} \neq 2$.

b. $P(1)$. 

True. $\frac{1}{1} = 1$.

c. $\exists x P(x)$. 

True, since it is true for $x = 1$.

d. $\forall x \neq 0 (P(x))$. 

False. $x = 2$ is a counterexample.



% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts] Let $P(x,y)$ be the statement ``$x > y$ and $x$ is divisible by $y$.'' Let the domain consist of positive integers and write English sentences describing the following propositions.

a. $\exists x \forall y P(x,y)$.

There exists a positive integer $x$ such that for each positive integer $y$, $x > y$ and $x$ is divisible by $y$.

b. $\exists y \forall x P(x,y)$

There exists a positive integer $y$ such that for each positive integer $x$, $x > y$ and $x$ is divisible by $y$.

c. $\forall x \exists y P(x,y)$

For every positive integer $x$, there exists a positive integer $y$ such that $x > y$ and $x$ is divisible by $y$.

d. $\forall y \exists x P(x,y)$

For every positive integer $y$, there exists a positive integer $x$ such that $x > y$ and $x$ is divisible by $y$.

% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts] Let $P(x,y)$, $Q(x,y)$, and $R(x)$ be propositional functions. Use logical equivalences to show that
	$\lnot \forall x ((\exists y (P(x,y) \implies Q(x,y))) \lor R(x))$ and $\exists x (\lnot R(x) \land \forall y ( \lnot Q(x,y) \land  P(x,y)))$ are equivalent.



\textit{Solution:}
 
\begin{tabular}[h]{rll}
&$\lnot \forall x ((\exists y (P(x,y) \implies Q(x,y))) \lor R(x))$  \\
&$\equiv \exists x \lnot ((\exists y (P(x,y) \implies Q(x,y))) \lor R(x))$ &   DeMorgan's Law (for Quantifiers)\\
&$\equiv \exists x (\lnot(\exists y (P(x,y) \implies Q(x,y))) \land \lnot R(x))$ &   DeMorgan's Law\\
&$\equiv \exists x  ((\forall y \lnot(P(x,y) \implies Q(x,y))) \land \lnot R(x))$ &   DeMorgan's Law (for Quantifiers)\\
&$\equiv \exists x  ((\forall y \lnot(\lnot P(x,y) \lor Q(x,y))) \land \lnot R(x))$ &  Logical Equivalence using Conditionals\\
&$\equiv \exists x  ((\forall y (\lnot(\lnot P(x,y)) \land \lnot Q(x,y))) \land \lnot R(x))$ &  DeMorgan's Law\\
&$\equiv \exists x  ((\forall y ( P(x,y) \land \lnot Q(x,y))) \land \lnot R(x))$ & Double Negation Law\\
&$\equiv \exists x  (\lnot R(x) \land (\forall y ( \lnot Q(x,y)\land P(x,y))) )$ & Commutative Law\\
\end{tabular}


% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts] Use rules of inference to show that if $p \land q$, $r \lor s$, and $p \implies \lnot r$, then $s$ is true.


\textit{Solution:} 

\begin{tabular}[h]{rp{1.75in}p{3in}}
\multicolumn{2}{l}{\textbf{Step}} & \textbf{Reason} \\
\hline
1. & $r \lor s$ & Premise\\
2. & $\lnot r \implies s$ & Logical Equivalence using Conditionals from (1).\\
3. & $p \implies \lnot r$ & Premise.\\
4. & $p \implies s$ & Hypothetical Syllogism from (2) and (3).\\
5. & $p\land q$ & Premise.\\
6. & $p$ & Simplification from (5).\\
\hline
$\therefore$ & $s$ & Modus ponens from (4) and (6).
\end{tabular}


% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts] Use rules of inference to show that if $(p\implies q) \land (q \implies p)$, $t \lor q$, $t \lor p$, and $(p \land q)\implies t$, then $t$ is true.


\textit{Solution:} \textit{Note that there are many ways to solve this problem, as only two of the first three premises are required. Any pair of those three (with the fourth) suffice to demonstrate the statement.}

\begin{tabular}[h]{rp{1.75in}p{3in}}
\multicolumn{2}{l}{\textbf{Step}} & \textbf{Reason} \\
\hline
1. & $t \lor p$ & Premise\\
2. & $t \lor q$ & Premise\\
3. & $(t \lor p) \land (t\lor q)$ & Conjunction from (1) and (2).\\
4. & $t \lor (q \land p)$ & Distributive Law from (3).\\
5. & $\lnot (q\land p) \implies t$ & Logical equivalence using conditionals from (4).\\
6. &  $(p \land q)\implies t$ & Premise.\\
7. & $[(p\land q)\implies t] \land [\lnot (p\land q)\implies t]$ & Conjunction from (5) and (6).\\
8. & $[(p\land q) \lor \lnot (p\land q)]\implies t$ & Logical equivalence using conditionals from (7).\\
9. & $(p\land q) \lor \lnot (p\land q)$ & Negation law.\\
\hline
$\therefore$ & $t$ & Modus ponens from (8) and (9).
\end{tabular}

\end{document} 