\documentclass[12pt,a4paper,notitlepage]{report}
 
\newcounter{conta}

\begin{document} \footnotesize

\noindent Gradua\c c\~ao em Matem\'atica Computacional \hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2003 \\
Professor: Newton Jos\'{e} Vieira \\
{\bf Primeira Prova/Solu\c c\~ao do professor} \hfill 26/05/2003

\begin{description}
 \item[Dura\c c\~ao:] 1 hora e 30 minutos.
 \item[Valores das quest\~oes:] 4 pontos cada uma.
 \item[Importante:] Toda resposta deve ser justificada.
\end{description}

\begin{enumerate}
 \item Determine que afirmativas s\~ao equivalentes umas \`as outras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(P\rightarrow Q)\wedge(P\rightarrow R)$.
        \item $(P\vee Q)\rightarrow  R$.
        \item $P\rightarrow (Q\wedge R)$.
        \item $P\rightarrow (Q\vee R)$.
        \item $(P\rightarrow R)\vee(\neg R\rightarrow \neg Q)$.
        \item $(P\wedge \neg Q)\rightarrow  R$.
      \end{list}

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

      (a) e (c) s\~ao equivalentes:
      \begin{itemize}
       \item $(P\rightarrow Q)\wedge(P\rightarrow R)\equiv(\neg P\vee Q)\wedge
              (\neg P\vee R)\equiv\neg P\vee(Q\wedge R)\equiv
              P\rightarrow (Q\wedge R)$.
      \end{itemize}
      (d) e (f) s\~ao equivalentes:
      \begin{itemize}
       \item $P\rightarrow (Q\vee R)\equiv\neg P\vee Q\vee R\equiv
              \neg (P\wedge \neg Q)\vee R\equiv (P\wedge \neg Q)
              \rightarrow R$.
      \end{itemize}
      (b) e (e) n\~ao s\~ao equivalentes entre si nem \`as outras. Observe que
      (e) \'e $(P\rightarrow R)\vee(\neg R\rightarrow \neg Q)\equiv
      (\neg P\vee R)\vee(R\vee\neg Q)\equiv\neg P\vee\neg Q\vee R\equiv
      \neg(P\wedge Q)\vee R\equiv (P\wedge Q)\rightarrow  R$. Assim, tem-se:
      \begin{center}
       \begin{tabular}{|l|l|} \hline
        F\'ormula & Equivalente a \\ \hline
        (a), (c) & $P\rightarrow (Q\wedge R)$ \\
        (b)      & $(P\vee Q)\rightarrow  R$ \\
        (d), (f) & $P\rightarrow (Q\vee R)$ \\
        (e)      & $(P\wedge Q)\rightarrow  R$ \\ \hline
       \end{tabular}
      \end{center}
 \item Encontre uma f\'ormula equivalente a:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P\vee Q$, usando apenas $\wedge$ e $\neg$.
        \item $P\wedge Q$, usando apenas $\vee$ e $\neg$.
        \item $P\rightarrow Q$, usando apenas $\wedge$ e $\neg$.
        \item $P\rightarrow Q$, usando apenas $\vee$ e $\neg$.
       \end{list}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P\vee Q \equiv \neg(\neg P\wedge\neg Q)$.
        \item $P\wedge Q \equiv \neg(\neg P\vee\neg Q)$.
        \item $P\rightarrow Q \equiv \neg(P\wedge\neg Q)$.
        \item $P\rightarrow Q \equiv \neg P\vee Q$.
       \end{list}

 \item Sejam os conjuntos $X=A\cup(B\backslash C)$ e $Y=(A\backslash B)\cup(B\backslash C)$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Descubra, usando diagramas de Venn, que rela\c c\~ao existe entre $X$ e $Y$
              (isto \'e, se $X\subseteq Y$, $Y\subseteq X$, $X=Y$ ou nada disto).
        \item Determine as formas l\'ogicas relativas a $x\in X$ e $x\in Y$. Se
              $X\subseteq Y$, $Y\subseteq X$ ou $X=Y$, justifique atrav\'es de tais formas
              l\'ogicas.
       \end{list}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y\subseteq X$.
        \item \begin{tabbing}
               $x\in X$\=$\equiv x\in A\cup(B\backslash C)$ \\
                       \>$\equiv x\in A\vee x\in B\backslash C$ \\
                       \>$\equiv x\in A\vee (x\in B\wedge x\not\in C)$ \\
              \end{tabbing}

              \begin{tabbing}
               $x\in Y$\=$\equiv x\in (A\backslash B)\cup(B\backslash C)$ \\
                       \>$\equiv x\in A\backslash B \vee x\in B\backslash C$ \\
                       \>$\equiv (x\in A\wedge x\not\in B)\vee (x\in B\wedge x\not\in C)$ \\
              \end{tabbing}

              Se $x\in Y$, ent\~ao $x\in A\wedge x\not\in B$ ou $x\in B\wedge x\not\in C$. No
              primeiro caso, segue-se que $x\in A$ e, portanto, $x\in X$; no segundo,
              segue-se imediatamente que $x\in X$. Assim, se $x\in Y$ ent\~ao $x\in X$.
              Portanto, $Y\subseteq X$.
       \end{list}

 \item 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 $x$ \'e tal que $x-2y=0$ para algum n\'umero $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}

       \mbox{\em Solu\c c\~ao:}

        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\forall x\exists y(x-2y=0)$. N\~ao h\'a vari\'aveis livres.

         \item $\forall a(\exists x(ax^2+4x-2=0)\leftrightarrow a\geq -2)$. N\~ao
                    h\'a vari\'aveis livres.

         \item $\forall x (x^3-3x<3\rightarrow x<10)$. N\~ao h\'a vari\'aveis livres.

         \item $[\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}

 \item Explicite as formas l\'ogicas das afirmativas abaixo. Podem ser usados os s\'{\i}mbolos
       $\in$, $\not\in$, $=$, $\not=$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\forall$
       e $\exists$, mas n\~ao $\subseteq$, $\not\subseteq$, ${\cal P}$, $\cap$, $\cup$, $\backslash$
       ou $\neg$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item ${\cal P}(A)\not\subseteq {\cal F}$.
        \item $x\in\cup{\cal F}\backslash \cap {\cal G}$.
        \item $\exists A\in{\cal F}\forall B\in{\cal G}(A\subseteq B)$.
        \item ${\cal P}(\cup_{i\in I}A_i)\not\subseteq \cup_{i\in I}{\cal P}(A_i)$.
       \end{list}

       \mbox{\em Solu\c c\~ao:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{tabbing}
               ${\cal P}(A)\not\subseteq {\cal F}$
                  \=$\equiv\neg\forall X(X\in{\cal P}(A)\rightarrow X\in{\cal F})$ \\
                  \>$\equiv\exists X(X\in{\cal P}(A) \wedge X\not\in{\cal F})$ \\
                  \>$\equiv\exists X(X\subseteq A \wedge X\not\in{\cal F})$ \\
                  \>$\equiv\exists X(\forall y(y\in X\rightarrow y\in A)\wedge X\not\in{\cal F})$ \\
              \end{tabbing}
        \item \begin{tabbing}
               $x\in\cup{\cal F}\backslash \cap {\cal G}$
                  \=$\equiv x\in\cup{\cal F}\wedge x\not\in\cap {\cal G}$. \\
                  \>$\equiv \exists A\in{\cal F}(x\in A) \wedge \neg \forall A\in{\cal G}(x\in A)$. \\
                  \>$\equiv \exists A\in{\cal F}(x\in A) \wedge \exists A\in{\cal G}(x\not\in A)$. \\
                  \>$\equiv \exists A(A\in{\cal F}\wedge x\in A) \wedge \exists A(A\in{\cal G}
                         \wedge x\not\in A)$. \\
              \end{tabbing}
        \item \begin{tabbing}
               $\exists A\in{\cal F}\forall B\in{\cal G}(A\subseteq B)$
                  \=$\equiv\exists A\in{\cal F}\forall B\in{\cal G}\forall x(x\in A\rightarrow x\in B)$ \\
                  \>$\equiv\exists A(A\in{\cal F}\wedge \forall B(B\in{\cal G}\rightarrow
                         \forall x(x\in A\rightarrow x\in B)))$ \\
              \end{tabbing}
        \item \begin{tabbing}
               ${\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(x\in X\rightarrow x\in\cup_{i\in I}A_i)\wedge
                         \forall i\in I (X\not\in {\cal P}(A_i)))$ \\
                  \>$\equiv\exists X(\forall x(x\in X\rightarrow \exists i\in I(x\in A_i))\wedge
                         \forall i\in I (X\not\subseteq A_i))$ \\
                  \>$\equiv\exists X(\forall x(x\in X\rightarrow \exists i(i\in I\wedge x\in A_i))\wedge
                         \forall i\in I \neg\forall x(x\in X\rightarrow x\in A_i))$ \\
                  \>$\equiv\exists X(\forall x(x\in X\rightarrow \exists i(i\in I\wedge x\in A_i))\wedge
                         \forall i\in I \exists x(x\in X\wedge x\not\in A_i))$ \\
                  \>$\equiv\exists X(\forall x(x\in X\rightarrow \exists i(i\in I\wedge x\in A_i))\wedge
                         \forall i(i\in I\rightarrow \exists x(x\in X\wedge x\not\in A_i)))$ \\
              \end{tabbing}
       \end{list}


\end{enumerate}

\end{document}
