% (find-angg "LATEX/2009-1-MD-prova-VS.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-1-MD-prova-VS.tex && latex    2009-1-MD-prova-VS.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-1-MD-prova-VS.tex && pdflatex 2009-1-MD-prova-VS.tex"))
% (eev "cd ~/LATEX/ && Scp 2009-1-MD-prova-VS.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2009-1-MD-prova-VS.dvi"))
% (find-dvipage "~/LATEX/2009-1-MD-prova-VS.dvi")
% (find-pspage  "~/LATEX/2009-1-MD-prova-VS.pdf")
% (find-pspage  "~/LATEX/2009-1-MD-prova-VS.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2009-1-MD-prova-VS.ps 2009-1-MD-prova-VS.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2009-1-MD-prova-VS.ps 2009-1-MD-prova-VS.dvi && ps2pdf 2009-1-MD-prova-VS.ps 2009-1-MD-prova-VS.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage  "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2009-1-MD-prova-VS.pdf" (ee-twupfile "LATEX/2009-1-MD-prova-VS.pdf") 'over)
% (ee-cp "~/LATEX/2009-1-MD-prova-VS.pdf" (ee-twusfile "LATEX/2009-1-MD-prova-VS.pdf") 'over)

\documentclass[oneside]{book}
\usepackage[latin1]{inputenc}
\usepackage{edrx08}       % (find-dn4ex "edrx08.sty")
%L process "edrx08.sty"  -- (find-dn4ex "edrx08.sty")
\input edrxheadfoot.tex   % (find-dn4ex "edrxheadfoot.tex")
\begin{document}

\input 2009-1-MD-prova-VS.dnt

%*
% (eedn4-51-bounded)

%Index of the slides:
%\msk
% To update the list of slides uncomment this line:
%\makelos{tmp.los}
% then rerun LaTeX on this file, and insert the contents of "tmp.los"
% below, by hand (i.e., with "insert-file"):
% (find-fline "tmp.los")
% (insert-file "tmp.los")

% (find-angg "LATEX/2009-1-MD-prova-VR.tex")

\def\depois#1{#1}
\def\sm#1{\begin{smallmatrix}#1\end{smallmatrix}}
\def\psm#1{\left(\begin{smallmatrix}#1\end{smallmatrix}\right)}

\def\notR{\not\mathrel{R}}
\def\notS{\not\mathrel{S}}
\def\notT{\not\mathrel{T}}
\def\notQ{\not\mathrel{Q}}
\def\notD{\not\mathrel{D}}
\def\sen{\operatorname{sen}}
\def\arcsen{\operatorname{arcsen}}
\def\sinal{\operatorname{sinal}}
\def\sinal{s}

% (find-dn4ex "edrxdnt.tex" "defdiag")
\long\def\Def  #1#2{\expandafter\def\csname #1\endcsname{#2}}
     \def\ifUndef#1{\expandafter\ifx\csname #1\endcsname\relax}
     \def\Assert #1{\ifUndef{#1}\errmessage{UNDEFINED: #1}\else\relax\fi}
     \def\Expand #1{\Assert{#1}\csname #1\endcsname}
% \long\def\defquestion cod#1 ref#2 val#3 qst#4 gab#5 spc#6{#1 #2 #3 #4 #5 #6}
\long\def\defquestion cod#1 ref#2 val#3 qst#4 gab#5 spc#6{
       \Def{Ref#1}{#2}
       \Def{Val#1}{#3}
  \long\Def{Qst#1}{#4}
  \long\Def{Gab#1}{#5}
  \long\Def{Spc#1}{#6}
}

% (find-LATEX "2009apr29-C1.tex")
% (find-LATEXfile "2009apr29-C1.tex" "newcounter")
% (find-es "tex" "newcounter")
\newcounter{questao}
\long\def\novaquestao{
  \par\noindent
  \refstepcounter{questao}
  {\bf (\arabic{questao})}
  }



% «Header»  (to ".Header")
\long\def\Header{{
  \setlength{\parindent}{0pt}
  \par Matemática Discreta
  \par PURO-UFF - 2009.1
  \par Professor: Eduardo Ochs
  \par Prova suplementar (VS) - 08/julho/2009
}}

% «Definicoes»  (to ".Definicoes")
\long\def\Definicoes{
% \par {\bf Dicas e definições:}
\par {\bf Definições:}

Um {\sl contra-exemplo} para $ýxÝA.P(a)$ é um $aÝA$ tal que $P(a)$ é
falso.

Uma sentença da forma $ýxÝA.P(a)$ é falsa se e só se algum $aÝA$ é um
contra-exemplo para $ýxÝA.P(a)$.

O {\sl conjunto das partes} de um conjunto $A$, $\Pts(A)$, é o
conjunto dos subconjuntos de $A$. Exemplo: se $A=\{4,5,6\}$ então
$\{4,5\} \in \Pts(A)$.

Se $A$ é um conjunto finito então $|A|$ é o número de elementos de
$A$.

A relação $R \subset A×A$ é {\sl reflexiva} quando $ýaÝA.\, aRa$.

A relação $R \subset A×A$ é {\sl simétrica} quando $ýa,bÝA.(aRb \to
bRa)$.

A relação $R \subset A×A$ é {\sl transitiva} quando $ýa,b,cÝA.(aRb ∧
bRc \to aRc)$.

Uma relação $R$ é uma {\sl relação de equivalência} quando $R$ é
reflexiva, simétrica e transitiva.

A {\sl classe de equivalência} de um elemento $a \in A$ pela relação
de equivalência $R \subset A×A$ é o conjunto $[a] = \sst{x \in
A}{aRx}$.

A {\sl inversa} de uma relação $R=\{(a_1,b_1), (a_2,b_2), \ldots\}$ é
a relação $R^{-1}=\{(b_1,a_1), (b_2,a_2), \ldots\}$.

{\sl Relação $R \subset A×A$ como grafo direcionado:} podemos
representar $R$ desenhando um grafo direcionado no qual os vértices
são os elementos de $A$ e cada seta $a \to b$ corresponde a um par
$(a,b) \in R$.

{\sl Relação $R \subset A×B$ como grafo direcionado:} podemos
representar $R$ desenhando o conjunto $A$ e o conjunto $B$ em separado
e desenhando uma seta $a \to b$ de um elemento $a \in A$ para um
elemento $b \in B$ para cada par $(a,b) \in R$.

A função $f: A \to B$ é {\sl injetiva} quando $ýa_1, a_2 \in A.\,
(f(a_1)=f(a_2) \to a_1=a_2)$.

A função $f: A \to B$ é {\sl sobrejetiva} quando $ýbÝB.\, ÎaÝA.\,
f(a)=b$.

Se $f:A \to B$ e $g: B \to C$ são funções, então a sua {\sl
composta}, $g¢f$, é uma função $g¢f: A \to C$, definida por
$ýaÝA.\, (g¢f)(a) = g(f(a))$.

A função {\sl identitidade em $A$}, $\id_A: A \to A$, é definida
por $ýaÝA.\, \id_A(a)=a$.

Duas funções $f:A \to B$ e $g:B \to A$ são {\sl inversas} quando
$f¢g = \id_B$ e $g¢f = \id_A$.
}

\long\def\Ask#1{
  \novaquestao
  {\bf (\Expand{Val#1} pontos)}
  \Expand{Qst#1}
  \bsk
  }
\long\def\Gab#1{
  \par {\bf (Questão {\tt #1} - \Expand{Val#1} pontos)}
  \Expand{Qst#1}
  \ssk\par {\bf Gabarito:}  
  \par \Expand{Gab#1}
  \bsk
  \bsk
  }

\def\Prova #1 #2 #3 #4 #5 {
  \setcounter{questao}{0}
  \Header
  \bsk
  \par {\bf Questões:}
  \ssk
  \Ask{#1}
  \Ask{#2}
  \Ask{#3}
  \Ask{#4}
  \Ask{#5}
  \newpage  
  \Definicoes
  \bsk
  \bsk
  \newpage  
}

% (find-kopkadaly4page (+ 12 126) "Index" "\\not")
% (find-kopkadaly4page (+ 12 631) "Index" "\\not")
% (find-kopkadaly4text)

% (find-LATEXfile "2008induction.tex" "\\def\\notS")
% (find-LATEXfile "2009-1-C1-prova-1.tex" "\\def\\sen")
\def\notR{\not\mathrel{R}}
\def\notQ{\not\mathrel{Q}}
\def\notD{\not\mathrel{D}}
\def\sen{\operatorname{sen}}
\def\arcsen{\operatorname{arcsen}}
\def\sinal{\operatorname{sinal}}
\def\sinal{s}

% \Ask{R}
% \Ask{Pipa}
% \Ask{Primos}
% \Ask{Arcsen}
% \Ask{Sinal}
% \Ask{Partes}

\Header

\bsk

% \Gab{Binary}
% \Gab{Induction}
% \Gab{Or}
% \newpage
% \Gab{P-any}
% \Gab{Square}

% \defquestion
%  cod{}
%  ref{}
%  val{}
%  qst{}
%  gab{}
%  spc{}



Vamos definir a operação $¥:\N×\N \to \{0,1\}$, a função $p:\N \to
\{0,1\}$ e a relação $E \subset \N×\N$ assim:

$\begin{array}{rcl}
 a¥b &=& \begin{cases}
           0 &\text{se $a+b$ é par} \\
           1 &\text{se $a+b$ é ímpar} \\
         \end{cases} \\
 p(a) &=& a¥0, \\
 aEb  &\Leftrightarrow& a¥b = 0. \\
 \end{array}
$

\msk
\bsk

\noindent {\bf (1)} (Total: 2.0 pontos). Mostre que $ýa,b,c \in
\{0,1\}$ temos $a¥a=0$, $a¥b=b¥a$, $a¥(b¥c)=(a¥b)¥c$, $p(p(a))=p(a)$,
$p(a)=p(a+2)$.

\bsk
\bsk


\noindent {\bf (2)} (Total: 1.0 pontos). Quais são as classes de
equivalência da relação $E$? Quem são $[0]$, $[1]$, $[2]$, $[3]$?

\bsk
% \bsk

\noindent {\bf (3)} (Total: 2.5 pontos). A matriz $8×8$ $M$,
%
$M=\psm{a_{11} & a_{12} & \ldots & a_{18} \\
        a_{21} & \ldots & \\
        \vdots & \ddots & \\
        a_{81} & \ldots &        & a_{88} \\
       }$,

é definida por:
%
$$a_{ij} = \begin{cases}
            1 & \text{se $i=1$ ou $j=1$,} \\
            1 & \text{se $i=7$ e $j=7$,} \\
            a_{(i-1)j}¥a_{i(j-1)} & \text{em todos os outros casos.} \\
          \end{cases}
$$

Calcule a matriz $M$.

\bsk
\bsk

\noindent {\bf (4)} (Total: 1.5 pontos). Diga se as seguintes
sentenças são verdadeiras ou falsas. Justifique.

a) $ýiÝ\{1,2,\ldots,8\}.\, ÎjÝ\{5,6,7,8\}.\, a_{ij}=0$

b) $ÎiÝ\{1,2,\ldots,8\}.\, ýjÝ\{5,6,7,8\}.\, a_{ij} = 0$

c) $ÎiÝ\{1,2,\ldots,8\}.\, ýjÝ\{5,6,7,8\}.\, a_{ij} \neq 0$

\bsk
\bsk

\noindent {\bf (5)} (Total: 3.0 pontos). Defina três relações, $F,G,H
\subseteq \N×\N$, assim:

$\begin{array}{rcl}
 aFb &\Leftrightarrow& (a-p(a) = b-p(b)) \\
 aGb &\Leftrightarrow& (a-p(a) = b) \\
 aHb &\Leftrightarrow& (a = b-p(b)) \\
 \end{array}
$

Para cada uma delas diga se ela é ou não reflexiva, simétrica,
transitiva, e se é ou não o gráfico de uma função. Justifique.



\newpage

\Definicoes

\newpage

{\bf Mini-gabarito:}

(1) Tabelas com 2, 4 ou 8 linhas.

(2) O conjunto dos pares e o conjunto dos ímpares; $[0] = [2] = \{0,
2, 4, \ldots\}$; $[1] = [3] = \{0, 2, 4, \ldots\}$.

(3)

$\psm{
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 &   & 1 &   & 1 &   & 1 &   \\
1 & 1 &   &   & 1 & 1 &   &   \\
1 &   &   &   & 1 &   &   &   \\
1 & 1 & 1 & 1 &   &   &   &   \\
1 &   & 1 &   &   &   &   &   \\
1 & 1 &   &   &   &   & 1 & 1 \\
1 &   &   &   &   &   & 1 &   \\ 
}$

(4a) Falso; o contra-exemplo é $i=1$

(4b) Verdadeiro; $i=5$ ou $i=6$

(4c) Verdadeiro; $i=1$

(5) $F$ é $RST$, $G$ é $\notR \notS T$, $H$ é $\notR \notS T$, 

$xFy = \psm{
| &   &   &   & 1 & 1 \\
| &   &   &   & 1 & 1 \\
| &   & 1 & 1 &   &   \\
| &   & 1 & 1 &   &   \\
1 & 1 &   &   &   &   \\
1 & 1 & - & - & - & - \\ 
},
\quad
xGy = \psm{
| &   &   &   & 0 & 0 \\
| &   &   &   & 1 & 1 \\
| &   & 0 & 0 &   &   \\
| &   & 1 & 1 &   &   \\
0 & 0 &   &   &   &   \\
1 & 1 & - & - & - & - \\ 
},
\quad
xHy = \psm{
| &   &   &   & 1 & 0 \\
| &   &   &   & 1 & 0 \\
| &   & 1 & 0 &   &   \\
| &   & 1 & 0 &   &   \\
1 & 0 &   &   &   &   \\
1 & 0 & - & - & - & - \\ 
}
$

$G$ é uma função, $F$ e $H$ não são.






%*

\end{document}

% Local Variables:
% coding:           raw-text-unix
% ee-anchor-format: "«%s»"
% End: