% (find-angg "LATEX/2018-2-MD-defs-recursivas.tex")
% (defun c () (interactive) (find-LATEXsh "lualatex -record 2018-2-MD-defs-recursivas.tex"))
% (defun d () (interactive) (find-xpdfpage "~/LATEX/2018-2-MD-defs-recursivas.pdf"))
% (defun e () (interactive) (find-LATEX "2018-2-MD-defs-recursivas.tex"))
% (defun u () (interactive) (find-latex-upload-links "2018-2-MD-defs-recursivas"))
% (find-xpdfpage "~/LATEX/2018-2-MD-defs-recursivas.pdf")
% (find-sh0 "cp -v  ~/LATEX/2018-2-MD-defs-recursivas.pdf /tmp/")
% (find-sh0 "cp -v  ~/LATEX/2018-2-MD-defs-recursivas.pdf /tmp/pen/")
%   file:///home/edrx/LATEX/2018-2-MD-defs-recursivas.pdf
%               file:///tmp/2018-2-MD-defs-recursivas.pdf
%           file:///tmp/pen/2018-2-MD-defs-recursivas.pdf
% http://angg.twu.net/LATEX/2018-2-MD-defs-recursivas.pdf
\documentclass[oneside]{article}
\usepackage[colorlinks]{hyperref} % (find-es "tex" "hyperref")
%\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{pict2e}
\usepackage{color}                % (find-LATEX "edrx15.sty" "colors")
\usepackage{colorweb}             % (find-es "tex" "colorweb")
%\usepackage{tikz}
%
% (find-dn6 "preamble6.lua" "preamble0")
%\usepackage{proof}   % For derivation trees ("%:" lines)
%\input diagxy        % For 2D diagrams ("%D" lines)
%\xyoption{curve}     % For the ".curve=" feature in 2D diagrams
\catcode`\^^J=10                      % (find-es "luatex" "spurious-omega")
\directlua{dofile "dednat6load.lua"}  % (find-LATEX "dednat6load.lua")
\def\expr#1{\directlua{output(tostring(#1))}}
\def\eval#1{\directlua{#1}}
%
\usepackage{edrx15}               % (find-angg "LATEX/edrx15.sty")
\input edrxaccents.tex            % (find-angg "LATEX/edrxaccents.tex")
\input edrxchars.tex              % (find-LATEX "edrxchars.tex")
\input edrxheadfoot.tex           % (find-dn4ex "edrxheadfoot.tex")
\input edrxgac2.tex               % (find-LATEX "edrxgac2.tex")
%
\begin{document}

\catcode`\^^J=10

\directlua{dofile "edrxtikz.lua"} % (find-LATEX "edrxtikz.lua")
\directlua{dofile "edrxpict.lua"} % (find-LATEX "edrxpict.lua")
%L V.__tostring = function (v) return format("(%.3f,%.3f)", v[1], v[2]) end


%  ____                          _                
% |  _ \ ___  ___ _   _ _ __ ___(_)_   ____ _ ___ 
% | |_) / _ \/ __| | | | '__/ __| \ \ / / _` / __|
% |  _ <  __/ (__| |_| | |  \__ \ |\ V / (_| \__ \
% |_| \_\___|\___|\__,_|_|  |___/_| \_/ \__,_|___/
%                                                 
% «defs-recursivas» (to ".defs-recursivas")

\section{Definições recursivas}

Os livros de matemática e computação ``pra adultos'' às vezes fazem
umas definições ridiculamente curtas para sequências, funções e
conjuntos e aí supõem que o leitor vai entender essas definições. O
livro da Judith Gersting explica definições recursivas a partir da
p.67; vamos ver alguns exemplos extras mais difíceis e alguns truques
para entender estas definições.

\subsection{Fake binary}

Seja $B:\N→\N$ a função que obedece estas duas condições:

(BP) $∀n∈\N. B(2n)=10·B(n)$

(BI) $∀n∈\N. B(2n+1)=B(2n)+1$

Note que fazendo $n=0$ em (BP) obtemos que $B(0)=0$, e com $n=0$ em
(BI) obtemos $B(1)=1$. Usando $n=1$, $n-2$, etc em (BP) e (BI) obtemos
$B(2)$, $B(3)$, etc. Exercícios: 1) entenda o padrão da função $B$; 2)
descubra o valor de $B(34)$; mostre os passos necessários para
calcular $B(34)$.


\subsection{Módulo}

Seja $\N^+=\setofst{n∈\N}{0<n}$, e seja $M:\Z×\N^+→\N$ a função que
obedece estas duas condições:

(MB) Se $0≤a<b$ então $M(a,b)=a$,

(MM) $M(a+b,b)=M(a,b)$.

