|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (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: