\documentclass[12pt]{article}
\usepackage[dvips]{graphicx}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{amsmath}
\usepackage{amssymb}

% the following produces 1 inch margins all around with no header or footer
\topmargin	=10.mm		% beyond 25.mm
\oddsidemargin	=0.mm		% beyond 25.mm
\evensidemargin	=0.mm		% beyond 25.mm
\headheight	=0.mm
\headsep	=0.mm
\textheight	=220.mm
\textwidth	=165.mm

\begin{document}

\begin{center} \Large \sc Adequacy of the Sheffer Stroke \end{center}

When dealing with propositional logic we tend to use the logical connectives: $\vee$, $\wedge$, $\to$, $\leftrightarrow$, and $\neg$. Of course these
connectives are not all independent from each other. In fact, in ``proof system $L$''
we only use $\to$ and $\neg$. All the other connectives are treated as second class
citizens --- they are abbreviations for statments involving $\to$ and $\neg$.  Another
way to state this is: ``The logical connectives $\to$ and $\neg$ are adequate.'' 
Meaning, everything that can be said, could be stated using just $\to$ and $\neg$.

It turns out that we can do even ``better''. Consider the {\bf Sheffer stroke}
denoted by $(\alpha \,|\, \beta)$ whose truth table is:
\begin{center}
\begin{tabular}{|c|c|c|} \hline
$\alpha$ & $\beta$ & $(\alpha\,|\,\beta)$\\ \hline
$T$ & $T$ & $F$ \\ \hline
$T$ & $F$ & $T$ \\ \hline
$F$ & $T$ & $T$ \\ \hline
$F$ & $F$ & $T$ \\ \hline
\end{tabular}
\end{center}

\noindent
The Sheffer stroke $(P\,|\, Q)$ can be thought of as ``not both $P$ and $Q$.''

Assuming that our usual logical connectives, $\{ \vee, \wedge, \to, \leftrightarrow, \neg \}$, are adequate, we
can reduce this set by noticing that 
$\alpha \leftrightarrow \beta$ is logically equivalent to $(\alpha \to \beta ) \wedge (\beta \to \alpha)$, so $\leftrightarrow$
is redundant. Also, $\alpha \vee \beta$ is logically equivalent to $\neg \alpha \to \beta$ and
$\alpha \wedge \beta$ is logically equivalent to $\neg (\alpha \to \neg \beta)$, so we can get along without
them as well. Thus $\{ \to, \neg \}$ is adequate.

Notice that $\alpha \to \beta$ is equivalent to $\neg \alpha \vee \beta$, so $\{ \vee, \neg \}$ is adequate. Or notice
that $\alpha \to \beta$ is equivalent to $\neg ( \alpha \wedge \neg \beta)$, so $\{ \wedge, \neg \}$ is adequate.

On the other hand, $\{ \vee, \wedge \}$ is not adequate. Notice that $\alpha \vee \alpha$, $\alpha \wedge \alpha$,
and $\alpha$ are all equivalent. There's no hope of building a negation from $\vee$ and $\wedge$ alone!

Consider the following truth tables...

\begin{center}
\begin{tabular}{|c|c|} \hline
$\alpha$ & $(\alpha\,|\,\alpha)$ \\ \hline
$T$ & $F$ \\ \hline
$F$ & $T$ \\ \hline
\end{tabular}
\begin{tabular}{|c|c|} \hline
$\alpha$ & $(\neg \alpha)$ \\ \hline
$T$ & $F$ \\ \hline
$F$ & $T$ \\ \hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|c|c|c|c|} \hline
$\alpha$ & $\beta$ & $(\alpha\,|\,\beta)$ & $((\alpha\,|\,\beta)\,|\,(\alpha\,|\,\beta))$ \\ \hline
$T$ & $T$ & $F$ & $T$ \\ \hline
$T$ & $F$ & $T$ & $F$ \\ \hline
$F$ & $T$ & $T$ & $F$ \\ \hline
$F$ & $F$ & $T$ & $F$ \\ \hline
\end{tabular}
\begin{tabular}{|c|c|c|} \hline
$\alpha$ & $\beta$ & $(\alpha \wedge \beta)$ \\ \hline
$T$ & $T$ & $T$ \\ \hline
$T$ & $F$ & $F$ \\ \hline
$F$ & $T$ & $F$ \\ \hline
$F$ & $F$ & $F$ \\ \hline
\end{tabular}
\end{center}

