% (find-angg "LATEX/2018-2-MD-VR.tex")
% (defun c () (interactive) (find-LATEXsh "lualatex -record 2018-2-MD-VR.tex"))
% (defun d () (interactive) (find-xpdfpage "~/LATEX/2018-2-MD-VR.pdf"))
% (defun e () (interactive) (find-LATEX "2018-2-MD-VR.tex"))
% (defun u () (interactive) (find-latex-upload-links "2018-2-MD-VR"))
% (find-xpdfpage "~/LATEX/2018-2-MD-VR.pdf")
% (find-sh0 "cp -v  ~/LATEX/2018-2-MD-VR.pdf /tmp/")
% (find-sh0 "cp -v  ~/LATEX/2018-2-MD-VR.pdf /tmp/pen/")
%   file:///home/edrx/LATEX/2018-2-MD-VR.pdf
%               file:///tmp/2018-2-MD-VR.pdf
%           file:///tmp/pen/2018-2-MD-VR.pdf
% http://angg.twu.net/LATEX/2018-2-MD-VR.pdf

% «.gab-1»	(to "gab-1")
% «.gab-2»	(to "gab-2")
% «.gab-3»	(to "gab-3")
% «.gab-4»	(to "gab-4")
% «.gab-5»	(to "gab-5")

\documentclass[oneside]{book}
\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




\def\V{\mathbf{V}}
\def\F{\mathbf{F}}

\def\Par  {\mathsf{par}}
\def\Impar{\mathsf{impar}}

\def\antitabular{\hskip-5.5pt}



%   ____      _                    _ _           
%  / ___|__ _| |__   ___  ___ __ _| | |__   ___  
% | |   / _` | '_ \ / _ \/ __/ _` | | '_ \ / _ \ 
% | |__| (_| | |_) |  __/ (_| (_| | | | | | (_) |
%  \____\__,_|_.__/ \___|\___\__,_|_|_| |_|\___/ 
%                                                

{\setlength{\parindent}{0em}
\footnotesize
\par Matemática Discreta
\par PURO-UFF - 2018.2
\par VR - 18/dez/2018 - Eduardo Ochs
\par Ambas as turmas.
\par Proibido usar quaisquer aparelhos eletrônicos.
\par Erros de tipo --- p.ex. confundir números com conjuntos,
\par listas ou valores de verdade --- são considerados erros graves. 

}

\bsk
\bsk

\def\T(Total: #1 pts){{\bf(Total: #1 pts)}}
\def\T(Total: #1 pts){{\bf(Total: #1)}}
\def\B       (#1 pts){{\bf(#1 pts)}}
% Usage:
% 1) \T(Total: 2.34 pts) Foo
% a) \B(0.45 pts) Bar

{
\setlength{\parindent}{0em}





1) \T(Total: 1.0 pts) Vamos definir a operação $Δ$ por:
$AΔB:=(A∖B)∪(B∖A)$. Calcule $(AΔB)ΔC$ e $AΔ(BΔC)$ no caso em que
$A=\{1,3,5,7\}$, $B=\{2,3,6,7\}$, $C=\{4,5,6,7\}$.

\bsk

2) \T(Total: 2.0 pts) Seja $F:\N×\N→\N$ a função que obedece:

(F0) $F(0,0)=0$,

(FV) $∀y∈\N.F(0,y+1)=F(0,y)+1$,

(FH) $∀x∈\N.F(x+1,0)=F(x,0)+10$,

(FM) $∀x,y∈\N.F(x+1,y+1)=F(x,y+1)+F(x+1,y)$.

a) \B(1.0 pts) Calcule $F(3,3)$.

b) \B(1.0 pts) Represente graficamente os valores de $F(x,y)$ para
$(x,y)∈\{0,1,2,3\}^2$.

\bsk

3) \T(Total: 2.0 pts) Sejam
$C(a,b,f):=\setofst{f(x)}{x∈\{a,\ldots,b\}}$,

$D(a,c,f):=(∀b∈\{a,\ldots,c-1\}.f(b+1)\not∈C(a,b,f))$,

$g:=\{(2,3),(3,4),(4,5),(5,3)\}$.

a) \B(0.5 pts) Calcule $C(3,4,g)$.

b) \B(1.5 pts) Calcule $D(2,5,g)$.


\bsk

4) \T(Total: 3.5 pts) Seja $(*)$ a seguinte proposição: {\sl todo
  inteiro ímpar é soma de dois inteiros consecutivos}.

a) \B(0.5 pts) Traduza $(*)$ para notação matemática.

b) \B(3.0 pts) Demonstre $(*)$ no formato com ``então''s e
``suponha''s.


\bsk


5) \T(Total: 4.0 pts) Sejam: $f(k) := k·10^k$, $P(k):=(f(k)=200)$,

$g(k):=9+9·10+\ldots+9·10^{k-1}$, $h(k):=10^k-1$, $Q(k):=(g(k)=h(k))$.

a) \B(0.2 pts) Calcule $f(k)$ e $P(k)$ para $k∈\{1,2,3,4\}$.

b) \B(0.2 pts) Calcule $\sum_{i=2}^6 f(i)$ e $\sum_{i=1}^4 f(2i)$.

c) \B(1.0 pts) Defina usando somatório uma função $s(k)$ que se
comporte como a função $g(k)$, e teste-a verificando se $s(3)=g(3)$,
$s(4)=g(4)$, $s(5)=g(5)$.

d) \B(0.2 pts) Calcule $s(-2)$, $s(-1)$, $s(0)$.

e) \B(0.4 pts) Seja $R(k):=(s(k)=h(k))$. Calcule $R(2)$, $R(1)$,
$R(0)$, $R(-1)$.

f) \B(2.0 pts) Mostre que se $k∈\N^+$ então $Q(k)→Q(k+1)$.



}


\newpage

%  ____  _               
% |  _ \(_) ___ __ _ ___ 
% | | | | |/ __/ _` / __|
% | |_| | | (_| (_| \__ \
% |____/|_|\___\__,_|___/
%                        


{\bf Dicas:}

$\{a,a+1,\ldots\} \;\; = \;\; \setofst{k∈\Z}{a≤k}$

$\{a,a+1,\ldots,b\} \;\; = \;\; \setofst{k∈\Z}{a≤k≤b}$

$\N^+ = \{1,2,\ldots\}$

$\sum_{i=2}^{4} 10^i = 11100$, \;\; $\sum_{i=4}^{2} 10^i = 0$

Se $P(x)=(x=x^2)$ então $P(0)=\V$, $P(1)=\V$, $P(2)=\F$

Se $A,B$ são conjuntos então $A×B = \setofst{(a,b)}{a∈A,b∈B}$

Se $A,B$ são conjuntos então $A∖B = \setofst{a∈A}{a\not∈B}$

$(∃!x∈A.P(a)) \;\; = \;\; (∃x∈A.P(a))∧(∀x',x''∈A.P(x')∧P(x'')→x'=x'')$

$(f:A→B) \;\; = \;\; (f⊆A×B) ∧ (∀a∈A.∃!b∈B.(a,b)∈f)$

Se $f,g$ são funções então $(f∘g)(x)=f(g(x)), \; f^2=f∘f, \; f^3=f∘f∘f$

Se $A,B$ são conjuntos então $B^A = \setofst{f}{f:A→B}$

Se $B$ é um conjunto então $\Pts(B) = \setofst{A}{A⊆B}$

$\Par(b):=(∃a∈\Z.2a=b)$; $\Impar(b):=(∃a∈\Z.2a+1=b)$.


\bsk

{\bf Uma demonstração com `$∀$' e `$∃$':}

\begin{minipage}[t]{23em}
\par 1) Suponha $a∈\Z$
\par 2) Suponha $\Impar(a)$
\par 3) Então $\Impar(a)$
\par 4) Então $∃b∈\Z.2b+1=a$ \hfill (Por 3, def)
\par 5) Suponha $b∈\Z,2b+1=a$
\par 6) Então $\begin{array}[t]{rcl}
               a^2 &=& (2b+1)^2 \\
                   &=& 4b^2 + 4b + 1 \\
                   &=& 2(b^2+2b) + 1 \\
               \end{array}$
\par 7) Então $2b^2+2b∈\Z∧2(b^2+2b)+1=a^2$
\par 8) Então $∃c∈\Z.2c+1=a^2$ \quad ($c:=2b^2+2b$)
\par 9) Então $\Impar(a^2)$
\par 10) Então $\Impar(a^2)$ \hfill (Usa 4, fecha 5)
\par 11) Então $\Impar(a)→\Impar(a^2)$ \hfill (fecha 2)
\par 12) Então $∀a∈\Z.\Impar(a)→\Impar(a^2)$ \hfill (fecha 1)
\end{minipage}

