\documentstyle[12pt,twoside,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}

\input{mk-macros}

\begin{document}

\lecnotes{March 16, 1995}{11}



\medskip

{\bf Reading:} Section 6 of Truss.

\section{Predicate calculus and first order logic}

There is  something missing in propositional logic, namely, the ability to
use variables and quantifiers. For example, we want to be able to say ``for
every $\epsilon>0$ there is a $\delta>0$ such that ...''. Predicate logic fixes
this.

First order logic is a specific version of predicate logic. It allows the use
of variables, constants, relations and functions and, of course, quantifiers.
To specify a logic we need to specify a set of constants denoted by
$\u{a},\u{b},\cdots$, a set of functions denoted by
$\u{f}(x),\u{g}(x,y),\cdots$ and a set of relations denoted by $\u{R}(x),
\u{Q}(x,y),\cdots$. We will explain why the boldface later.

A {\em term} is either a variable, or a constant, or a function applied to
other terms. To be specific, we will use two functions: $\u{s}(x)$, the {\em
successor} function and $\u{+}(x,y)$, the {\em addition} function. We will
write $x\u{+}y$ instead of the cumbersome $\u{+}(x,y)$. 

\begin{examples}
\item $\u{a}\u{+}x$.
\item $\u{s}(x)\u{+}\u{s}(\u{s}(\u{0}))$.
\end{examples}

A {\em formula} (like a sentence) is defined inductively by using one of the
connectives of propositional logic. In addition, we will use the quantifiers
$\exists$ and $\forall$. The base case are the relations whose inputs are
terms. To be specific we will use the relations $x\u{<}y$, the {\em less than}
relation and $x=y$, the {\em equality} relation.

\begin{examples}
\item $\u{s}(\u{0})\u{<} x$.
\item $\exists x (x\u{<}\u{0})$.
\item $\forall x \exists y (x\u{<}y)$.
\item $[\u{P}(\u{0})\land(\forall
n(\u{P}(n)\rightarrow\u{P}(\u{s}(n))))]\rightarrow(\forall n \u{P}(n))$.
\end{examples}

A variable is said to be {\em free} if it is not quantified. In example 4,
$\u{P}(n)$ is any formula with one free variable. Parenthesis should be used to
dispense of ambiguities, in particular when using quantifiers.

Now we define the equivalent of an assignment. An  {\em interpretation} consists of a
universe \Om\ together with a specification of the constants, the functions and
the relations in our language.

\newpage
\begin{examples}
\item In the above examples, we can let $\Om=\nats$ and define $\u{0}=0$,
$\u{s}$ as the function $s(n)=n+1$ and $\u{+}$ as + and $\u{<}$ as $<$.
\item As above but let $\Omega=\ints$.
\item As above but now we define $\u{0}=1$, $\u{s}()$ as the function
$s(n)=2n$, $\u{<}$ as ``divides'' and $\u{+}$ as $\times$.
\end{examples}

It is customary to use traditional functions for traditional names. For
example, we usually interpret $\u{+}$ as the natural addition.  We say that an
interpretation is a {\em model} of a set $\Gamma$ of formulae if it makes every
formula in $\Gamma$ true.

\exm
Let $\Gamma=\{\forall x \u{R}(x,x), \forall x\forall
y(\u{R}(x,y)\land\u{R}(y,x)\rightarrow x=y), \forall x\forall y\forall z
(\u{R}(x,y)\land\u{R}(y,z))\rightarrow\u{R}(x,z)\}$. The models of \Ga\ are
precisely the partial ordered sets $(\Omega,R)$.
\eexm

\exr
Describe the models of the formula $\exists x\exists y\forall z
(x=z)\lor(y=z)$.
\eexr

Just as in propositional logic, we can define logical equivalence by saying
that two formulae are logically equivalent ($\psi\equiv\varphi$) iff they have
the same models.  Clearly, we can use the rules of boolean algebra to
manipulate the connectives and get equivalent formulae. In addition, the
following rules are true:

\begin{enumerate}
\item $\neg\exists x\psi(x)\equiv\forall x \neg\psi(x)$.
\item $\neg\forall x\psi(x)\equiv\exists x \neg\psi(x)$.
\item $Q x\psi(x)\equiv Q y\psi(y)$ where $Q=\exists,\forall$.
\item $(Q x\psi(x))\odot\varphi\equiv Q x(\psi(x)\odot\varphi)$ where
$Q=\exists,\forall$, $\odot=\land,\lor$ and $x$ does not occur in $\varphi$.
\end{enumerate}

