\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document} \footnotesize
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Solu\c c\~ao da Primeira Lista de Exerc\'{\i}cios}

\begin{flushleft} \large\bf
{Preliminares Matem\'{a}ticas}
\end{flushleft}

\begin{enumerate}
 \item {\it Prove:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$.
        
              \begin{eqnarray*}
               x \in A\cup(B\cap C) & \Leftrightarrow & x \in A \mbox{ ou }
                                                        x \in B\cap C \\
                       & \Leftrightarrow & x \in A \mbox{ ou }
                                                  (x \in B \mbox{ e }
                                                        x \in C) \\
                       & \Leftrightarrow & (x \in A \mbox{ ou }
                                                         x \in B) \mbox{ e }
                                                        (x \in A \mbox{ ou }
                                                         x \in C) \\
                       & \Leftrightarrow & x \in A \cup B
                                                 \mbox{ e } x \in A \cup C) \\
                       & \Leftrightarrow & x \in 
                          (A\cup B)\cap(A\cup C)\mbox{.}
              \end{eqnarray*}
              
        \item $\overline{(A\cup B)}=(\overline{A}\cap\overline{B})$.
        
              \begin{eqnarray*}
               x \in \overline{(A\cup B)} & \Leftrightarrow & x \not\in A\cup B \\
                       & \Leftrightarrow & x \not\in A \mbox{ e } x \not\in B \\
                       & \Leftrightarrow & x \in \overline{A} \mbox{ e }
                                                          x \in \overline{B} \\
                       & \Leftrightarrow & x \in \overline{A} \cap 
                            \overline{B}\mbox{.}
              \end{eqnarray*}
              
        \item se $A\cap B=A\cup B$, ent\~{a}o $A=B$.
        
              Suponha que $A\not=B$. Ent\~ao existe $x$ tal que $x\in A$ e
              $x\not\in B$, ou ent\~ao existe $x$ tal que $x\in B$ e $x\not\in A$. Em
              ambos os casos, $x\not\in A\cap B$ e $x\in A\cup B$, e portanto
              $A\cap B\not=A\cup B$.
              
       \end{list}
 \item {\it Prove que sim ou que n\~{a}o ($\mbox{\cal P}(X)$ \'{e} o
       conjunto pot\^{e}ncia de $X$):}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\cal P}(A)\cap\mbox{\cal P}(B)=\mbox{\cal P}(A\cap B)$?
        
              Sim, pois:
               
              \begin{eqnarray*}
               X \in \mbox{\cal P}(A)\cap\mbox{\cal P}(B) & \Leftrightarrow & 
                     X \in \mbox{\cal P}(A) \mbox{ e } X \in \mbox{\cal P}(B)\\
                  & \Leftrightarrow &  X \subseteq A \mbox{ e } X \subseteq B \\  
                  & \Leftrightarrow &  X \subseteq A \cap B \\  
                  & \Leftrightarrow &  X \in \mbox{\cal P}(A\cap B)\mbox{.} \\  
             \end{eqnarray*}

        \item $\mbox{\cal P}(A)\cup\mbox{\cal P}(B)=\mbox{\cal P}(A\cup B)$?

             Nao. Seja $A=\{a\}$ e $B=\{b\}$. Temos:
             \[\mbox{\cal P}(A)\cup\mbox{\cal P}(B)=
                \{\phi,\{a\}\}\cup\{\phi,\{b\}\}= \{\phi,\{a\},\{b\}\}\mbox{.}\]
             Por outro lado:
             \[\mbox{\cal P}(A\cup B)=\mbox{\cal P}(\{a,b\})=
                \{\phi,\{a\},\{b\},\{a,b\}\}\mbox{.}\]

       \end{list}
       
 \item {\it Que condi\c{c}\~{a}o deve ser satisfeita por duas fun\c{c}\~{o}es $f$ e
       $g$ para que $f\cup g$ seja uma fun\c{c}\~{a}o?}
       
       Sejam $A$ e $B$ os dom\'{\i}nios de $f$ e $g$. Ent\~ao $f\cup g$ ser\'a
       uma fun\c c\~ao se, e somente se, $f(x)=g(x)$ para todo $x\in A\cap B$.
       
 \item {\it Sejam $A$ e $B$ conjuntos de $n$ e $k$ elementos, respectivamente.
       Determine quantas fun\c{c}\~{o}es de $A$ para $B$ existem de cada um dos
       tipos:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it Totais:} $k^n$, pois cada um dos $n$ elementos de $A$ deve ser
              mapeado em algum dos $k$ elementos de $B$.
        \item {\it Parciais:} $(k+1)^n$, pelo mesmo racioc\'{\i}nio, bastando, para
              isto, supor que $B$ tem mais um valor: ``indefinido''.
        \item {\it Injetivas:} $\left\{\begin{array}{ll} 0 & \mbox{se } n>k \\
                          k\times(k-1)\times\cdots\times(k-n+1) & \mbox{se }
                          n\leq k \end{array} \right.$
        \item {\it Sobrejetivas:} $\left\{\begin{array}{ll} 0 & \mbox{se } n<k \\
                          n\times(n-1)\times\cdots\times(n-k+1)\times k^{(n-k)}
                           & \mbox{se } n\geq k \end{array} \right.$

              onde $n\times(n-1)\times\cdots\times(n-k+1)$ \'e o n\'umero de
              ``acasalamentos'' poss\'{\i}veis de todos os elementos de $B$ com
              elementos de $A$, e $k^{(n-k)}$ \'e o n\'umero de
              distribui\c c\~oes poss\'{\i}veis dos elementos restantes de $A$.
        \item {\it Bijetivas:} $\left\{\begin{array}{ll} 0 & \mbox{se } n\not=k \\
                          k! & \mbox{se } n=k \end{array} \right.$
       \end{list}
 \item {\it Uma fun\c{c}\~{a}o total $f:\mbox{\bf N}\rightarrow
       \mbox{\bf N}$ \'{e} dita ser {\em monot\^{o}nica crescente\/} se $f(n)<f(n+1)$
       para todo $n\in\mbox{\bf N}$. Prove que existe um n\'{u}mero n\~{a}o cont\'{a}vel de
       fun\c{c}\~{o}es monot\^{o}nicas crescentes.}
       
       O conjunto das fun\c c\~oes monot\^onicas crescentes \'e infinito. Logo,
       deve-se mostrar que n\~ao \'e enumer\'avel. Suponha que tais fun\c c\~oes
       possam ser enumeradas: $f_0, f_1, f_2, \ldots$. Seja a fun\c c\~ao
       $g: \mbox{\bf N}\rightarrow \mbox{\bf N}$, definida da seguinte forma:
       \[\left\{\begin{array}{ll} g(0)=f_0(0)+1  \\
                          g(n)=g(n-1) + f_n(n)& \mbox{se }
                          n>0 \end{array} \right.\]
       N\~ao \'e dif\'{\i}cil mostrar que $g$ \'e monot\^onica crescente, e que
       $g(k)\not=f_k(k)$ para todo $k\in\mbox{\bf N}$, ou seja, $g$ \'e uma
       fun\c c\~ao monot\^onica crescente diferente de $f_k$, para todo $k$.
       Logo, o conjunto das fun\c{c}\~{o}es monot\^{o}nicas crescentes n\~ao \'e
       cont\'avel.
 \item {\it D\^{e} uma defini\c{c}\~{a}o recursiva do conjunto dos
       subconjuntos finitos de {\bf N}. Use uni\~{a}o como operador.}
       
       O conjunto dos subconjuntos finitos de {\bf N},
       $\mbox{\it SF\/}(\mbox{\bf N})$, pode ser definido {\em recursivamente\/}
       da seguinte forma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\phi\in\mbox{\it SF\/}(\mbox{\bf N})$;
        \item se $X\in\mbox{\it SF\/}(\mbox{\bf N})$ e $n\in\mbox{\bf N}$, ent\~ao
              $X\cup\{n\}\in\mbox{\it SF\/}(\mbox{\bf N})$.
       \end{list}
 \item {\it D\^{e} uma defini\c{c}\~{a}o recursiva do conjunto
       dos nodos de um grafo direcionado que podem ser alcan\c{c}ados a partir
       de um nodo $x$. Use a rela\c{c}\~{a}o de adjac\^{e}ncia como
       opera\c{c}\~{a}o.}
       
       O conjunto dos nodos de um grafo direcionado, $G=(N,A)$, que podem ser
       alcan\c{c}ados a partir de um nodo $x$, $S_G(x)$, pode ser
       definido {\em recursivamente\/} da seguinte forma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x\in S_G(x)$;
        \item se $x\in S_G(x)$ e $[x,y]\in A$, ent\~ao
              $y\in S_G(x)$.
       \end{list}
  
 \item {\it Seja uma \'{a}rvore em que cada nodo tem no m\'{a}ximo $k$ filhos. Se ela
       tiver exatamente $i$ nodos internos, quais s\~{a}o os n\'{u}meros
       m\'{\i}nimo e m\'{a}ximo de nodos que a fronteira da mesma pode ter? }
       
       Evidentemente, o n\'umero m\'{\i}nimo de nodos da fronteira ocorrer\'a
       quando cada nodo interno tiver exatamente 1 filho, caso em que a 
       fonteira ter\'a, evidentementre, 1 nodo apenas. J\'a o n\'umero m\'aximo
       de nodos da fronteira ocorrer\'a quando cada nodo interno tiver
       exatamente k filhos. Neste caso, a \'arvore ter\'a $ik+1$ nodos, quais
       sejam, os $ik$ nodos que s\~ao ``filhos'', mais a raiz. Portanto, a
       fronteira ter\'a $ik+1-i=(k-1)i+1$ nodos.

 \item {\it Prove, por indu\c{c}\~{a}o, que
       $\sum_{i=0}^{n}2^i=2^{n+1}-1$ para todo $n\in \mbox{\bf N}$.}
       
       Observe, inicialmente, que $\sum_{i=0}^02^i=2^0=1=2^{0+1}-1$. Suponha,
       como hip\'otese de indu\c c\~ao, que $\sum_{i=0}^{n}2^i=2^{n+1}-1$ para
       um certo $n\in \mbox{\bf N}$. Deve-se ent\~ao provar que
       $\sum_{i=0}^{n+1}2^i=2^{n+2}-1$. Ora,
       
       \begin{eqnarray*}
         \sum_{i=0}^{n+1}2^i & = & \sum_{i=0}^{n}2^i + 2^{n+1}\mbox{,
                                           pela defini\c c\~ao de somat\'oria}\\
                             & = & 2^{n+1}-1 + 2^{n+1}\mbox{,
                                           pela hip\'otese de indu\c c\~ao} \\
                             & = & 2.2^{n+1}-1 \\
                             & = & 2^{n+2}-1
       \end{eqnarray*}
 
 \item {\it Uma {\em \'{a}rvore bin\'{a}ria completa\/} de
       profundidade $n$ \'{e} uma \'{a}rvore estritamente bin\'{a}ria na qual
       cada nodo nos n\'{\i}veis anteriores a $n$ tem filhos e cada nodo no
       n\'{\i}vel $n$ \'{e} uma folha. Prove que uma \'{a}rvore bin\'{a}ria
       completa de profundidade $n$ tem $2^{n+1}-1$ nodos.}
       
       Uma \'{a}rvore bin\'{a}ria completa (ABC) de profundidade $0$ tem 1 nodo,
       e $2^{0+1}-1=1$. Suponha, como hip\'otese de indu\c c\~ao, que uma
       ABC de profundidade $n$ tem $2^{n+1}-1$ nodos. Deve-se, ent\~ao, provar
       que uma ABC de profundidade $n+1$ tem $2^{n+2}-1$ nodos. Mas, pela
       defini\c c\~ao, uma ABC de profundidade $n+1$ \'e formada por 1 nodo raiz
       mais 2 ABC's, ambas de profundidade $n$; assim, pela hip\'otese de
       indu\c c\~ao, uma ABC de profundidade $n+1$ ter\'a $2(2^{n+1}-1)+1$
       nodos, ou seja, $2^{n+2}-1$ nodos.
\end{enumerate}

\end{document}
