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

\documentclass[oneside]{article}
\usepackage[latin1]{inputenc}
\usepackage[x11names]{xcolor} % (find-es "tex" "xcolor")
\usepackage[colorlinks]{hyperref} % (find-es "tex" "hyperref")
\usepackage{edrx08}       % (find-dn4ex "edrx08.sty")
%L process "edrx08.sty"  -- (find-dn4ex "edrx08.sty")
\input edrxheadfoot.tex   % (find-dn4ex "edrxheadfoot.tex")
\begin{document}

%\input 2010-1-C2-exercs-P4.dnt

%
% (eedn4-51-bounded)

% (find-es "tex" "newcounter")
\newcounter{myex}
\long\def\newex{
  \par\noindent
  \refstepcounter{myex}
  {\bf (\arabic{myex})}
  }

% (find-kopkadaly4page (+ 12 136) "underbrace")

\def\u#1{\und{#1}}
\def\uu#1{#1}
\def\pp{\ensuremath{\mathbin{+\hskip-.75ex+}}}
\def\myfparbox#1{\fbox{\parbox{10cm}{#1}}}
\def\eqn#1{\overset{\scriptscriptstyle #1}{=}}
\def\eqnt#1{\overset{\scriptscriptstyle{\text{#1}}}{=}}

\def\intxx#1#2#3{\int#3\,dx}
\def\INTXX#1#2#3{#3}

\def\intx#1#2#3{\int_{x=#1}^{x=#2}#3\,dx}
\def\INTX#1#2#3{\left.#3\right|_{x=#1}^{x=#2}}

\def\INTXX#1#2#3{#3}
\def\INTxx#1#2#3{#3}
\def\INTxx#1#2#3{\left.#3\right|_{x=#1}^{x=#2}}
\def\intxx#1#2#3{\int_{x=#1}^{x=#2}#3\,dx}
\def\inttt#1#2#3{\int_{t=#1}^{t=#2}#3\,dt}
\def\intab#1{\intxx ab{#1}}
\def\INTab#1{\INTxx ab{#1}}

\def\intx #1{\int#1\,dx}
\def\intt #1{\int#1\,dt}




Cálculo 2 - 2010.1

Exercícios de preparação para VS extra

{\bf Versão preliminar} - veja a data no rodapé

