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

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{3cm}
\addtolength{\oddsidemargin}{-1cm}
\addtolength{\textwidth}{2.5cm}
%=================================================================

\newcounter{conta}
\pagestyle{empty}
\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 Terceira Prova/Solu\c c\~ao do professor} \hfill 21/07/2003

\begin{enumerate}
 \item Suponha que $R$ e $S$ sejam rela\c c\~oes de $A$ para $B$. Quais dentre as
       seguintes afirmativas s\~ao verdadeiras? Justifique suas respostas com provas
       ou contra-exemplos.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R^{-1}=\mbox{\em Im\/}(R)\times \mbox{\em Dom\/}(R)$.
        \item $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$.
       \end{list}

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

        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\em Falsa\/}. Contra-exemplo: $A=\{1,2\}$, $B=\{3,4\}$, $R=\{(1,3),(2,4)\}$. Tem-se:
              \begin{itemize}
               \item $R^{-1}=\{(3,1),(4,2)\}$.
               \item $\mbox{\em Im\/}(R)\times \mbox{\em Dom\/}(R)=\{3,4\}\times\{1,2\}=
                      \{(3,1),(3,2),(4,1),(4,2)\}$.
              \end{itemize}
        \item {\em Verdadeira\/}. $R\cup S$ \'e uma rela\c c\~ao de $A$ para $B$; portanto, $(R\cup S)^{-1}$
              \'e uma rela\c c\~ao de $B$ para $A$. $R^{-1}$ e $S^{-1}$ s\~ao rela\c c\~oes de $A$ para $B$;
              portanto, $R^{-1}\cup S^{-1}$ \'e uma rela\c c\~ao de $B$ para $A$. Sejam $a\in A$ e $b\in B$
              arbitr\'arios. Segue-se que:
              \begin{tabbing}
               $(b,a)\in(R\cup S)^{-1}$\= {\em sse\/} $(a,b)\in R\cup S$ \\
                                       \> {\em sse\/} $(a,b)\in R$ ou $(a,b)\in S$ \\
                                       \> {\em sse\/} $(b,a)\in R^{-1}$ ou $(b,a)\in S^{-1}$ \\
                                       \> {\em sse\/} $(b,a)\in R^{-1}\cup S^{-1}$.
              \end{tabbing}
              Como $a$ e $b$ s\~ao arbitr\'arios, conclui-se que $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$.
       \end{list}
      

 \item Determine, para cada rela\c c\~ao $R$ abaixo, se ela \'e uma ordem parcial
       sobre $A$. Se n\~ao for, diga por que  n\~ao. Se for, diga ainda se ela \'e
       ou n\~ao uma ordem total.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A=\{a,b,c\}$. $R=\{(a,a),(a,b),(b,b),(b,c),(c,c),(c,a)\}$.

        \item $A=\mbox{o conjunto das palavras da lingua portuguesa}$. \\
              $R=\{(x,y)\in A\times A\,|\, x \mbox{ ocorre em $y$}\}$.

        \item $A=\mbox{\bf R}$. $R=\{(x,y)\in \mbox{\bf R}\times\mbox{\bf R}\,|\,
               |x|\leq |y|\}$.

        \item $A=\mbox{\bf R}$. $R=\{(x,y)\in \mbox{\bf R}\times\mbox{\bf R}\,|\,
               |x|< |y| \mbox{ ou } x=y\}$.
       \end{list}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R$ n\~ao \'e ordem parcial, pois {\em n\~ao \'e transitiva\/}: em
              particular, $(a,b)\in R$ e $(b,c)\in R$, mas $(a,c)\not\in R$.

        \item $R$ \'e ordem parcial, pois:
               \begin{itemize}
                \item \'e reflexiva: toda palavra ocorre nela mesma;
                \item \'e anti-sim\'etrica: $x$ ocorre em $y$ e $y$ ocorre em $x$ apenas se $x=y$;
                \item \'e transitiva: se $x$ ocorre em $y$ e $y$ ocorre em $z$, ent\~ao $x$ ocorre em $z$.
               \end{itemize}
              $R$ n\~ao \'e ordem total, pois existem palavras tais que nenhuma delas ocorre
              na outra. Exemplo: ``para'' e ``todo''.

        \item $R$ n\~ao \'e ordem parcial, pois {\em n\~ao \'e anti-sim\'etrica\/}: $(-1,1)\in R$, pois
                 $|-1|\leq |1|$, e $(1,-1)\in R$, pois $|1|\leq |-1|$, mas $-1\not=1$.

        \item $R$ \'e ordem parcial, pois:
               \begin{itemize}
                \item \'e reflexiva: $\forall x\in\mbox{\bf R} (x=x)$;
                \item \'e anti-sim\'etrica: $\forall x\in\mbox{\bf R}\forall y\in\mbox{\bf R}$
                      se $[|x|<|y|$ ou $x=y]$ e $[|x|>|y|$ ou $x=y]$ ent\~ao $x=y$;
                \item \'e transitiva: isto decorre do fato de ambas as rela\c c\~oes usadas na
                      defini\c c\~ao de $R$, $<$ e $=$, serem transitivas.
               \end{itemize}
              $R$ n\~ao \'e ordem total, pois $(-1,1)\not\in R$ e $(1,-1)\not\in R$.

       \end{list}


 \item Seja $f:(\mbox{\bf R}\backslash\{1\})\rightarrow \mbox{\bf R}$, tal que:
       \[f(x)=\frac{x+1}{x-1}\mbox{.}\]
       Prove que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $f$ \'e injetora.
        \item $f$ \'e sobrejetora.
       \end{list}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sim, $f$ \'e injetora.

                Sejam $x,y\in\mbox{\bf R}\backslash\{1\}$ arbitr\'arios. Suponha que $f(x)=f(y)$.
                Ent\~ao: $(x+1)/(x-1)=(y+1)/(y-1)$. Como $x\not=1$ e $y\not=1$, segue-se que
                $(x+1)(y-1)=(x-1)/(y+1)$, de onde se tira que $xy-x+y-1=xy+x-y-1$. Simplificando
                esta \'ultima, tem-se que $-x+y=x-y$, ou ainda, $2y=2x$. Logo, $x=y$. Como $x$ e $y$
                s\~ao elementos arbitr\'arios de $\mbox{\bf R}\backslash\{1\}$ tais que
                $f(x)=f(y)$, conclui-se que $f$ \'e injetora.

        \item $f$ {\em n\~ao\/} \'e sobrejetora.

                 Seja $x\in\mbox{\bf R}\backslash\{1\}$ tal que $f(x)=1$, ou seja, $(x+1)/(x-1)=1$.
                 Neste caso, como $x\not=1$, $x+1=x-1$. Logo, $1=-1$. Absurdo! Conclui-se, ent\~ao,
                 n\~ao existe $x\in\mbox{\bf R}\backslash\{1\}$ tal que $f(x)=1$. Portanto, $f$
                 n\~ao \'e sobrejetora.
       \end{list}


 \item Prove, por indu\c c\~ao, que para todo $n\in\mbox{\bf N}$, $(n+1)^2-n$ \'e
       \'{\i}mpar.

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

       Inicialmente, veja que $(0+1)^2-0=1$, e $1$ \'e \'{\i}mpar. Seja $n$ um n\'umero
       natural arbitr\'ario, e suponha, como hip\'otese de indu\c c\~ao, que $(n+1)^2-n$ \'e
       \'{\i}mpar. Tem-se:
       \begin{tabbing}
        $(n+1+1)^2-(n+1)$\=$=(n+1)^2+2(n+1)+1-(n+1)$ \\
                                  \>$=(n+1)^2-n+2(n+1)$.
       \end{tabbing}
       A parte $(n+1)^2-n$ \'e \'{\i}mpar pela hip\'otese de indu\c c\~ao, e a parte
       $2(n+1)$ \'e par por defini\c c\~ao. A soma de um n\'umero \'{\i}mpar com um
       n\'umero par \'e um n\'umero \'{\i}mpar, como requerido.

 \item Seja a sequ\^encia $a_0, a_1, a_2, \ldots$ definida recursivamente assim:
       \begin{enumerate}
        \item[\ ] $a_0=2$;
        \item[\ ] para todo $n\geq 1$, $a_n=3a_{n-1}+5\times 3^n$.
       \end{enumerate}
       Prove que para todo $n\in\mbox{\bf N}$, $a_n=(2+5n)3^n$.

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

       Caso base: $a_0=2$, por defini\c c\~ao. E $(2+5\times 0)\times 3^0=2$.
       Seja $n\in\mbox{\bf N}$, e suponha, como hip\'otese de indu\c c\~ao, que
       $a_n=(2+5n)3^n$. Segue-se que:
       \begin{tabbing}
        $a_n$\=$=3a_n+5\times 3^{n+1}$, pela defini\c c\~ao de $a_n$ \\
                 \>$=3(2+5n)\times 3^n+5\times 3^{n+1}$, pela hip\a'otese de indu\c c\~ao \\
                 \>$=(2+5n)\times 3^{n+1}+5\times 3^{n+1}$ \\
                 \>$=(2+5n+5)\times 3^{n+1}$ \\
                 \>$=(2+5(n+1))\times 3^{n+1}$.
       \end{tabbing}

\end{enumerate}
 
\end{document}