Thus $(\alpha\,|\,\alpha)$ is equivalent to $(\neg \alpha)$, and $((\alpha\,|\,\beta)\,|\,(\alpha\,|\,\beta))$
is equivalent to $(\alpha \wedge \beta)$. Therefore, since $\{ \neg, \wedge \}$ is adequate, any proposition 
$\alpha$ can be translated to another (logically equivalent) proposition $\beta$ involving only these two connectives
--- any occurance of $\neg \sigma$ can be replaced with with $(\sigma\,|\,\sigma)$ and any occurance of $(\sigma \wedge \tau)$ 
can be replaced with $((\sigma\,|\,\tau)\,|\,(\sigma\,|\,\tau))$. Therefore, $\{\,(\,|\,)\,\}$ is adequate.

\newpage

\begin{center} \Large \sc Inadequacy of Conjunction and Disjunction Alone \end{center}

Not that I'm trying to make $\vee$ and $\wedge$ feel bad, but they are inadequate by
themselves. O.K. Maybe I do have it out for them. Let's rub it in by proving they are inadequate
in a more formal way.

\vspace{0.3in}

Let $\beta$ be a proposition logically equivalent to $(\neg \alpha)$ such that $\beta$ is the
shortest proposition built up using only $\alpha$ and the connectives $\wedge$ and $\vee$. 
This implies that we have the following truth table:

\begin{center}
\begin{tabular}{|c|c|c|} \hline
$\alpha$ & $(\neg \alpha)$ & $\beta$ \\ \hline
$T$ & $F$ & $F$ \\ \hline
$F$ & $T$ & $T$ \\ \hline
\end{tabular}
\end{center}

Since $\beta$ is built up from $\alpha$ using only the connectives $\wedge$ and $\vee$ 
(and $\beta=\alpha$ does not yield the correct truth table) we must have that $\beta$ is either 
of the form $(\sigma \wedge \tau)$ or $(\sigma \vee \tau)$ where $\sigma$ and
$\tau$ are propositions. Clearly $\sigma$ and $\tau$ must be built up from $\alpha$ using only
$\wedge$ and $\vee$.

Consider, $(\sigma \wedge \tau)$. If $\alpha$ is $F$ then $\beta=(\sigma \wedge \tau)$ is $T$ thus
both $\sigma$ and $\tau$ are $T$. If $\alpha$ is $T$ then $\beta=(\sigma \wedge \tau)$ is $F$ thus
either $\sigma$ or $\tau$ must be $F$. Thus we have (at least) one of the following:

\begin{center}
\begin{tabular}{|c|c|} \hline
$\alpha$ & $\sigma$ \\ \hline
$T$ & $F$ \\ \hline
$F$ & $T$ \\ \hline
\end{tabular}
{\bf OR}
\begin{tabular}{|c|c|} \hline
$\alpha$ & $\tau$ \\ \hline
$T$ & $F$ \\ \hline
$F$ & $T$ \\ \hline
\end{tabular}
\end{center}

Thus either $\sigma$ or $\tau$ is a proposition logically equivalent to $\beta$. But $\sigma$
and $\tau$ are shorter than $\beta$ and they are built up from $\alpha$ using only $\wedge$ 
and $\vee$. Thus $\beta$ is not the shortest such proposition. (contradiction)

Thus we must have that $\beta = (\sigma \vee \tau)$. If $\alpha$ is $T$ then $\beta=(\sigma \vee \tau)$
is $F$ thus both $\sigma$ and $\tau$ are $F$. If $\alpha$ is $F$ then $\beta=(\sigma \vee \tau)$ is $T$
thus either $\sigma$ or $\tau$ must be $T$. Thus we have (at least) one of the following:
\begin{center}
\begin{tabular}{|c|c|} \hline
$\alpha$ & $\sigma$ \\ \hline
$T$ & $F$ \\ \hline
$F$ & $T$ \\ \hline
\end{tabular}
{\bf OR}
\begin{tabular}{|c|c|} \hline
$\alpha$ & $\tau$ \\ \hline
$T$ & $F$ \\ \hline
$F$ & $T$ \\ \hline
\end{tabular}
\end{center}

Thus either $\sigma$ or $\tau$ is a proposition logically equivalent to $\beta$. But $\sigma$
and $\tau$ are shorter than $\beta$ and they are built up from $\alpha$ using only $\wedge$ 
and $\vee$. Again, $\beta$ is not the shortest such proposition. (contradiction)

Therefore, no such $\beta$ can exist. Thus $(\neg \alpha)$ cannot be built up from $\alpha$
using only $\wedge$ and $\vee$. Hence, the set $\{ \wedge, \vee \}$ is not adequate.
\end{document}
