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

\par Matemática discreta
\par PURO-UFF - 2009.1
\par Notas sobre construção indutivas e indução estrutural
\par (Versão para discussão, só pras pessoas não precisarem
\par copiar as definições e figuras)
\par 13/maio/2009
\msk


{\bf Um exemplo simples de indução estrutural}

Considere a seqüência de subconjuntos de $\N$ definida por:

$A_0 = \emptyset$

$A_1 = \sof{1,2}$

% $A_{n+1} = A_n \cup \sst{10a+b}{aİA_n, bİ\{1,2\}}$
%
% ou, equivalentemente:

$A_{n+1} = A_n \cup \sst{10a+1}{aİA_n} \cup \sst{10a+2}{aİA_n}$

Os próximos termos da seqüência são:

$A_2 = \sof{1,2,11,12,21,21}$

$A_3 = \sof{1,2,11,12,21,21,111,112,121, \ldots, 212, 221, 222}$

Essa seqüência é ``crescente'' --- $ınİ\N.\,A_n \subsetneq A_{n+1}$.

Defina:

$A = \bigcup_{nİ\N} A_n$

Fato (intuitivamente verdadeiro --- mas ainda não sabemos provar isto!):

$A = \sst{aİ\N}{\text{a expansão decimal de $k$ só tem `1's e `2's}}$.

\msk

Uma prova de que $2122İA$:

%:
%:  -----
%:  2İA_1
%:  ----------
%:  2·10+1İA_2
%:  ----------
%:  21İA_2
%:  ---------------
%:  21·10+2İA_3
%:  ---------------
%:  212İA_3
%:  -----------------
%:  212·10+2İA_4
%:  -----------------
%:  2122İA_4
%:  ----------------------
%:  2122İ\bigcup_{nİ\N}A_n
%:  ----------------------¯{(def)}
%:      2122İA
%:
%:      ^2122-in-A
%:
$$\ded{2122-in-A}$$

Para provarmos que um certo número --- por exemplo, 21321 --- não
pertence a $A$ precisamos de uma técnica especial: precisamos
``desmontar'' o 21321, retirando um dígito do final dele de cada vez,
até encontrarmos um número --- o 213 --- que ``evidentemente'' não
pode pertencer a nenhum $A_n$... mais precisamente: $213 \ni A_1$
porque $213 \neq 1$ e $213 \neq 2$, e o 213 não é nem da forma $10n+1$
nem da forma $10n+2$...

Para mostrarmos que

$A = \sst{aİ\N}{\text{a expansão decimal de $k$ só tem `1's e `2's}}$

temos que mostrar que qualquer número formado só por `1's e `2's está
em $A$ --- fizemos isto acima pro 2122 --- e temos que mostrar que
números com outros dígitos que não 1 e 2 não estão em $A$.

% \msk

\newpage

Um caso mais interessante, usando strings e concatenação:

\def\str#1{\text{``\texttt{#1}''}}

% $E_0 = \emptyset$

$E_0 = \sof{\str{a}, \str{b}, \str{0}, \str{1}, \str{2}, \str{3}}$

$E_{n+1} = E_n \cup \sst{\str{(}..\aa..\str{+}..\bb..\str{)}}{\aa,\bbİE_n}$

$\qquad\qquad\;\;\;\,\, \cup \sst{\str{(}..\aa..\str{*}..\bb..\str{)}}{\aa,\bbİE_n}$

$E = \bigcup_{nİ\N} E_n$

Uma prova de que $\str{((0+1)*(2*(3+2)))}İE$:

%:
%:                                               \str{3}İE_0  \str{2}İE_0
%:                                               ------------------------(+)
%:  \str{0}İE_0   \str{1}İE_0      \str{2}İE_0      \str{(3+2)}İE_1
%:  -------------------------(+)   --------------------------------(*)
%:      \str{(0+1)}İE_1               \str{(2*(3+2))}İE_2
%:      -------------------------------------------------(*)
%:            \str{((0+1)*(2*(3+2)))}İE_3
%:            ---------------------------
%:             \str{((0+1)*(2*(3+2)))}İE
%:
%:             ^+*
%:
$$\ded{+*}$$

\msk

O que realmente importa aqui é que existe essentialmente uma só

``prova'' (em árvore, no formato certo, etc) de que um certo

string está em $E$; se lermos esta prova de baixo para cima

veremos que ela ``desmonta'' o string, e ela mostra a sua

construção a partir de strings menores -- a sua ``estrutura''.

\bsk

Exercícios (grandes, vamos passar boa parte da aula discutindo-os):

O conjunto $E$ definido acima pode ser visto como o conjunto

das ``árvores'' com `*'s e `+'s nos nós e `0's, `1's, `2's e `3's

nas ``folhas'' --- mas estas ``árvores'' estão representadas

linearmente, como strings...
%: 
%:           3  2
%:           ----
%:  0  1  2   +
%:  ----  -----
%:   +      *
%:   --------
%:      *
%:
%:      ^tree
%:
$$\str{((0+1)*(2*(3+2)))} \equiv \left(\cded{tree}\right)$$


Cada uma destas ``árvores'' em $E$ pode ser vista como uma

expressão aritmética.

$*$ Defina a ``altura'' de uma expressão em $E$.

$*$ Defina o ``valor'' de uma expressão em $E$.

$*$ Defina o ``comprimento'' de uma expressão em $E$.

$*$ Defina o ``conectivo central'' de uma expressão em $E$.

$*$ Mostre como converter entre os formatos ``linear'' e ``árvore''.

\msk

% (Não tive tempo de criar o código em LaTeX pra 






%*

\end{document}

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