|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (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: