\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}

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


\noindent {\bf Data de entrega:} 14/09/00.

\vspace*{.5cm}
Resolva os exerc\'{\i}cios abaixo, extra\'{\i}dos do livro texto.

\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.
              \item O prato principal ser\'a carne de boi ou peixe. A salada ser\'a de ervilhas ou de
                    milho. N\~ao teremos ambos peixe como prato principal e salada de milho. Portanto,
                    n\~ao teremos ambos carne de boi como prato principal e salada de ervilhas.
              \item John ou Bill est\'a dizendo a verdade. Sam ou Bill est\'a mentindo. Portanto,
                    John est\'a dizendo a verdade ou Sam est\'a mentindo.
              \item Ou as vendas ir\~ao aumentar e o chefe vai ficar satisfeito, ou as despesas ir\~ao
                    aumentar e o chefe n\~ao vai ficar satisfeito. Portanto, as vendas e as despesas
                    n\~ao v\~ao ambos aumentar.
             \end{list}
  \end{enumerate}
 \item[Se\c c\~ao 1.2] \ 
 
  \begin{enumerate}
   \item[3.]  Encontre uma f\'ormula usando apenas os conectivos $\wedge$ e $\neg$ que seja
              equivalente a $P\vee Q$. Justifique sua resposta com uma tabela da verdade.
   \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.
   \item[7.]  Use tabelas da verdade para determinar quais das seguintes afirmativas s\~ao
              tautologias, quais s\~ao contradi\c c\~oes e quais n\~ao s\~ao nem uma coisa nem outra:
              \begin{list}{(\alph{conta})}{\usecounter{conta}}
               \item $(P\vee Q)\wedge(\neg P\vee\neg Q)$
               \item $(P\vee Q)\wedge(\neg P\wedge\neg Q)$
               \item $(P\vee Q)\vee(\neg P\vee\neg Q)$
               \item $[P\vee(Q\vee\neg R)]\vee(\neg P\vee R)$
              \end{list}
   \item[9.] Use as leis enunciadas no texto para encontrar f\'ormulas mais simples equivalentes \`as
             seguintes f\'ormulas. (Veja Exemplos 1.2.5 e 1.2.7.)
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $\neg(\neg P\wedge\neg Q)$
              \item $\neg(\neg P\vee Q)\vee(P\wedge \neg R)$
              \item $(P\wedge Q)\vee(P\wedge\neg Q)$
              \item $(P\wedge R)\vee[\neg R\wedge(P\vee Q)]$
             \end{list}
   \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?
  \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.
              \item $x$ \'e divis\'{\i}vel por ambos, 2 e 3, mas n\~ao por 4.
              \item $x$ e $y$ s\~ao n\'umeros naturais, e exatamente um deles \'e
                    primo.
              \item $x$ e $y$ s\~ao homens e, ou $x$ \'e maior que $y$ ou $y$
                    \'e maior que $x$.
             \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\}$.
              \item $5\not\in\{x\in\mbox{\bf R}\,\,|\,\, 13-2x>c\}$.
              \item $w\in\{x\in\mbox{\bf R}\,\,|\,\, 13-2x>c\}$.
              \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\}$.)
             \end{list}
  \end{enumerate}
  
 \item[Se\c c\~ao 1.4] \ 
 
  \begin{enumerate}
   \item[4.] Verifique as identidades seguintes dizendo o que significa um
             objeto $x$ pertencer a cada conjunto (usando s\'{\i}mbolos
             l\'ogicos) e u\-san\-do equival\^encias l\'ogicas.
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $A\backslash (A\cap B)=A\backslash B$.
              \item $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$.
              \item $(A\cup B)\backslash C=(A\backslash C)\cup(B\backslash C)$.
             \end{list}
   \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 equivalentes.
              \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}
   \item[8.] \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Fa\c ca diagramas de Venn para os conjuntos
                    $(A\cup B)\backslash C$ e $A\cup(B\backslash C)$. \'E
                    poss\'{\i}vel, a partir dos diagramas, concluir se um destes
                    conjuntos \'e necessariamente um subconjunto do outro?
              \item D\^e um exemplo de conjuntos $A$, $B$ e $C$ para os quais
                    $(A\cup B)\backslash C\not= A\cup(B\backslash C)$.
             \end{list}
  \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}
             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.
              \item[(c)] Estar chovendo \'e uma condi\c c\~ao suficiente para 
                       estar ventando e sem sol.
              \item[(d)] Estar chovendo \'e uma condi\c c\~ao necess\'aria para
                       estar ventando e sem sol.
              \item[(e)] N\~ao est\'a chovendo, se est\'a ensolarado ou n\~ao est\'a
                       ventando.
              \item[(f)] Estar ventando \'e uma condi\c c\~ao necess\'aria para
                        estar chovendo, assim como a falta de sol.
              \item[(g)] Ou est\'a ventando somente se est\'a chovendo, ou
                         n\~ao est\'a ensolarado somente se est\'a chovendo. 
             \end{list}
   \item[4.] \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Mostre que $P\leftrightarrow Q$ \'e equivalente a
                        $(P\wedge Q)\vee(\neg P\wedge\neg Q)$.
              \item Mostre que $(P\rightarrow R)\wedge(Q\rightarrow R)$ \'e
                    equivalente a $(P\vee Q)\rightarrow R$.
             \end{list}
   \item[6.] Quais das seguintes f\'ormulas s\~ao equivalentes?
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $P\rightarrow(Q\rightarrow R)$.
              \item $Q\rightarrow(P\rightarrow R)$.
              \item $(P\rightarrow Q)\wedge(P\rightarrow R)$.
              \item $(P\wedge Q)\rightarrow R$.
              \item $P\rightarrow(Q\wedge R)$.
             \end{list}
  \end{enumerate}


 \item[Se\c c\~ao 2.1] \ 
 
  \begin{enumerate}
   \item[1.] Analise as formas l\'ogicas das seguintes afirmativas:
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Qualquer um que tenha perdoado pelo menos uma pessoa \'e um santo.
              \item Ningu\'em da turma de C\'alculo \'e mais esperto que todos da turma de
                    Matem\'atica Discreta.
              \item Todo aquele que tenha comprado um Rolls Royce a dinheiro tem um tio rico.
              \item Se algu\'em no dormit\'orio tiver sarampo,  ent\~ao todo aquele que tiver um amigo no
                    dormit\'orio ter\'a de ficar em quarentena.
              \item Todo mundo gosta de Mary, exceto ela mesma.
              \item Jane viu um urso, e Roger viu um tamb\'em.
              \item Jane viu um urso, e Roger o viu tamb\'em.
              \item Se algu\'em pode faz\^e-lo, Jones pode.
              \item Se Jones pode faz\^e-lo, qualquer um pode.
             \end{list}
   \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$.
              \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$.
              \item Todas as solu\c c\~oes da inequa\c c\~ao $x^3-3x<3$ s\~ao menores que 10.
              \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.
             \end{list}
   \item[3.] Traduza as afirmativas a seguir para portugu\^es coloquial.
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $\forall x[(H(x)\wedge \forall y\neg M(x,y))\rightarrow U(x)]$, onde $H(x)$
                    significa {\em $x$ \'e um homem\/}, $M(x,y)$ significa {\em $x$ \'e casado com $y$\/},
                    e $U(x)$ significa {\em $x$ \'e infeliz\/}. 
              \item $\exists z(P(z,x)\wedge S(z,y)\wedge W(y))$, onde $P(z,x)$
                    significa {\em $z$ \'e um dos pais de $x$\/}, $S(z,y)$ significa {\em $z$ e $y$
                    s\~ao irm\~aos\/}, e $W(y)$ significa {\em $y$ \'e uma mulher\/}. 
             \end{list}
   \item[4.] Dentre as afirmativas abaixo, quais s\~ao verdadeiras e quais s\~ao falsas? O universo de
             discurso \'e {\bf N}.
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item $\forall x\exists y (2x-y=0)$.
              \item $\exists y\forall x (2x-y=0)$.
              \item $\forall x\exists y (x-2y=0)$.
              \item $\forall x(x<10\rightarrow \forall y(y<x\rightarrow y<9))$.
              \item $\exists y\exists z (y+z=100)$.
              \item $\forall x\exists y(y>x\wedge \exists z(y+z=100))$.
             \end{list}
\end{enumerate}

 \item[Se\c c\~ao 2.2] \ 
 
  \begin{enumerate}
   \item[1.] Negue estas afirmativas e reexpresse o resultado como afirmativas positivas equivalentes.
             (Veja Exemplo 2.2.1.)
             \begin{list}{(\alph{conta})}{\usecounter{conta}}
              \item Todo aquele que est\'a cursando matem\'atica tem um amigo que necessita de ajuda com
                    seu ``para casa''.
              \item Existe algu\'em na turma de calouros que n\~ao tem um colega de quarto.
              \item Todo mundo tem um colega de quarto que detesta todo mundo.
              \item $\forall a\in A\exists b\in B(a\in C\leftrightarrow b\in C)$.
              \item $A\cup B\subseteq C\backslash D$.
              \item $\forall y>0\exists x(ax^2+bx+c=y)$.
             \end{list}
   \item[5.] Mostre que o quantificador existencial distribui sobre disjun\c c\~ao. Em outras palavras,
             mostre que $\exists x(P(x)\vee Q(x))$ \'e equivalente a $\exists xP(x)\vee \exists xQ(x)$.
             (Sugest\~ao: Use o fato de que o quantificador universal distribui sobre conjun\c c\~ao.)
   \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)$. (Sugest\~ao: Comece exibindo os significados dos quantificadores
             ligados em termos de quantificadores n\~ao ligados.)
   \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)$.
              \item $\exists x\exists! y T(x,y)$.
              \item $\exists! x\exists y T(x,y)$.
              \item $\exists y\exists! x T(x,y)$.
              \item $\exists! x\exists! y T(x,y)$.
              \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))]$.
             \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)$.
              \item $x\in \cup{\cal F}\backslash \cup{\cal G}$.
              \item $A\subseteq \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}$.
              \item $\{n^2+n+1\,\,|\,\, n\in \mbox{\bf N}\}\subseteq \{2n+1\,\,|\,\, n\in \mbox{\bf N}\}$.
              \item $\{x\in B\,\,|\,\, x\not\in C\}\in {\cal P}(A)$.
              \item $x\in \cap_{i\in I}(A_i\cup B_i)$.
              \item $x\in (\cap_{i\in I}A_i)\cup(\cap_{i\in I}B_i)$.
              \item ${\cal P}(\cup_{i\in I}A_i)\not\subseteq \cup_{i\in I}{\cal P}(A_i)$.
             \end{list}
   \item[6.] Mostre que para quaisquer conjuntos $A$ e $B$
             ${\cal P}(A\cap B)={\cal P}(A)\cap{\cal P}(B)$, mostrando que as afirmativas $x\in {\cal P}(A\cap B)$
             e $x\in {\cal P}(A)\cap{\cal P}(B)$ s\~ao equivalentes. (Veja Exemplo 2.3.3.)
   \item[7.] D\^e exemplos de conjuntos $A$ e $B$ para os quais ${\cal P}(A\cup B)\not={\cal P}(A)\cup{\cal P}(B)$.
  \end{enumerate}

\end{description}

\end{document}