\documentstyle[12pt]{article}
 
\newcounter{conta}

\begin{document}

\noindent {Bacharelado em Ci\^encia da Computa\c c\~ao} \hfill DCC/ICEx/UFMG \\
\noindent {\em Matem\'atica Discreta} \hfill $2^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova/Solu\c c\~ao do professor} \hfill 26/09/2000

\begin{enumerate}
 \item {\footnotesize Seja o seguinte argumento:
       \begin{quote} \em
        Se $2+2=4$, ent\~ao a lua \'e feita de queijo. A lua n\~ao \'e feita de queijo.
        Portanto, $2+2\not=4$.
       \end{quote}
       Explicite sua forma l\'ogica e determine se ele \'e v\'alido.}

       Sejam $P$ a afirmativa ``$2+2=4$'' e $Q$ a afirmativa ``a lua \'e feita de queijo''.
       A forma l\'ogica do argumento \'e:
       \begin{center}
       \begin{tabular}{l}
        $P\rightarrow Q$ \\
        $\neg Q$ \\ \hline
        $\neg P$
       \end{tabular}
       \end{center}
       A tabela a seguir mostra que o argumento \'e v\'alido: $\neg P$ \'e verdadeira sempre
       que $P\rightarrow Q$ e $\neg Q$ s\~ap verdadeiras (verifique {\em \'ultima linha\/} da
       tabela).
       \begin{center}
       \begin{tabular}{|cc|cc|c|} \hline
        $P$ & $Q$ & $P\rightarrow Q$ & $\neg Q$ & $\neg P$ \\ \hline
         V  &  V  &       V          &    F     &    F     \\
         V  &  F  &       F          &    V     &    F     \\
         F  &  V  &       V          &    F     &    V     \\
         F  &  F  &    {\bf  V}      & {\bf  V} & {\bf  V} \\ \hline
       \end{tabular}
       \end{center}

 \item {\footnotesize Verifique quais dentre as afirmativas seguintes s\~ao equivalentes \`a
       afirmativa $(P\wedge Q)\rightarrow (R\vee S)$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(P\wedge \neg R)\rightarrow (\neg Q\vee S)$
        \item $(\neg R\wedge\neg S)\rightarrow (\neg P\wedge\neg Q)$
       \end{list}}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(P\wedge \neg R)\rightarrow (\neg Q\vee S)\equiv(P\wedge Q)\rightarrow (R\vee S)$, pois:
              \begin{tabbing}
               $(P\wedge \neg R)\rightarrow (\neg Q\vee S)$\=$\equiv\neg (P\wedge \neg R)\vee
                  (\neg Q\vee S)$\= \ \ \ \=pela \kill
               $(P\wedge \neg R)\rightarrow (\neg Q\vee S)$\>$\equiv\neg (P\wedge \neg R)\vee
                  (\neg Q\vee S)$ \>pois $\alpha\rightarrow\beta\equiv\neg\alpha\vee\beta$ \\
                      \>$\equiv\neg P\vee \neg\neg R\vee \neg Q\vee S$ \>pela lei de De Morgan \\
                      \>$\equiv \neg P\vee R\vee \neg Q\vee S$ \\
                      \>$\equiv\neg(\neg P\vee \neg Q)\rightarrow (R\vee S)$ 
                                 \>pois $\alpha\rightarrow\beta\equiv\neg\alpha\vee\beta$ \\
                      \>$\equiv (P\wedge Q)\rightarrow (R\vee S)$ 
                                 \> pela lei de De Morgan \\
              \end{tabbing}
        \item $(\neg R\wedge\neg S)\rightarrow (\neg P\wedge\neg Q)\not\equiv(P\wedge Q)\rightarrow (R\vee S)$,
              pois:
              \begin{tabbing}
               $(\neg R\wedge\neg S)\rightarrow (\neg P\wedge\neg Q)$\=$\equiv\neg(\neg R\wedge\neg S)\vee
                 (\neg P\wedge\neg Q)$ \=pela \kill
               $(\neg R\wedge\neg S)\rightarrow (\neg P\wedge\neg Q)$\>$\equiv\neg(\neg R\wedge\neg S)\vee
                 (\neg P\wedge\neg Q)$ \>pois $\alpha\rightarrow\beta\equiv\neg\alpha\vee\beta$ \\
                    \>$\equiv R\vee S\vee\neg P\wedge\neg Q$ \>pela lei de De Morgan \\
                    \>$\equiv \neg(\neg P\wedge \neg Q)\rightarrow (R\vee S)$ 
                               \>pois $\alpha\rightarrow\beta\equiv\neg\alpha\vee\beta$ \\
                    \>$\equiv (P\vee Q)\rightarrow (R\vee S)$ \>pela lei de De Morgan \\
              \end{tabbing}
              Observe, ent\~ao, que se $R$ e $S$ s\~ao falsos e um dos dois, $P$ ou $Q$, \'e
              verdadeiro e o outro \'e falso,
              $(P\wedge Q)\rightarrow (R\vee S)$ \'e falso, enquanto que
              $(\neg R\wedge\neg S)\rightarrow (\neg P\wedge\neg Q)$ (que equivale a 
              $(P\vee Q)\rightarrow (R\vee S)$) \'e verdeiro para esta mesma situa\c c\~ao.
       \end{list}

 \item {\footnotesize Verifique, para cada afirmativa abaixo, se ela \'e tautologia,
       contradi\c c\~ao ou conting\^encia.\footnote{
       O que n\~ao \'e tautologia nem contradi\c c\~ao \'e conting\^encia.}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se a vida \'e curta, ent\~ao se Deus existe, a vida \'e curta.
        \item Se Deus existe ou n\~ao existe, ent\~ao a Terra \'e azul.
        \item Se Deus existe e n\~ao existe, ent\~ao a Terra \'e azul.
       \end{list}}


       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se a vida \'e curta, ent\~ao se Deus existe, a vida \'e curta.

              Sejam $D$ a afirmativa ``Deus existe'' e $C$ a afirmativa ``a vida \'e curta''.
              A forma l\'ogica da afirmativa \'e: $C\rightarrow (D\rightarrow C)$. Ela \'e
              uma {\em tautologia\/}, pois: para ela ser falsa, $C$ deve ser verdadeira e
              $D\rightarrow C$ falsa; mas para $D\rightarrow C$ ser falsa, $D$ deve ser verdadeira
              e $C$ deve ser falsa. Como ficou dito que $C$ deve ser verdadeira, contradi\c c\~ao!
              Logo, a afirmativa em quest\~ao n\~ao pode ser falsa.

        \item Se Deus existe ou n\~ao existe, ent\~ao a Terra \'e azul.

              Sejam $D$ a afirmativa ``Deus existe'' e $A$ a afirmativa ``a terra \'e azul''.
              A forma l\'ogica da afirmativa \'e: $(D \vee \neg D)\rightarrow A$. Ela \'e
              uma {\em conting\^encia\/}, pois: como $D\vee \neg D$ \'e uma tautologia,
              $(D \vee \neg D)\rightarrow A$ \'e verdadeira se $A$ \'e verdadeira, e
              \'e falsa se $A$ \'e falsa.

        \item Se Deus existe e n\~ao existe, ent\~ao a Terra \'e azul.

              Sejam $D$ a afirmativa ``Deus existe'' e $A$ a afirmativa ``a terra \'e azul''.
              A forma l\'ogica da afirmativa \'e: $(D \wedge \neg D)\rightarrow A$. Ela \'e
              uma {\em tautologia\/}, pois: como $D\vee \neg D$ \'e uma contradi\c c\~ao,
              $(D \wedge \neg D)\rightarrow A$ \'e verdadeira, seja $A$ verdadeira ou falsa.

       \end{list}


 \item {\footnotesize Simplifique as seguintes afirmativas. Quais vari\'aveis s\~ao livres e quais s\~ao
       ligadas? Se a afirmativa n\~ao tem vari\'aveis ligadas, diga se ela \'e verdadeira ou
       falsa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $0\in\{x\in\mbox{\bf Z}\,\,|\,\, 2x-1\geq 0\}$
        \item $0\in\{x\in\mbox{\bf Z}\,\,|\,\, 2x>y\}$
        \item $0\not\in\{y\,\,|\,\,6\not\in\{x\,\,|\,\,\mbox{$x$ \'e
               divis\'{\i}vel por $y$}\}\}$
       \end{list}}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $0\in\{x\in\mbox{\bf Z}\,\,|\,\, 2x-1\geq 0\}$ \'e equivalente a $-1\geq 0$, que \'e
              falsa. A vari\'avel $x$ \'e ligada.

        \item $0\in\{x\in\mbox{\bf Z}\,\,|\,\, 2x>y\}$ \'e equivalente a $y<0$. A vari\'avel $x$ \'e ligada
              e vari\'avel $y$ \'e livre.

        \item $0\not\in\{y\,\,|\,\,6\not\in\{x\,\,|\,\,\mbox{$x$ \'e
               divis\'{\i}vel por $y$}\}\}$ equivale a $0\not\in\{y\,\,|\,\, 6$ n\~ao  \'e
               divis\'{\i}vel por $y\}$ que, por sua vez, equivale a `` 6 \'e
               divis\'{\i}vel por 0'', que \'e falsa. As vari\'aveis $x$ e $y$ s\~ao ligadas.
       \end{list}
       
 \item {\footnotesize Prove que $(A\backslash B)\backslash C=A\backslash (B\cup C)$, mostrando a
       equival\^encia das afirmativas $x\in (A\backslash B)\backslash C$ e $x\in A\backslash(B\cup C)$.}

       A equival\^encia segue de:
       \begin{tabbing}
               $x\in (A\backslash B)\backslash C$\=$\equiv  x\in A\backslash B \wedge x\not\in C$
                        \ \ \ \ \ \ \ \ \ \ \ \ \ \=pela def de ``$\backslash$'' \\
                 \>$\equiv x\in A\wedge x\not\in B \wedge x\not\in C$ \>pela def de ``$\backslash$'' \\
                 \>$\equiv x\in A \wedge \neg( x\in B \vee x\in C) $ \> por De Morgan\\
                 \>$\equiv x\in A \wedge x\not\in B \cup C$ \> pela def de ``$\cup$''\\
                 \>$\equiv x\in A \backslash(B \cup C) $ \> elar def de ``$\backslash$''.
       \end{tabbing}

 \item{\footnotesize  Explicite as formas l\'ogicas das seguintes afirmativas. 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Ningu\'em gosta daqueles que s\~ao antip\'aticos.
        \item Todos gostam de quem gosta de Maria.
        \item $A\subseteq B$ \'e condi\c c\~ao suficiente para que $A$ e $C\backslash B$
              sejam disjuntos.
       \end{list}}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\forall x[\mbox{\em antip\'atico\/}(x)\rightarrow \neg \exists y\mbox{\em gosta\/}(y,x)]$
        \item $\forall x[\mbox{\em gosta\/}(x,\mbox{\em Maria\/})\rightarrow \forall y\mbox{\em gosta\/}(y,x)]$
        \item \begin{tabbing}
               $A\subseteq B\rightarrow A\cap C\backslash B=\emptyset$\=$\equiv  \forall x[x\in A\rightarrow
                x\in B]\rightarrow\neg\exists x(x\in A\wedge x\in C\backslash B)$' \\
              \>$\equiv  \forall x[x\in A\rightarrow x\in B]\rightarrow\neg \exists x(x\in A\wedge x\in C\wedge x\not\in B)$ \\
              \>$\equiv  \forall x[x\in A\rightarrow x\in B]\rightarrow\forall x(x\not\in A\vee x\not\in C\vee x\in B)$ \\
              \>$\equiv  \forall x[x\in A\rightarrow x\in B]\rightarrow\forall x[(x\in A\wedge x\in C)\rightarrow x\in B]$ \\
              \end{tabbing}
       \end{list}


 \item {\footnotesize Mostre que $\neg \exists x\in A P(x)$ e $\forall x\in A \neg P(x)$ s\~ao equivalentes.
       ({\em Pista\/}: observe os lembretes 1 e 2.)}




 \item Analise as formas l\'ogicas das afirmativas a seguir. Para isto, desvencilhe-se das opera\c c\~oes sobre
       conjuntos (menos ``$\in$''), re-expressando as afirmativas utilizando conectivos l\'ogicos.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $x\in \cup{\cal F}\backslash\cap{\cal G}$
        \item $C\in{\cal P}(A)\cap{\cal P}(B)$
        \item $x\in (\cup_{i\in I}A_i)\cap(\cup_{i\in I}B_i)$
       \end{list}


\end{enumerate}


\vspace*{.5cm}
\noindent {\bf Lembretes:}
\begin{description}
 \item[1:] $\forall x\in A P(x)$ equivale a $\forall x (x\in A\rightarrow P(x))$.
 \item[2:] $\exists x\in A P(x)$ equivale a $\exists x (x\in A\wedge P(x))$.
 \item[3:] $\cap{\cal F}$ \'e a interse\c c\~ao dos conjuntos da fam\'{\i}lia
           ${\cal F}$: $\{x\,\,|\,\, \forall A\in{\cal F}(x\in A)\}$.
 \item[4:] $\cup{\cal F}$ \'e a uni\~ao dos conjuntos da fam\'{\i}lia
           ${\cal F}$: $\{x\,\,|\,\, \exists A\in{\cal F}(x\in A)\}$.
 \item[5:] ${\cal P}(A)$ \'e o {\em conjunto pot\^encia\/} de $A$.
 \item[6:] $\cup_{i\in I}A_i=\cup\{A_i\,\,|\,\,i\in I\}$
\end{description}

\end{document}