|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (find-angg "LATEX/2009-1-MD-prova-VR.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-1-MD-prova-VR.tex && latex 2009-1-MD-prova-VR.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-1-MD-prova-VR.tex && pdflatex 2009-1-MD-prova-VR.tex"))
% (eev "cd ~/LATEX/ && Scp 2009-1-MD-prova-VR.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2009-1-MD-prova-VR.dvi"))
% (defun p () (interactive) (find-pspage "~/LATEX/2009-1-MD-prova-VR.pdf"))
% (defun p () (interactive) (find-pspage "~/LATEX/2009-1-MD-prova-VR.ps"))
% (find-dvipage "~/LATEX/2009-1-MD-prova-VR.dvi")
% (find-pspage "~/LATEX/2009-1-MD-prova-VR.pdf")
% (find-pspage "~/LATEX/2009-1-MD-prova-VR.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2009-1-MD-prova-VR.ps 2009-1-MD-prova-VR.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2009-1-MD-prova-VR.ps 2009-1-MD-prova-VR.dvi && ps2pdf 2009-1-MD-prova-VR.ps 2009-1-MD-prova-VR.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2009-1-MD-prova-VR.pdf" (ee-twupfile "LATEX/2009-1-MD-prova-VR.pdf") 'over)
% (ee-cp "~/LATEX/2009-1-MD-prova-VR.pdf" (ee-twusfile "LATEX/2009-1-MD-prova-VR.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 2009-1-MD-prova-VR.dnt
%*
% (eedn4-51-bounded)
%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")
\def\depois#1{#1}
% (find-dn4ex "edrxdnt.tex" "defdiag")
\long\def\Def #1#2{\expandafter\def\csname #1\endcsname{#2}}
\def\ifUndef#1{\expandafter\ifx\csname #1\endcsname\relax}
\def\Assert #1{\ifUndef{#1}\errmessage{UNDEFINED: #1}\else\relax\fi}
\def\Expand #1{\Assert{#1}\csname #1\endcsname}
% \long\def\defquestion cod#1 ref#2 val#3 qst#4 gab#5 spc#6{#1 #2 #3 #4 #5 #6}
\long\def\defquestion cod#1 ref#2 val#3 qst#4 gab#5 spc#6{
\Def{Ref#1}{#2}
\Def{Val#1}{#3}
\long\Def{Qst#1}{#4}
\long\Def{Gab#1}{#5}
\long\Def{Spc#1}{#6}
}
% (find-LATEX "2009apr29-C1.tex")
% (find-LATEXfile "2009apr29-C1.tex" "newcounter")
% (find-es "tex" "newcounter")
\newcounter{questao}
\long\def\novaquestao{
\par\noindent
\refstepcounter{questao}
{\bf (\arabic{questao})}
}
% «Header» (to ".Header")
\long\def\Header{{
\setlength{\parindent}{0pt}
\par Matemática Discreta
\par PURO-UFF - 2009.1
\par Professor: Eduardo Ochs
\par Prova de reposição (VR) - 01/julho/2009
}}
% «Definicoes» (to ".Definicoes")
\long\def\Definicoes{
% \par {\bf Dicas e definições:}
\par {\bf Definições:}
Um {\sl contra-exemplo} para $ýxÝA.P(a)$ é um $aÝA$ tal que $P(a)$ é
falso.
Uma sentença da forma $ýxÝA.P(a)$ é falsa se e só se algum $aÝA$ é um
contra-exemplo para $ýxÝA.P(a)$.
O {\sl conjunto das partes} de um conjunto $A$, $\Pts(A)$, é o
conjunto dos subconjuntos de $A$. Exemplo: se $A=\{4,5,6\}$ então
$\{4,5\} \in \Pts(A)$.
Se $A$ é um conjunto finito então $|A|$ é o número de elementos de
$A$.
A relação $R \subset A×A$ é {\sl reflexiva} quando $ýaÝA.\, aRa$.
A relação $R \subset A×A$ é {\sl simétrica} quando $ýa,bÝA.(aRb \to
bRa)$.
A relação $R \subset A×A$ é {\sl transitiva} quando $ýa,b,cÝA.(aRb ∧
bRc \to aRc)$.
Uma relação $R$ é uma {\sl relação de equivalência} quando $R$ é
reflexiva, simétrica e transitiva.
A {\sl classe de equivalência} de um elemento $a \in A$ pela relação
de equivalência $R \subset A×A$ é o conjunto $[a] = \sst{x \in
A}{aRx}$.
A {\sl inversa} de uma relação $R=\{(a_1,b_1), (a_2,b_2), \ldots\}$ é
a relação $R^{-1}=\{(b_1,a_1), (b_2,a_2), \ldots\}$.
{\sl Relação $R \subset A×A$ como grafo direcionado:} podemos
representar $R$ desenhando um grafo direcionado no qual os vértices
são os elementos de $A$ e cada seta $a \to b$ corresponde a um par
$(a,b) \in R$.
{\sl Relação $R \subset A×B$ como grafo direcionado:} podemos
representar $R$ desenhando o conjunto $A$ e o conjunto $B$ em separado
e desenhando uma seta $a \to b$ de um elemento $a \in A$ para um
elemento $b \in B$ para cada par $(a,b) \in R$.
A função $f: A \to B$ é {\sl injetiva} quando $ýa_1, a_2 \in A.\,
(f(a_1)=f(a_2) \to a_1=a_2)$.
A função $f: A \to B$ é {\sl sobrejetiva} quando $ýbÝB.\, ÎaÝA.\,
f(a)=b$.
Se $f:A \to B$ e $g: B \to C$ são funções, então a sua {\sl
composta}, $g¢f$, é uma função $g¢f: A \to C$, definida por
$ýaÝA.\, (g¢f)(a) = g(f(a))$.
A função {\sl identitidade em $A$}, $\id_A: A \to A$, é definida
por $ýaÝA.\, \id_A(a)=a$.
Duas funções $f:A \to B$ e $g:B \to A$ são {\sl inversas} quando
$f¢g = \id_B$ e $g¢f = \id_A$.
}
\long\def\Ask#1{
\novaquestao
{\bf (\Expand{Val#1} pontos)}
\Expand{Qst#1}
\bsk
}
\long\def\Gab#1{
\par {\bf (Questão {\tt #1} - \Expand{Val#1} pontos)}
\Expand{Qst#1}
\ssk\par {\bf Gabarito:}
\par \Expand{Gab#1}
\bsk
\bsk
}
\def\Prova #1 #2 #3 #4 #5 {
\setcounter{questao}{0}
\Header
\bsk
\par {\bf Questões:}
\ssk
\Ask{#1}
\Ask{#2}
\Ask{#3}
\Ask{#4}
\Ask{#5}
\newpage
\Definicoes
\bsk
\bsk
\newpage
}
% (find-kopkadaly4page (+ 12 126) "Index" "\\not")
% (find-kopkadaly4page (+ 12 631) "Index" "\\not")
% (find-kopkadaly4text)
% (find-LATEXfile "2008induction.tex" "\\def\\notS")
% (find-LATEXfile "2009-1-C1-prova-1.tex" "\\def\\sen")
\def\notR{\not\mathrel{R}}
\def\notQ{\not\mathrel{Q}}
\def\notD{\not\mathrel{D}}
\def\sen{\operatorname{sen}}
\def\arcsen{\operatorname{arcsen}}
\def\sinal{\operatorname{sinal}}
\def\sinal{s}
%%%%%%%%%%%%%%%%%%%%%%%%
\defquestion
cod{Binary}
ref{inventei}
val{2.0}
qst{
Digamos que a seqüência $(b_0, b_1, b_2, \ldots)$ obedece estas
três propriedades: (1) $b_0=0$, (2) $ýkÝ\N.\,b_{2k} = 10b_k$, (3)
$ýkÝ\N.\,b_{2k+1} = 10b_k + 1$. O que você sabe sobre $b_{12}$?
}
gab{
$b_1 = b_{2·0+1} = 10b_0 + 1 = 1$
$b_3 = b_{2·1+1} = 10b_1 + 1 = 11$
$b_6 = b_{2·3} = 10b_3 = 110$
$b_{12} = b_{2·6} = 10b_6 = 1100$
}
spc{}
%%%%%%%%%%%%%
\defquestion
cod{Induction}
ref{}
val{2.5}
qst{
Considere a seqüência $(a_0, a_1, a_2, \ldots)$ definida por: $a_0
= 0$, $a_{n+1} = 10a_n + 1$. Defina $P(n) = (9a_n + 1 = 10^n)$.
a) (0.4 pts) Calcule $a_1, a_2, a_3, P(0), P(1), P(2), P(3)$.
b) (0.9 pts) Mostre que $P(20) \to P(21)$.
c) (0.9 pts) Mostre que $P(n) \to P(n+1)$ vale para qualquer $n$.
d) (0.3 pts) Prove $ýnÝ\N.P(n)$.
}
gab{
$a_1 = 1$, $a_2 = 11$, $a_3 = 111$
$P(0) = (9a_0 + 1 = 10^0) = (9·0 + 1 = 1) = V$
$P(1) = (9a_1 + 1 = 10^1) = (9·1 + 1 = 10) = V$
$P(2) = (9a_2 + 1 = 10^2) = (9·11 + 1 = 100) = V$
$P(3) = (9a_3 + 1 = 10^3) = (9·111 + 1 = 1000) = V$
$\begin{array}{rcl}
P(20) \to P(21)
& \bij & (9a_{20} + 1 = 10^{20} \to 9a_{21} + 1 = 10^{21}) \\
& \bij & (9a_{20} + 1 = 10^{20} \to 9(10a_{20}+1) + 1 = 10·10^{20}) \\
& \bij & (9a_{20} + 1 = 10^{20} \to 90a_{20} + 10 = 10·10^{20}) \\
& \bij & (9a_{20} + 1 = 10^{20} \to 10(9a_{20} + 1) = 10·10^{20}) \\
\end{array}
$
$\begin{array}{rcl}
P(n) \to P(n+1)
& \bij & (9a_{n} + 1 = 10^{n} \to 9a_{n+1} + 1 = 10^{n+1}) \\
& \bij & (9a_{n} + 1 = 10^{n} \to 9(10a_{n}+1) + 1 = 10·10^{n}) \\
& \bij & (9a_{n} + 1 = 10^{n} \to 90a_{n} + 10 = 10·10^{n}) \\
& \bij & (9a_{n} + 1 = 10^{n} \to 10(9a_{n} + 1) = 10·10^{n}) \\
\end{array}
$
}
spc{}
%%%%%%%%%%%%%
\defquestion
cod{Or}
ref{Inventei}
val{1.0}
qst{
Prove que $(P \to Q) ∨ (Q \to P)$ é sempre verdade.
}
gab{
Tabela de verdade (4 linhas).
}
spc{}
%%%%%%%%%
\defquestion
cod{P-any}
ref{Inventei}
val{2.5}
qst{
Defina uma proposição sobre os naturais, $P: \N \to Ø$, tal que
$P(0)$, $P(1)$, $P(2)$, $P(3)$, $P(5)$ sejam verdadeiras mas $P(4)$
seja falsa. Diga quais são os valores de verdade de $P(6)$, $P(7)$,
$P(20)$ e $P(100)$. Diga se $ýnÝ\N.\,P(n) \to P(n+1)$ é verdadeiro
ou falso, e porquê.
}
gab{
Uma possibilidade: $P(n) = (n \neq 4)$.
$P(6) = P(7) = P(20) = P(100) = V$
$(P(3) \to P(4)) = (V \to F) = F$
$(ýnÝ\N.\,P(n) \to P(n+1)) = F$, o contra-exemplo é $n=3$.
}
spc{}
%%%%%%%%%%
\defquestion
cod{Square}
ref{Inventei}
val{2.0}
qst{
Seja $A=\{0,1,2,3\}$ e seja $R=\{(0,1),$ $(1,2),$ $(2,3),$ $(3,0),$
$(0,2)\} \subseteq A^2$ uma relação sobre $A$. Seja $S=RþR³$.
a) (0.6 pts) Represente $S$ como conjunto.
b) (0.7 pts) Represente $R$ e $S$ como grafos direcionados.
c) (0.7 pts) Mostre que $S$ não é transitiva.
}
gab{
$S = \{(0,1),(1,0),$ $(1,2),(2,1),$ $(2,3),(3,2),$ $(3,0),(0,3),$
$(0,2),(2,0)\}$
Desenho:
$R =
\left(
\begin{smallmatrix} 0 & 1 \\
3 & 2 \\
\end{smallmatrix}
\right)
$
com setas $0 \to 1 \to 2 \to 3 \to 0$ e $0 \to 2$, sem a diagonal
$1 \to 3$.
$S$ é a mesma coisa, mas as setas são bidirecionais.
Contra-exemplo: $1S2 ∧ 2S3 \not\to 1R2$.
}
spc{}
%%%%%%%%%%%
\Prova Induction Binary Or P-any Square
\Prova P-any Square Induction Binary Or
\Prova Or P-any Induction Binary Square
\Prova Square Or P-any Induction Binary
\Prova Binary P-any Induction Square Or
\Prova Square Or P-any Induction Binary
\Prova Induction Or Square Binary P-any
\Prova Or Square Binary P-any Induction
\Prova Or P-any Binary Induction Square
\Prova Or P-any Induction Square Binary
\Prova Or Induction P-any Square Binary
\Prova Square Induction Binary Or P-any
\Prova Square P-any Or Binary Induction
\Prova Or Induction P-any Square Binary
\Prova Binary Or Induction Square P-any
\Prova P-any Or Square Binary Induction
\Prova Binary Or Induction Square P-any
\Prova Or Binary Square P-any Induction
\Prova Induction Or Square P-any Binary
\Prova Square Induction Or Binary P-any
\Prova P-any Induction Binary Or Square
\Prova Induction P-any Binary Square Or
\Prova Induction Binary P-any Or Square
\Prova Or Induction Square Binary P-any
\Prova Or Induction Binary Square P-any
\Prova Binary P-any Induction Or Square
\Prova Induction Binary Square Or P-any
\Prova Square Induction Binary P-any Or
\Prova Square Binary Induction P-any Or
\Prova Or Induction Square P-any Binary
\Prova P-any Or Binary Induction Square
\Prova P-any Or Induction Square Binary
\Prova Induction Square P-any Binary Or
\Prova Induction Square Or Binary P-any
\Prova Induction Binary P-any Square Or
% \Ask{R}
% \Ask{Pipa}
% \Ask{Primos}
% \Ask{Arcsen}
% \Ask{Sinal}
% \Ask{Partes}
\newpage
{\bf Gabarito:}
\bsk
\Gab{Binary}
\Gab{Induction}
\Gab{Or}
\newpage
\Gab{P-any}
\Gab{Square}
% \defquestion
% cod{}
% ref{}
% val{}
% qst{}
% gab{}
% spc{}
%*
\end{document}
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
random = math.random
shuffle = function (A)
local B = {}
for i=1,#A do B[i]=A[i] end
for i=#A,2,-1 do
local r = random(1, i)
B[r], B[i] = B[i], B[r]
end
return B
end
from = function (A, n)
if n == nil then
return A[random(1, #A)]
end
A = shuffle(A)
while #A > n do A[#A] = nil end
return A
end
questoes = function ()
local a = from(split "Pipa Primos")
local B = from(shuffle(split "Sinal Arcsen RRRRR Partes"), 3)
tinsert(B, a)
-- return shuffle(B)
return shuffle(split("Binary Induction Or P-any Square"))
end
prova = function ()
local a, b, c, d, e = unpack(questoes())
printf("\\Prova %9s %9s %9s %9s %9s\n", a, b, c, d, e)
end
for i=1,30 do PP(questoes()) end
for i=1,35 do prova() end
for i=1,10 do PP(from{"Pipa", "Primos"}) end
for i=1,10 do PP(from(split {"Pipa", "Primos"}) end
for i=1,40 do PP(shuffle({"aa", "bb", "cc", "dd", "ee"})) end
%*
\end{document}
% Local Variables:
% coding: raw-text-unix
% ee-anchor-format: "«%s»"
% End: