\section{Propositions}

Now we consider the kinds of statements that we might want to convince people 
about\.

\subsection{What are propositions?}

\begin{definition}
  A {\em proposition\/} is a statement that has a truth value,
  $\ms{true}$ or $\ms{false}$. 
\end{definition}

Examples:
\begin{enumerate}
\item
  $5$ is a prime number. 

  This is a proposition, and it's true. 

\item
  $8$ is a prime number. 

  This is a false proposition.

\item
  $x$ is a prime number. 

  This is not a proposition\.
  It has no truth value, because we don't know what $x$ is\.
  It's said to be an {\em unbound variable}. 

\item 
  There is an least one prime number.

  This is a true proposition\.  In math notation, it can be written as
  $\exists x (x \mbox{ is a prime})$\. The quantifier $\exists$
  ``binds'' $x$.

\item
  All natural numbers $\geq 2$ are primes. 

  This is a false proposition\.  It can be written as $\forall x \in N,
  x \geq 2 (x \mbox{ is a prime})$\. The quantifier $\forall$ also binds $x$. 

  We will revisit the quantifiers soon (they have their own reasoning
  methods)\.  For now, we are just using them as shorthand notation for
  the English phrases. 

\item
  All $x$ of the form $n^2 + n + 41$, where $n \in N$, are prime. 

  This is a proposition\.
  Is it true or false?
  That's not immediately obvious\. 
  Certainly this proposition is true for many natural numbers $n$:

  \[
  \begin{array}{cc}
    n = 0 \rightarrow 41 & (prime) \\
    n = 1 \rightarrow 43 & (prime) \\
    n = 2 \rightarrow 47 & (prime) \\
    n = 3 \rightarrow 53 & (prime) \\
    \ldots & (more\ primes) \\
    n = 20 \rightarrow 461 & (prime) \\
    \ldots & (still\ more\ primes) \\
    n = 39 \rightarrow 1601 & (prime)
  \end{array}
  \]

  However, if $n = 40$, then $n^2 + n + 41 = 40^2 + 40 + 41 = 41 \cdot 41$,
  which is not prime\.  
  Since it is not the case that the expression is prime {\em for all} $n$, 
  the proposition is false!

\item 
  ``true'' and ``false'' are regarded as propositions, 
  with the obvious truth values.

\item
  $\forall A, B (\bar{A} \cup \bar{B} = \overline{A \cup B})$. 

  Propositions can be about other things besides numbers, for instance, sets\.
  This proposition happens to be false. 

\forstudents{
\item
  $\forall A, B (\bar{A} \cup \bar{B} = \bar{A \cap B})$. \\
  $\forall A, B (\bar{A} \cap \bar{B} = \bar{A \cup B})$. 

  These are called De Morgan's laws and are true.
}

\item
  The original Pentium chip always divided correctly\.

  Intel's ``proofs'' by authority and by sampling turned out to be
  invalid\.  The proposition is false.

\item White can always win at chess.

  A proposition whose truth value nobody knows.

\item Every even integer greater than 2 is the sum of two prime
  numbers.

  No one knows whether this proposition is true or false\.  This is
  the Goldbach Conjecture, which dates back to 1742\.  It was described
  in {\em The Boston Globe} as ``one of the great unsolved
  mysteries.'' 
  Unfortunately, the ``example'' they gave was $20=9+11$!

\item There is no $x, y, z \in N^+, n \geq 3$ such that $x^n + y^n =
  z^n$.

  This is Fermat's last theorem, which he stated in the 1640s\.  
  Although he claimed it, he never proved it\. 
  Only recently have we learned for sure that it's true\.  
  Andrew Wiles, in 1994, gave a 130-page proof\.  
  After months of work, other mathematicians found bugs\. 
  Wiles needed hundreds of more pages to fix them\.  
  But even while we didn't know if it was true or false, it
  was still a proposition.

\item There is no $x, y, z, w \in \naturals^+$ such that
  $x^4+y^4+z^4=w^4$.  

  Note the similarity to Fermat's Theorem\.  This statement was
  conjectured by Euler (1769)\.  The first counterexample was found by
  Elkies, 218 years later\.  The smallest one:
  $95800^4+217519^4+414560^4=422481^4$.

\item Every map can be colored with four colors, in such a way that no two
  adjacent regions have the same color (Four-Color Theorem).

  This proposition was first ``proved'' in 1879\.  
  The ``proof'' stood for 10 years before a flaw was found\.  
  Recently, the theorem was proved with computer aid\.
  People still debate whether this is a valid proof\.  
  After all, nobody has proved that the computer is working correctly!
\end{enumerate}

Not all sentences are propositions:
\begin{itemize}
\item $x = y$.  (Truth depends on knowing what $x$ and $y$ are.)
\item What time is it?
\item This sentence is false.
\end{itemize}

Propositions involve previously {\em defined} terms:
     \begin{itemize}
     \item prime, map, triangle, chess, fair coin, probability.
     \item $+$, $=$, $1$, $\ge$.
     \end{itemize}

\subsection{Compound propositions and truth tables}

Logical connectives are used to combine simple propositions into compound
propositions\.
And ($\wedge$), or ($\vee$), exclusive-or ($\oplus$), and not ($\neg$),
which we already mentioned for Booleans, are also used for propositions\.  
Other connectives used for propositions include implication 
(if-then, $\implies$) and double implication 
(equivalence, $\Leftrightarrow$)\.  
These are very important in logical reasoning\.
The truth values of compound propositions are obtained from the truth
values of the simpler propositions according to the {\em truth tables\/}:

\begin{tabular}{cc}
  $P$  & $\neg P$ \\
  \hline T  &   F \\
  F  &   T \\
\end{tabular}

\noindent If a proposition $P$ is true, then its negation is false, and
vice versa.

\begin{tabular}{ccccc}
  $P$  & $Q$ &    $P \wedge Q$ &  $P \vee Q$ & $P \oplus Q$ \\
  \hline
  T  &  T     &  T &             T   &        F\\
  T  &  F    &   F  &            T  &         T\\
  F  &  T   &    F   &           T &          T\\
  F  &  F  &     F    &          F&           F\\
\end{tabular}

Important: $\vee$ means {\bf inclusive} or\.  
It is true if either \emph{or both} of the two statements are true\.  
Sometimes in English or is used to mean exclusive or: 
``David or Lars will teach today'' is saying one but not both.
%%
%% As I am not a native English speaker, I cannot really make any
%% definite statements on the meaning of either...of in English, but my
%% dictionaries suggest that, depending on the context, it can actually
%% mean either OR, or XOR, or AND! The sample sentences I found include:
%%  
%% 1. He must be either mad or drunk.
%%  
%% 2. He is taller than either you or me.
%%  
%% 3. There were houses on either side of the road.
%%  
%% 4. Either of them will do.
%%
%% Perhaps we should also add a comment roughly as follows:
%%
%%   In general, we will be *very* explicit if we want you to use XOR,
%%   i.e., we would write something like "prove that either X or Y, but
%%   not both, holds".
%%
%% This would reduce some problem set confusions.   /Lars
%%

\vspace{2ex}

\begin{tabular}{cccc}
  $P$ & $Q$ &   $P \Rightarrow Q$ &  $P \Leftrightarrow Q$ \\
  \hline
  T&    T   &       T  &               T \\
  T &   F  &        F   &              F \\
  F  &  T &         T    &             F \\
  F   & F&          T     &            T \\
\end{tabular}

The nice thing about these truth tables is that it doesn't matter what
the specific propositions are; we know how to get compound truth value
from basic truth values.

The only slightly mysterious column here is the implication column\.
We say that $P \Rightarrow Q$ is false only if the hypothesis $P$ is
true and the conclusion $Q$ is false\.  Some thought shows this aligns
with our intuition\.  Consider the statement ``if you do your
homework, then I will give you an A''\.  Under what circumstances
would you accuse me of lying\?  Well, I am clearly lying if you do
your homework but then you don't get an A\.  But if you skip your
homework and I give you an A \emph{anyway,} you won't say I'm lying\.
In this case the statement promises nothing, so it is true regardless
of what I do.

One way to determine truth values for compound propositions is by
adding new columns to the basic truth table(s).  Consider for example 
\[
(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) 
\]
To decide the truth value of this messy proposition, we can evaluate
its sub-propositions in a truth table and then combine their evaluations to
evaluate the whole\.  This yields a column containing all T values\.  
That is, the expression is always true, regardless
of the truth values of $P$ and $Q$.

\begin{tabular}{ccccccc}
  $P$  &$Q$  &  $P \Rightarrow Q$  & $\neg Q$&  $\neg P$ &  $\neg Q\Rightarrow\neg P$ & $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) $ \\
  \hline
  T&    T   &       T &              F   &      F&        T &T\\
  T &   F  &        F  &             T  &       F &       F &T\\
  F  &  T &         T   &            F &        T  &      T &T\\
  F   & F&          T    &           T&         T   &     T &T\\
\end{tabular}

An expression (like this one) whose column contains all T is called a
{\em tautology}.

