% (find-angg "LATEX/2009apr29-MD.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009apr29-MD.tex && latex    2009apr29-MD.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009apr29-MD.tex && pdflatex 2009apr29-MD.tex"))
% (eev "cd ~/LATEX/ && Scp 2009apr29-MD.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (find-dvipage "~/LATEX/2009apr29-MD.dvi")
% (find-pspage  "~/LATEX/2009apr29-MD.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2009apr29-MD.ps 2009apr29-MD.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -P pk  -o 2009apr29-MD.ps 2009apr29-MD.dvi && ps2pdf 2009apr29-MD.ps 2009apr29-MD.pdf")
% (find-pspage  "~/LATEX/2009apr29-MD.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage  "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2009apr29-MD.pdf" (ee-twupfile "LATEX/2009apr29-MD.pdf") 'over)
% (ee-cp "~/LATEX/2009apr29-MD.pdf" (ee-twusfile "LATEX/2009apr29-MD.pdf") 'over)
% (find-twusfile "2009.1/MD/")
% (ee-cp "~/LATEX/2009apr29-MD.pdf" (ee-twusfile "2009.1/MD/2009-apr-29.pdf") 'over)

\documentclass[oneside]{book}
\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 2009apr29-MD.dnt

%*
% (eedn4-51-bounded)
% (find-es "tex" "newcounter")

\def\sm#1{\begin{smallmatrix}#1\end{smallmatrix}}

\newcounter{myex}
\long\def\newex{
  \par\noindent
  \refstepcounter{myex}
  {\bf (\arabic{myex})}
  }

% (find-dn4exfile "edrxheadfoot.tex")
% \edrxnotes{MD 2009apr29}

%%%%%
%
% página 1
%
%%%%%

\par Matemática discreta
\par PURO-UFF - 2009.1
\par Exercícios - 29/abril/2009
\msk

\newex Complete:
$$ \sof{6, 7, 8, \ldots, 20} = \sst{xÝ\_\_\_}{\_\_\_} $$

\newex Normalmente usamos certas letras para variáveis cujos valores
são reais, outras letras para variáveis cujos valores são inteiros, e
outras letras para variáveis cujos valores são naturais. Descubra qual
é a convenção e melhore a resposta do exercício acima.

\msk

Vamos usar a notação $a|b$ para ``$a$ divide $b$''; $2|4$ é verdade,
$3|5$ é falso.

\newex Complete:
$$ a|b \iff Î\_Ý\_.\,\_\_\_ $$       \label{defDab0}
onde o ``$\_\_\_$'' não envolve divisão, só produto.

\newex Use a expressão que você obteve acima como uma definição formal
de divisibilidade,
$$ D(a,b) \iff Î\_Ý\_.\,\_\_\_ $$    \label{defDab}
e agora teste-a:

\newex mostre que $D(10,20)$ é verdadeira.
\newex Um dos ``esquemas de prova'' da seção 2.9 do Scheinerman
corresponde ao que você usou no exercício anterior. Qual?
\newex Mostre que $D(10,10)$ é verdadeira.
\newex Mostre que $D(10,0)$ é verdadeira.
\newex Mostre que $D(0,10)$ é falsa.
\newex Qual dos ``esquemas de prova'' você usou no exercício anterior?

\msk
Defina:

$P(n) = (10n<2)$,

$Q(n) = (10n \neq 2)$,

$R(n) = (10n > 2)$,

$I(n) = (Q(n) \to Q(n+1))$.

Prove, do modo mais formal que você puder, que:

\newex $P(n)∨R(n) \bij Q(n)$
\newex $P(n) \to Q(n)$
\newex $R(n) \to Q(n)$
\newex $ýnÝ\N.\;R(n) \to R(n+1)$
\newex $ýnÝ\N.\;¬P(n) \to ¬P(n+1)$
\newex $P(0)$
\newex $I(0)$
\newex $I(1)$
\newex $I(2)$
\newex Tente provar $I(n)$ no caso geral (i.e., para qualquer $nÝ\N$).
Isto é possível, mas é bem mais difícil do que pode parecer à primeira
vista. Anote as tentativas que você fez, e porque elas não deram certo.

\newex Finja que você sabe que $ýnÝ\N.I(n)$. Agora prove
formalmente que $ýnÝ\N.Q(n)$, e que $¬D(10,2)$.

\newpage

%%%%%
%
% página 2
%
%%%%%

Sejam $A = \sof{2, 3, 4}$ e $B = \sof{5, 6}$.

Represente estes conjuntos no plano $(x,y)$:

\newex $\sst{(x,y)Ý\R^2}{xÝA, yÝB}$     \label{234x56}
\newex $A$, como subcojunto do eixo $x$
\newex $B$, como subcojunto do eixo $y$
\newex $\sst{(x,0)Ý\R^2}{xÝA}$
\newex $\sst{(0,y)Ý\R^2}{yÝB}$

Represente estes conjuntos no plano $(x,y)$:

\newex $\sst{(x,y)Ý\R^2}{xÝB, yÝA}$
\newex $\sst{(x,y)Ý\R^2}{xÝB, yÝA}$
\newex $B$, como subcojunto do eixo $x$
\newex $A$, como subcojunto do eixo $y$
\newex $\sst{(x,0)Ý\R^2}{xÝB}$
\newex $\sst{(0,y)Ý\R^2}{yÝA}$

\msk

\def\pp#1#2{(#1,#2)}
\def\brokenmatrix#1#2{
  \begin{matrix} #1 \{ &
          #2 & \}
  \end{matrix}
  }


Usando a notação $\pp\_\_$ para denotar pares ordenados podemos
representar um produto de dois conjuntos finitos bidimensionalmente
como uma lista de pares:
%
$$\brokenmatrix{
    \sof{1,2}×\sof{3,4} =
  }{ \pp13, & \pp23, \\
   & \pp14, & \pp24
  }
$$
%
e se representamos o segundo conjunto ``na vertical'' isto fica ainda
mais claro:
%
$$\brokenmatrix{
    \sof{1,2}× \begin{matrix} \{3, \\ \;4\} \end{matrix} =
  }{ \pp13, & \pp23, \\
   & \pp14, & \pp24
  }
$$
%
repare que a ordem na qual listamos os elementos dos dois conjuntos
vai influenciar na ordem ``natural'' para listarmos os elementos do
produto:
%
$$\brokenmatrix{
    \sof{1,2}× \begin{matrix} \{4, \\ \;3\} \end{matrix} =
  }{ \pp14, & \pp24, \\
   & \pp13, & \pp23
  }
$$
%
mas repare que os conjuntos em si não mudam.

\newex Porque os conjuntos não mudam se mudamos a ordem dos seus
elementos? Explique com as suas palavras ou encontre um trecho do
livro do Scheinerman (ou de outro) que justifique isto.

\newex Tente representar $\N×\N$ bidimensionalmente como uma lista de
pares.

\newex Tente representar $\Z×\Z$ bidimensionalmente como uma lista de
pares.

\newex Encontre uma representação bidimensional para
$\sof{2,3,4}×\sof{5,6}$ que corresponda ao que você obteve no
exercício \ref{234x56}.    \label{23456-bidi}

\newex Nós às vezes usamos uma representação bidimensional com 0s e 1s
para representar funções de conjuntos como o do exercício
\ref{23456-bidi} no conjunto $\sof{0,1}$. Descreva a função que é
representada por isto aqui: $\sm{100\\010}$.

\newex Nós às vezes usamos essa mesma representação bidimensional com
0s e 1s para representar {\sl subconjuntos}, além de funções. Descreva
o subconjunto que é representado por isto aqui: $\sm{100\\010}$.
  \label{23456-sub01}

\newpage

%%%%%
%
% página 3
%
%%%%%

\newex O que é $\sof{0,1,2,3,4,5,6}^2$?

\newex Quantos elementos $\sof{0,1,2,3,4,5,6}$ tem? E
$\sof{0,1,2,3,4,5,6}^2$?

\msk

Use a idéia do exercício \ref{23456-sub01} para representar
estes subconjuntos de $\sof{0,1,2,3,4,5,6}^2$ como retângulos de 0s e
1s:

\newex $\sst{(x,y)Ý\sof{0,1,2,3,4,5,6}^2}{x|y}$
\newex $\sst{(x,y)Ý\sof{0,1,2,3,4,5,6}^2}{y|x}$



% \newpage

%%%%%
%
% página 4
%
%%%%%





%*

\end{document}

% Local Variables:
% coding:           raw-text-unix
% ee-anchor-format: "«%s»"
% End: