\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document} \footnotesize

\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2001 \\
Professor: Newton Jos\'{e} Vieira \hfill http://www.dcc.ufmg.br/\verb+~+nvieira \\
{\bf Terceira Lista de Exerc\'{\i}cios/Solu\c c\~ao de Exerc\'{\i}cios Selecionados}

\begin{description} \footnotesize

 \item[Se\c c\~ao 4.1] \ 
 
  \begin{enumerate}

   \item[5.]

       Os casos n\~ao s\~ao exaustivos; falta considerar os casos: (3) $x\in A$
       e $y\in D$, e (4) $x\in C$ e $y\in B$.

   \item[7.]

       Sim, \'e verdade que, para quaisquer conjuntos $A$, $B$ e $C$, $A\times
       (B\backslash C)=(A\times B)\backslash(A\times C)$.

       Prova: 
   
           \begin{tabbing}
            $(x,y)\in (A\times B)\backslash(A\times C)$ \=sse $(x,y)\in
             A\times B\wedge (x,y)\not\in A\times C$ \\
            \>sse $(x\in A\wedge y\in B)\wedge(x\not\in A\vee y\not\in C)$ \\
            \>sse $(x\in A\wedge y\in B\wedge x\not\in A)\vee
             (x\in A\wedge y\in B\wedge y\not\in C)$ \\
            \>sse $x\in A\wedge y\in B\wedge y\not\in C$ \\
            \>sse $x\in A\wedge y\in B\backslash C$ \\
            \>sse $(x,y)\in A\times(B\backslash C)$ \\
           \end{tabbing}
          Como $(x,y)$  \'e um par arbitr\'ario, segue-se que $A\times
       (B\backslash C)=(A\times B)\backslash(A\times C)$.
         
   \item[8.]

       A provar: se $(A\times B)\cap (C\times D)=\phi$ ent\~ao $A\cap C=\phi\vee
             B\cap D=\phi$.

       Suponha que $(A\times B)\cap (C\times D)=\phi$; disto, segue-se que
       $\neg \exists x\exists y[(x,y)\in A\times B\wedge (x,y)\in C\times D]$, que
       equivale a $\forall x\forall y[(x\not\in A\vee y\not\in B)\vee
       (x\not\in C\vee y\not\in D)]$, que equivale a $\forall x\forall y
       [(x\in A\wedge x\in C)\rightarrow (y\not\in B\vee y\not\in D)]$.
       Suponha que $A\cap C\not=\phi$; neste caso, seja um elemento $a$ tal que
       $a\in A$ e $a\in C$. Pela \'ultima afirmativa universal acima, tem-se que
       $y\not\in B$ ou $y\not\in D$, para qualquer $y$; logo, $B\cap D=\phi$.
       Assim, dado que $(A\times B)\cap (C\times D)=\phi$, se $A\cap C\not=\phi$
       ent\~ao $B\cap D=\phi$, ou seja, se $(A\times B)\cap (C\times D)=\phi$
       ent\~ao $A\cap C=\phi\vee B\cap D=\phi$.

  \end{enumerate}

 \item[Se\c c\~ao 4.2] \ 
 
  \begin{enumerate}

   \item[6.] 

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R\subseteq \mbox{\em Dom\/}(R)\times \mbox{\em Im\/}(R)$ \'e verdadeira:

           Seja $(a,b)$ um par arbitr\'ario de $R$. Por defini\c c\~ao, $a\in\mbox{\em Dom\/}(R)$
           e $b\in\mbox{\em Im\/}(R)$; assim, $(a,b)\in\mbox{\em Dom\/}(R)\times \mbox{\em Im\/}(R)$.
           Conclus\~ao: $R\subseteq \mbox{\em Dom\/}(R)\times \mbox{\em Im\/}(R)$.

        \item \'E verdadeiro que se $R\subseteq S$ ent\~ao $R^{-1}\subseteq S^{-1}$:

           Suponha que $R\subseteq S$. Seja um par arbitr\'ario $(b,a)\in R^{-1}$. Segue-se
           disto que $(a,b)\in R$; e, como $R\subseteq S$, $(a,b)\in S$. Desta \'ultima deduz-se
           que $(b,a)\in S^{-1}$. Como $(b,a)$ \'e arbitr\'ario, segue-se que $R^{-1}\subseteq S^{-1}$.
           Portanto, se $R\subseteq S$ ent\~ao $R^{-1}\subseteq S^{-1}$.

        \item $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$ \'e verdadeira:

           Seja $(a,b)$ um par arbitr\'ario de $A\times B$.
           \begin{tabbing}
            $(a,b)\in (R\cup S)^{-1}$ \=sse $(a,b)\in R^{-1}$ ou $(a,b)\in S^{-1}$ \ \=pela \kill
            $(b,a)\in (R\cup S)^{-1}$ \>sse $(a,b)\in R\cup S$ \>pela def. de inversa\\
              \>sse $(a,b)\in R$ ou $(a,b)\in S$ \\
              \>sse $(b,a)\in R^{-1}$ ou $(b,a)\in S^{-1}$ \>pela def. de inversa\\
              \>sse $(b,a)\in R^{-1}\cup S^{-1}$
           \end{tabbing}
           Como $(a,b)$ \'e um par arbitr\'ario, conclui-se que  $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$.
       \end{list}

  \end{enumerate}

 \item[Se\c c\~ao 4.3] \ 

  \begin{enumerate}

   \item[8(a).] Para toda rela\c c\~ao $R\subseteq A\times B$, $R\circ i_A=R$:

       1. $R\circ i_A\subseteq R$:

       Seja um par arbitr\'ario $(a,b)\in R\circ i_A$. Ent\~ao existe um elemento $c\in A$ tal que
       $(a,c)\in i_A$ e $(c,b)\in R$. Como $i_A=\{(x,y)\in A\times A\,\,|\,\, x=y\}$, segue-se que $a=c$.
       Assim, $(a,b)\in R$. Como $(a,b)$ \'e um par arbitr\'ario, conclui-se que $R\circ i_A\subseteq R$.
      
       2. $R\subseteq R\circ i_A$:

       Seja um par arbitr\'ario $(a,b)\in R$. Como $i_A=\{(x,y)\in A\times A\,\,|\,\, x=y\}$, sabe-se que
       $(a,a)\in i_A$. Assim, $(a,b)\in R\circ i_A$. Como $(a,b)$ \'e um par arbitr\'ario, conclui-se que
       $R\subseteq R\circ i_A$.

   \item[9(b).] Suponha que $R,S\subseteq A\times A$ s\~ao rela\c c\~oes sim\'etricas.
       \begin{itemize}
        \item $R\cap S$ \'e sim\'etrica ($\forall a,b\in A [(a,b)\in R\cap S\rightarrow (b,a)\in R\cap S]$):

              Seja $a,b\in A$ arbitr\'arios e suponha que $(a,b)\in R\cap S$. Segue-se, ent\~ao, que
              $(a,b)\in R$ e $(a,b)\in S$. Como $R$ e $S$ s\~ao sim\'etricas, $(b,a)\in R$ e 
              $(b,a)\in S$. Assim, $(b,a)\in R\cap S$. Como $a$ e $b$ s\~ao arbitr\'arios, conclui-se
              que $R\cap S$ \'e sim\'etrica.

        \item $R\cup S$ \'e sim\'etrica ($\forall a,b\in A [(a,b)\in R\cup S\rightarrow (b,a)\in R\cup S]$):

              Seja $a,b\in A$ arbitr\'arios e suponha que $(a,b)\in R\cup S$. Segue-se, ent\~ao, que
              $(a,b)\in R$ ou $(a,b)\in S$. Como $R$ e $S$ s\~ao sim\'etricas, $(b,a)\in R$ ou 
              $(b,a)\in S$. Assim, $(b,a)\in R\cup S$. Como $a$ e $b$ s\~ao arbitr\'arios, conclui-se
              que $R\cup S$ \'e sim\'etrica.

        \item $R^{-1}$ \'e sim\'etrica ($\forall a,b\in A [(a,b)\in R^{-1}\rightarrow (b,a)\in R^{-1}]$):

              Seja $a,b\in A$ arbitr\'arios e suponha que $(a,b)\in R^{-1}$. Segue-se, ent\~ao, que
              $(b,a)\in R$. Como $R$ \'e sim\'etrica, $(a,b)\in R$. Desta \'ultima, deduz-se que
              $(b,a)\in R^{-1}$. Como $a$ e $b$ s\~ao arbitr\'arios, conclui-se que $R^{-1}$ \'e 
              sim\'etrica.

        \item $R\circ S$ nem sempre \'e sim\'etrica. Contra-exemplo:

              $R=\{(a,b),(b,a)\}$, $S=\{(b,c),(c,b)\}$, Tem-se: $R\circ S=\{(c,a)\}$.

       \end{itemize}
  \end{enumerate}

 \item[Se\c c\~ao 5.1] \ 
 
  \begin{enumerate}

   \item[1.]

      (e) \
 
       $f$ n\~ao \'e fun\c c\~ao, pois existem palavras com mais de uma letra;
       $g$ \'e fun\c c\~ao, pois toda palavra tem uma letra inicial e ela \'e
       \'unica.
 
      (f) \

       $R$ \'e uma fun\c c\~ao, visto que, estando as pessoas sentadas em volta
       de uma mesa redonda,
       \begin{itemize}
        \item uma pessoa sempre estar\'a sentada \`a direita de algu\'em, e
        \item este algu\'em ser\'a \'unico.
       \end{itemize}
         
   \item[3.]

       $L\circ H=i_N=\{(n,n)\,|\,n\in N\}$
    
       $H\circ L=\{(c_1,c_2)\in C\times C\,|\, \mbox{$c_2$ \'e a capital do
               pa\'{\i}s da cidade $c_1$}\}$

   \item[4.]

       \[(f\circ g)(x)=f(g(x))=f(2x-1)=\frac{1}{(2x-1)^2+2}\mbox{.}\]
       \[(g\circ f)(x)=g(f(x))=g(\frac{1}{x^2+2})=2\frac{1}{x^2+2}-1=
       -\frac{x^2}{x^2+2}\mbox{.}\]

   \item[5(a).]

       Hip\'oteses: $f:A\rightarrow B$, $C\subseteq A$; por defini\c c\~ao:
       $f\!\uparrow\! C=f\cap(C\times B)$
    
       i) Provando $f\!\uparrow\! C: C\rightarrow B$: \\
       {\it Exist\^encia\/}. Seja um $c\in C$ arbitr\'ario. Como $C\subseteq A$,
       $c\in A$ e, como $f:A\rightarrow B$, existe $b$ tal que $(c,b)\in f$. E
       como $(c,b)\in C\times B$ e $f\!\uparrow\! C=f\cap(C\times B)$, segue-se que
       $(c,b)\in f\!\uparrow\! C$.
       Logo, para todo $c\in C$ existe $b\in B$ tal que $(c,b)\in f\!\uparrow\! C$. \\
       {\it Unicidade\/}. Pela defini\c c\~ao de $f\!\uparrow\! C$, se $(c,b_1)\in
       f\!\uparrow\! C$ e $(c,b_2)\in f\!\uparrow\! C$, ent\~ao $(c,b_1)\in f$ e
       $(c,b_2)\in f$. Como $f$ \'e uma fun\c c\~ao, $b_1=b_2$.

       ii) Provando $\forall c\in C f(c)=f\!\uparrow\! C(c)$: \\
       Segue diretamente das hip\'oteses e de $f\!\uparrow\! C: C\rightarrow B$.

  \end{enumerate}

 \item[Se\c c\~ao 5.2] \ 
 
  \begin{enumerate}

   \item[3.]

      Hip\'oteses: $A=\mbox{\bf R}\backslash\{1\}$; $f:A\rightarrow A$, onde:
      \[f(x)=\frac{x+1}{x-1}\mbox{.}\]
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item $f$ \'e bijetiva.
     
           Sejam $x,y\in A$, arbitr\'arios, e suponha que $f(x)=f(y)$.
           Ent\~ao $(x+1)/(x-1)=(y+1)/(y-1)$. Disto, segue-se que $(x+1)(y-1)=
           (x-1)(y+1)$, que implica em $xy-x+y-1=xy+x-y-1$. Simplificando,
           deduz-se que $x=y$. Portanto, $f$ \'e injetiva. Basta provar agora
           que $f$ \'e sobrejetiva, ou seja, que para todo $y\in A$, existe $x$
           tal que $f(x)=y$. Assim, seja um $y\in A$, arbitr\'ario, e considere
           $x_0=(y+1)/(y-1)$. Tem-se: \[f(x_0)=\frac{x_0+1}{x_0-1}=
           \frac{(y+1)/(y-1)+1}{(y+1)/(y-1)-1}=\frac{(y+1+y-1)/(y-1)}
           {(y+1-y+1)/(y-1)}=\frac{2y}{2}=y\mbox{.}\] Logo, existe $x$ tal que
           $f(x)=y$, para qualquer $y$.
       \item $f\circ f=i_A$.

           Seja $x\in A$, arbitr\'ario. Ent\~ao: \[(f\circ f)(x)=f(f(x))=
           f(\frac{x+1}{x-1})=\frac{(x+1)/(x-1)+1}{(x+1)/(x-1)-1}=\frac{2x}{2}=
           x\mbox{.}\] Logo, $f\circ f=i_A$.

      \end{list}

   \item[4.]

      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item $f(2)=\{y\in\mbox{\bf R}\,|\, y^2<2\}=$ conjunto dos reais entre
             $-\sqrt{2}$ e $\sqrt{2}$.
       \item $f$ n\~ao \'e injetiva. Contra-exemplo: $f(0)=f(-1)=\phi$.
     
             $f$ n\~ao \'e sobrejetiva. Por exemplo, n\~ao existe $x\in\mbox{\bf
             R}$ tal que $f(x)=\{0\}$.
      \end{list}

  \end{enumerate}

 \item[Se\c c\~ao 6.1] \ 
 
  \begin{enumerate}

   \item[3.]

        $0^3=0=[0(0+1)/2]^2$. Suponha, como hip\'otese de indu\c c\~ao, que
        $0^3+1^3+2^3+\cdots+n^3=[n(n+1)/2]^2$, para um $n\in\mbox{\bf N}$
        arbitr\'ario. Tem-se:
        \begin{eqnarray*}
         0^3+1^3+2^3+\cdots+(n+1)^3 & = &  [n(n+1)/2]^2 + (n+1)^3\mbox{, pela
         hip\'otese de indu\c c\~ao} \\
         & = & (n+1)^2[n^2/4 + (n+1)] \\
         & = & (n+1)^2[(n^2+4n+4)/4] \\
         & = & (n+1)^2[(n+2)^2/4] \\
         & = & [(n+1)(n+2)/2]^2
        \end{eqnarray*}
        Logo, $0^3+1^3+2^3+\cdots+n^3=[n(n+1)/2]^2$ para todo $n\in\mbox{\bf N}$.

   \item[9.]

        $2^{10}=1024>1000=10^3$. Suponha, como hip\'otese de indu\c c\~ao, que
        $2^n>n^3$ para um $n\geq 10$ arbitr\'ario. Ent\~ao:
        \begin{eqnarray*}
         2^{n+1} & = &  2\times 2^n \\
         & > & 2\times n^3\mbox{, pela hip\'otese de indu\c c\~ao.}
        \end{eqnarray*}
        Basta, ent\~ao, mostrar que $2n^3\geq (n+1)^3$, ou seja, que $2n^3\geq
        n^3+3n^2+3n+1$, ou ainda, que $n^3\geq 3n^2+3n+1$ (para $n\geq 10$), ou
        ainda, dividindo ambos os lados por $n^2$, que $n\geq 3+(3/n)+(1/n^2)$
        (para $n\geq 10$), o que \'e \'obvio.

  \end{enumerate}

 \item[Se\c c\~ao 6.2] \ 
 
  \begin{enumerate}

   \item[4.]

        {\bf Obs:} $|A|$: n\'umero de elementos do conjunto $A$.
 
        Deve-se provar: $\forall n\in\mbox{\bf N}\forall A (|A| = n\rightarrow
        |{\cal P}(A)|=2^n)$.
      
        Caso base: $n=0$. Neste caso, o \'unico conjunto de tamanho 0 \'e $\phi$.
        E ${\cal P}(\phi)=\{\phi\}$ tem $1=2^0$ elemento.
      
        Passo de indu\c c\~ao: Suponha, como hip\'otese de indu\c c\~ao, que
        $\forall A (|A| = n\rightarrow |{\cal P}(A)|=2^n)$, para um certo $n\in
        \mbox{\bf N}$ arbitr\'ario. Seja, ent\~ao, um conjunto arbitr\'ario $B$ de
        $n+1$ elementos; deve-se provar que ${\cal P}(B)$ tem $2^{n+1}$ elementos.
        Seja $b$ um elemento arbitr\'ario de $B$, e $B'=B\backslash \{b\}$; pela
        hip\'otese de indu\c c\~ao, como $B'$ tem $n$ elementos, ${\cal P}(B')$
        tem $2^n$ elementos. Mas, \[{\cal P}(B)={\cal P}(B')\cup \{X\cup\{b\}\,|\,
        X\in {\cal P}(B')\}\mbox{.}\] Assim, ${\cal P}(B)$ tem $2^n+2^n=2^{n+1}$
        elementos.

   \item[5.]
 
        Caso base: $|{\cal P}_2(\phi)|=0=0(0-1)/2$.
      
        Passo de indu\c c\~ao: Suponha, como hip\'otese de indu\c c\~ao, que
        ${\cal P}_2(A)$ tem $n(n-1)/2$ elementos para conjuntos $A$ com tamanho
        $n\in\mbox{\bf N}$ arbitr\'ario. Seja um conjunto $B$ de tamanho $n+1$, e
        seja $B'=B\backslash\{b\}$, onde $b$ \'e um elemento arbitr\'ario de $B$.
        Como $B'$ tem $n$ elementos,
        pela hip\'otese de indu\c c\~ao, ${\cal P}_2(B')$ tem $n(n-1)/2$
        elementos. Mas, \[{\cal P}_2(B)={\cal P}_2(B')\cup \{\{b,x\}\,|\, x\in B'
        \}\mbox{.}\] Logo, ${\cal P}_2(B)$ tem $[n(n-1)/2]+n=(n(n-1)+2n)/2=
        (n-1+2)n/2=(n+1)n/2$ elementos.
      
   \item[6.]
 
        Caso base: Se $n=1$, o tri\^angulo \'e coberto com um \'unico ladrilho.
      
        Passo de indu\c c\~ao: Suponha que um tri\^angulo equil\'atero
        repartido em $4^n$ tri\^angulos, sendo um do canto removido, como
        definido no enunciado, pode ser coberto por ladrilhos da forma
        \begin{picture}(20,10)
         \put(0,0){\line(1,0){20}}
         \put(0,0){\line(1,2){5}}
         \put(10,0){\line(-1,2){5}}
         \put(10,0){\line(1,2){5}}
         \put(20,0){\line(-1,2){5}}
         \put(5,10){\line(1,0){10}}
        \end{picture}. Seja, ent\~ao, um tri\^angulo equil\'atero repartido em
        $4^{n+1}$ tri\^angulos, sendo um do canto removido, como definido no
        enunciado. Tal tri\^angulo \'e constitu\'{\i}do de $4$ ``subtri\^angulos''
        repartidos em $4^n$ tri\^angulos, como mostra a figura:
        \begin{center}
        \begin{picture}(80,80)
         \put(0,0){\line(1,0){80}}
         \put(0,0){\line(1,2){40}}
         \put(40,0){\line(-1,2){20}}
         \put(40,0){\line(1,2){20}}
         \put(80,0){\line(-1,2){40}}
         \put(20,40){\line(1,0){40}}
        \end{picture}
        \end{center}
        Um dos 3 tri\^angulos das pontas tem um canto removido e, pela hip\'otese de
        indu\c c\~ao, pode ser coberto. Mas, com um \'unico ladrilho da forma
        \begin{picture}(20,10)
         \put(0,0){\line(1,0){20}}
         \put(0,0){\line(1,2){5}}
         \put(10,0){\line(-1,2){5}}
         \put(10,0){\line(1,2){5}}
         \put(20,0){\line(-1,2){5}}
         \put(5,10){\line(1,0){10}}
        \end{picture}, pode-se cobrir um canto de cada um dos outros 3
        tri\^angulos, o central e os outros dois das pontas: basta fazer com que
        ele cubra a ponta do tri\^angulo interno oposta \`a ponta removida (e,
        obviamente, as pontas adjacentes dos outros dois tri\^angulos). Com isto,
        pela hip\'otese de indu\c c\~ao, pode-se tamb\'em cobrir os 3 tri\^angulos
        restantes.

    \item[7.]
  
        Caso base: Se $n=0$, tem-se 1 regi\~ao; e $(0^2+0+2)/2=1$.
      
        Passo de indu\c c\~ao: Suponha que $n$ cordas repartem o c\'{\i}rculo em
        $(n^2+n+2)/2$ regi\~oes. Sejam $n+1$ cordas com as caracter\'{\i}sticas
        dadas no enunciado. Se 1 corda for retirada, fica-se com $n$ cordas tais
        que, pela hip\'otese de indu\c c\~ao, repartem o c\'{\i}rculo em
        $(n^2+n+2)/2$ regi\~oes. A corda retirada tem interse\c c\~ao com cada uma
        das outras $n$ em exatamente um ponto; com isto, como pode ser facilmente
        observado, ao recolocar a corda $n+1$ regi\~oes s\~ao divididas em duas
        cada uma. Logo, com as $n+1$ cordas, tem-se $(n^2+n+2)/2+(n+1)$ regi\~oes,
        e $(n^2+n+2)/2+(n+1)=(n^2+n+2+2n+2)/2=[(n+1)^2+n+3]/2$.
     
  \end{enumerate}

\end{description}

\end{document}