\exm
$\forall x\psi(x)\land\exists y\varphi(y)\equiv\forall x\exists
y(\psi(x)\land\varphi(y))\equiv\exists y\forall x(\psi(x)\land\varphi(y))$.
Note that in general $\forall x\exists y\u{P}(x,y)\not\equiv\exists y\forall
x\u{P}(x,y)$.
\eexm


\exr
Show that any formula  has an equivalent formula in {\em prenex normal form}.
That is, one in the form $Q_1x_1Q_2x_2,\cdots,Q_kx_k\psi(x_1,\cdots,x_k)$ where
the $Q_i$'s are quantifiers and $\psi$ is quantifier free.
\eexr

\section{Boolean circuits}

We have said that a propositional sentence on $n$ variables can be thought of
as a function from $\{\T,\F\}^n$ to $\{\T,\F\}$. By renaming \T\ and \F\ as 1
and 0, we can think of such a sentence as a function
$f:\{0,1\}^n\mapsto\{0,1\}$. We can think of the variables as {\em
inputs} to the function and we can view the connectives as operations (or
{\em gates}). 

We can generalize to the case where the function has $m$ outputs. That is,
where $f:\{0,1\}^n\mapsto\{0,1\}^m$.

\exm
Let $x$ and $y$ be 2 $n/2$-bit numbers. Let $m=n/2+1$ and define $f(x,y)$ as
the binary representation of $x+y$.
\eexm

A {\em Boolean circuit} (or {\em switching} circuit) on $n$ inputs and $m$
outputs can be defined in the natural way. Such a circuit computes a function
from $\{0,1\}^n$ to $\{0,1\}^m$. 

\vspace*{3in}

Given a circuit $C$, the {\em size} of $C$ is defined as the number of gates in
$C$. The {\em depth} of $C$ is defined as the length of the longest path
between an input and an output. Here, we are looking at the underlying graph of
the circuit as a directed acyclic graph.

Just as a particular sentence has many equivalent representations, a function
can be computed by many circuits. For a given function $f$ we define $s(f)$ as
the size of the smallest circuit that computes $f$. Similarly, we define
$d(f)$.

If we write any function $f$ in DNF, we can see that the resulting circuit
has $n-1$ $\land$-gates for each term. If there are $T$ terms then there will
be $T-1$ $\lor$-gates. Therefore,
for any function on $n$ variables, $s(f)\le (n-1)\times2^n$. This does not mean
that we cannot do better. In fact, using the so called Karnaugh Maps one can
minimize the number of terms used in a DNF. Karnaugh maps are based on the fact
that $(x\land y)\lor(x\land\neg y)\equiv x$. Hence, if two terms differ only in
that one has the literal $y$ and the other the literal $\neg y$ then one can
remove the variable $y$ from each and drop one of the terms.

\section{The parity function}

We will now study a particular function in more detail. The function is
$f(x_1,\cdots,x_n)=x_1\oplus\cdots\oplus x_n$ where $\oplus$ is the sum modulo
2 of its arguments. That is, $f$ outputs 1 iff the number of inputs which are 1
is odd. This is called the {\em parity} function. 

Lets start by writing the parity function in DNF. Each term has an odd number
of positive literals and for each way of picking an odd number of 1's, there is
a corresponding term.

How many terms do we get?

\thm
The above is the smallest DNF for $x_1\oplus\cdots\oplus x_n$.
\ethm

\pf
We will show that we cannot have a term of length less than $n$. If this is so,
then the theorem will follow as each term {\em accepts} exactly one input with
an odd number of 1's and there are $2^{n-1}$ such inputs.

By way of contradiction, assume that there is a term of size less than $n$.
There is a variable which does not appear in the term (say $x_n$). We can set
the remaining variables in such a way that the term is satisfied and then set
$x_n$ in such a way that the input has an even number of 1's. This input will
still satisfy the term and, therefore, the DNF.
\epf

We now show that we can build a much smaller circuit for the parity function.
The circuit is based on the fact that $\oplus$ is associative. We build a
complete binary tree with $n$ leaves and we put a $\oplus$-gate in each inner
node. We then ``simulate'' each $\oplus$-gate with gates from
$\{\land,\lor,\neg\}$. The final circuit has $5(n-1)$ gates.

\end{document}
