\documentclass[12pt,a4paper]{report}
 
\newcounter{conta}
\pagestyle{empty}
\begin{document}

\noindent {Bacharelado em Ci\^encia da Computa\c c\~ao} \hfill DCC/ICEx/UFMG \\
{\em Matem\'atica Discreta} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2001 \\
Professor: Newton Jos\'e Vieira \\
{\bf Terceira Prova} \hfill 13/06/2001

\vspace*{.2cm}
\begin{enumerate} \footnotesize
 \item {\em O que h\'a de errado com a seguinte prova de que para quaisquer conjuntos $A$, $B$, $C$ e $D$,
       $(A\cup C)\times(B\cup D)\subseteq(A\times B)\cup (C\times D)$?
       \begin{quote}
        {\em Prova\/}. Suponha que $(x,y)\in(A\cup C)\times(B\cup D)$. Ent\~ao $x\in A\cup C$ e
        $y\in B\cup D$ e, assim, $x\in A$ ou $x\in C$ e tamb\'em $y\in B$ ou $y\in D$.
        Considerando estes casos separadamente:

        {\em Caso 1}. $x\in A$ e $y\in B$. Ent\~ao $(x,y)\in A\times B$.

        {\em Caso 2}. $x\in C$ e $y\in D$. Ent\~ao $(x,y)\in C\times D$.
       \end{quote}
       Assim, $(x,y)\in A\times B$ ou $(x,y)\in C\times D$. Portanto, $(x,y)\in(A\times B)\cup
       (C\times D)$.}

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

       Os casos apresentados n\~ao esgotam todas as possibilidades. Faltou considerar:
       (3) $x\in A$ e $y\in D$ e (4) $x\in C$ e $y\in B$. Considerando-se estes dois novos casos,
       n\~ao \'e poss\'{\i}vel completar a prova.

 \item {\em Seja $R$ uma rela\c c\~ao de $A$ para $B$, e $S$ e $T$ rela\c c\~oes de $B$ para $C$. Mostre que as
       seguintes afirmativas s\~ao verdadeiras ou falsas, justificando suas respostas com provas ou
       contraexemplos.
       \begin{enumerate}
        \item se $S\subseteq T$ ent\~ao $S\circ R\subseteq T\circ R$.
        \item se $S\circ R\subseteq T\circ R$ ent\~ao $S\subseteq T$.
       \end{enumerate}}
 
       \underline{\em Solu\c c\~ao\/}:
       \begin{enumerate}
        \item se $S\subseteq T$ ent\~ao $S\circ R\subseteq T\circ R$. \'E verdadeira.

              {\em Prova}: Inicialmente, observe que $S\circ R\subseteq A\times C$ e tamb\'em $T\circ R
                  \subseteq A\times C$. Suponha que $S\subseteq T$. Seja um par arbitr\'ario $(a,c)\in S\circ R$.
                  Seja, ent\~ao, um elemento $b\in B$ tal que $(a,b)\in R$ e $(b,c)\in S$. Como $S\subseteq T$,
                  $(b,c)\in T$. Logo, $(a,c)\in T\circ R$. Como $(a,c)$ \'e um par arbitr\'ario de $S\circ R$,
                  segue-se que $S\circ R\subseteq T\circ R$. Conclus\~ao: se $S\subseteq T$ ent\~ao
                  $S\circ R\subseteq T\circ R$.

        \item se $S\circ R\subseteq T\circ R$ ent\~ao $S\subseteq T$. \'E falsa.

              {\em Contra-exemplo}: $S=\{(a,a)\}$, $R=\emptyset$, $T=\emptyset$.

       \end{enumerate}

 \item {\em Seja $P$ o conjunto de todas as pessoas do mundo. Sejam as fun\c c\~oes:
       \begin{itemize}
        \item $f:P\rightarrow\mathcal{P}(P)$, tal que $f(p)=\mbox{ pessoas da fam\'{\i}lia de } p$;
        \item $t:\mathcal{P}(P)\rightarrow \mbox{\bf N},$ tal que $t(A)=|A|$;
        \item $g:\mbox{\bf N}\rightarrow \{\mbox{\em pequena},\mbox{\em m\'edia},\mbox{\em grande}\}$,
              onde
              \begin{itemize}
               \item $g(0)=g(1)=g(2)=g(3)=\mbox{\em pequena}$;
               \item $g(4)=g(5)=\mbox{\em m\'edia}$;
               \item $g(n)=\mbox{\em grande}$ para $n\geq 6$.
              \end{itemize}
       \end{itemize}
       Escreva, em portugu\^es coloquial, o que significa cada uma das afirmativas:
       \begin{enumerate}
        \item $\forall p\in P (p\in f(p))$
        \item $g\circ t\circ f(\mbox{\em Am\'elia})=\mbox{\em grande}$
       \end{enumerate}}

       \underline{\em Solu\c c\~ao\/}:
       \begin{enumerate}
        \item $\forall p\in P (p\in f(p))$: Toda pessoa pertence \`a pr\'opria fam\'{\i}lia.
        \item $g\circ t\circ f(\mbox{\em Am\'elia})=\mbox{\em grande}$:
              A fam\'{\i}lia de Am\'elia \'e grande.
       \end{enumerate}

 \item {\em Seja $A=\mbox{\bf R}\backslash\{1\}$ e seja $f:A\rightarrow \mbox{\bf R}$ definida como segue:
       \[f(x)=\frac{x+1}{x-1}\mbox{.}\]
       \begin{enumerate}
        \item Mostre que $f$ \'e injetiva.
        \item Mostre que $f$ \'e n\~ao \'e bijetiva.
       \end{enumerate}}

       \underline{\em Solu\c c\~ao\/}:
       \begin{enumerate}
        \item $f$ \'e injetiva. {\em Prova}:

              Sejam $y\in\mbox{\bf R}$ e $z\in\mbox{\bf R}$ arbitr\'arios. Suponha que $f(y)=f(z)$.
              Com isto, $(y+1)/(y-1)=(z+1)/(z-1)$. Segue-se, ent\~ao, que $yz-y+z-1=yz+y-z-1$, de
              onde se conclui que $y=z$. Assim, se $f(y)=f(z)$, ent\~ao $y=z$. Sendo $y$ e $z$
              reais arbitr\'arios, conclui-se que $f$ \'e injetiva.

        \item $f$ n\~ao \'e bijetiva. {\em Prova}:

              Suponha que existe $x\in\mbox{\bf R}\backslash\{1\}$ tal que $f(x)=1$. Neste caso,
              $(x+1)/(x-1)=1$, de onde se tira que $x+1=x-1$, o que \'e um absurdo. Logo, n\~ao
              existe $x\in\mbox{\bf R}\backslash\{1\}$ tal que $f(x)=1$ e, portanto, $f$ n\~ao
              \'e  sobrejetiva. Logo, n\~ao \'e bijetiva.
       \end{enumerate}

 \item {\em Prove, por indu\c c\~ao, que $\sum_{i=1}^n(i\times i!)=(n+1)!-1$ para todo $n\geq 1$.}

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

       Para $n=1$, $\sum_{i=1}^n(i\times i!)=1\times 1!=1=2-1=2!-1=(n+1)!-1$. Seja um n\'umero $n\geq 1$
       arbitr\'ario. Suponha, como hip\'otese de indu\c c\~ao, que $\sum_{i=1}^n(i\times i!)=(n+1)!-1$.
       Tem-se:
       \begin{tabbing}
        $\sum_{i=1}^{n+1}(i\times i!)$\=$=\sum_{i=1}^n(i\times i!)+ (n+1)(n+1)!$ \ \ \=\ \\
               \>$=(n+1)!-1+(n+1)(n+1)!$  \> pela hip\a'otese de indu\c c\~ao\\
               \>$=(n+2)(n+1)!-1$ \\
               \>$=(n+2)!-1$.
       \end{tabbing}
\end{enumerate}


\end{document}

