% 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{hyperref}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{array}

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

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

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\stepcounter{problem}\textbf{Problem \thesection.\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}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}



\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"

\lhead{COM S 330 --- Exam 1 Topics}

\renewcommand{\arraystretch}{1.25}



\clearpage
\section{Translating Propositions and English Sentences}
\setcounter{problem}{0}

\textbf{Format:} Given propositional variables corresponding to English sentences and a compound proposition, translate the compound proposition into an English sentence.

\problem Let $p$ and $q$ be the propositions\\
\begin{tabular}[h]{c@{ : }l}
$p$ & I bought a lottery ticket this week.\\
$q$ & I won the million dollar jackpot.
\end{tabular}\\
Express each of these propositions as an English sentence.
\begin{enumerate}
\item $\lnot p$
\item $p \implies q$
\item $p \land q$ 
\item $p \iff q$
\item $\lnot p \lor (p \land q)$
\end{enumerate}

(These compound propositions may include quantifiers.)

\problem 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)$

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

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

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

\medskip

\textbf{Format:} Given propositional variables corresponding to English sentences and a complicated English sentence, translate the English sentence into a compound proposition.



\clearpage
\section{Constructing Truth Tables}
\setcounter{problem}{0}

\textbf{Format:} Given a compound proposition, build a truth table evaluating the proposition for all truth assignments of the propositional variables.

\textbf{Method:} Build a table. Add columns for each operation as to show your work.

\problem Construct a truth table for the compound proposition $(p \iff q) \xor (\lnot p \iff \lnot r)$.

\problem Construct a truth table for the compound propositions $((p\implies (q\implies r))\implies s)$.

(Sometimes we want to determine that a compound proposition is a tautology or a contradiction, so you do the same as above, except note that every row evaluates to $\TRUE$ or $\FALSE$.)

\problem Show that $[p \land (p\implies q)]\implies q$ is a tautology using truth tables.


\clearpage
\section{Demonstrating Logical Equivalences}
\setcounter{problem}{0}

\textbf{Format:} Given two compound propositions, demonstrate they are equivalent using logical equivalences.

\textbf{Method:} Start with one compound proposition, and show equivalences using the tables of logical equivalences (on cheat sheet). Use ``Logical equivalence using conditionals'' or ``Logical equivalence using biconditionals'' in order to remove/add conditionals and biconditionals so you can work with other equivalences.


\textbf{Note:} My strategy is as follows:

\begin{enumerate}
\item Use logical equivalences to remove conditionals and biconditionals ($p \iff q \equiv (p \implies q)\land (q \implies p)$; $p \implies q \equiv \lnot p \lor q$; others).
\item Use DeMorgan's Laws and the Double-negation Law to push all negations to be directly above each propositional variable ($\lnot (p\land q) \equiv \lnot p \lor \lnot q$; $\lnot (p \lor q) \equiv \lnot p \land \lnot q$).
\item Use Distributive, Associative, and Commutative laws to group similar terms.
\item Use Idempotent, Identity, and Domination laws to simplify like terms.
\item Repeat above steps as necessary.
\end{enumerate}
Perform the above steps starting with each side of the equation until reaching a commond mid-point, then reverse the steps from the right-hand side to create one list of logical equivalences.

\problem Prove that $(p \implies q) \lor (p \implies r)$ and $p \implies (q\lor r)$ are logically equivalent (without using this equivalence from the tables).

\problem Select a logical equivalence using conditionals. Prove the equivalence without using this equivalence from the tables.

\problem Select a logical equivalence using biconditionals. Prove the equivalence without using this equivalence from the tables.

(The compound propositions may involve quantifiers, so be sure to check the logical equivalences using quantifiers.)

\problem 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.

\clearpage
\section{Finding Satisfying Assignments}
\setcounter{problem}{0}

\textbf{Format:} Given a compound proposition, find an assignment of the propositional variables such that the compound proposition is satisfied (i.e. true).

\textbf{Method:} Present the values of your variables and evaluate the compound proposition.

\problem Find an assignment of the variables $p, q, r$ such that the proposition
\[ (p \lor \lnot q) \land (p \lor q) \land (q \lor r) \land (q \lor \lnot r) \land (r \lor \lnot p)\land (r \lor p) \] 




\clearpage
\section{Rules of Inference}
\setcounter{problem}{0}

\textbf{Format:} Given a set of premises, \emph{use rules of inference} to prove a conclusion.

\textbf{Method:} Use tabular ``step/reason'' proof to list true propositions and how they are built from premises and previous conclusions until final conclusion is determined.
Both Rules of Inference and Logical Equivalences can be used (and will be on cheat sheet).

\problem Use rules of inference to show that if $p \land q$, $r \lor s$, and $p \implies \lnot r$, then $s$ is true.

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem 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.

