%*
% (eedn4a-bounded)
% (find-sh0 "cd ~/LATEX/ && dvips  -D 300 -P pk -o tmp.ps tmp.dvi")
% (find-sh0 "cd ~/LATEX/ && dvired -D 300 -P pk -o tmp.ps tmp.dvi")
% (find-pspage "~/LATEX/tmp.ps")

Matemática Discreta - Primeira Prova (P1)

PURO-UFF - 2010.1

12/abril/2010

Prof: Eduardo Ochs

Aluno: {\bf \ALUNO}

Matrícula: {\bf \MATRICULA}

Posição: {\bf \POSICAO}

\bsk
\bsk

\def\myif{Ð{if}}
\def\V{¦V}
\def\F{¦F}
\def\squig{\squigto}
\def\concat{+\!\!+}

Seqüências infinitas podem ser vistas como listas infinitas, e podem
ser definidas ``indutivamente''. Por exemplo, a seqüência $(a_0, a_1,
a_2, \ldots) = (1, 2, 4, 8, \ldots)$ pode ser definida por duas
condições: $a_0=1$ e $ýnÝ\N.a_{n+1}=2a_n$ --- se expandimos
$ýnÝ\N.a_{n+1}=2a_n$ obtemos $a_1 = 2a_0$, $a_2 = 2a_1$, etc, e com
isto podemos calcular o valor de cada um dos `$a_n$'s.

Além disso, podemos definir em matematiquês um ``if'' parecido com os
de linguagens de programação usando uma função de três argumentos, com
as seguintes regras de redução:
%
$$\begin{array}{rcl}
  \myif(\V, a, b) &\squig& a \\
  \myif(\F, a, b) &\squig& b \\
  \end{array}
$$
%
Então, por exemplo:
%
$$\begin{array}{l}
  \myif((2<4), 2, 4) \squig \myif(\V, 2, 4) \squig 2 \\
  \myif((99<9), 99, 9) \squig \myif(\F, 99, 9) \squig 9\\
  \end{array}
$$
%
e podemos definir $Ð{min}(a,b) = \myif((a<b), a, b)$.

Se consideramos cada número $nÝ\N$ como uma seqüência de caracteres
começando pelo dígito mais significativo de $n$ --- o 123 como
``123'', o 4 como ``4'', 1000 como ``1000'', e o 0 como ``'' ---,
podemos definir uma operação, $\concat$, que ``concatena os dígitos de
dois números'': $1000 \concat 123 = 1000123$, $4 \concat 22 \concat 0
= 422$, etc. Na questão 3 você vai ter que usar esta operação
informalmente, e na questão 4 você vai ter que encontrar uma definição
formal para ela.



\bsk
\bsk

\noindent {\bf (1)} (0.5 pontos). Digamos que a seqüência $(d_0, d_1,
d_2, \ldots)$ obedece
%
$$d_0=0 ∧(ýnÝ\N.d_{n+1}=10d_n+9).$$
%
Calcule $d_1$, $d_2$, $d_3$, $d_4$.

\bsk

\noindent {\bf (2)} (2.0 pontos). Use a função `$\myif$' para definir
formalmente uma seqüência $(k_0, k_1, k_2, \ldots) = (0, 9, \ldots, 9,
99, \ldots, 99, 999, \ldots, 999, \ldots)$ tal que $k_1=9$, $k_9=9$,
$k_{10}=99$, $k_{99}=99$, $k_{100}=999$, etc; mostre que a
sua definição funciona.

\newpage

\noindent {\bf (3)} (2.5 pontos). A seqüência de conjuntos $(A_0, A_1,
A_2, \ldots)$ é definida por:
%
$$\begin{array}{rcl}
  A_0 &=& \{2\} \\
  A_{n+1} &=& A_n \; þ \\
           && \sst{1 \concat a \concat 4}{a Ý A_n} \; þ \\
           && \sst{a \concat 3 \concat b}{a Ý A_n, b Ý A_n}. \\
  \end{array}
$$
%
Calcule $A_1$ e $A_2$.

\bsk

\noindent {\bf (4)} (2.0 pontos). Use a seqüência dos `$k_n$'s da
questão 2 para definir formalmente $a \concat b$.

\bsk

\noindent {\bf (5)} (4.0 pontos). Considere a relação $R \subseteq
A_1×A_2$ definida por: $aRc$ se e só se
%
$$(1 \concat a \concat 4 = c) ∨ (ÎbÝA_1.(a \concat 3 \concat b = c)).$$
%
Represente $R$ como conjunto e graficamente. $R$ é uma função? E $R^{-1}$?






% (find-LATEX "2009-2-MD-prova-2.tex")

\bsk
\bsk
\bsk
\bsk
\bsk
\bsk


A prova é para ser feita em duas horas, sem consulta.

Responda claramente e justifique cada passo.

Lembre que a correção irá julgar o que você escreveu, e

que é impossível ler o que você pensou mas não escreveu.

Lembre que a resposta esperada para cada questão não é só

uma fórmula ou um número --- a ``resposta certa'' é um

raciocínio claro e convincente, com todos os detalhes

necessários, mostrando que você sabe traduzir corretamente

entre as várias linguagens (português, diagramas,

matematiquês, etc) e explicando o que você está fazendo

quando for preciso.

Você pode fazer perguntas ao professor durante a prova,

mas não pode confiar nas respostas.

Cuidado: respostas parecidas demais com as de colegas

podem fazer com que sua prova seja anulada!

Dica: {\sl confira as suas respostas!}

\ssk

{\bf Boa prova!}



% Foo:
% \POSICAO,
% \MATRICULA,
% \EMAIL,
% \ALUNO.




%*