Warning: this is an htmlized version!
The original is across this link,
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 $23+45$ 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= 23+45
%D    E1 .tex= 23+20
%D    E2 .tex= 6+45
%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, $23+45$,
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 $23+45$ temos que primeiro calcular os
valores de $23$ e $45$ 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             23+45  23+20  223  46
%D 2D                           
%D 2D  +30 145 275    6+45   6+20   26
%D 2D                           
%D 2D  +30 70   235     105    50
%D 2D
%D (( 23+45 23+20 ~> 23+20 6+20 ~> 6+20 26 ~>
%D    23+45 6+45  ~> 6+45  6+20 ~> 
%D    23+20  223   .> 223   46   ~>
%D    23+45 275  .> 275  145 ~> 145 70 ~>
%D                      275  235 ~> 235 70 ~>
%D    6+45   105   .> 105   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{23}+45}$ 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'=MM$

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

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

Por exemplo, $(2+M+7)T(2+MM+7)$ é verdade --- pela condição (iii),
com $\aa=2+$, $\bb=M$, $\bb'=MM$, $\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+N5)$. Mostre que
$(A)T^*(23+45)$.

%:*+*{+}*
%:**{}*

%D diagram subst-1
%D 2Dx     100     +40      +40      +50    +40    +40
%D 2D  100                          M+N5  A+N5
%D 2D
%D 2D  +20                          M+NN  A+NN
%D 2D
%D 2D  +20                          M+MN  A+MN
%D 2D
%D 2D  +20                 MM+MM  M+MM  A+MM    
%D 2D                                              
%D 2D  +20 2M+M   NM+M    MM+M    M+M    A+M     
%D 2D                                              
%D 2D  +20 2M+A   NM+A    MM+A    M+A    A+A    A
%D 2D
%D (( M+N5   A+N5 <=
%D    M+NN   A+NN <=
%D    M+MN   A+MN <=
%D    MM+MM M+MM <=  M+MM A+MM <=
%D    2M+M   NM+M <=  NM+M MM+M <=  MM+M M+M <=  M+M A+M <=
%D    2M+A   NM+A <=  NM+A MM+A <=  MM+A M+A <=  M+A A+A <=  A+A A <=
%D
%D    2M+M 2M+A <=                                                                    
%D    NM+M NM+A <=                                                                 
%D    MM+MM MM+M <=  MM+M MM+A <=                                               
%D    M+N5 M+NN <=  M+NN M+MN <=  M+MN M+MM <=  M+MM M+M <=  M+M M+A <=       
%D    A+N5 A+NN <=  A+NN A+MN <=  A+MN A+MM <=  A+MM 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 $23+45$, 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(23+45)$ é 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^* (23+45)$ na
qual um dos sublinhados esteja nesta posição: $2\u{3\,+}\,45$. Porque
você não consegue?

\newex Tente encontrar uma árvore de parsing para $A T^* (23+45)$ 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 $678$, uma
com sublinhados nestas posições, $\u{\u{67}8}$, e outra com
sublinhados nestas: $\u{6\u{78}}$.

\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{(#1B \to #2B)}

 (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 $xA.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 $9B$. 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 $9B$ num sistema dedutivo chamado
``dedução natural'':
%:
%:  (ii)    (iii)
%:  ----  --------
%:  3B   3B->6B      (iii)
%:  --------------MP   --------
%:        6B          6B->9B
%:        ---------------------MP
%:                   9B
%:
%:                   ^9inB-nd
%:
$$\ded{9inB-nd}$$

Cada barra dela é de uma destas formas:
%:
%:  (ii)   (iii)        P  P->Q
%:  ----   -----        -------MP
%:  3B    #1B->#2B      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: