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


% «.Definicoes»	(to "Definicoes")
% «.Header»	(to "Header")


\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-2.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")

\def\depois#1{#1}

% (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 Segunda prova - 26/junho/2009
}}

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

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
  \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 {
  \setcounter{questao}{0}
  \Header
  \bsk
  \Definicoes
  \bsk
  \bsk
  \par {\bf Questões (2.5 pontos cada):}
  \ssk
  \Ask{#1}
  \Ask{#2}
  \Ask{#3}
  \Ask{#4}
  \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}

%%%%%%%%%%%%%%%%%%%%%%%%

\defquestion
 cod{RRRRR}
 ref{Sch 81/82 1, parte}
 val{2.5}
 qst{
   Para cada uma das relações $R \subseteq \{1,2,3,4,5\}^2$ abaixo
   diga se a relação $R$ é reflexiva, simétrica, e/ou transitiva;
   quando não for, justifique porquê.
 
   a) $R=\{(1,1), (2,2), (3,3), (4,4), (5,5)\}$,
 
   b) $R=\{(1,2), (2,3), (3,4), (4,5)\}$,
 
   c) $R=\{(1,1), (1,2), (1,3), (1,4), (1,5)\}$,

   d) $R=\{(1,1), (1,2), (2,1), (3,4), (4,3)\}$,
 
   e) $R=\{1,2,3,4,5\}^2$
 }
 gab{
   a) Reflexiva, simétrica, transitiva.

   b) Não-reflexiva ($1\notR1$), não-simétrica ($1R2$ mas $2\notR1$),
   não-transitiva ($1R2$ e $2R3$ mas $1\notR3$).

   c) Não-reflexiva ($2\notR2$), não-simétrica ($1R2$ mas $2\notR1$),
   transitiva.

   d) Não-reflexiva ($2\notR2$), simétrica, não-transitiva ($2R1$ e $1R2$ mas $2\notR2$).

   e) Reflexiva, simétrica, transitiva.
 }
 spc{}

%%%%%%%%%

\defquestion
 cod{Pipa}
 ref{Inventei}
 val{2.5}
 qst{
   Seja $A = \{0, 1, 2, 3, 4\}$. Considere a seguinte relação $G
   \subset A×A$: $G=\{(0,1), (0,2), (1, 3), (2, 3), (3, 4)\}$.

   Crie as relações $R$, $S$ e $T$,
   acrescentando o menor número possível de pares a $G$, tais que
     $G \subseteq R \subseteq A×A$,
     $G \subseteq S \subseteq A×A$,
     $G \subseteq T \subseteq A×A$,
   \depois{$R$ é reflexiva, $S$ é simétrica, $T$ é transitiva,}
   e:

   a) Represente a relação $G$ como um grafo direcionado.

   b) Represente a relação $R$ como um grafo direcionado.

   c) Represente a relação $S$ como um grafo direcionado.

   d) Represente a relação $T$ como um grafo direcionado.

   e) Agora crie uma relação $F \subset G$ tal que $F$ tenha um
   elemento a menos que $G$ e $F$ seja o gráfico de uma função $f$.
   Descreva a função $f$ e diga o seu domínio e a sua imagem.
 }
 gab{
   a) $G$ é uma pipa.

   b) $R$ é a pipa com loops.

   c) $S$ é a pipa com setas bidirecionais.

   d) $T$ é a pipa com 4 setas a mais.

   e) $F=\{(0,1), (1, 3), (2, 3), (3, 4)\}$ ou
   $F=\{(0,2), (1, 3), (2, 3), (3, 4)\}$;

   $f:\{0,1,2,3\} \to \{1, 3, 4\}$.
}
 spc{}

%%%%%%%%%%

\defquestion
 cod{Primos}
 ref{Inventei}
 val{2.5}
 qst{
   Seja $A = \{2, 3, 4, 6, 9, 12, 27, 36\}$. Considere a seguinte
   relação $P \subset A×A$: $aPb$ se e só se ``é possível ir de $a$
   para $b$ multiplicando $a$ por um primo'' --- ou seja, se e só se
   existe um primo $p$ (lembre que 1 não é primo!) tal que $ap=b$.

   \ssk

   a) (0.3 pts) Represente $P \subseteq A \depois{× A}$ como um grafo
   direcionado.

   b) (0.3 pts) Represente $P$ como um conjunto.

   \ssk

   Agora crie as relações $R$, $S$ e $T$, acrescentando o menor
   número possível de pares a $P$, tais que
     $P \subseteq R \subseteq A×A$,
     $P \subseteq S \subseteq A×A$,
     $P \subseteq T \subseteq A×A$, e:

   \ssk

   c) (0.3 pts) Represente a relação $R$ como um grafo direcionado.

   d) (0.3 pts) Represente a relação $S$ como um grafo direcionado.

   e) (0.4 pts) Represente a relação $T$ como um grafo direcionado.

   f) (0.5 pts) Represente como um grafo direcionado a relação $D
   \subseteq A×A$ definida por: $aDb$ se e só se $a<b$ e $a$ é um
   divisor de $b$.

   g) (0.4 pts) A relação $D$ é reflexiva? É simétrica? É transitiva?
   Quando não for, mostre porquê. A relação $D$ é igual a alguma das
   relações dos itens anteriores?
 }
 gab{
   Desenho:
   $\left(
    \begin{smallmatrix} 4 & 12 & 36 \\
                        2 & 6  &    \\
                          & 3  &  9 & 27 \\
    \end{smallmatrix}
    \right)
   $

   a) $P$ é $4 \to 12 \to 36$, $2 \to 6$, $3 \to 9 \to 27$, e $2 \to
   4$, $3 \to 6 \to 12$.

   b) $P=\{(2,4), (2,6), (3,6), (3,9), (4,12), (6,12), (9, 27)\}$

   c) $R$ é $P$ com loops.

   d) $S$ é $P$ com setas bidirecionais.

   e) $T$ é o fecho transitivo.

   f) $D$ é $T$ com mais a seta $9 \to 36$.

   g) $D$ não é reflexiva ($2\notD2$), não é simétrica ($2D4$ mas
   $4\notD2$), é transitiva, é estritamnete maior que $T$.
}
 spc{}

%%%%%%%%%%

\defquestion
 cod{Arcsen}
 ref{Sch p.183 8}
 val{2.5}
 qst{
  A função seno, $\sen: \R \to \R$, não é nem injetiva nem
  sobrejetiva, e a função $\arcsen: [-1,1] \to \R$ não é sobrejetiva,
  mas mesmo assim costumamos dizer que o arcsen é a inversa do seno...
  Explique isto, e defina duas funções, $s$ e $a$, ``parecidas'' com o
  seno e o arcsen --- você vai ter que explicar em que sentido $s$ e
  $a$ são parecidas com sen e arcsen! --- tais que $s$ e $a$ sejam
  realmente inversas uma da outra. (Sugestões: funções compostas;
  restrição de domínio).
 }
 gab{
  $s: [-\pi,\pi] \to [-1,1]$, restrição do sen,

  $a: [-1,1] \to [-\pi,\pi]$, restrição do arcsen,

  $s = a^{-1}$ 

  $a = s^{-1}$.

  $ýxÝ[-1,1]. \, \sen(\arcsen(x))=x$.

  $\arcsen(s(\theta))=x$.
 }
 spc{}


%%%%%%%%%%%

\defquestion
 cod{Sinal}
 ref{inventei}
 val{2.5}
 qst{
  Seja $\sinal: \R \to \{-1,0,1\}$ a função que retorna -1 quando
  recebe um número negativo, 0 quando recebe 0 e 1 quando recebe um
  número positivo.

  Sejam $A=\{-3,-2,0,2,4\}$ e $B=\{-4,-2,0,2,3\}$.

  Seja $S \subseteq A×A$ a relação $S = \sst{(a_1,a_2) \in
  A×A}{\sinal(a_1)=\sinal(a_2)}$. A relação $S$ é uma relação de
  equivalência.

  \ssk

  a) (0.4 pts) Diga qual é a classe de equivalência do 2 por $S$.

  b) (0.7 pts) Diga quais são todas as classes de equivalência de $S$.
  Represente as classes de equivalência de $S$ graficamente ---
  desenhe o conjunto $A$ e faça um círculo em torno de cada grupo de
  elementos equivalentes.

  \ssk

  Seja $\sinal^2: \R^2 \to \{-1,0,1\}^2$ a função que recebe um par
  $(x,y)\in \R^2$ e retorna $(\sinal(x), \sinal(y))$.

  Seja $Q\subseteq (A×B)×(A×B)$ a relação que diz que $(a,b)Q(a'b')$ é
  verdadeiro se e só se $\sinal(a)=\sinal(a')$ e
  $\sinal(b)=\sinal(b')$.

  \ssk

  c) (0.4 pts) Mostre -- expandindo as definições --- que
  $(2,2)Q(3,4)$ e $(2,3)\notQ(-2,3)$.

  d) (1.0 pts) Represente $A×B \subseteq \R^2$ como um conjunto de
  pontos do plano e represente suas classes de equivalência
  graficamente, como no item (c).
 }
 gab{
  a) (0.4 pts) $[2]=\{2,4\}$

  b) (0.7 pts) $\{\{-4,-2\}, \{0\}, \{2,4\}\}$; $(-4,-2), (0), (2,
  4)$.

  c) (0.4 pts) $(2,2)Q(3,4) \bij
                2R3´2R4 \bij
                (\sinal(2){=}\sinal(2) ´ \sinal(2){=}\sinal(4)) \bij
                (1{=}1 ´ 1{=}1) \bij
                V´V \bij
                V$;

                $(2,3)Q(-2,3) \bij
                2R-2´3R3 \bij
                (1{=}-1 ´ 1{=}1) \bij
                F´V \bij
                F$

  d) (1.0 pts) 9 blobs no plano.
 }
 spc{}

%%%%%%%%%%%

\defquestion
 cod{Partes}
 ref{Sch 98 ex 13.7}
 val{2.5}
 qst{
  Sejam $A = \{4, 5\}$, $B = \Pts(A)$, e seja $S \subseteq B×B$ a
  relação ``tem o mesmo tamanho que''. A relação $S$ é uma relação de
  equivalência sobre $B$.

  a) (1.0 pts) Diga quem é $[\{4\}]$, a classe de equivalência de
  $\{4\}ÝB$. (lembre que $[\{4\}] \subseteq B$). Diga quem é
  $|[\{4\}]|$.

  b) (1.5 pts) Seja $f:B \to \N$ a função que para cada $XÝB$ retorna
  $|[X]|$. Seja $F$ o gráfico de $f$. $F$ é uma relação, e portanto um
  conjunto. Diga quem é $F$.
}
 gab{
  a) $[\{4\}] = \{\{4\},\{5\}\}$; $|[\{4\}]| = 2$.

  b) $F = \{(\{\}, 1),
            (\{4\}, 2),
            (\{5\}, 2),
            (\{4,5\}, 1)\}$.
}
 spc{}

\Prova   RRRRR  Primos  Partes  Arcsen
\Prova  Primos   RRRRR   Sinal  Arcsen
\Prova  Partes  Primos  Arcsen   RRRRR
\Prova   RRRRR  Arcsen  Partes  Primos
\Prova    Pipa   Sinal   RRRRR  Partes
\Prova   RRRRR  Primos  Partes  Arcsen
\Prova   RRRRR  Partes    Pipa   Sinal
\Prova   RRRRR   Sinal  Arcsen  Primos
\Prova    Pipa   Sinal  Arcsen   RRRRR
\Prova   RRRRR  Arcsen   Sinal  Primos
\Prova   Sinal  Partes  Primos   RRRRR
\Prova  Arcsen  Partes   RRRRR    Pipa
\Prova  Partes   RRRRR  Primos  Arcsen
\Prova    Pipa  Arcsen  Partes   Sinal
\Prova  Partes   RRRRR   Sinal  Primos
\Prova  Partes   RRRRR   Sinal    Pipa
\Prova    Pipa   Sinal  Arcsen   RRRRR
\Prova    Pipa  Arcsen   Sinal  Partes
\Prova    Pipa   Sinal   RRRRR  Arcsen
\Prova  Arcsen   RRRRR  Primos  Partes
\Prova  Partes    Pipa  Arcsen   RRRRR
\Prova    Pipa   Sinal  Arcsen   RRRRR
\Prova  Primos  Arcsen  Partes   Sinal
\Prova   RRRRR   Sinal  Primos  Partes
\Prova   RRRRR    Pipa  Arcsen   Sinal
\Prova   RRRRR    Pipa   Sinal  Arcsen
\Prova  Partes  Primos   Sinal   RRRRR
\Prova   RRRRR  Primos  Arcsen   Sinal
\Prova  Partes   Sinal  Primos  Arcsen
\Prova  Primos  Partes   RRRRR   Sinal
\Prova   Sinal  Arcsen    Pipa   RRRRR
\Prova  Arcsen  Partes    Pipa   RRRRR
\Prova  Partes  Arcsen  Primos   Sinal
\Prova  Partes   RRRRR    Pipa   Sinal
\Prova  Arcsen   Sinal    Pipa   RRRRR


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

\newpage

{\bf Gabarito:}

\bsk

\Gab{Pipa}
\Gab{Primos}
\Gab{RRRRR}
\Gab{Sinal}
\Gab{Arcsen}
\Gab{Partes}

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






%

\end{document}



 (eepitch-lua51)
 (eepitch-kill)
 (eepitch-lua51)
random = math.random
shuffle = function (A)
    local B = {}
    for i=1,#A do B[i]=A[i] end
    for i=#A,2,-1 do
      local r = random(1, i)
      B[r], B[i] = B[i], B[r]
    end
    return B
  end
from = function (A, n)
    if n == nil then
      return A[random(1, #A)]
    end
    A = shuffle(A)
    while #A > n do A[#A] = nil end
    return A
  end
questoes = function ()
    local a = from(split "Pipa Primos")
    local B = from(shuffle(split "Sinal Arcsen RRRRR Partes"), 3)
    tinsert(B, a)
    return shuffle(B)
  end
prova = function ()
    local a, b, c, d = unpack(questoes())
    printf("\\Prova %7s %7s %7s %7s\n", a, b, c, d)
  end

for i=1,20 do PP(questoes()) end
for i=1,35 do prova() end







for i=1,10 do PP(from{"Pipa", "Primos"}) end
for i=1,10 do PP(from(split {"Pipa", "Primos"}) end



for i=1,40 do PP(shuffle({"aa", "bb", "cc", "dd", "ee"})) end



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