\problem Use rules of inference to show that if $(p\land q) \lor r$, $(p \land \lnot q)\lor s$, $(\lnot p\land q) \lor t$, and $(\lnot p \land \lnot q) \lor u$, then $r \lor s\lor t \lor u$ is true.


\medskip
\textbf{Format:} Given a rule of inference, use truth tables to demonstrated that the rule is correct.

\textbf{Method:} Build a truth table constructed using all propositional variables in the rule. Cross out the rows where any of the premises are false. Determine that the conclusion is true for all remaining rows.

\problem Use truth tables to demonstrate that Resolution is a correct rule of inference.

\problem Use truth tables to demonstrate that Conditional Resolution is a correct rule of inference.




\clearpage
\section{Knights, Knaves, and Others}
\setcounter{problem}{0}

\textbf{Format:} Given a set of possible types of people that say propositions, determine what possible types the people can be.

\textbf{Method:} Use truth tables or proof by case analysis.

\problem On the island of Flopi, there are three types of people: Knights, Knaves, and Floppers. All inhabitants know which type the others are, but they are otherwise indistinguishable. Knights always tell the truth. Knaves always lie. Floppers always choose to lie or tell the truth by doing the opposite of the previous speaker (i.e. if someone just spoke a lie, the flopper will tell the truth; if someone just spoke a truth, the flopper will lie). While on your vacation, you come across three inhabitants, $A$, $B$, and $C$. They say the following, in order:
\begin{quote}
$A$ says, ``We are all knights.''\\
$B$ says, ``$C$ is a knight.''\\
$C$ says, ``$A$ is a knave.''\\
$A$ says, ``$C$ lied.''
\end{quote}
Determine all possibilities of $A$, $B$, and $C$ being Knights, Knaves, or Floppers (not all need to be distinct).



\problem  In the country of Togliristan (where Knights, Knaves, and Togglers live), Togglers will alternate between telling the truth and lying (no matter what other people say). You meet two people, $A$ and $B$.
They say, in order:
\begin{quote}
$A$ : $B$ is a Knave.

$B$ : $A$ is a Knave.

$A$ : $B$ is a Knight.

$B$ : $A$ is a Toggler.
\end{quote}
Determine what types of people $A$ and $B$ are.








\clearpage
\section{Basic Proofs}
\setcounter{problem}{0}

\textbf{Format:} Give a proof of a statement. May require a specific type of proof (direct, contrapositive, contradiction).

\textbf{Method:} Determine if proof is of type ``$p \implies q$'' or just ``$p$'' and determine how to organize a direct proof (Assume $p$ is true. Use that information to demonstrate $q$ is true), contrapositive (Assume $\lnot q$ is true. Use that information to demonstrate $\lnot p$ is true), or contradiction (Assume $p \land \lnot q$ is true and find a contradiction; Assume $\lnot p$ is true and find a contradiction.)

\textbf{Tip:} It can be helpful to carefully write out what you mean by $p$, $q$, $\lnot p$, or $\lnot q$, when you are trying to demonstrate your proof technique. Also, if you are given a choice of proof method, then announce your method at the beginning of your proof.

\problem Give a direct proof of the following statement: If $x$ and $y$ are rational numbers, then $x + y$ and $xy$ are rational numbers.

\problem Give a proof of the following statement: If $x$ is a rational number and $y$ is irrational, then $x+y$ and $xy$ are irrational.

(You may need to adapt an existing proof in order to give a proof of the statement.)

\problem Prove that $\sqrt{3}$ is irrational.

\problem Prove that $\sqrt{7}$ is irrational.

\problem Prove that $\sqrt{35}$ is irrational.

\problem Prove that $\sqrt{12}$ is irrational.

\clearpage
\section{Tiling Problems}
\setcounter{problem}{0}

\textbf{Format:} Given a description of a chessboard (either an $m \times n$ chessboard, or one that has had some squares removed), demonstrate that a tiling exists or does not exist using some set of polyominoes.

\textbf{Method:} For existence of a tiling: demonstrate the tiling (usually by tiling a small part of the board and then replicating that tiling across the board). For non-existence of a tiling, prove something along the lines of ``If $C$ has a tiling, then $C$ has property X.'' Then show that $C$ does not have property X.

\problem Prove that if $n$ is even, then the $m \times n$ chessboard has a domino tiling.

\problem Prove that if $n$ and $m$ are odd, then the $m \times n$ chessboard does not have a domino tiling.

\problem Let $n$ be an even number. Prove that if we remove the top-left and bottom-right squares from the $n \times n$ chessboard, the resulting board does not have a domino tiling.

\problem Let $n$ be a multiple of 3. Prove that the $m \times n$ chessboard has a tiling using straight triominoes.

\problem Let $n$ be a number not divisible by 3. Prove that the $n \times n$ chessboard does not have a tiling using straight triominoes.

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem The \emph{L-shaped Tetris piece} (or \emph{tetromino}, see \href{http://en.wikipedia.org/wiki/Tetromino}{the Wikipedia page}) consists of four squares: three of which are in a line and a fourth attached to one end of that line. See the figure below for all of the arrangements of the L-shaped Tetris piece (or L-piece).

% If you are using this TeX file for your homework, you will want to comment this out!
\begin{center}
\includegraphics[height=0.5in]{figures/tetrominoes-L}
\end{center}

Adapt the proofs from the book and class about domino tilings to prove the following:

\textbf{a.} If $m$ is an even number and $n$ is a multiple of 4, then the $m \times n$ chessboard can be tiled using L-pieces.

\textbf{b.} If a chessboard has a tilling using L-pieces, then the chessboard has a domino tiling.

\textbf{c.} If $m$ and $n$ are odd numbers, then the $m\times n$ chessboard cannot be tiled using L-pieces. 

\textbf{d.} Show that if $k$ is even, then the $3 \times 4k$ chessboard can be tiled using L-pieces. 


\problem Let the \emph{T-piece} be the tetromino (4 squares) that covers positions $(1,1)$, $(1,2)$, $(1,3)$, and $(2,2)$.

\textbf{a.} Prove that if $n$ and $m$ are multiples of 4, then the $m \times n$ chessboard can be tiled using T-pieces.

\textbf{b.} Prove that the $2 \times n$ chessboard cannot be tiled using T-pieces.

\textbf{c.} Prove that the $2 \times n$ chessboard with the top-left and bottom-right squares removed can be tiled using T-pieces.

\textbf{d.} Prove that the $3 \times n$ chessboard cannot be tiled using T-pieces.



\clearpage
\section{Set Definitions}
\setcounter{problem}{0}



\problem Let $\universe = \{1,2,3,4,5,6,7\}$, $A = \{ 1, 3, 5, 7\}$, $B = \{4,5,6,7\}$. Determine the following sets:
\[ \overline{A}, \quad A \cap B, \quad A \cup B, \quad A \setminus B, \quad A \symmdiff B.\]


\problem Consider our definitions of $\Z$, $\Q$, $\R$, and $\C$. Recall that $A \subseteq B$ means ``$A$ is a subset of $B$'' and $A \not \subseteq B$ means ``$A$ is not a subset of $B$.''

Prove that (a) $\Z \subseteq \Q$, (b) $\Q \not \subseteq \Z$, (c) $\R \not \subseteq \Q$, (d) $\R \subseteq \C$, and (e) $\C \not \subseteq \R$.

\problem Recall the definition of the cartesian product $A \times B$. 

Prove that (a) If $A \subseteq B$ then $A \times A \subseteq B \times B$. (b) $\Z \times \Q \subseteq \Q \times \R$. 


\clearpage
\section{Set Containment or Equality}
\setcounter{problem}{0}

\textbf{Format:} Given some sets, determine if a set built from set operations is a subset of or is equal to another set.

\textbf{Method:} To demonstrate $A \subseteq B$, you must say that if $a \in A$ then $a \in B$. To demonstrate $A = B$ you must show $A \subseteq B$ and $B \subseteq A$.

\problem Let $A$, $B$, and $C$ be sets. Prove that $(A \symmdiff B) \symmdiff C = (A \setminus (B \cup C)) \cup (B \setminus (A \cup C)) \cup (C \setminus (A \cup B))$.

(Note: $\cP(A)$ is the \emph{power set} of $A$ and consists of \emph{subsets of $A$}. That is, $S \in \cP(A)$ if and only if $S \subseteq A$.)

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem Prove that if $A \subseteq B$, then $\cP(A) \subseteq \cP(B)$.

\problem Let $A$ and $B$ be sets. Prove that $\cP(A) \cap \cP(B) = \cP(A \cap B)$.

\problem Let $A$ and $B$ be sets. Prove that $\cP(A) \cup \cP(B) \subseteq \cP(A \cup B)$.

\problem Let $A$ and $B$ be sets. Prove that if $A \not\subseteq B$ and $B \not\subseteq A$ then $\cP(A) \cup \cP(B) \neq \cP(A \cup B)$.



\clearpage
\section{Set Equality by Set Identities}
\setcounter{problem}{0}

\textbf{Format:} Use definitions of set operations and set identities to prove an equality of sets.

\textbf{Method:} Start with the left-hand side of the equality, use definitions and set identities to step-by-step transform the set into the right-hand side.

\textbf{Note:} This is very close to the method and format for proving logical equivalences (they are actually the same thing, after performing a translation between set operations and logical operations).
My strategy is as follows:

\begin{enumerate}
\item Use set definitions to remove any symmetric differences ($A \symmdiff B = (A \setminus B) \cup (B \setminus A)$) and set differences ($A \setminus B = A \cap \overline{B}$).
\item Use DeMorgan's Laws and the Complementation Law to push all complements to be directly above each set ($\overline{A \cup B} = \overline{A} \cap \overline{B}$; $\overline{A \cap B} = \overline{A} \cup \overline{B}$).
\item Use Distributive, Associative, and Commutative laws to group similar terms.
\item Use Idempotent, Identity, and Domination laws to simplify like terms.
\item Repeat above steps as necessary.
\end{enumerate}
Perform the above steps starting with each side of the equation until reaching a commond mid-point, then reverse the steps from the right-hand side to create one list of set equalities.


\problem Let $A$, $B$, and $C$ be subsets of a universe $\universe$. Use definitions of set operations and set identities to prove the following equality of sets:
\[
	((B \cap A) \cup (B \cap C))\setminus (A \cap B \cap C) = (B \cap (A \symmdiff C))
\]
[Hint: Show both sides are equal to the set $((B \cap A) \setminus C) \cup ((B\cap C) \setminus A)$.]

\problem Let $A$, $B$, and $C$ be subsets of a universe $\universe$. Use definitions of set operations and set identities to prove the following equality of sets: 
\[
	(A \symmdiff B) \symmdiff C = (A \setminus (B \cup C)) \cup (B \setminus (A \cup C)) \cup (C \setminus (A \cup B)).
\]

\problem Use definitions of set operations and set identities to prove that the symmetric difference is associative. That is
\[
	(A \symmdiff B) \symmdiff C = A \symmdiff (B \symmdiff C).
\]





\clearpage
\section{Set Sizes}
\setcounter{problem}{0}

\textbf{Format:} Given a set built from others using set operations, prove the size of the set equals the given formula.

\textbf{Method:} Count how many elements are in each part of the set.

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem  Let $A$ and $B$ be sets. Prove that $|A\cup B|= |A| + |B| - |A \cap B|$, using the following steps:
\begin{enumerate}
\item Prove that if $E$ and $F$ are disjoint sets (i.e. $E \cap F = \varnothing$) then $|E \cup F| = |E| + |F|$.
\item Prove that $|A \cup B| = |A| + |B \setminus A|$.
\item Prove that $|B \setminus A| = |B| - |A \cap B|$.
\item Conclude that $|A \cup B| = |A| + |B| - |A \cap B|$.
\end{enumerate}








\clearpage
\section{Types of Functions}
\setcounter{problem}{0}




\textbf{Format:} Given a function, determine if it is injective, surjective, both, or neither.

\textbf{Method:} Let $f : A \to B$ be a function.

\begin{itemize}
\item To show $f$ is injective: Prove ``$\forall x, y \in A, (f(x) = f(y) \implies x = y)$.''
\item To show $f$ is \emph{not} injective: Prove ``$\exists x, y \in A, (f(x) = f(y) \land x \neq y)$.''
\item To show $f$ is surjective: Prove ``$\forall y \in B, \exists x \in A, f(x) = y.$''
\item To show $f$ is \emph{not} surjective: Prove $\exists y \in B, \forall x\in A, f(x) \neq y.$''
\end{itemize}

\textbf{Note:} Be sure to know how to build functions from other functions, including $f_1 +f_2$, $f_1f_2$, and $f_1 \circ f_2$.

\problem Let $A = \{a,b,c\}$, $B = \{1,2,3,4\}$, and $C = \{\pi, \phi, i\}$. Define functions $f : A \to B$ and $g : B \to C$ as
\[
	f(x) = \begin{cases} 2 & x = a\\3 & x = b\\ 4 & x = c\end{cases} \quad
	g(x) = \begin{cases} \pi & x = 1\\ \phi & x = 2 \\ i & x = 3 \\ \pi & x = 4 \end{cases}
\]
Consider each of the functions $f$, $g$, $g \circ f$ and determine if they are injective, surjective, or both.

\problem Consider the following function $f : \N \to \Z$:
\[
	f(n) = (-1)^n\left(\frac{n}{2}+\frac{1}{4}\right)  - \frac{1}{4}.
\]
\begin{enumerate}
\item Write out the elements $f(0)$, $f(1)$, $f(2)$, $f(3)$, $f(4)$, $f(5)$.
\item Prove that $f$ is injective. 
\item Prove that $f$ is surjective.
\item Describe a function $g : \Z \to \Q$ that is surjective (and prove it is surjective).
\end{enumerate}

\problem Let $f : A \to B$ and $g : B \to C$ be functions. Prove that if $f$ and $g$ are bijections, then $g \circ f$ is a bijection.





\end{document} 