%  Functionally complete sets of logical operators.

%\input mathhead.tex
%\magnification=\magstep1
%\nopagenumbers
\font\bigrm=cmr17
\font\medrm=cmr12
\font\medbf=cmbx12
\def\sc{\it}
\def\sectioncount{\count11}
\sectioncount=0
\def\theoremcount{\count12}
\theoremcount=0
\def\lemmacount{\count13}
\lemmacount=0
\def\corollarycount{\count14}
\corollarycount=0
\def\exerciseno{\count15}
\exerciseno=0
\def\algorithmcount{\count16}
\algorithmcount=0
\def\figurecount{\count17}
\figurecount=0
\def\ex{\advance\exerciseno by 1
        \item{\the\exerciseno.}
       }
\def\section#1{\advance\sectioncount by 1
     \medskip
     {\par \noindent \bf\the\sectioncount.\enskip #1.}
     \medskip
%     \headline={{\sl #1\hfil\the\pageno}}
     \theoremcount=0
     \lemmacount=0
     \corollarycount=0
    }
\long\def\longtheorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\theorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longlemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\lemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longcorollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\corollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longalgorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\algorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\figure#1#2#3{\advance\figurecount by 1
                \vbox{
                      \vskip #1
                      \special{psfile="#2"}
                      \vskip .3true in
                      \centerline{Figure\ \the\figurecount.}
                     }
                \medskip
                \figurelabel{#3}
            }
\def\proof{{\bf\noindent Proof}:\enskip}
%\def\qed{\hfill \vrule width4pt height8pt depth0pt}
\def\qed{\hfill\vbox to 4pt{\hrule\hbox to 4pt
            {\vrule height 3pt depth 0pt \hfill \vrule}\vfill\hrule}
            \medskip
            }
\def\exerciselabel#1{\edef#1{\the\exerciseno}}
\def\theoremlabel#1{\edef#1{\the\sectioncount.\the\theoremcount}}
\def\lemmalabel#1{\edef#1{\the\sectioncount.\the\lemmacount}}
\def\corollarylabel#1{\edef#1{\the\sectioncount.\the\corollarycount}}
\def\algorithmlabel#1{\edef#1{\the\sectioncount.\the\algorithmcount}}
\def\figurelabel#1{\edef#1{\the\figurecount}}
\def\svs#1{{\sl S}_{#1}}
\def\dsvs#1{\dual{{\sl S}_{#1}}}
\def\dual#1{#1^*}
\def\comp#1{{\overline #1}}
\def\bibitem#1#2{
        \vbox{
          \smallskip\noindent \hangindent2\parindent \textindent{[#1]\ } #2}
        }
\def\Z{{\bf Z}}
\def\T{\top}
\def\true{\top}
\def\false{\bot}
\def\F{\bot}
\def\iff{\leftrightarrow}
\def\underline#1{{\bf #1}}
\def\notequal{\not=}
\def\plusminus{\pm}
\def\circle{\circ}
\def\N{{\rm\bf N}}
\def\Z{{\rm\bf Z}}
\def\R{{\rm\bf R}}
\def\Q{{\rm\bf Q}}
\def\C{{\rm\bf C}}
\def\page{\vfill\eject}
\def\title#1{\centerline{\bigrm #1}\bigskip}

\def\author#1{\centerline{\bf #1}\par}
\def\department#1{\centerline{#1}\par}
\def\university#1{\centerline{#1}\par}
\def\address#1{\centerline{#1}\par}

\def\by#1#2#3#4{\author{#1}\department{#2}\university{#3}\address{#4}
                \bigskip}
\def\({\left (}
\def\){\right )}
\def\[{\left [}
\def\]{\right ]}
\def\lf{\left\lfloor}
\def\rf{\right\rfloor}
\def\lc{\left\lceil}
\def\rc{\right\rceil}


\magnification=\magstep1
\nopagenumbers

\centerline{{\bigrm Functionally Complete Sets}}
\bigskip

\noindent
{\bf Purpose.}  The purpose of this project is to determine that the
usual logical operators are sufficient to give every possible truth table.
Furthermore, you will find other sets of logical operators that are
sufficient to give all possible sets of truth tables.

\noindent
{\bf Definitions.}  A set of logical operators is called {\bf functionally
complete} if every compound proposition is logically equivalent to a
compound proposition involving only operations in the set.  The
operators in compound propositions are the usual operators of
conjunction ($\wedge$), disjunction ($\vee$), negation ($\neg$) , 
implication ($\to$), and biconditional ($\leftrightarrow$).

\noindent
{\bf Procedure.}  Complete the following steps to determine sets of
operators that are functionally complete and to better understand
what functionally complete means.

\item{1.}Prove that the operators $\vee$ and $\neg$ are functionally
complete.  (Hint: First, show every statement involving only one logical 
operator and two simple propositions, like $p\to q$, is
logically equivalent to a compound propositions involving
only $\vee$ and $\neg$.)

\item{2.}Next prove that the operators $\wedge$ and $\neg$ are
functionally complete.

\item{3.}Consider the operator NAND, denoted by $|$.  The proposition
$p | q$ is defined to be 
equivalent with the proposition $\neg (p\wedge q)$.  Show that
NAND is functionally complete.

\item{4.}The operator NOR is denoted by $\downarrow$.  The proposition 
$p\downarrow q$ is defined to be 
equivalent with the proposition $\neg (p\vee q)$.
Show NOR is functionally complete.

\item{5.}Find a compound statement involving
only NAND whose truth table is given below.

$$
\matrix{
  p & q & r & ? \cr
  T & T & T & T \cr
  T & T & F & T \cr
  T & F & T & F \cr
  T & F & F & T \cr
  F & T & T & F \cr
  F & T & F & T \cr
  F & F & T & T \cr
  F & F & F & F \cr
}
$$

\item{6.}The definition of a functionally complete  set of operators
is that any compound
proposition involving the usual logical operators is logically equivalent
with a proposition involving only the operators in the functionally
complete set.  Now, suppose that you make up a ``truth table" 
involving the propositions $p_1,p_2,\cdots ,p_n$ by
assigning arbitrarily T and F values to each of the $2^n$ rows.  Is it always
possible to find a compound proposition involving the statements
$p_1,p_2,\cdots ,p_n$ and the usual logical operators which gives the
made up truth table?  Determine the answer to this question.  If you
think the answer is no, then you should find an example of a table which is
not the truth table for any compound proposition.
You may want to start looking for a table with $n=2$.  If you do not
find an example, then maybe try $n=3$, and so on.  On the other hand, if
you think the answer is yes, then you need to prove that no matter which
table you write down, you can find a compound proposition giving this
table.  In this case, it may be a good idea to try an induction proof.
In either case, you will need to prove your answer.


\bye