\documentstyle[12pt]{article}
 
\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 Primeira Lista de Exerc\'{\i}cios/Solu\c c\~ao de Exerc\'{\i}cios Selecionados}

\begin{description}
 \item[Se\c c\~ao 1.1] \ 

 
  \begin{enumerate}

   \item[4.] Identifique as premissas e conclus\~oes dos seguintes argumentos e analise suas formas
             l\'ogicas. Voc\^e acha que o racioc\'{\i}nio \'e v\'alido?
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Jane e Pete n\~ao ganhar\~ao, ambos, o trof\'eu de matem\'atica. Pete ganhar\'a
                    o trof\'eu de matem\'atica ou o de qu\'{\i}mica. Jane ganhar\'a o trof\'eu de
                    matem\'atica. Portanto, Pete ganhar\'a o trof\'eu de qu\'{\i}mica.

                    \underline{\em Solu\c c\~ao\/}:

                    Sejam:
                    \begin{itemize}
                     \item $J$: Jane ganhar\'a o trof\'eu de matem\'atica;
                     \item $M$: Pete ganhar\'a o trof\'eu de matem\'atica;
                     \item $Q$: Pete ganhar\'a o trof\'eu de qu\'{\i}mica.
                    \end{itemize}

                    Premissas: (1) $\neg (J\wedge M)$; (2) $M\vee Q$ (3) $J$. Conclus\~ao: $Q$.


                    Sim, o racioc\'{\i}nio \'e v\'alido, pois a conclus\~ao $Q$ \'e verdadeira sempre que
                    todas as premissas s\~ao verdadeiras: $J$ sendo verdadeira (premissa 3), para que a
                    premissa 1 seja verdadeira, $M$ deve ser falsa; neste caso, sendo a premissa 2
                    verdadeira, $Q$ deve ser verdadeira.
             \end{list}
  \end{enumerate}
 \item[Se\c c\~ao 1.2] \ 
 
  \begin{enumerate}
   \item[5.]  Use tabelas da verdade para determinar se os argumentos do e\-xer\-c\'{\i}\-cio 4 da Se\c c\~ao
              1.1 s\~ao v\'alidos.
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item  \underline{\em Solu\c c\~ao\/}:

                    O argumento \'e v\'alido, pois a conclus\~ao $Q$ \'e verdadeira sempre que
                    todas as premissas s\~ao verdadeiras: s\'o existe uma linha na tabela abaixo em que
                    todas as premissas s\~ao verdadeiras, a terceira linha, e nela $Q$ \'e verdadeira.

                    \begin{tabular}{ccccc}
                     $J$ & $M$ & $Q$ & $\neg (J\wedge M)$    & $M\vee Q$ \\ \hline
                      V  &  V  &  V  &         F             &    V      \\
                      V  &  V  &  F  &         F             &    V      \\
                      V  &  F  &  V  &         V             &    V      \\
                      V  &  F  &  F  &         V             &    F      \\
                      F  &  V  &  V  &         V             &    V      \\
                      F  &  V  &  F  &         V             &    V      \\
                      F  &  F  &  V  &         V             &    V      \\
                      F  &  F  &  F  &         V             &    F      \\
                    \end{tabular}
              \end{list}

   \item[10.] Use a primeira lei de DeMorgan e a lei da nega\c c\~ao dupla para derivar a segunda lei de
              DeMorgan.

              \underline{\em Solu\c c\~ao\/}:

               \begin{tabbing}
                $\neg P\wedge\neg Q$\=$\equiv\neg\neg(\neg P\wedge\neg Q)$ \ \ \=(nega\c c\~ao dupla) \\
                                    \>$\equiv\neg(\neg\neg P\vee\neg\neg Q)$ \>(primeira lei de DeMorgan) \\
                                    \>$\equiv\neg(P\vee Q)$ \>(nega\c c\~ao dupla)
               \end{tabbing}

   \item[14.] Suponha que a conclus\~ao de um argumento seja uma tautologia. O que voc\^e pode concluir
              sobre a validade de tal argumento? E se a conclus\~ao for uma contradi\c c\~ao? E se
              uma das premissas for uma tautologia? E se uma das premissas for uma contradi\c c\~ao?

              \underline{\em Solu\c c\~ao\/}:

              \begin{itemize}
               \item Se a conclus\~ao \'e uma tautologia, o argumento \'e v\'alido.
               \item Se a conclus\~ao \'e uma contradi\c c\~ao, o argumento \'e v\'alido apenas no caso
                     em que a conjun\c c\~ao das premissas \'e uma contradi\c c\~ao.
               \item Se uma das premissas for uma tautologia ela n\~ao influi na validade do argumento:
                     o argumento ser\'a v\'alido se a conclus\~ao for verdadeira sempre que as outras
                     premissas forem verdadeiras.
               \item Se uma das premissas for uma contradi\c c\~ao, o argumento \'e v\'alido.
              \end{itemize}
              
  \end{enumerate}

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

  \begin{enumerate}
   \item[1.] Analise as formas l\'ogicas das seguintes afirmativas:
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item 3 \'e um divisor comum de 6, 9 e 15.

                    \underline{\em Solu\c c\~ao\/}: $D(6,3)\wedge D(9,3)\wedge D(15,3)$, onde $D(x,y)$ significa
                    $x$ \'e divis\'{\i}vel por $y$.

              \item $x$ \'e divis\'{\i}vel por ambos, 2 e 3, mas n\~ao por 4.

                    \underline{\em Solu\c c\~ao\/}: $D(x,2)\wedge D(x,3)\wedge \neg D(x,4)$.

              \item $x$ e $y$ s\~ao n\'umeros naturais, e exatamente um deles \'e
                    primo.

                    \underline{\em Solu\c c\~ao\/}: $x\in\mbox{\bf N}\wedge y\in\mbox{\bf N}\wedge (P(x)\vee P(y))
                    \wedge\neg(P(x)\wedge P(y))$, onde $P(x)$ significa $x$ \'e primo.

              \item $x$ e $y$ s\~ao homens e, ou $x$ \'e maior que $y$ ou $y$
                    \'e maior que $x$.

                    \underline{\em Solu\c c\~ao\/}: $H(x)\wedge H(y)\wedge (M(x,y)\vee M(y,x))\wedge\neg
                    (M(x,y)\wedge M(y,x))$, onde $H(x)$ significa $x$ \'e homem, e $M(x,y)$ significa $x$ \'e
                    maior que $y$.

             \end{list}
   \item[3.] Simplifique as afirmativas que seguem. Quais vari\'aveis s\~ao livres
             e quais s\~ao ligadas? Se a afirmativa n\~ao tem vari\'aveis livres,
             diga se ela \'e verdadeira ou falsa.
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $-3\in\{x\in\mbox{\bf R}\,\,|\,\, 13-2x>1\}$.

                    \underline{\em Solu\c c\~ao\/}: 
                    A afirmativa diz que $13-2\times(-3)>1$, ou seja, $19>1$, o que \'e verdadeiro.
                    N\~ao h\'a vari\'aveis livres; $x$ \'e ligada.

              \item $5\not\in\{x\in\mbox{\bf R}\,\,|\,\, 13-2x>c\}$.

                    \underline{\em Solu\c c\~ao\/}: A afirmativa diz que $\neg(13-2\times 5>c)$, ou seja,
                    $3\leq c$. A vari\'avel $x$ \'e ligada e $c$ \'e livre.

              \item $w\in\{x\in\mbox{\bf R}\,\,|\,\, 13-2x>c\}$.

                    \underline{\em Solu\c c\~ao\/}: A afirmativa diz que $13-2w>c$. A vari\'avel $x$ \'e
                    ligada e as vari\'aveis $w$ e $c$ s\~ao livres.

              \item $4\in\{x\in\{y\,\,|\,\, \mbox{$y$ \'e primo}\}\,\,|\,\,
                     13-2x>1\}$. (Tal afirmativa pode ficar mais f\'acil de ler
                     se fizermos $P=\{y\,\,|\,\, \mbox{$y$ \'e primo}\}$; usando
                     tal nota\c c\~ao, podemos reescrever a afirmativa como
                     $4\in\{x\in P\,\,|\,\, 13-2x>1\}$.)

                    \underline{\em Solu\c c\~ao\/}: A afirmativa diz que 4 \'e um n\'umero primo e que, al\'em
                    disso, $13-2\times 4>1$. Apesar desta \'ultima ser verdadeira, 4 n\~ao \'e um n\'umero primo.
                    Logo, a afirmativa \'e falsa.
             \end{list}
  \end{enumerate}
  
 \item[Se\c c\~ao 1.4] \ 
 
  \begin{enumerate}
   \item[5.] Para cada um dos conjuntos a seguir, diga (usando s\'{\i}mbolos
             l\'ogicos) o que significa um objeto $x$ ser elemento do conjunto.
             Em seguida, determine quais destes conjuntos s\~ao iguais entre si
             determinando que afirmativas s\~ao e\-qui\-va\-len\-tes.
              \begin{list}{(\alph{conta})}{\usecounter{conta}}
               \item $(A\backslash B)\backslash C$.
               \item $A\backslash (B\backslash C)$.
               \item $(A\backslash B)\cup(A\cap C)$.
               \item $(A\backslash B)\cap(A\backslash C)$.
               \item $A\backslash (B\cup C)$.
              \end{list}

             \mbox{\em Solu\c c\~ao\/}:
              \begin{list}{(\alph{conta})}{\usecounter{conta}}
               \item $x\in(A\backslash B)\backslash C\equiv x\in A\backslash B\wedge x\not\in C\equiv
                      x\in A\wedge x\not\in B\wedge x\not\in C$.
               \item $x\in A\backslash (B\backslash C)\equiv x\in A\wedge x\not\in B\backslash C\equiv
                      x\in A\wedge \neg(x\in B\wedge x\not\in C)\equiv x\in A\wedge(x\not\in B\vee x\in C)$.
               \item $x\in (A\backslash B)\cup(A\cap C)\equiv x\in A\backslash B \vee x\in A\cap C
                      \equiv (x\in A\wedge x\not\in B) \vee (x\in A\wedge x\in C)
                      \equiv  x\in A\wedge(x\not\in B \vee x\in C)$.
               \item $x\in(A\backslash B)\cap(A\backslash C)\equiv x\in A\backslash B \wedge x\in A\backslash C
                      \equiv (x\in A\wedge x\not\in B) \wedge (x\in A\wedge x\not\in C)\equiv
                       x\in A\wedge x\not\in B\wedge x\not\in C$.
               \item $x\in A\backslash (B\cup C)\equiv x\in A\wedge x\not\in B\cup C\equiv
                      x\in A\wedge \neg(x\in B\vee x\in C) \equiv x\in A\wedge x\not\in B\wedge x\not\in C$.
              \end{list}

              Assim, os conjuntos referidos em (a), (d) e (e) s\~ao iguais, e os conjuntos referidos em (b) e (c)
              s\~ao iguais.
  \end{enumerate}

 \item[Se\c c\~ao 1.5] \ 
 
  \begin{enumerate}
   \item[2.] Analise a forma l\'ogica da seguinte afirmativa:
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Se est\'a chovendo, ent\~ao est\'a ventando e n\~ao est\'a
                    ensolarado.
             \end{list}

             \mbox{\em Solu\c c\~ao\/}: Sejam as vari\'aveis proposicionais:
             \begin{itemize}
              \item $C$: est\'a chovendo;
              \item $V$: est\'a ventando;
              \item $S$: est\'a ensolarado.
             \end{itemize}

             A forma l\'ogica da senten\c ca \'e: $C\rightarrow(V\wedge\neg S)$.

             Agora analise as seguintes afirmativas. E, para cada uma delas,
             determine se ela \'e equivalente a (a) ou \`a rec\'{\i}proca de (a).
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item[(b)] Est\'a ventando e n\~ao est\'a ensolarado somente se est\'a
                    chovendo.

                   \mbox{\em Solu\c c\~ao\/}: $(V\wedge\neg S)\rightarrow C$. \'E a rec\'{\i}proca de (a).

              \item[(c)] Estar chovendo \'e uma condi\c c\~ao suficiente para 
                       estar ventando e sem sol.

                   \mbox{\em Solu\c c\~ao\/}: $C\rightarrow(V\wedge\neg S)$. O mesmo que (a).

              \item[(d)] Estar chovendo \'e uma condi\c c\~ao necess\'aria para
                       estar ventando e sem sol.

                   \mbox{\em Solu\c c\~ao\/}: $(V\wedge\neg S)\rightarrow C$. \'E a rec\'{\i}proca de (a).

              \item[(e)] N\~ao est\'a chovendo, se est\'a ensolarado ou n\~ao est\'a
                       ventando.

             \mbox{\em Solu\c c\~ao\/}: $(S\vee\neg V)\rightarrow \neg C$. \'E equivalente a (a):
             \begin{itemize}
              \item $(S\vee\neg V)\rightarrow \neg C\equiv \neg(S\vee\neg V)\vee \neg C\equiv
                     (\neg S\wedge V) \vee \neg C\equiv C\rightarrow(V\wedge\neg S)$.
             \end{itemize}

              \item[(f)] Estar ventando \'e uma condi\c c\~ao necess\'aria para
                        estar chovendo, assim como a falta de sol.

             \mbox{\em Solu\c c\~ao\/}: $(C\rightarrow V)\wedge(C\rightarrow \neg S)$. \'E equivalente a (a):
             \begin{itemize}
              \item $(C\rightarrow V)\wedge(C\rightarrow \neg S)\equiv (\neg C\vee V)\wedge (\neg C\vee\neg S)
                    \equiv \neg C \vee (V\wedge\neg S)\equiv C\rightarrow(V\wedge\neg S)$.
             \end{itemize}


              \item[(g)] Ou est\'a ventando somente se est\'a chovendo, ou
                         n\~ao est\'a ensolarado somente se est\'a chovendo. 

             \mbox{\em Solu\c c\~ao\/}: $(V\rightarrow C)\vee(\neg S\rightarrow C)$. \'E equivalente \`a
                       rec\'{\i}proca de (a):
             \begin{itemize}
              \item $(V\rightarrow C)\vee(\neg S\rightarrow C)\equiv (\neg V\vee C)\vee(S\vee C)
                     \equiv C\vee (\neg V\vee S)\equiv C\vee \neg(V\wedge\neg S)\equiv (V\wedge\neg S)\rightarrow C$.
             \end{itemize}

             \end{list}
  \end{enumerate}


 \item[Se\c c\~ao 2.1] \ 
 
  \begin{enumerate}
   \item[2.] Analise as formas l\'ogicas das afirmativas abaixo.O universo de discurso \'e {\bf R}.
             Quais s\~ao as vari\'aveis livres em cada afirmativa?
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Todo n\'umero maior que $x$ \'e maior que $y$.

                    \mbox{\em Solu\c c\~ao\/}: $\forall z(z>x\rightarrow z>y)$. Vari\'aveis livres: $x$ e $y$.

              \item Para todo n\'umero $a$, a equa\c c\~ao $ax^2+4x-2=0$ tem pelo menos uma solu\c c\~ao
                    se, e somente se, $a\geq -2$.

                    \mbox{\em Solu\c c\~ao\/}: $\forall a(\exists x(ax^2+4x-2=0)\leftrightarrow a\geq -2)$. N\~ao
                    h\'a vari\'aveis livres.

              \item Todas as solu\c c\~oes da inequa\c c\~ao $x^3-3x<3$ s\~ao menores que 10.

                    \mbox{\em Solu\c c\~ao\/}: $\forall x (x^3-3x<3\rightarrow x<10)$. N\~ao
                    h\'a vari\'aveis livres.

              \item Se existe um n\'umero $x$ tal que $x^2+5x=w$ e existe um n\'umero $y$ tal que
                    $4-y^2=w$, ent\~ao $w$ est\'a entre -10 e 10.

                    \mbox{\em Solu\c c\~ao\/}: $[\exists x(x^2+5x=w)\wedge\exists y(4-y^2=w)]\rightarrow
                     (w>-10\wedge w<10)$. Apenas $w$ \'e vari\'avel livre.

             \end{list}
\end{enumerate}

 \item[Se\c c\~ao 2.2] \ 
 
  \begin{enumerate}
   \item[2.] Estas afirmativas s\~ao verdadeiras ou falsas? O universo de discurso \'e {\bf N}:
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $\forall x(x<7 \rightarrow \exists a\exists b\exists c(a^2+b^2+c^2=x))$.

                    \underline{\em Solu\c c\~ao\/}: \'E verdadeira. Para cada $x\in\{0,1,2,3,4,5,6\}$
                    (ou seja, para cada $x\in\mbox{\bf N}$ tal que $x< 7$), existem n\'umeros naturais
                    $a$, $b$ e $c$ tais que $a^2+b^2+c^2=x$; por exemplo:

                    \begin{tabular}{cccc}
                     $x$ & $a$ & $b$ & $c$ \\ \hline
                      0  &  0  &  0  &  0 \\
                      1  &  1  &  0  &  0 \\
                      2  &  1  &  1  &  0 \\
                      3  &  1  &  1  &  1 \\
                      4  &  2  &  0  &  0 \\
                      5  &  2  &  1  &  0 \\
                      6  &  2  &  1  &  1 
                    \end{tabular}

              \item $\exists ! x((x-4)^2=9)$.

                    \underline{\em Solu\c c\~ao\/}: \'E falsa. A equa\c c\~ao $(x-4)^2=9$ tem duas
                    solu\c c\~oes: $x=1$ e $x=7$.

              \item $\exists ! x((x-4)^2=25)$.

                    \underline{\em Solu\c c\~ao\/}: \'E verdadeira. A equa\c c\~ao $(x-4)^2=25$ tem apenas
                    uma solu\c c\~ao em {\bf N}: $x=9$; a outra solu\c c\~ao, $x=-1$ n\~ao pertence a {\bf N}.

              \item $\exists x\exists y((x-4)^2=25 \wedge (y-4)^2=25)$.

                    \underline{\em Solu\c c\~ao\/}: \'E verdadeira. Por exemplo, para $x=9$ e $y=9$ as
                    equa\c c\~oes $(x-4)^2=25$ e $(y-4)^2=25$ s\~ao satisfeitas.

             \end{list}
   \item[7.] Mostre que $(\forall x\in A P(x))\wedge(\forall x\in B P(x))$ \'e equivalente a
             $\forall x\in (A\cup B) P(x)$. (Dica: Comece exibindo os significados dos quantificadores
             ligados em termos de quantificadores n\~ao ligados.)

            \underline{\em Solu\c c\~ao\/}: 

               \begin{tabbing}
                $(\forall x\in A P(x))$\=$\wedge(\forall x\in B P(x))$ \\
                  \>$\equiv \forall x(x\in A\rightarrow P(x))\wedge\forall x(x\in B\rightarrow P(x))$ \= \\
                  \>$\equiv \forall x[(x\in A\rightarrow P(x))\wedge(x\in B\rightarrow P(x))]$ \>(distr. $\forall$
                              sobre $\wedge$) \\
                  \>$\equiv \forall x[(x\in A\vee x\in B)\rightarrow P(x)]$ \\
                  \>$\equiv \forall x\in (A\cup B) P(x)$ \\
               \end{tabbing}


   \item[9.] Suponha que $T(x,y)$ signifique ``$x$ \'e um professor de $y$''. O que significa cada uma das
             afirmativas abaixo? Em que circunst\^ancias cada uma \'e verdadeira? Quais s\~ao equivalentes
             a quais?
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $\exists! y T(x,y)$.

                    \underline{\em Solu\c c\~ao\/}: $x$ leciona para um \'unico aluno.
 
              \item $\exists x\exists! y T(x,y)$.

                    \underline{\em Solu\c c\~ao\/}: H\'a professor que leciona para um \'unico aluno.
 
              \item $\exists! x\exists y T(x,y)$.

                    \underline{\em Solu\c c\~ao\/}: H\'a um \'unico professor com alunos.
 
              \item $\exists y\exists! x T(x,y)$.

                    \underline{\em Solu\c c\~ao\/}: H\'a aluno com um \'unico professor.
 
              \item $\exists! x\exists! y T(x,y)$.

                    \underline{\em Solu\c c\~ao\/}: Apenas um professor leciona, e para um \'unico aluno.
 
              \item $\exists x\exists y[T(x,y)\wedge\neg\exists u\exists v(T(u,v)\wedge(u\not=x\vee v\not=y))]$.

                    \underline{\em Solu\c c\~ao\/}: Apenas um professor leciona, e para um \'unico aluno.
                    Equivalente a (e).
 
             \end{list}
  \end{enumerate}

 \item[Se\c c\~ao 2.3] \ 
 
  \begin{enumerate}
   \item[1.] Analise as formas l\'ogicas das afirmativas a seguir. Voc\^e pode usar os s\'{\i}mbolos $\in$,
             $\not\in$, $=$, $\not=$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\forall$ e $\exists$
             nas suas respostas, mas n\~ao $\subseteq$, $\not\subseteq$, ${\cal P}$, $\cap$, $\cup$, $\backslash$,
             $\{$, $\}$ ou $\neg$. (Assim, voc\^e deve aplicar as defini\c c\~oes de algumas nota\c c\~oes da
             teoria dos conjuntos, e deve usar equival\^encias para se livrar de ocorr\^encias de $\neg$.)
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item ${\cal F}\subseteq {\cal P}(A)$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    ${\cal F}\subseteq {\cal P}(A)$ \\
                       \>$\equiv \forall X[X\in{\cal F}\rightarrow X\in{\cal P}(A)]$ \\
                       \>$\equiv \forall X[X\in{\cal F}\rightarrow X\subseteq A]$ \\
                       \>$\equiv \forall X[X\in{\cal F}\rightarrow \forall x (x\in X\rightarrow x\in A)]$
                   \end{tabbing}
  
              \item $x\in \cup{\cal F}\backslash \cup{\cal G}$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $x\in \cup{\cal F}\backslash \cup{\cal G}$ \\
                       \>$\equiv x\in \cup{\cal F}\wedge x\not\in\cup{\cal G}$ \\
                       \>$\equiv \exists X\in{\cal F}(x\in X)\wedge \neg \exists Y\in{\cal G}(x\in Y)$ \\
                       \>$\equiv \exists X\in{\cal F}(x\in X)\wedge \forall Y\in{\cal G}(x\not\in Y)$
                   \end{tabbing}

              \item $A\subseteq \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $A\subseteq \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}$ \\
                       \>$\equiv \forall x[x\in A\rightarrow x\in\{2n+1\,\,|\,\, n\in \mbox{\bf N}\}]$ \\
                       \>$\equiv \forall x[x\in A\rightarrow x\in\{y\,\,|\,\, \exists n\in \mbox{\bf N}(y=2n+1)\}]$ \\
                       \>$\equiv \forall x[x\in A\rightarrow \exists n\in \mbox{\bf N}(x=2n+1)\}]$ 
                   \end{tabbing}

              \item $\{n^2+n+1\,\,|\,\, n\in \mbox{\bf N}\}\subseteq \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $\{n^2+n+1\,\,|\,\, n\in \mbox{\bf N}\}\subseteq \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}$ \\
                       \>$\equiv \forall x[x\in\{n^2+n+1\,\,|\,\, n\in \mbox{\bf N}\}\rightarrow x\in
                                      \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}]$ \\
                       \>$\equiv \forall x[x\in\{y\,\,|\,\, \exists n\in\mbox{\bf N}(y=n^2+n+1)\}\rightarrow x\in
                                      \{z\,\,|\,\, \exists n\in \mbox{\bf N}(z=2n+1)\}]$ \\
                       \>$\equiv \forall x[\exists n\in\mbox{\bf N}(x=n^2+n+1)\rightarrow
                                      \exists n\in \mbox{\bf N}(x=2n+1)]$
                   \end{tabbing}

              \item $\{x\in B\,\,|\,\, x\not\in C\}\in {\cal P}(A)$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $\{x\in B\,\,|\,\, x\not\in C\}\in {\cal P}(A)$ \\
                       \>$\equiv \{x\in B\,\,|\,\, x\not\in C\}\subseteq A$ \\
                       \>$\equiv \forall y[y\in\{x\in B\,\,|\,\, x\not\in C\}\rightarrow y\in A]$ \\
                       \>$\equiv \forall y[y\in\{x\,\,|\,\, x\in B\wedge x\not\in C\}\rightarrow y\in A]$ \\
                       \>$\equiv \forall y[(y\in B\wedge y\not\in C)\rightarrow y\in A]$
                   \end{tabbing}

              \item $x\in \cap_{i\in I}(A_i\cup B_i)$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $x\in \cap_{i\in I}(A_i\cup B_i)$ \\
                       \>$\equiv \forall i\in I(x\in A_i\cup B_i)$ \\
                       \>$\equiv \forall i\in I(x\in A_i\vee x\in B_i)$
                   \end{tabbing}

              \item $x\in (\cap_{i\in I}A_i)\cup(\cap_{i\in I}B_i)$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $x\in (\cap_{i\in I}A_i)\cup(\cap_{i\in I}B_i)$ \\
                       \>$\equiv (x\in\cap_{i\in I}A_i)\vee (x\in\cap_{i\in I}B_i)$ \\
                       \>$\equiv \forall i\in I(x\in A_i)\vee \forall i\in I(x\in B_i)$ 
                   \end{tabbing}

              \item ${\cal P}(\cup_{i\in I}A_i)\not\subseteq \cup_{i\in I}{\cal P}(A_i)$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    ${\cal P}(\cup_{i\in I}A_i)\not\subseteq \cup_{i\in I}{\cal P}(A_i)$ \\
                       \>$\equiv \neg\forall X[X\in{\cal P}(\cup_{i\in I}A_i)\rightarrow
                                                     X\in\cup_{i\in I}{\cal P}(A_i)]$ \\
                       \>$\equiv \exists X[X\in{\cal P}(\cup_{i\in I}A_i)\wedge
                                                     X\not\in\cup_{i\in I}{\cal P}(A_i)]$ \\
                       \>$\equiv \exists X[X\subseteq\cup_{i\in I}A_i\wedge
                                                     \neg\exists i\in I(X\in {\cal P}(A_i))]$ \\
                       \>$\equiv \exists X[\forall x\in X(x\in\cup_{i\in I}A_i)\wedge
                                                     \forall i\in I(X\not\subseteq A_i)]$ \\
                       \>$\equiv \exists X[\forall x\in X\exists i\in I(x\in A_i)\wedge
                                                     \forall i\in I\neg(\forall x\in X(x\in A_i))]$ \\
                       \>$\equiv \exists X[\forall x\in X\exists i\in I(x\in A_i)\wedge
                                                     \forall i\in I\exists x\in X(x\not\in A_i)]$
                   \end{tabbing}

             \end{list}

   \item[8.] Verifique as seguintes identidades explicitando (usando s\'{\i}mbolos l\'ogicos) o que
             significa para um objeto $x$ ser um elemento de cada conjunto e, em seguida, usando equival\^encias
             l\'ogicas.
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $\cup_{i\in I}(A_i\cup B_i)=(\cup_{i\in I}A_i)\cup(\cup_{i\in I}B_i)$.

                   \underline{\em Solu\c c\~ao\/}:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $x\in \cup_{i\in I}(A_i\cup B_i)$ \\
                       \>$\equiv \exists i\in I(x\in A_i\cup B_i)$ \\
                       \>$\equiv \exists i\in I(x\in A_i\vee x\in B_i)$
                   \end{tabbing}

                   Por outro lado:
                   \begin{tabbing}
                    xxxx\=xx \kill
                    $x\in (\cup_{i\in I}A_i)\cup(\cup_{i\in I}B_i)$ \\
                       \>$\equiv x\in \cup_{i\in I}A_i\vee x\in\cup_{i\in I}B_i$ \\
                       \>$\equiv \exists i\in I(x\in A_i)\vee \exists i\in I(x\in B_i)$ \\
                       \>$\equiv \exists i\in I(x\in A_i\vee x\in B_i)$ (pois $\exists$ distribui sobre $\vee$)\\
                   \end{tabbing}

                   Logo, $x\in \cup_{i\in I}(A_i\cup B_i)$ \'e equivalente a
                   $x\in (\cup_{i\in I}A_i)\cup(\cup_{i\in I}B_i)$, qualquer que seja $x$. Assim,
                    $\cup_{i\in I}(A_i\cup B_i)=(\cup_{i\in I}A_i)\cup(\cup_{i\in I}B_i)$.

             \end{list}
  \end{enumerate}

\end{description}

\end{document}