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

\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{1}^{\mbox{\underline{o}}}$ semestre de 2001 \\
Professor: Newton Jos\'{e} Vieira \\
{\bf Primeira Prova/Solu\c c\~ao do Professor}

\begin{enumerate} \footnotesize
 \item Explicite as formas l\'ogicas das seguintes afirmativas. Em nenhuma delas deve ser
       usada quantifica\c c\~ao.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Eu n\~ao vou \`a praia, ou eu vou mas n\~ao haver\'a sol.

              \underline{\em Solu\c c\~ao\/}: Sejam as vari\'aveis e respectivos significados:
              \begin{enumerate}
               \item[$P$:] {\em vou \`a praia\/};
               \item[$S$:] {\em haver\'a sol\/}.
              \end{enumerate}
               Resposta: $\neg P\vee(P\wedge\neg S)$. 

        \item Se este g\'as tem um cheiro desagrad\'avel ou n\~ao \'e explosivo, ent\~ao n\~ao
              \'e hidrog\^enio.

              \underline{\em Solu\c c\~ao\/}: Sejam as vari\'aveis:
              \begin{enumerate}
               \item[$D$:] {\em este g\'as tem cheiro desagrad\'avel\/};
               \item[$E$:] {\em este g\'as \'e explosivo\/};
               \item[$H$:] {\em este g\'as \'e hidrog\^encio\/}.
              \end{enumerate}
               Resposta: $(D\vee\neg E)\rightarrow \neg H$. 

        \item Est\'a ventando e n\~ao est\'a ensolarado somente se est\'a chovendo.

              \underline{\em Solu\c c\~ao\/}: Sejam as vari\'aveis:
              \begin{enumerate}
               \item[$V$:] {\em est\'a ventando\/};
               \item[$E$:] {\em est\'a ensolarado\/};
               \item[$C$:] {\em est\'a chovendo\/}.
              \end{enumerate}
               Resposta: $(V\wedge\neg E)\rightarrow C$. 

        \item Estar chovendo \'e uma condi\c c\~ao necess\'aria para estar ventando e n\~ao
              ensolarado.

              \underline{\em Solu\c c\~ao\/}: A resposta \'e a mesma que a do item anterior.
       \end{list}

 \item Expresse em L\'ogica de Predicados (com quantificadores):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Todo ser humano \'e mortal.

              \underline{\em Solu\c c\~ao\/}: Sejam os predicados:
              \begin{enumerate}
               \item[$H(x)$:] {\em $x$ \'e humano\/};
               \item[$M(x)$:] {\em $x$ \'e mortal\/}.
              \end{enumerate}
               Resposta: $\forall x(H(x)\rightarrow M(x))$.

        \item Todo n\'umero maior que $x$ \'e maior que $y$.

               Resposta: $\forall z(z>x\rightarrow z>y)$.

        \item H\'a homens que n\~ao t\^em amigos.

              \underline{\em Solu\c c\~ao\/}: Sejam os predicados:
              \begin{enumerate}
               \item[$H(x)$:] {\em $x$ \'e homem\/};
               \item[$A(x,y)$:] {\em $x$ \'e amigo de $y$\/}.
              \end{enumerate}
               Resposta: $\exists x(H(x)\wedge\neg\exists y A(x,y))$.

        \item Todo aluno tem um colega do qual ele n\~ao gosta.

              \underline{\em Solu\c c\~ao\/}: Sejam os predicados:
              \begin{enumerate}
               \item[$A(x)$:] {\em $x$ \'e aluno\/};
               \item[$C(x,y)$:] {\em $x$ \'e colega de $y$\/}.
               \item[$G(x,y)$:] {\em $x$ gosta de $y$\/}.
              \end{enumerate}
               Resposta: $\forall x[A(x)\rightarrow\exists y(A(y)\wedge C(x,y)\wedge\neg G(x,y))]$.

       \end{list}

 \item Sejam os conjuntos $X=A\backslash(B\cup C)$ e $Y=(A\backslash B)\cup(A\backslash C)$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre, usando diagramas de Venn, que $X\subseteq Y$.

              \underline{\em Solu\c c\~ao\/}: No diagrama de Venn para $X$ a parte hachurada final
              consta da \'area de $A$ que n\~ao \'e comum a $B$ nem a $C$, enquanto que no
              diagrama de Venn para $Y$ a parte hachurada final consta de toda a \'area de $X$
              acrescida da \'area comum a $A$ e a $B$, mas n\~ao a $C$ (relativa a $(A\cap B)\backslash C$),
              e acrescida tamb\'em da \'area comum a $A$ e a $C$, mas n\~ao a $B$ (relativa
              a $(A\cap C)\backslash B$). Assim, como toda a \'area relativa a $X$
              est\'a contida na \'area relativa a $Y$, $X\subseteq Y$.

        \item D\^e um exemplo de conjuntos $A$, $B$ e $C$ para os quais $X\not=Y$.

              \underline{\em Solu\c c\~ao\/}: Basta que $(A\cap B)\backslash C\not=\emptyset$ ou
              $(A\cap C)\backslash B\not=\emptyset$. Por exemplo: $A=\{a\}$, $B=\{a\}$ e $C=\emptyset$.

        \item Mostre que $X\subseteq Y$ mostrando que $x\in Y$ \'e consequ\^encia l\'ogica de
              $x\in X$.

              \underline{\em Solu\c c\~ao\/}: Deve-se mostrar que, sempre que $x\in X$ \'e verdadeiro,
              $x\in Y$ tamb\'em \'e. Tem-se:

              \begin{tabbing}
               $x\in X$ \=$\equiv$ $x\in A\wedge \neg(x\in B\vee x\in C)$ \ \  \=p, \kill
               $x\in X$ \>$\equiv$ $x\in A\backslash(B\cup C)$            \>pela def. de $X$ \\
                        \>$\equiv$ $x\in A\wedge x\not\in (B\cup C)$      \>pela def. de ``$\backslash$'' \\
                        \>$\equiv$ $x\in A\wedge \neg(x\in B\vee x\in C)$ \>pela def. de ``$\cup$'' \\
                        \>$\equiv$ $x\in A\wedge x\not\in B\wedge x\not\in C$ \>por De Morgan
              \end{tabbing}

              e

              \begin{tabbing}
               $x\in Y$ \=$\equiv$ $(x\in A\wedge x\not\in B)\vee(x\in A\wedge x\not\in C)$ \ \  \=p, \kill
               $x\in Y$ \>$\equiv$ $x\in (A\backslash B)\cup(A\backslash C)$         \>pela def. de $Y$ \\
                        \>$\equiv$ $x\in (A\backslash B)\vee x\in(A\backslash C)$    \>pela def. de ``$\cup$'' \\
                        \>$\equiv$ $(x\in A\wedge x\not\in B)\vee(x\in A\wedge x\not\in C)$ \>pela def. de ``$\backslash$'' \\
                        \>$\equiv$ $x\in A\wedge (x\not\in B\vee x\not\in C)$ \>pela distr. de ``$\wedge$'' sobre ``$\vee$''
              \end{tabbing}

              Assim, se $x\in X$ ent\~ao $x\in A$, $x\not\in B$ e $x\not\in C$. Neste caso, segue-se que
              $x\in A$ e $x\not\in B\vee x\not\in C$ s\~ao verdadeiros, ou seja, $x\in Y$.
       \end{list}

 \item Simplifique as afirmativas abaixo. Para as que n\~ao t\^em vari\'aveis livres, diga se
       s\~ao verdadeiras ou falsas.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $2\in\{x\,\,|\,\, x \mbox{ \'e par}\}$.

              \underline{\em Solu\c c\~ao\/}: $2\in\{x\,\,|\,\, x \mbox{ \'e par}\}\equiv 2 \mbox{ \'e par}$.
              Assim, a afirmativa \'e verdadeira.

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

              \underline{\em Solu\c c\~ao\/}: $2\in\{x\in\mbox{\bf R}\,\,|\,\, x^2-2x>2\}\equiv
               2^2-2\times 2>2\equiv 4-4>2\equiv 0>2$.
              Assim, a afirmativa \'e falsa.

        \item $y^2\not\in\{x^2\,\,|\,\, x>10\}$.

              \underline{\em Solu\c c\~ao\/}: $y^2\not\in\{x^2\,\,|\,\, x>10\}\equiv y^2\not\in\{z\,|\, \exists x
                (x>10\wedge z=x^2)\}$. Esta \'ultima \'e equivalente a $\neg\exists x(x>10\wedge y^2=x^2)$, que
                equiva a $\forall x(x>10\rightarrow y^2\not=x^2)$. A vari\'avel $y$ \'e livre.
        \item $2\in\{x\in\{x\,\,|\,\, x \mbox{ \'e par}\}\,\,|\,\, x^2-2x>2\}$.

              \underline{\em Solu\c c\~ao\/}: $2\in\{x\in\{x\,\,|\,\, x \mbox{ \'e par}\}\,\,|\,\, x^2-2x>2\}$
              equivale a ``2 \'e par e $0>2$''. \'E falsa.
       \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 F}\subseteq {\cal P}(A)$.

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

              \begin{tabbing}
               $\mathcal{F}\subseteq \mathcal{P}(A)$ \=\ \kill
               $\mathcal{F}\subseteq \mathcal{P}(A)$ \>$\equiv$
                                        $\forall X(X\in\mathcal{F}\rightarrow X\in\mathcal{P}(A))$\\
                 \>$\equiv$ $\forall X(X\in\mathcal{F}\rightarrow X\subseteq A)$\\
                 \>$\equiv$ $\forall X[X\in\mathcal{F}\rightarrow \forall x(x\in X\rightarrow x\in A)]$
              \end{tabbing}

        \item $x\in\cap({\cal F}\cup {\cal G})$.

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

              \begin{tabbing}
               $x\in\cap(\mathcal{F}\cup \mathcal{G})$ \=\ \kill
               $x\in\cap(\mathcal{F}\cup \mathcal{G})$ \>$\equiv$
                                          $\forall X\in\mathcal{F}\cup \mathcal{G}(x\in X)$ \\
                  \>$\equiv$ $\forall X(X\in\mathcal{F}\cup \mathcal{G}\rightarrow x\in X)$ \\
                  \>$\equiv$ $\forall X[(X\in\mathcal{F}\vee X\in\mathcal{G})\rightarrow x\in X]$
              \end{tabbing}

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

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

              \begin{tabbing}
               $A\subseteq \{2n+1\,\,|\,\, n\in\mbox{\bf N}\}$ \=\ \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 $x\in\cap_{i\in I}(A_i\backslash B_i)$.

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

              \begin{tabbing}
               $x\in\cap_{i\in I}(A_i\backslash B_i)$ \=\ \kill
               $x\in\cap_{i\in I}(A_i\backslash B_i)$ \>$\equiv$ $\forall i\in I(x\in A_i\backslash B_i)$ \\
                 \>$\equiv$ $\forall i\in I(x\in A_i\wedge x\not\in B_i)$
              \end{tabbing}

       \end{list}
\end{enumerate}

\end{document}
