|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (find-angg "LATEX/2009-2-MD-prova-1.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-2-MD-prova-1.tex && latex 2009-2-MD-prova-1.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-2-MD-prova-1.tex && pdflatex 2009-2-MD-prova-1.tex"))
% (eev "cd ~/LATEX/ && Scp 2009-2-MD-prova-1.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2009-2-MD-prova-1.dvi"))
% (find-dvipage "~/LATEX/2009-2-MD-prova-1.dvi")
% (find-pspage "~/LATEX/2009-2-MD-prova-1.pdf")
% (find-pspage "~/LATEX/2009-2-MD-prova-1.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2009-2-MD-prova-1.ps 2009-2-MD-prova-1.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2009-2-MD-prova-1.ps 2009-2-MD-prova-1.dvi && ps2pdf 2009-2-MD-prova-1.ps 2009-2-MD-prova-1.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2009-2-MD-prova-1.pdf" (ee-twupfile "LATEX/2009-2-MD-prova-1.pdf") 'over)
% (ee-cp "~/LATEX/2009-2-MD-prova-1.pdf" (ee-twusfile "LATEX/2009-2-MD-prova-1.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-2-MD-prova-1.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\eqdef{\;=\;}
\def\ssdef{\;\;\;\text{se e só se}\;\;\;}
\def\redto{\;\;\squigto\;\;}
\def\compr{Ð{compr}}
% (find-LATEX "2009-2-C2-prova-1.tex")
% (find-LATEX "2009-2-MD-prova-1-notas.tex")
Matemática Discreta - Primeira Prova (P1)
PURO-UFF - 2009.2
07/outubro/2009
Prof: Eduardo Ochs
\bsk
\bsk
1) (3.0 pontos) Considere as duas sentenças abaixo:
\ssk
(*) Todo múltiplo de 3 é múltiplo de 9.
(**) $ýaÝ\Z.\,(9|a \to 3|a)$.
\ssk
a) (0.3 pts) Traduza a sentença (*) para Matematiquês.
b) (0.3 pts) Traduza a sentença (**) para Português.
c) (2.4 pts) Para cada uma das sentenças (*) e (**) diga se ela é
verdadeira ou falsa; se ela for verdadeira demonstre-a, se ela for
falsa, refute-a.
\bsk
\bsk
2) (2.0 pontos) Considere as quatro sentenças abaixo:
$(P∧Q) \to R$ (vamos chamar esta de ``$A$''),
$P \to (Q \to R)$ (vamos chamar esta de ``$B$''),
$Q \to (P \to R)$ (vamos chamar esta de ``$C$''),
$Q \to R$ (vamos chamar esta de ``$D$'').
Quais as relações entre as sentenças acima? Quais são logicamente
equivalentes, quais não são? $C \to D$ ou $C \not\to D$? Diga tudo que
você puder sobre elas.
\bsk
\bsk
3) (2.0 pontos) Minha tia tem 30 CDs, ``Roberto Carlos 1'', ``Roberto
Carlos 2'', etc, até ``Roberto Carlos 30'', e ela tem um aparelho de
CD com uma bandeja na qual cabem 4 CDs. Os espaços para CDs na bandeja
são numerados de 1 a 4, e quando ela aperta o botão ``TOCAR TUDO'' do
aparelho ele toca os CDs das bandejas 1, 2, 3 e 4 em ordem.
a) (1.0 pts) Quantos modos diferentes ela tem de programar o aparelho
para tocar 4 CDs?
b) (1.0 pts) Expresse a resposta do problema anterior formalmente
usando a linguagem de conjuntos e listas.
\bsk
\bsk
4) (1.0 pontos) Sejam $A=\sof{1,2}$, $B=\sof{3,4}$, $C=\sof{5,6}$.
Mostre que $(A×B)×C$ e $A×(B×C)$ são conjuntos diferentes.
% b) Sejam $A'=\sof{1,2,3,4,5}$, $B'=\sof{2,3,4,5,6}$,
% $C'=\sof{3,4,5,6,7}$. Mostre que $(A'×B')×C'$ e $A'×(B'×C')$ são
% conjuntos diferentes.
\bsk
\bsk
5) (2.0 pontos) Sejam $A=\sof{1,2}$ e $B=\sof{\sof{1,2},1,2}$. Calcule
o valor de verdade das duas sentenças abaixo:
a) $AÝB$
b) $A \subseteq B$
% \bsk
% \bsk
\newpage
Algumas definições:
$\Pts(A) \eqdef \sst{B}{B \subseteq A}$
$A×B \eqdef \sst{(a,b)}{aÝA, bÝB}$
$AÌB \eqdef \sst{aÝA}{aÝB}$
$A \subseteq B \ssdef ýaÝA,\,aÝB$
$A = B \ssdef A \subseteq B ∧ B \subseteq A$
$a|b \ssdef ÎxÝ\Z.\,ax=b$
$a \text{ é {\sl par}} \ssdef ÎxÝ\Z.\,a=2x$
$a \text{ é {\sl ímpar}} \ssdef ÎxÝ\Z.\,a=2x + 1$
\msk
Dicas:
$ÎaÝ\sof{4,5,6}.\,a^2 = 25 \redto 4^2=25 ∨ 5^2=25 ∨ 6^2=25$
$ýaÝ\sof{4,5,6}.\,a^2 = 25 \redto 4^2=25 ∧ 5^2=25 ∧ 6^2=25$
$aÝ\sof{4,5,6} \redto a=4 ∨ a=5 ∨ a=6$
Operações sobre listas: se $a$ é uma lista então
$\compr(a)$ é o comprimento de $a$ e $a_1, \ldots, a_{\compr(a)}$ são
as componentes de $a$. Se $\compr(a) = 3$ então $a=(a_1, a_2, a_3)$.
\bsk
\bsk
A prova é para ser feita em duas horas, sem consulta.
Responda claramente e justifique cada passo.
Lembre que a correção irá julgar o que você escreveu, e
que é impossível ler o que você pensou mas não escreveu.
Lembre que a resposta esperada para cada questão não é só
uma fórmula ou um número --- a ``resposta certa'' é um
raciocínio claro e convincente, com todos os detalhes
necessários, mostrando que você sabe traduzir corretamente
entre as várias linguagens (português, diagramas,
matematiquês, etc) e explicando o que você está fazendo
quando for preciso.
Outra dica: {\sl confira as suas respostas!}
\ssk
{\bf Boa prova!}
\newpage
Mini-gabarito (versão: 2009oct14, sem a lista dos erros
comuns e sem a pontuação por idéias específicas):
{\myttchars
\footnotesize
\begin{verbatim}
1a) (0.3 pts)
(*) Todo múltiplo de 3 é múltiplo de 9.
Para todo xÝ\Z se x é múltiplo de 3 então x é múltiplo de 9.
Para todo xÝ\Z se 3 divide x então 9 divide x.
Para todo xÝ\Z se 3|x então 9|x.
ýxÝ\Z.(3|x -> 9|x).
1b) (0.3 pts)
(**) ýaÝ\Z.(9|a -> 3|a).
Para aÝZ se 9 divide a então 3 divide a.
Para todo inteiro a se 9 divide a então 3 divide a.
1c) (2.4 pts)
A sentença (*), "ýxÝ\Z.(3|x -> 9|x)", é falsa.
Para refutá-la basta mostrar um contra-exemplo; os contra-exemplos
possíveis são 3, 6, 12, 15, 21, 24, ... e -3, -6, -12, -15, etc.
Em detalhes:
3|12 é verdade e 9|12 é falso;
daí (3|12 -> 9|12) é falso,
e se x=12 então (3|12 -> 9|12) é falso;
daí (ýxÝ\Z.(3|x -> 9|x)) é falso.
A sentença (**), "ýaÝ\Z.(9|a -> 3|a)", é verdadeira. Vamos prová-la.
Começamos supondo que a é um inteiro tal que 9|a.
Então pela definição de divisibilidade existe um inteiro b tal que 9b=a.
Como 9=3·3 então 9b=(3·3)b=3(3b); como 9b=a então a=9b=3(3b).
Dai existe um inteiro c, c=3b, tal que a=3c, e pela definição de
divisibilidade temos que 3|a.
Concluímos que para qualquer aÝZ se 9|a então 3|a -
ou seja, que ýaÝ\Z.(9|a -> 3|a).
2) (2.0 pts)
"A" "D" "B" "C"
P Q R P∧Q (P∧Q)->R Q->R P->(Q->R) P->R Q->(P->R)
--------------------------------------------------------
F F F F V V V V V
F F V F V V V V V
F V F F V F V V V
F V V F V V V V V
V F F F V V V F V
V F V F V V V V V
V V F V F F F F F
V V V V V V V V V
As sentenças A, B e C são logicamente equivalentes,
e a sentença D não é equivalente a nenhuma delas.
Em todas as situções nas quais D é verdade A, B e C
também são verdade, portanto D->A, D->B e D->C são
verdade; mas A-/->D, B-/->D e C-/->D, porque há uma
situação - P=0, Q=1 e R=0 - na qual A, B e C são
verdadeiras mas a D é falsa.
3a) (1.0 pts)
Ela tem que pôr um dos 30 CDs na primeira bandeja,
um dos 29 outros CDs na segunda bandeja,
um dos 28 outros CDs na terceira bandeja,
e um dos 27 outros CDs na quarta bandeja.
Daí ela tem 30·29·28·27 modos diferentes de colocar
quatro CDs no aparelho.
b) (1.0 pts)
Um modo de escolher os 4 CDs é uma lista de quatro
números, (a,b,c,d), na qual a,b,c,d Ý {1, 2, ..., 30}
e não há repetições - ou seja, a!=b ∧ a!=c ∧ a!=d ∧
b!=c ∧ b!=d ∧ c!=d.
O conjunto das soluções do problema é o conjunto de
todas estas listas:
S = {(a,b,c,d)| a,b,c,dÝ{1,2,...,30} ∧
a!=b ∧ a!=c ∧ a!=d ∧
b!=c ∧ b!=d ∧
c!=d},
e vimos que S tem exatamente 30·29·28·27 elementos
diferentes; em matematiquês, |S| = 30·29·28·27.
4) (1.0 pts) Há várias provas possíveis. Uma é:
(A×B)×C
--> {(x,c)|xÝA×B, cÝC}
--> {(x,c)|xÝ{(a,b)|aÝA, bÝB}, cÝC}
--> {((a,b),c)|aÝA, bÝB, cÝC}
--> {((a,b),c)|aÝ{1,2}, bÝ{3,4}, cÝ{5,6}}
--> {((1,3),5), ((1,3),6), ((1,4),5), ((1,4),6),
((2,3),5), ((2,3),6), ((2,4),5), ((2,4),6)}
A×(B×C)
--> {(a,y)|aÝA, yÝB×C}
--> {(a,(b,c))|aÝA, bÝB, cÝC}
--> {(1,(3,5)), (1,(3,6)), (1,(4,5)), (1,(4,6)),
(2,(3,5)), (2,(3,6)), (2,(4,5)), (2,(4,6))}
e aí vemos que (A×B)×C tem elementos que não estão em A×(B×C)
e vice-versa.
5) (2.0 pts)
A = {1, 2}
B = {{1, 2}, 1, 2}
AÝB --> A={1, 2} ∨ A=1 ∨ A=2
--> V ∨ F ∨ F
--> V
A \subseteq B --> ýaÝA. aÝB
--> ýaÝ{1, 2}. aÝB
--> 1ÝB ∧ 2ÝB
--> V ∧ V
--> V
\end{verbatim}
}
%*
\end{document}
% Local Variables:
% coding: raw-text-unix
% ee-anchor-format: "«%s»"
% End: