% (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:
