\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\Large\bf Tutorial 1.}\\


\section{Predicate logic}

Consider the statement, ``Every cloud has a silver lining''. 
To say this more formally, we let the variable $x$ range over the set
of all clouds, the {\em universe of discourse}. Then,

$\forall x : x \quad has \quad a \quad silver \quad lining $\\

Here the symbol $\forall$ means ``for every'' or ``for all''.
Another way to say the same is to let $S$ be the set of clouds. Then\\

$\forall x \in S: x \quad has \quad a \quad silver \quad lining $\\

Here the symbol $\forall$ means ``for every'' or ``for all''.

And less formally we can say,

$\forall cloud \quad x: x \quad has \quad a \quad silver \quad lining $\\
 
Other examples : ``Every child is a boy or a girl'', 
can be restated as\\

$\forall$ child $x$ : ($x$ is a boy) $\vee$ ($x$ is a girl)\\

Let $x$ stand for a boolean (0-1 or True/False) variable. Then the following
statement is a tautology.
$$\forall x : (x \vee \overline{x})$$

The symbol $\exists$ means ``there exists'' or ``there is at least
one''. So e.g., ``There is always an easy way out'' is the same as\\

$\exists$ way $x$ : ($x$ is easy) $\wedge$ ($x$ is a way out)\\

As a second example, let $x,y$ be boolean variables. Then
we could say, 

$$\exists x,y : (x \vee y) \wedge (x \vee \overline{y})$$

These symbols, $\exists$ and $\forall$, are called {\em quantifiers}.
They can
be used together (and also repeatedly). E.g. ``There is a tallest man''
can be written as \\

$\exists$ man $x$ $\forall$ man $y$ : $x$ is at least as tall as $y$\\

Or ``Every tennis tournament has a winner'' is
$$\forall tournament \quad x \quad \exists player \quad y : y \quad wins \quad x$$

Notice that the order of the quantifiers can change the meaning of the
statement.  For example the above statement with quantifiers reversed is
$$\exists player \quad y \quad \forall tournament \quad x : y \quad wins \quad x$$
which means that the same person wins every tournament whereas all the 
earlier version meant was that each tournament has a winner, not necessarily
the same person.

What happens to quantifiers when they are negated?
We represent ``not for every'' as $\overline{\forall}$ or $\neg \forall$ 
and ``there does 
not exist'' as $\overline{\exists}$ or $\neg \exists$.

The following statement is a tautology:
$$\overline{\exists} x : (x \wedge \overline{x})$$
That is there is no $x$ for which both $x$ and the negation of $x$ are true.
In other words for every $x$ one of $x$ and $\overline{x}$ is false and the
other is true. So we could rewrite the above as
$$\forall x: \overline{x \wedge \overline{x}}$$
which is the same as $$\forall x: \overline{x} \vee x$$

What we did above can be expressed more generally. Let $P$ be any predicate
(possibly quantified).
Then $\overline{\exists} x : P$ is equivalent to $\forall x : \overline{P}$.
and similarly, $\overline{\forall}$ is the same as $\exists x: \overline{P}$.

What is the negation of the statement ``Every dog has its day''?  
We can express the negation as
$\overline{\forall} dog \quad x$: $x$ has its day.
Then using the rule above, this is the same as \\

$\exists dog \quad x:$ $x$ does not have its day.\\

In other words there is a dog that does not have its day.

A more involved example is to show that

$$\overline{\forall} x,y\exists z \forall w \exists v : (x \wedge v \wedge \overline{y}) \vee \overline {(x \wedge y \wedge z)}$$

is the same as 

$$\exists x,y \forall z \exists w \forall v : (\overline{x} \vee \overline{v} \vee y) \wedge (x \wedge y \wedge z)$$ 

Note that 

$\neg (\exists x \forall y \ldots) = \overline{\exists}x \forall y \ldots$

\section{Proofs about sets}

In this section we carefully prove the following identity. Below
$A,B,C$ are finite sets.
\begin{lemma}
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
\end{lemma}

This is known as the {\em distributive law of set intersection} and will
be useful later in the course.

{\em Proof. }
Let $X = A \cap (B \cup C)$ and $Y = (A \cap B) \cup (A \cap C)$.
Then we will show that 
\begin{enumerate}
\item  $X \subseteq Y$ {\em and} 
\item  $Y \subseteq X$.
\end{enumerate}

This will show that $X$ and $Y$ must be the same set.

\begin{enumerate}
\item   $X \subseteq Y$.

Let $x$ be any element of $X$. Then $x \in A$ and $x \in (B \cup C)$.

That is $x$ is in $A$ and also in $B$ or in $C$. 
Let us examine these cases separately:
 \begin{enumerate}
  \item $x$ is in $B$.  Then $x$ is in $A \cap B$.
  \item $x$ is in $C$. Then $x$ is in $A \cap C$. 
 \end{enumerate}

Therefore $x$ is in $A \cap B$ or in $A \cap C$.
That is $x$ is always an element in their union, 
$x \in (A \cap B) \cup (A \cap C)$. 

\item $Y \subseteq X$.

Let $x\in Y$, i.e., $x \in (A \cap B) \cup (A \cap C)$.
There are two cases:
\begin{enumerate}
\item $x$ is in $A\cap B$. Then $x \in A$ and $x\in B$.
\item $x$ is in $A\cap C$. Then $x \in A$ and $x\in C$.
\end{enumerate}

Therefore $x$ is in $A$, and $x$ is in $B\cup C$
That is $x$ is in $A \cap (B \cup C)$.

$x\in X$.
\end{enumerate}


\qed


\section{Proof by contradiction}

\begin{lemma}
For any integers $m$ and $n$, $^m\sqrt{n}$, the 
$m^{th}$ root of $n$ is either an integer or
irrational.
\end{lemma}

So for example the lemma tells us that $\sqrt{2}$, $4^{1/3}$, $10^{1/5}$ 
are all irrational numbers.\\

{\em Proof. } 
Every real number is either an integer, or a ratio of two integers with
the denominator greater than 1, or irrational. Let us assume for the
purpose of getting a contradiction that for some integers $m,n$ the 
number $n^{1/m}$ is of the second kind, i.e., it is the ratio of two 
integers with the denominator greater than 1.
$$ n^{1/m} = {a \over b}$$ 
for some integers $a,b$ which have no common divisors greater than $1$ 
and $b \not{=} 1.$

Rearranging terms, 
$$a^m - nb^m = 0$$
Let $p$ be a prime divisor of $b$ (such a prime divisor exists since 
$b >1$). 
Then $a^m$ must also be divisible
by the same prime. By the fundamental theorem of arithmetic (prime factorization theorem) this means that $p$ is a divisor of $a$. 
But then since we assumed that $a,b$ have no common divisors, this is a 
contradiction.
\qed

Using the same idea as above we can prove the following more general statement.
\begin{lemma}
Let the coefficients of the polynomial $a_0+a_1x+a_2x^2+\ldots+x^n=0$ 
be integers. Then any root of the polynomial is either integral or 
irrational.
\end{lemma}

{\em Proof.} 
There are 3 possibilities for a root $x$ of the polynomial. It is
either integral, the ratio of two integers with the denominator greater
than 1 or irrational. Let us assume for a contradiction that $x = s/t$
for integers $s$ and $t$ which have no common divisors and such that $t >1$.

Then 
$$ a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+s^n = 0$$

Let $p$ be a prime divisor of $t$. Then $p$ divides $s^n$ and therefore
$p$ divides $s$. Since we assumed $s,t$ have no common divisors this is 
a contradiction.
\qed

\section{Proof by cases}

We have already seen proofs involving cases (e.g., the proof of the
distributive law).
Now we look at another problem that involves cases. The key to such
proofs is to make sure that we cover {\em all} the cases.

{\em You are given 3 identical looking balls,
and told that one of them is heavier than the other two.
Can you find the heavy ball using one weighing of a physical 
balance?}

{\em Solution.}
Place one ball on each pan of the balance. 
There are 3 possible outcomes:
\begin{enumerate}
\item The left pan is heavier. Then the ball in the left pan is the
answer.
\item The right pan is heavier. Then the ball in the right pan is the
answer.
\item The pans are equal. Then the third ball must be the heavy one!
\end{enumerate}

\section{Team problems}

Now we'll work out some tougher problems.

\begin{enumerate}
\item A hundred soldiers are standing in an array of 10 columns and 10 rows.
Let $T_i$ be the tallest soldier in the $i^th$ column and 
$S_j$ the shortest soldier in the $j^th$ row ($i,j$ run from 1 to 10).
Who is taller: the tallest of the $S_j$'s or the shortest of the 
$T_i$'s? Prove your answer taking care of all the cases.

\item Now you are given 12 identical looking balls, and told that
one of them is of different weight from the other 11, but you don't 
know in advance whether it is heavier or lighter. Can you
find the ball that is of different weight using only 3 weighings?

\end{enumerate}

\end{document}

