\documentstyle[12pt,psfig]{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}
\newcommand{\binom}[2]{{#1 \choose #2}}

\begin{document}

{\bf Tutorial 8 Solutions}

(a) A boolean function $f$ maps each $0,1$ string of length $k$ to one
of $0,1$. We can define a mapping from boolean functions to 
subsets of $0,1$ strings of length $k$ as follows: A function
$f$ is mapped to the subset of strings that it maps to $0$.
This mapping from boolean functions to subsets of the set of all
strings of length $k$ is a injection because for any two distinct functions
there is some string which one of them sends to $0$ while the other
maps to $1$. It is also a surjection because we can define the 
inverse map from subsets of $\{0,1\}^k$ to boolean functions as
follows: map a subset $S$ of strings to the function which maps
the strings in the subset to $0$ and all other strings to $1$. 
Therefore we have a bijection. Hence the number of boolean functions
is the number of subsets of $0,1$ strings of length $k$. There are $2^k$
strings of length $k$. The number of subsets is $2^{2^k}$.

(b) Consider some circuit with $s$ gates and $k$ inputs. Each gate has at most
two input wires.  We can describe a circuit completely by specifying the
origins of the input wires of each gate and the types of the gates,
since we can assume without loss of generality that the output of the
entire circuit comes from some particular gate.  The total number of
inputs plus gates is $s+k$, so number of possibilities for the origin of
each input wire of a gate is $s+k$.  The total number of ways in which
we can wire the inputs to a single gate is therefore at most $(s+k)^2$.
Furthermore, each gate will be either AND, OR, or NOT.  Therefore, there
are a total of at most $3(s+k)^2$ possible gates in a circuit of $s$
gates and $k$ inputs.  There are $s$ gates to be chosen from this set.
So, by the product rule, the total number of boolean circuits is at most
$(3(s+k)^2)^s$.

(c) We have just established that there are at most $(3(s+k)^2)^s$
circuits on $k$ inputs of size $s$.  We now want to show that for
$s=\frac{2^k}{6k}$, this will cover less than half of the $2^{2^k}$
boolean functions on $k$ inputs.  We will show this by substitution.
We can first note that for $k \geq 9$, $\frac{2^k}{6k} > k$.

$$(3(s+k)^2)^s \leq ((s+k)^3)^s \hspace{1em}\mbox{for}\hspace{1em} k \geq 3$$
$$= (s+k)^{3s} $$
$$\leq s^{6s} \hspace{1em}\mbox{for}\hspace{1em} k \geq 9$$
$$= 2^{6s \lg{s}}$$
$$= 2^{(6(2^k)/(6k))(\lg{(2^k)/(6k))}}$$
$$= 2^{(2^k/k)(k-\lg{6k})}$$
$$\leq 2^{2^k-1}$$
$$= \frac{1}{2}2^{2^k}$$
\qed

(d) Last time, we looked at functions from $\cal{N}$ to $\{0,1\}$, which
is an uncountably large set.  Now, we are looking only at functions
$\{0,1\}^k$ to $\{0,1\}$, which is a finite set for any fixed $k$.
Therefore, all of the functions from $\{0,1\}^k$ to $\{0,1\}$ are
computable, although possibly very slowly.

\end{document}