Repare que agora não estamos usando `$∀$' e nem dizendo em que
conjuntos os valores de $a$ e $b$ moram --- estamos copiando o que
muitos livros de matemática e computação fazem: estamos deixando tudo
implícito! Tanto em (MB) quanto em (MM) fica implícito que $a∈\Z$ e
$b∈\N^+$.

Exercícios: 1) Use (MB) para calcular $M(0,5), M(1,5), \dots, M(4,5)$;
2) Use (MM) para calcular $M(5,5), M(6,5), \dots$; 3) Use (MM) para
calcular $M(-1,5), M(-2,5), \dots$.

\subsection{Noves}

Seja $D:\N→\N$ a função que obedece estas três condições:

(DZ) $D(0)=0$

(DP) Se $D(n)=n$ então $D(n+1)=10D(n)+9$

(DC) Se $D(n)≠n$ então $D(n+1)=D(n)$

Exercícios: 1) Calcule $D(0), D(1), \dots, D(11)$. 2) Entenda o padrão
e descubra os valores de $D(99), D(100), D(101), \ldots, D(999),
D(1000), D(1001)$.

\subsection{Concatenação de números}

Seja $C:\N×\N→\N$ a função que obedece:

(CD) $C(a,b) = a·(D(b)+1)+b$

Exercícios: 1) Calcule $C(12,345)$; 2) Calcule $C(12,0)$; 3) Calcule
$C(0,12)$.

\subsection{Um conjunto de números}

Seja $S⊆\N$ o conjuntos que obedece:

(S0) $0∈S$,

(S2) Se $n∈S$ então $10n+2∈S$,

(S3) Se $n∈S$ então $10n+3∈S$.

Exercícios: 1) Prove que $23322∈S$; 2) Explique porque não dá pra
provar que $45∈S$.

\subsection{Strings}

\def\str#1{\ensuremath{\text{``{\tt#1}''}}}
\def\Ss#1#2{\mathsf{#1}_\mathsf{#2}}
\def\ED{\Ss ED}
\def\EN{\Ss EN}
\def\EB{\Ss EB}
\def\EM{\Ss EM}
\def\ES{\Ss ES}

O ``Exemplo 23'' na página 70 do livro da Judith define {\sl strings},
que às vezes são chamados de {\sl sequências de caracteres} ou de {\sl
  cadeias de caracteres} --- ou só {\sl cadeias} --- em português.
Alguns exemplos de strings: \str{Hello}, \str{1+2}, \str{}, \str{)+}.
Vamos usar `..' (como em Lua) para a operação de concatenação de
strings. Exemplos:

$\str{Hello}..\str{1+2} = \str{Hello1+2}$

\str{}..\str{)+} $=$ \str{)+}


\subsection{Um conjunto de expressões}

Digamos que os conjuntos de strings $\ED$, $\EN$ e $\ES$
obedecem:

(ED) $\str0, \str1, \ldots, \str9 ∈ \ED$

(EN1) Se $d∈\ED$ então $d∈\EN$

(EN2) Se $n∈\EN$ e $d∈\ED$ então $n..d∈\EN$

(ES1) Se $n∈\EN$ então $n∈\ES$

(ES2) Se $s,t∈\ES$ então $s..\str+..t∈\ES$

(ESP) Se $s∈\ES$ então $\str(..s..\str)∈\EN$

Exercícios: 1) Prove que $\str{123}∈\EN$; 2) Prove que $\str{123}∈\ES$
e $\str{123+4+56}∈\ES$; 3) Prove que $\str{(123+4+56)}∈\EN$; 4) Prove
que $\str{(123+4+56)}∈\ES$; 5) Prove que $\str{(123+4+56)+78}∈\ES$.


\subsection{Outro conjunto de expressões}

Vamos {\sl reusar} os símbolos $\ED$, $\EN$ e $\ES$ do item anterior
--- com outro significado.

Digamos que os conjuntos de strings $\ED$, $\EN$, $\EB$, $\EM$ e $\ES$
obedecem:

(ED) $\str0, \str1, \ldots, \str9 ∈ \ED$

(EN1) $d∈\EN$

(EN2) $n..d∈\EN$

(EB1) $n∈\EB$

(EM1) $b∈\EM$

(EM2) $m..\str*..b∈\EM$

(ES1) $m∈\ES$

(ES2) $s..\str+..m∈\ES$

(EBP) $\str(..s..\str)∈\EB$

Agora estamos usando uma convenção no nome das variáveis para deixar a
especificação mais curta. A convenção é:

$d,d',d''∈\ED$

$n,n',n''∈\EN$

$b,b',b''∈\EB$

$m,m',m''∈\EM$

$s,s',s''∈\ES$

\noindent e os `$∀$'s ficam implícitos. Por exemplo, (EM2) por extenso
é:

$∀m∈\EM.∀b∈\EM.m..\str*..b∈\EM$.

Exercícios: 1) prove que $\str{123+4*56+78}∈\ES$; 2) prove que
$\str{(123+4)*56}∈\EM$.

\newpage

\subsection{Valores de expressões}

É fácil ver que os conjuntos $\ED$, $\EN$, $\EB$, $\EM$ e $\ES$ do
item anterior obedecem $\ED⊂\EN⊂\EB⊂\EM⊂\ES$. Vamos definir uma função
$V:\ES→\N$ da seguinte forma:

(VD) $V(\str0)=0, V(\str1)=1, \ldots, V(\str9)=9$

(VN2) $V(n..d)=10V(n)+V(d)$

(VM2) $V(m..\str*..b)=V(m)·V(b)$

(VS2) $V(s..\str+..m)=V(s)·V(m)$

(VP) $V(\str(..s..\str))=V(s)$





% (find-books "__discrete/__discrete.el" "gersting")
% (find-gerstingpage (+ 20  67)   "Definições recursivas")
% (find-gerstingpage (+ 20  69)   "Conjuntos recursivos")





\end{document}

% Local Variables:
% coding: utf-8-unix
% End: