|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (find-angg "LATEX/2010-1-MD-exercs-P4.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010-1-MD-exercs-P4.tex && latex 2010-1-MD-exercs-P4.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010-1-MD-exercs-P4.tex && pdflatex 2010-1-MD-exercs-P4.tex"))
% (eev "cd ~/LATEX/ && Scp 2010-1-MD-exercs-P4.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2010-1-MD-exercs-P4.dvi"))
% (find-dvipage "~/LATEX/2010-1-MD-exercs-P4.dvi")
% (find-pspage "~/LATEX/2010-1-MD-exercs-P4.pdf")
% (find-pspage "~/LATEX/2010-1-MD-exercs-P4.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2010-1-MD-exercs-P4.ps 2010-1-MD-exercs-P4.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2010-1-MD-exercs-P4.ps 2010-1-MD-exercs-P4.dvi && ps2pdf 2010-1-MD-exercs-P4.ps 2010-1-MD-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-MD-exercs-P4.pdf" (ee-twupfile "LATEX/2010-1-MD-exercs-P4.pdf") 'over)
% (ee-cp "~/LATEX/2010-1-MD-exercs-P4.pdf" (ee-twusfile "LATEX/2010-1-MD-exercs-P4.pdf") 'over)
% (find-twusfile "LATEX/" "2010-1-MD-exercs-P4")
% http://angg.twu.net/LATEX/2010-1-MD-exercs-P4.pdf
\documentclass[oneside]{book}
\usepackage[brazil]{babel}
\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 2010-1-MD-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}}}
Matemática Discreta - 2010jul13
Exercícios de preparação para VS extra -
{\bf versão preliminar}
\bsk
%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")
Uma das idéias cruciais de Matemática Discreta --- e que não é
explicada claramente no livro do Scheinerman --- é a idéia de {\sl
redução}: uma seqüência (válida) de reduções nos dá um modo de
calcular o valor de uma expressão. Nós denotamos ``$\aa$ pode ser
reduzido a $\bb$ (em um passo)'' por $\aa \squigto \bb$. Por exemplo,
para calcularmos o valor de $2·3+4·5$ nós seguimos qualquer uma das
seqüências de redução no diagrama abaixo,
%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|?
\bsk
Podemos usar a idéia de subexpressões para nos ajudar a entender {\bf
todos} os tipos de expressões em matematiquês que apareceram no
curso. Por exemplo:
%
$$\def\RR#1#2{\u{\u{#1}\,\u{R}\,\u{#2}}}
\u{ý\u{a},\u{b},\u{c}Ý\u{A}.\;\u{\u{\RR ab ∧ \RR bc} \to \RR ac}}
$$
%
onde o $a$, o $b$ e o $c$ no `$ý\u{a},\u{b},\u{c}Ý\u{A}$' são {\sl
nomes de variáveis} (lembre que coisas como `$Î2Ý\N$' e
`$ý\{2,3\}\subset \N$' são inadmissíveis, são erros conceituais
gravíssimos, e que pessoas que escreveram coisas assim apesar de todos
os avisos mereciam ter suas provas anuladas... vou dar mais detalhes
sobre ``nomes de variáveis'' na próxima versão da lista).
\newex Digamos que $A = \{1,2,3,4\} \subset \N$. Identifique quais das
subexpressões de
%
$$\def\RR#1#2{\u{\u{#1}\,\u{R}\,\u{#2}}}
\u{ý\u{a},\u{b},\u{c}Ý\u{A}.\;\u{\u{\RR ab ∧ \RR bc} \to \RR ac}}
$$
%
têm valores que são números, quais têm valores que são conjuntos,
quais têm valores que são valores de verdade, etc.
\newex Faça o mesmo para todas as subexpressões das expressões em
matematiquês que aparecem nos enunciados da P3. {\sl Anote todas as
suas dúvidas e discuta-as com seus colegas.}
\bsk
Digamos que $B \subset \{0,1,2,3,4,5,6,7,8,9\}$; temos 1024 `$B$'s
possíveis. Vamos nos restringir aos `$B$'s que obedecem as condições
abaixo:
(i) $B \subset \{0,1,2,3,4,5,6,7,8,9\}$,
(ii) $3 Ý B$,
\def\II#1#2{(#1ÝB \to #2ÝB)}
(iii) $\II03 ∧ \II14 ∧ \II25 ∧ \II36 ∧ \II47 ∧ \II58 ∧ \II69$.
\msk
\newex Encontre três valores para $B$ diferentes que obedeçam as
condições (i), (ii), (iii) acima.
\bsk
Dizemos que um número $n$ ``é da forma $4k+1$'' quando existe um valor
para $kÝ\Z$ tal que $n=4k+1$. Os inteiros 5, 21 e -7 são da forma
$4k+1$; os números 2, $\frac34$ e $\pi$ não são. Expressões como ``xxx
da forma blá'' são muito comuns em linguagem matemática. A proposição
$1>2 ∧ 2>0 \to 1>0$ ``é da forma $P \to Q$'' (para $P = (1>2 ∧ 2>0)$ e
$Q=(1>0)$); a proposição $ýxÝA.x=2∧x=3$ não é da forma $P∧Q$, mas
contém uma subexpressão da forma $P∧Q$.
\msk
Temos muitos modos diferentes de escrever a prova de que se $B$
obedece as condições (i), (ii) e (iii) acima, então $9ÝB$. Vamos ver
alguns modos (mais precisamente: alguns ``sistemas dedutivos'') nos
quais podemos caracterizar precisamente o que é uma prova e o que não
\'e, usando a idéia de que cada passo tem que ser de uma das poucas
formas permitidas. Como a definição {\sl precisa} de ``sistema
dedutiva'' é difícil (porque é geral demais), vamos começar com alguns
exemplos.
A árvore abaixo é uma prova de $9ÝB$ num sistema dedutivo chamado
``dedução natural'':
%:
%: (ii) (iii)
%: ---- --------
%: 3ÝB 3ÝB->6ÝB (iii)
%: --------------MP --------
%: 6ÝB 6ÝB->9ÝB
%: ---------------------MP
%: 9ÝB
%:
%: ^9inB-nd
%:
$$\ded{9inB-nd}$$
Cada barra dela é de uma destas formas:
%:
%: (ii) (iii) P P->Q
%: ---- ----- -------MP
%: 3ÝB #1ÝB->#2ÝB Q
%:
%: ^ii ^^2-iii ^MP
%:
$$\ded{ii} \qquad
\dediii03 \quad
\dediii14 \quad
\dediii25
$$
$$
\dediii36 \quad
\dediii47 \quad
\dediii58
$$
$$\dediii69 \qquad
\ded{MP}
$$
% (find-kopkadaly4page (+ 12 136) "underbrace")
% Substituição de iguais por iguais
% Associatividade
% Regras derivadas
% Soma com certa precisão não é associativa
% Problemas sobre os Bs
% Parsing de proposições sobre Bs
% set formation
%
% (find-books "__comp/__comp.el" "hopcroft")
% (find-hopcroftmupage (+ 16 28) "1.5.1. Alphabets")
%*
\end{document}
% Local Variables:
% coding: raw-text-unix
% ee-anchor-format: "«%s»"
% End: