% (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:
