\documentclass[12pt,a4paper]{article}

\addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1.0in}

\newcounter{conta}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Matem\'{a}tica Discreta}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: 25/11/2002

\noindent {\bf Fundamentos de Matem\'{a}tica}
 
\begin{enumerate}
 \item Sejam os conjuntos $A=\{n\in \mbox{\bf N}\,|\,n\leq 8\}$ e $\{n\in \mbox{\bf Z}
       \,|\,-5\leq n\leq 5\}$. Liste os elementos dos conjuntos seguintes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cap B$.
        \item $A-B$.
        \item $C=\{n\in A\cup B\,|\,n=2k \mbox{ para algum } k\in\mbox{\bf Z}\}$.
        \item $D=(A-B)\cup(B-A)$.
        \item $[(A\cap C)-(A\cap D)]\times[(A\cap D)-(A\cap C)]$.
       \end{list}

 \item O que se pode dizer sobre os conjuntos $A$ e $B$, caso:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cup B=A$?
        \item $A\cap B=A$?
        \item $A-B=A$?
        \item $A-B=B-A$?
        \item $A\cup B=A\cap B$?
       \end{list}

 \item Prove que
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{A\cup B}=\overline{A}\cap \overline{B}$.
        \item se $A\cap B=A\cup B$ ent\~ao $A=B$.
        \item $(A-B)\cup (B-A)=(A\cup B)-(A\cap B)$.
        \item $A\times(B\cap C)=(A\times B)\cap(A\times C)$.
       \end{list}

 \item Prove que ${\cal P}(A)\cup{\cal P}(B)\subseteq {\cal P}(A\cup B)$, mas
       n\~{a}o vice-versa, isto \'{e}, nem sempre ${\cal P}(A\cup B)\subseteq
       {\cal P}(A)\cup{\cal P}(B)$.

 \item Que propriedades (dentre reflexividade, simetria e transitividade)
       t\^{e}m as seguintes rela\c{c}\~{o}es?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\subseteq$ sobre ${\cal P}(X)$ ($X$ \'{e} um conjunto qualquer).
        \item $R$ sobre ${\cal P}(X)$ definida por: $A R B$ se, e somente se,
              $A=\bar{B}$.
        \item $R$ sobre $\bf N$ definida por: $a R b$ se, e somente se,
              $b$ \'{e} divis\'{\i}vel por $a$.
        \item $R$ sobre $\bf R$ definida por: $a R b$ se, e somente se,
              $a-b$ \'{e} um n\'umero inteiro.
       \end{list}

 \item Considere as seguintes rela\c{c}\~{o}es de equival\^{e}ncia sobre o
       conjunto dos seres humanos:
       \begin{enumerate}
        \item[\ ] $R_1$: $x R_1 y \Leftrightarrow$ $x$ e $y$ s\~{a}o do
                  mesmo sexo;
        \item[\ ] $R_2$: $x R_2 y \Leftrightarrow$ $x$ e $y$ t\^{e}m a mesma
                  data de anivers\'{a}rio.
       \end{enumerate}
       Quantas classes de equival\^{e}ncia tem a parti\c{c}\~{a}o induzida por cada uma
       delas?

 \item Classifique (ou seja, diga se s\~{a}o injetoras, etc.) as seguintes
       fun\c{c}\~{o}es de {\bf N} para {\bf N}:      
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $f(n)=n+1$.
        \item $f(n)=n\div 2$, onde ``$\div$'' \'e divis\~ao inteira.
        \item $f(n)=n^2+1$.
        \item $f(n)=n(n+1)/2$.
        \item $f(n)=n-1$ se $n$ \'e \'{\i}mpar, e $f(n)=n+1$, caso contr\'ario.
       \end{list}

 \item D\^{e} uma prova direta de que se $n$ n\~{a}o \'{e} divis\'{\i}vel por 3,
       ent\~{a}o $n^2+2$ \'{e} divis\'{\i}vel por 3.

 \item D\^{e} uma prova indireta de que se $x^2+y^2=z^2$, ent\~{a}o pelo menos um,
       dentre $x$, $y$ e $z$, \'{e} par.

 \item Prove que se $x^2+y=13$ e $y\not=4$ ent\~ao $x\not=3$, onde $x$ e $y$ s\~ao
       n\'umeros reais.

 \item Prove que um n\'{u}mero natural $n$ \'{e} \'{\i}mpar se, e somente se, $n^2$
       \'{e} \'{\i}mpar.

 \item D\^{e} uma prova por contradi\c{c}\~{a}o de que $\log_2 5$ \'{e} irracional.

 \item Prove que \'{e} verdadeiro ou falso: ``todo inteiro positivo pode ser escrito
       como a soma dos quadrados de dois n\'{u}meros inteiros''.

 \item Use o princ\'{\i}pio da casa de pombos ({\it pigeonhole principle\/}) para provar que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Em qualquer grupo de $m\geq 2$ pessoas existem 2 pessoas com o
              mesmo n\'{u}meros de amigos no grupo. (Observe que siclano \'{e} amigo
              de beltrano $\Leftrightarrow$ beltrano \'{e} amigo de siclano.)
        \item Supondo que uma certa empresa tem 6 computadores, cada um
              conectado a zero ou mais dos outros computadores, ent\~{a}o existem no
              m\'{\i}nimo 2 computadores diretamente conectados ao mesmo n\'{u}mero de
              computadores.
        \item Qualquer conjunto de 7 n\'{u}meros inteiros distintos cont\'{e}m dois
              n\'{u}meros cuja soma ou diferen\c{c}a \'{e} m\'{u}ltiplo de 10.
       \end{list}
\end{enumerate}


\end{document}
\endinput
\end
 

 