\bsk

{\bf Uma demonstração por indução:}

\begin{minipage}[t]{33em}
\par 1) Lema: $∀a∈\Z.\Par(a)→\Impar(a+1)$
\par 2) Lema: $∀a∈\Z.\Impar(a)→\Par(a+1)$
\par 3) Suponha $n∈\N$
\par 4) Então $n∈\Z$
\par 5) Então $\Par(n)→\Impar(n+1)$   \hfill (Por 1, com $a:=n$)
\par 6) Então $\Impar(n)→\Par(n+1)$   \hfill (Por 2, com $a:=n$)
\par 7) Então $\Par(n)∨\Impar(n)→\Par(n+1)∨\Impar(n+1)$  \hfill (Por 5 e 6)
\par 8) Então $∀n∈\N.\Par(n)∨\Impar(n)→\Par(n+1)∨\Impar(n+1)$ \hfill (Fecha 4)
\par 9) Lema: $\Par(0)$
\par 10) Então $\Par(0)∨\Impar(0)$
\par 11) Então $∀n∈\N.\Par(n)∨\Impar(n)$  \hfill (Por 10 e 8)
\end{minipage}



\newpage

%   ____       _                _ _        
%  / ___| __ _| |__   __ _ _ __(_) |_ ___  
% | |  _ / _` | '_ \ / _` | '__| | __/ _ \ 
% | |_| | (_| | |_) | (_| | |  | | || (_) |
%  \____|\__,_|_.__/ \__,_|_|  |_|\__\___/ 
%                                          
{\bf Mini-gabarito (não revisado)}

\msk

% «gab-1» (to ".gab-1")

1) $\def\myeq{\;\;\;=\;\;\;}
    \def\myeq{\\&=&}
    \begin{array}[t]{rcl}
        AΔB &=& \{1,3,5,7\}Δ\{2,3,6,7\} \\
            &=& (\{1,3,5,7\}∖\{2,3,6,7\}) ∪ (\{2,3,6,7\}∖\{1,3,5,7\}) \\
            &=& \{1,5\}∪\{2,6\} \\
            &=& \{1,2,5,6\} \\
        BΔC &=& \{2,3,6,7\}Δ\{4,5,6,7\} \myeq \{2,3,4,5\} \\
    (AΔB)ΔC &=& \{1,2,5,6\}Δ\{4,5,6,7\} \myeq \{1,2,4,7\} \\
    AΔ(BΔC) &=& \{1,3,5,7\}Δ\{2,3,4,5\} \myeq \{1,2,4,7\} \\
    \end{array}
   $

\msk

% «gab-2» (to ".gab-2")

2a) Veja abaixo.

2b) $\def\Fxy#1#2#3{F(#1,#2)=#3}
     \begin{array}[t]{cccc}
     \Fxy033 & \Fxy13{16} & \Fxy23{60} & \Fxy33{165} \\
     \Fxy022 & \Fxy12{13} & \Fxy22{44} & \Fxy32{105} \\
     \Fxy011 & \Fxy11{11} & \Fxy21{31} & \Fxy31{61} \\
     \Fxy000 & \Fxy10{10} & \Fxy20{20} & \Fxy30{30} \\
     \end{array}
    $

\msk

% «gab-3» (to ".gab-3")

3a) $C(3,4,g) = \setofst{g(x)}{x∈\{3,4\}} = \{g(3),g(4)\} = \{4,5\}$ 

3b) $\begin{array}{rcl}
     C(2,2,g) &=& \{g(2)\} = \{3\} \\
     C(2,3,g) &=& \{g(2),g(3)\} = \{3,4\} \\
     C(2,4,g) &=& \{g(2),g(3),g(4)\} = \{3,4,5\} \\
     D(2,5,g) &=& ∀b∈\{2,\ldots,4\}.g(b+1)\not∈C(2,b,g) \\
              &=& ∀b∈\{2,3,4\}.     g(b+1)\not∈C(2,b,g) \\
              &=& (g(2+1)\not∈C(2,2,g)) ∧ \\
               && (g(3+1)\not∈C(2,3,g)) ∧ \\
               && (g(4+1)\not∈C(2,4,g))   \\
              &=& g(3)\not∈\{3\} ∧
                  g(4)\not∈\{3,4\} ∧
                  g(5)\not∈\{3,4,5\} \\
              &=&    4\not∈\{3\} ∧
                     5\not∈\{3,4\} ∧
                     6\not∈\{3,4,5\} \\
              &=& \V \\
     \end{array}
    $

\msk

% «gab-4» (to ".gab-4")

4a) $∀a∈\Z.\Impar(a)→∃b∈\Z.a=b+(b+1)$

4b)
\begin{minipage}[t]{27em}
\par 1) Suponha $a∈\Z$, $\Impar(a)$
\par 2) Então   $\Impar(a)$
\par 3) Então   $∃k∈\Z.2k+1=a$
\par 4) Suponha $k∈\Z$, $2k+1=a$
\par 5) Então   $a=k+(k+1)$
\par 6) Então $∃b∈\Z.a=b+(b+1)$ \quad ($b:=k$)
\par 7) Então $∃b∈\Z.a=b+(b+1)$          \hfill (usa 3, fecha 4)
\par 8) Então $\Impar(a)→∃b∈\Z.a=b+(b+1)$       \hfill (fecha 2)
\par 9) Então $∀a∈\Z.\Impar(a)→∃b∈\Z.a=b+(b+1)$ \hfill (fecha 1)
\par
\end{minipage}

\newpage


% «gab-5» (to ".gab-5")

5a) $f(0)=0$,
    $f(1)=10$,
    $f(2)=200$,
    $f(3)=3000$,

\quad\;\;
    $P(0)=\F$,
    $P(1)=\F$,
    $P(2)=\V$,
    $P(3)=\F$

5b) $\sum_{i=2}^6 f(i)  =   6543200$,
    $\sum_{i=1}^4 f(2i) = 806040200$.

5c) Seja $s(k) = \sum_{i=0}^{k-1} 9·10^i$. Então:

$\begin{array}{rclclcl}
 s(3) &=& \sum_{i=0}^{3-1} 9·10^i &=& 9·10^0 + 9·10^1 + 9·10^2                   \\&=& g(3) \\
 s(4) &=& \sum_{i=0}^{4-1} 9·10^i &=& 9·10^0 + 9·10^1 + 9·10^2 + 9·10^3          \\&=& g(4) \\
 s(5) &=& \sum_{i=0}^{5-1} 9·10^i &=& 9·10^0 + 9·10^1 + 9·10^2 + 9·10^3 + 9·10^4 \\&=& g(5) \\
 \end{array}
$

5d) $\begin{array}[t]{l}
     s(-2) = \sum_{i=0}^{-2-1} 9·10^i = 0 \\
     s(-1) = \sum_{i=0}^{-1-1} 9·10^i = 0 \\
     s(0)  = \sum_{i=0}^{0-1}  9·10^i = 0 \\
     \end{array}
    $

5e)
$\begin{array}[t]{l}
     R(2) = (s(2)=h(2)) = (99=10^2-1) = \V \\
     R(1) = (s(1)=h(1)) = ( 9=10^1-1) = \V \\
     R(0) = (s(0)=h(0)) = ( 0=10^0-1) = \V \\
     R(-1) = (s(-1)=h(-1)) = ( 0=10^{-1}-1) = \F \\
     \end{array}
    $

5f)
\begin{minipage}[t]{27em}
\par 1) Suponha $k∈\N^+$
\par 2) Suponha $Q(k)$
\par 3) Então   $g(k)=h(k)$
\par 4) Então   $g(k+1)-g(k)= 9·10^k$
\par 5) Então   $h(k+1) = 10^{k+1}-1$
\par 6) Então   $\begin{array}[t]{rcl}
                 h(k+1)-h(k) &=& (10^{k+1}-1) - (10^k-1) \\
                             &=& 10·10^k - 10^k \\
                             &=& 9·10^k \\
                 \end{array}$
\par 7) Então $g(k+1)-g(k) = h(k+1)-h(k)$
\par 8) Então $g(k)+(g(k+1)-g(k)) = h(k)+(h(k+1)-h(k))$
\par 9) Então $g(k+1)=h(k+1)$
\par 10) Então $Q(k+1)$
\par 11) Então $Q(k)→Q(k+1)$       \hfill (fecha 2)
\par
\end{minipage}





\end{document}

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