\url{http://angg.twu.net/2010.1-C2.html}

\bsk
\bsk


Esta lista de exercícios é sobre {\sl como você pode encontrar e
  demonstrar as suas próprias formulas de integração}, e como escrever
as suas demonstrações de um modo {\sl confiável} e {\sl claro}.

Pense que você está escrevendo para a sua tia, que sabe muito pouco
sobre integração... ela, como qualquer pessoa sensata, sabe que essa
história de Matemática é uma grande enganação: as pessoas escrevem
fórmulas imponentes pra impressionar os outros e pra convencê-los de
coisas que em geral são {\sl falsas}. Ela --- a sua tia --- só
acredita em ``demonstrações'' muito bem explicadas, nas quais ela
entende cada passo e vê que cada passo é uma aplicação simples de uma
das poucas regras que ela aceita. Ela fez o doutorado dela em
Geometria Algébrica na década de 70 e desde que você tem 10 anos você
tenta dizer pra ela: ``tia, isso aqui é VERDADE! Tá no livro!!!'', e
ela te responde que as pessoas como você só dormem tranqüilas porque
não sabem como são feitas as salsichas, as leis, os livros e as letras
de Axé Music...






%     _          _            
%    / \   _ __ | |_ ___  ___ 
%   / _ \ | '_ \| __/ _ \/ __|
%  / ___ \| | | | ||  __/\__ \
% /_/   \_\_| |_|\__\___||___/
%                             


\subsection*{Antes de começar...}

Encontre no seu livro de Cálculo uma tabela com as ``regras
satisfeitas por integrais definidas'' (obs: no Thomas, 11ª ed., essa
tabela está no capítulo ``A integral definida'', e as regras se chamam
``ordem de integração'', ``integral de largura 0'', ``multiplicação
por constante'', ``soma e diferença'', ``aditividade'',
``desigualdades max/min'' e ``dominação'').

Em alguns dos exercícios você vai ter que mostrar como calcular certas
integrais {\sl usando apenas estas regras}, ou usando elas e o mínimo
possível a mais, e {\sl justificando cada igualdade} --- ou seja,
indicando que regra justifica cada `='.

Um exemplo: se $f,g:\R \to \R$ são funções deriváveis, então pela
regra do produto temos $(f(x)g(x))' = f'(x)g(x) + f(x)g'(x)$; pela
definição de primitiva, $f(x)g(x) = \int f'(x)g(x) + f(x)g'(x)\,dx$;
para quaisquer $a,bÝ\R$, pelo TFC2, $\INTab{(f(x)g(x))} =
\intab{f'(x)g(x) + f(x)g'(x)}$; pela regra da soma de integrais
definidas, $\intab{f'(x)g(x) + f(x)g'(x)} = \intab{f'(x)g(x)} +
\intab{f(x)g'(x)}$, e reordenando os termos desta igualdade,
$\intab{f(x)g'(x)} = \INTab{(f(x)g(x))} - \intab{f'(x)g(x)}$.

A sua tia não faz questão de que todas as justificativas sejam
escritas em Português. Pra ela isto aqui,
%
$$\begin{array}{rcl}
  (f(x)g(x))' &\eqnt{(r.prod)}& f'(x)g(x) + f(x)g'(x) \\
  f(x)g(x) &\eqnt{(def prim)}& \int f'(x)g(x) + f(x)g'(x)\,dx \\
  \INTab{(f(x)g(x))} % &\eqnt{(TFC2)}& \intab{(f(x)g(x))'} \\
                     &\eqnt{(TFC2)}& \intab{f'(x)g(x) + f(x)g'(x)} \\
                     &\eqnt{(soma)}& \intab{f'(x)g(x)} + \intab{f(x)g'(x)} \\
  \intab{f(x)g'(x)}  &=& \INTab{(f(x)g(x))} - \intab{f'(x)g(x)} \\
  \end{array}
$$
%
é tão aceitável quanto a explicação em Português do parágrafo
anterior, e é visualmente mais claro.

\msk

\newex Digamos que a sua tia ainda não acredite na fórmula de
integração por partes. Mostre, de um modo que seja convincente pra
ela, que $\intab{xe^x} = \INTab{(xe^x)} - \intab{e^x}$.

\newex Convença-a de que $\int xe^x\,dx = xe^x - \int e^x\,dx$. (Aqui
você vai ter que ser BEM cuidadoso com o seu argumento --- ela
desconfia em dobro de qualquer argumento envolvento integrais
indefinidas).

\newex Convença-a de que $\intab{f(x)g''(x)} = \INTab{(f(x)g'(x))} +
\INTab{(f'(x)g(x))} - \intab{f''(x)g(x)}$.

\newex Convença-a de que $\intxx23{\sen 2x} = \frac12 \intxx46{\sen x}$.

\msk

% (find-books "__analysis/__analysis.el" "thomas")
% (find-thomas11-1page (+  58  347)     "Rules satisfied by definite integrals")
% (find-thomas11-1page (+  58  353)     "Using properties and known values to find other integrals")

Outra coisa: lembre da definição de ``boa primitiva'' do
Malta/Pesco/Lopes --- $F(x) = \inttt0x{e^{2x}}$ é uma primitiva para
$e^{2x}$, mas não é uma ``boa primitiva'' porque ainda envolve o sinal
de integral; $G(x) = \frac12 e^{2x} + 42$ é uma ``boa primitiva'' para
$e^{2x}$. Em alguns (poucos) dos exercícios abaixo encontrar uma
``primitiva'' (``qualquer'') vai ser suficiente; mas na maior parte
deles você vai precisar encontrar uma ``boa primitiva''.



%  ____                  _             __  _ _     _           
% |  _ \ __ _ _ __ ___  (_)_ ____   __/_/_| (_) __| | __ _ ___ 
% | |_) / _` | '__/ __| | | '_ \ \ / / _` | | |/ _` |/ _` / __|
% |  _ < (_| | |  \__ \ | | | | \ V / (_| | | | (_| | (_| \__ \
% |_| \_\__, |_|  |___/ |_|_| |_|\_/ \__,_|_|_|\__,_|\__,_|___/
%       |___/                                                  

\section{Regras inválidas}

As ``regras'' abaixo são todas inválidas: elas valem em alguns casos,
mas nem sempre, e uma ``demonstração'' que use qualquer uma destas
regras provavelmente chega a conclusões erradas (obs: na década de 80,
quando a sua tia dava aula na extinta Faculdade Federal da Ilha das
Ostras, ela dava 0 numa prova imediatamente se encontrasse qualquer
aplicação de uma ``regra inválida'' nos desenvolvimentos).

Mostre porque cada uma das ``regras'' abaixo é inválida.

\msk

\newex $\sqrt{a+b} = \sqrt{a}+\sqrt{b}$
\newex $\sen(x+y) = \sen x + \sen y$
\newex $\cos(2x) = 2 \cos x$
\newex $\sqrt{a^2} = a$
% \newex $\sqrt{a}^2 = a$
\newex $\arcsen(\sen ) = $
% \newex $\sen(\arcsen s) = s$
\newex $\frac{a}{b} - \frac{a}{2b} = \frac{a}{b}$
\newex $\intx{f(x)g(x)} = \intx{f(x)}·\intx{g(x)}$
\newex $\intx{\frac{f(x)}{g(x)}} = \frac{\intx{f(x)}}{\intx{g(x)}}$
% \newex algumas questões envolvendo desigualdades





%  ____        __                                                  
% |  _ \  ___ / _|___   _ __   ___  _ __    ___ __ _ ___  ___  ___ 
% | | | |/ _ \ |_/ __| | '_ \ / _ \| '__|  / __/ _` / __|/ _ \/ __|
% | |_| |  __/  _\__ \ | |_) | (_) | |    | (_| (_| \__ \ (_) \__ \
% |____/ \___|_| |___/ | .__/ \___/|_|     \___\__,_|___/\___/|___/
%                      |_|                                         

\section{Definições por casos}

\def\mycases#1{\begin{cases}#1\end{cases}}
\def\quand#1#2{#1 & \text{quando $#2$} \\}


Vou dizer que uma função $f$ é {\sl definida por casos (com $n$
  casos)} quando a sua definição é da forma:
%
$$f(x) = \mycases{\quand{f_1(x)}{xÝI_1}
                  \quand{f_2(x)}{xÝI_2}
                    &\vdots\\
                  \quand{f_n(x)}{xÝI_n}
                 }
$$
%
onde $I_1, I_2, \ldots, I_n$ são intervalos (disjuntos).

A função $|·|$ tem uma definição por casos com dois casos;
funções-escada e funções poligonais, que vimos bastante durante o
curso, também são definidas por casos.

Vou dizer que uma definição por casos é {\sl pura} quando as
expressões para $f_1, \ldots, f_n$ não envolvem nenhuma função
definida por casos. Por exemplo, esta definição não é pura:
%
$$g(x) = \mycases{\quand{|x+2|}{xÝ(-,1)}
                  \quand{|x-3|}{xÝ[1,)}
                 }
$$

\newex Faça o gráfico da $g$.

\newex Encontre uma definição por casos pura para a função $g$ (você
vai precisar de pelo menos 4 casos).

\newex Faço o gráfico de $g¢g$.

\newex Encontre uma definição por casos pura para a função $g¢g$.

\msk

Se $f$ e $g$ são definidas por casos e suas definições são puras, é
fácil encontrar uma definição por casos pura para $f+g$: a gente
primeiro aumenta o número de intervalos em cada uma das definições
para que os intervalos fiquem iguais, depois soma as definições em
cada intervalo.

\msk

\newex Faça o gráfico de $|x|+|x-2|$.

\newex Encontre uma definição por casos pura para $|x|+|x-2|$.

\newex Se
%
$$f(x) = \mycases{\quand{f_1(x)}{xÝ(-,0)}
                  \quand{f_2(x)}{xÝ[0,2)}
                  \quand{f_3(x)}{xÝ[2,)}
                 }
  \quad
  \text{e}
  \quad
  g(x) = \mycases{\quand{g_1(x)}{xÝ(-,1]}
                  \quand{g_2(x)}{xÝ(1,3]}
                  \quand{g_3(x)}{xÝ(3,)}
                 }
$$
%
são definições por casos puras, encontre uma definição por casos pura
para $f+g$.

\msk

\newex Mostre como calcular $\intxx{-\pi}{\pi}{\sen |x|}$.





%  _       _           _                                _       
% (_)_ __ | |_      __| | ___    ___  ___  ___ __ _  __| | __ _ 
% | | '_ \| __|    / _` |/ _ \  / _ \/ __|/ __/ _` |/ _` |/ _` |
% | | | | | |_ _  | (_| |  __/ |  __/\__ \ (_| (_| | (_| | (_| |
% |_|_| |_|\__(_)  \__,_|\___|  \___||___/\___\__,_|\__,_|\__,_|
%                                                               

\section{Integrais de funções-escada}

\msk

Agora seja $f$ a função-escada dada por:
%
$$f(x) = \mycases{\quand{0}{xÝ(-,1)}
                  \quand{1}{xÝ[1,4)}
                  \quand{-2}{xÝ[4,5)}
                  \quand{0}{xÝ[5,)}
                 }
$$



\newex Mostre que $\intxx25{f(x)=0}$ usando apenas a definição da $f$
e as ``regras satisfeitas por integrais definidas''.

\newex Encontre uma definição por casos pura para $F(x) =
\inttt0x{f(t)}$. (Obs: lembre da definição de ``boa primitiva'' do
Malta/Pesco/Lopes!)

\newex Trace o gráfico de $y=\inttt0x{f(t)}$.

\newex Encontre uma definição por casos pura para $y=\inttt0x{f(t)}$.

\newex Encontre uma primitiva, $F$, para esta $f$ (ou seja: $F(x) =
\int f(x)\,dx$).

\newex Sejam:
%
$$f(x) = \mycases{\quand{f_1(x)}{xÝ(-,0)}
                  \quand{f_2(x)}{xÝ [0,2)}
                  \quand{f_3(x)}{xÝ [2,)}
                 }
  \quad
  \text{e}
  \quad
  F(x) = \mycases{\quand{\inttt0x{f_1(x)}}{xÝ(-,0)}
                  \quand{\inttt0x{f_2(x)}}{xÝ [0,2)}
                  \quand{\inttt0x{f_3(x)}}{xÝ [2,)}
                 }
$$

Mostre que a ``regra'' $F(x) = \intx{f(x)}$ é inválida.






\end{document}
















%  ____                                    
% | __ )  __ _  __ _ _   _ _ __   ___ __ _ 
% |  _ \ / _` |/ _` | | | | '_ \ / __/ _` |
% | |_) | (_| | (_| | |_| | | | | (_| (_| |
% |____/ \__,_|\__, |\__,_|_| |_|\___\__,_|
%              |___/              )_)      

\subsection*{Bagunça}

% Nestes exercícios você vai aprender a fazer contas passo a passo com
% todos os detalhes possíveis.

Vamos começar com um exemplo. Como $\int e^{x/2}\,dx = 2e^{2/x}$,
então, por integração por partes:

$$\def\intx#1#2#3{\int#3\,dx}
  \def\INTX#1#2#3{#3}
  \begin{array}{rcl}
  \intx02{x^5·e^{x/2}} &\eqn{(1)}& \INTX02{x^5 · 2e^{x/2}} - \intx02{5x^4 · 2e^{x/2}} \\
                       &\eqn{(2)}& \INTX02{x^5 · 2e^{x/2}} - (\INTX02{5x^4 · 4e^{x/2}} - \intx02{20x^3 · 4e^{x/2}}) \\
                       &\eqn{(3)}& \INTX02{x^5 · 2e^{x/2}} - \INTX02{5x^4 · 4e^{x/2}} + \intx02{20x^3 · 4e^{x/2}} \\
  \end{array}
$$

onde a passagem `$\eqn{(1)}$' usa a fórmula $\int fg'\,dx = fg - \int
f'g\,dx$ com $f(x)=x^5$ e $g(x)=e^{x/2}$, e a passagem `$\eqn{(1)}$'
usa a mesma fórmula, mas agora com $f(x)=5x^4$ e $g(x)=2e^{x/2}$, para
substituir $\intxx02{5x^4 · 2e^{x/2}}$ por $\INTXX02{5x^4 · 4e^{x/2}}
- \intxx02{20x^3 · 4e^{x/2}}$ dentro de uma expressão maior...

Se sabemos que $B = C - D$ então para qualquer valor de $A$ temos $A -
B = A - (C - D)$; a igualdade `$\eqn{(2)}$' usa esta idéia (exercício
trivial: para que valores de $A$, $B$, $C$, $D$?). Isto é um caso
particular de uma regra chamada ``substituição de iguais por iguais'',
que vai ser uma de nossas regras básicas.

Acrescentando algumas marcações na série de igualdades acima, temos:

$$\def\intx#1#2#3{\int#3\,dx}
  \def\INTX#1#2#3{#3}
  \def\ovx#1#2{\overbrace{#2}^{#1}}
  \def\undx#1#2{\underbrace{#2}_{#1}}
  \begin{array}{rcl}
  \intx02{\ovx{f}{x^5}·\ovx{g''}{e^{x/2}}} &\eqn{(1)}& \INTX02{x^5 · 2e^{x/2}} - \intx02{5x^4 · 2e^{x/2}} \\
                       &\eqn{(2)}& \INTX02{x^5 · 2e^{x/2}} - (\INTX02{5x^4 · 4e^{x/2}} - \intx02{20x^3 · 4e^{x/2}}) \\
                       &\eqn{(3)}& \INTX02{\undx{f}{x^5} · \undx{g'}{2e^{x/2}}} - \INTX02{\undx{f'}{5x^4} · \undx{g}{4e^{x/2}}} + \intx02{\undx{f''}{20x^3} · \undx{g}{4e^{x/2}}} \\
  \end{array}
$$



\bsk
\bsk

% (find-books "__analysis/__analysis.el" "thomas")

% Regras:
% TFC 1
% \bsk

\def\intx #1{\int#1\,dx}
\def\intxx#1#2#3{\int_{x=#1}^{x=#2}#3\,dx}
\def\INTXX#1#2#3{\left.#3\right|_{x=#1}^{x=#2}}

\newex (integral de uma função-escada)
\newex (substituição trigonométrica passo a passo)
\newex (várias regras sobre integrais de funções descontínuas)

\bsk

Vários dos exercícios desta lista vão ser da forma ``demonstre que
$\text{expr}_1 = \text{expr}_2$''. As demonstrações vão ser por séries
de igualdades: $\text{expr}_1 = \aa = \bb = \ldots = Ï =
\text{expr}_2$, onde cada `=' é uma aplicação de uma das regras
básicas --- ou de alguma regra que você demonstrou que vale num
exercícios anterior.

{\sl Preciso listar as ``regras básicas'' permitidas, dar exemplos de
  como responder, dar alguns exercícios do tipo ``diga que regra foi
  usada em cada um dos `='s desta demonstração'' e alguns exercícios
  da forma ``complete os detalhes da demonstração abaxio, introduzindo
  passos extras para que cada igualdade seja a aplicação de uma regra
  só''.}





% Quais são os passos válidos?


%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")

%L forths["<~"] = function () pusharrow("<~") end
%L forths["~>"] = function () pusharrow("~>") end


%D diagram red-1
%D 2Dx     100   +50  +40
%D 2D  100 E0    E1
%D 2D
%D 2D  +30 E2    E3   E4
%D 2D
%D (( E0 .tex= 2·3+4·5
%D    E1 .tex= 2·3+20
%D    E2 .tex= 6+4·5
%D    E3 .tex= 6+20
%D    E4 .tex= 26
%D    E0 E1 ~>
%D    E0 E2 ~> E1 E3 ~>
%D    E2 E3 ~> E3 E4 ~>
%D ))
%D enddiagram
%D
$$\diag{red-1}$$



Podemos marcar as ``subexpressões'' da expressão original, $2·3+4·5$,
sublinhando-as:
%
$$\u{\u{\u{2}·\u{3}}+\u{\u{4}·\u{5}}}$$

Vamos interpretar estes sublinhados como uma espécie de parênteses ---
o primeiro significado que vamos dar para eles vai ser que eles vão
nos dizer como calcular o valor de uma expressão maior a partir de
expressões menores. Por exemplo, em
$\u{\u{\uu{2}·\uu{3}}+\u{\uu{4}·\uu{5}}}$ eles dizem que para
calcularmos o valor de $2·3+4·5$ temos que primeiro calcular os
valores de $2·3$ e $4·5$ e depois somar os resultados.

Repare que podemos aumentar o diagrama anterior incluindo seqüências
de reduções {\sl erradas}, que dão resultados errados:
%
%D diagram red-2
%D 2Dx     100   +35      +45    +50    +40   +35
%D 2D  100             2·3+4·5  2·3+20  2·23  46
%D 2D                           
%D 2D  +30 14·5 2·7·5    6+4·5   6+20   26
%D 2D                           
%D 2D  +30 70   2·35     10·5    50
%D 2D
%D (( 2·3+4·5 2·3+20 ~> 2·3+20 6+20 ~> 6+20 26 ~>
%D    2·3+4·5 6+4·5  ~> 6+4·5  6+20 ~> 
%D    2·3+20  2·23   .> 2·23   46   ~>
%D    2·3+4·5 2·7·5  .> 2·7·5  14·5 ~> 14·5 70 ~>
%D                      2·7·5  2·35 ~> 2·35 70 ~>
%D    6+4·5   10·5   .> 10·5   50   ~>
%D    
%D ))
%D enddiagram
%D
$$\diag{red-2}$$

\newex Encontre um modo de converter entre sublinhados e seqüências de
reduções. Quais são as seqüências de reduções (isto é, caminhos no
diagrama acima) correspondentes a $\u{\u{2·\u{3+4}}·5}$ e
$\u{2·\u{\u{3+4}·5}}$? Os dois caminhos correspondentes a
$\u{\u{2·3}+4·5}$ dão o mesmo resultado?

\newex Podemos considerar que cada ``+'' no diagrama acima representa
um ``8'', cada ``$·$'' representa um ``9'' (como na P1), e que $\aa
\diagxyto/~>/<100> \bb$ quer dizer $\aa R \bb$ e $\aa
\diagxyto/.>/<100> \bb$ quer dizer $\aa S \bb$; então $S =
\{(2839485,28785), \, (283920,2823), \, (69485,1085)\} \subset \N^2$.
Escreva $R \subset \N^2$ como conjunto.

\newex Reescreva o diagrama acima trocando os `$·$'s e `+'s por `8's e
`9's e use-o para representar o fecho transitivo de $R$ (vamos chamar
o fecho transitivo de ``$R^+$''). Sugestão: use um terceiro tipo de
seta, $\aa \to \bb$, para representar os pares que só pertencem a
$R^+$.

\newex $R^+ \bsl R$ é um conjunto de pares, e portanto uma relação.
$28785(R^+ \bsl R)70$ é verdade? E $28785(R^+ \bsl R)2835$?

\bsk

\myfparbox{Releia a seção 1.5 do Hopcroft/Ullman/Motwani (esta seção
  se chama ``The Central Concepts of Automata Theory'' na
  edição em Inglês).}

\bsk

Na seção 1.5 do Hopcroft/Ullman/Motwani aparecem as noções de {\sl
  alfabeto} e de {\sl palavra}. Se $Æ$ é um alfabeto, então $Æ^+$ é o
conjunto das palavras de comprimento $\ge 1$ formadas por ``letras''
de $Æ$, e $Æ^*$ é o conjunto das palavras de comprimento $\ge 0$
formadas por letras de $Æ$. Se $Æ=\{0,1,2,3,4,5,6,7,8,9\}$, então $\N
\subset Æ^+$, mas $Æ^+$ tem palavras que parecem com números naturais
escritos errado --- por exemplo, 04321. Em $Æ^*$ temos uma operação de
concatenação que é bem parecida com o ``\pp'' que usamos no curso;
$Æ^*$ é um monóide, o seu elemento neutro é a palavra de comprimento
0, que o H/U/M denota por $\ee$. Ele escreve a concatenação ``direto''
(mais formalmente: ``por justaposição'') --- $\aa\bb$ ao invés de
$\aa\pp\bb$.

\newex Se $Æ=\{4,5\}$, calcule $Æ^2$, $Æ^2þÆ^1$, $Æ^2þÆ^1þÆ^0$.

\newex Encarando 004 como um elemento de $Æ^*$, calcule $004^3$ e
$004^0$.

\newex Seja $A=\{004,5\} \subset Æ^*$. Calcule $A^2$.

\bsk

Vamos aumentar o nosso alfabeto um pouco. A partir de agora $Æ$ vai
ser:
%
$$Æ=\{0,1,2,3,4,5,6,7,8,9,+,·,N,M,A\}$$
%
e as relações $R$ e $S$ da página anterior vão passar a ser $R,S
\subseteq (Æ^*)^2$. {\sl Com isto não vamos mais precisar trocar
  `$·$'s e `+'s por `8's e `9's.}

\msk

Vou definir uma relação nova, $T$, sobre $Æ^*$, assim: $xTy$ vai ser
verdade se e só se existem $\aa,\bb,\bb',\cc \in Æ^*$ tais que $x =
\aa\bb\cc$, $x = \aa\bb'\cc$, e $\bb$ e $\bb'$ obedecem alguma das
condições (i)--(iv) abaixo:

(i) $\bb=N$ e $\bb'Ý\N$ (lembre que $\N \subset Æ^*$)

(ii) $\bb=M$ e $\bb'=N$

(iii) $\bb=M$ e $\bb'=M·M$

(iv) $\bb=A$ e $\bb'=M$

(v) $\bb=A$ e $\bb'=A+A$

Por exemplo, $(2+M+7)T(2+M·M+7)$ é verdade --- pela condição (iii),
com $\aa=2+$, $\bb=M$, $\bb'=M·M$, $\cc=+7$.

\newex Vamos escrever $xTy$ como $x \funto y$. Para cada uma das setas
do diagrama abaixo justifique porque $xTy$ é verdade, dizendo qual das
regras (i)--(v) for utilizada e quem era $\aa$, $\bb$, $\bb'$, $\cc$.

\newex Pelo diagrama abaixo dá pra ver que $(A)T^*(A+N·5)$. Mostre que
$(A)T^*(2·3+4·5)$.

%:+{+}
%:·{·}

%D diagram subst-1
%D 2Dx     100     +40      +40      +50    +40    +40
%D 2D  100                          M+N·5  A+N·5
%D 2D
%D 2D  +20                          M+N·N  A+N·N
%D 2D
%D 2D  +20                          M+M·N  A+M·N
%D 2D
%D 2D  +20                 M·M+M·M  M+M·M  A+M·M    
%D 2D                                              
%D 2D  +20 2·M+M   N·M+M    M·M+M    M+M    A+M     
%D 2D                                              
%D 2D  +20 2·M+A   N·M+A    M·M+A    M+A    A+A    A
%D 2D
%D (( M+N·5   A+N·5 <=
%D    M+N·N   A+N·N <=
%D    M+M·N   A+M·N <=
%D    M·M+M·M M+M·M <=  M+M·M A+M·M <=
%D    2·M+M   N·M+M <=  N·M+M M·M+M <=  M·M+M M+M <=  M+M A+M <=
%D    2·M+A   N·M+A <=  N·M+A M·M+A <=  M·M+A M+A <=  M+A A+A <=  A+A A <=
%D
%D    2·M+M 2·M+A <=                                                                    
%D    N·M+M N·M+A <=                                                                 
%D    M·M+M·M M·M+M <=  M·M+M M·M+A <=                                               
%D    M+N·5 M+N·N <=  M+N·N M+M·N <=  M+M·N M+M·M <=  M+M·M M+M <=  M+M M+A <=       
%D    A+N·5 A+N·N <=  A+N·N A+M·N <=  A+M·N A+M·M <=  A+M·M A+M <=  A+M A+A <=       
%D ))
%D enddiagram
%D
$$\diag{subst-1}$$

\newex Podemos usar os sublinhados pra indicar ``de onde vem cada
subexpressão'' de uma palavra como $2·3+4·5$, e podemos usar
%
\def\uu#1{\u{\u{#1}}}
\def\uN#1{\underbrace{#1}_N}
\def\uM#1{\underbrace{#1}_M}
\def\uMN#1{\uM{\uN{#1}}}
\def\uAM#1{\uA{\uM{#1}}}
\def\uA#1{\underbrace{#1}_A}
%
$$\u{\uu{\uu{2}·\uu{3}} +
     \uu{\uu{4}·\uu{5}}}$$
%
como abreviação para:
%
$$\uA{\uAM{\uMN{2}·\uMN{3}} +
      \uAM{\uMN{4}·\uMN{5}}}$$

A partir destes diagrama com chaves --- vamos chamá-los de {\sl
 árvores de parsing} --- é fácil ver como obter uma série de
``substituições'' (cada $x \funto y$ é uma substituição de uma letra
por uma outra letra ou por uma expressão um pouco maior) que mostram
que $(A)T(2·3+4·5)$ é verdade.

\msk

Qualquer linguagem de programação usa idéias parecidas com as que
acabamos de ver para entender expressões e descobrir como
interpretá-las (você vai ver tudo isto em detalhes daqui a alguns
períodos, no curso de Linguagens Formais).

\newex Tente encontrar uma árvore de parsing que mostra que $M T^*
(3+4)$. Porque você não consegue?

\newex Tente encontrar uma árvore de parsing que mostra que $A T^*
(3+)$. Porque você não consegue?

\newex Tente encontrar uma árvore de parsing para $A T^* (2·3+4·5)$ na
qual um dos sublinhados esteja nesta posição: $2·\u{3\,+}\,4·5$. Porque
você não consegue?

\newex Tente encontrar uma árvore de parsing para $A T^* (2·3+4·5)$ na
qual um dos sublinhados esteja nesta posição: $2·\u{3+4}·5$. Porque
você não consegue?

\newex Encontre duas árvores de parsing diferentes para $6·7·8$, uma
com sublinhados nestas posições, $\u{\u{6·7}·8}$, e outra com
sublinhados nestas: $\u{6·\u{7·8}}$.

\msk

Se $M T^* x$, vamos dizer que $x$ é uma {\sl expressão multiplicativa};

se $A T^* x$, vamos dizer que $x$ é uma {\sl expressão aditiva}.

\msk

\newex Pegue algumas expressões em C e tente marcá-las com sublinhados
do modo que você imagina que o C faça. Como você acha que o C parseia
\verb|3+16-4-2+5|? E \verb|16/4/-2|? E \verb|2+3+4+5|? E
\verb|a=4-b=c+5|?




% (find-books "__analysis/__analysis.el" "thomas")
% (find-kopkadaly4page (+ 12 136) "underbrace")

%

\end{document}

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