Prova1-A

Prévia do material em texto

Departamento de Cieˆncias da Computac¸a˜o
Universidade Federal de Minas Gerais
Matema´tica Discreta
Prof. Jeroen van de Graaf
Prova 01, valendo 30 % da nota final — 27/04/2011
Prova individual com durac¸a˜o de 100 minutos. Inı´cio a`s 07:30 e te´rmino a`s 09:10.
1. (10 pontos)
(a) Determine se (¬p ∧ (p→ q))→ ¬q e´ uma tautologia. Deˆ uma prova ou um contra-exemplo.
(b) Idem para (¬q ∧ (p→ q))→ ¬p.
2. (10 pontos) Considere M(x, y) como “x enviou um email para y” e T (x, y) como “x telefonou para
y”, em que o domı´nio e´ formado por todos os estudantes de uma determinada turma com 10 ou
mais alunos. Use quantificadores para expressar cada uma das proposic¸o˜es a seguir (supondo
que cada email enviado, foi recebido):
(a) Ariane nunca mandou um email ou telefonou para Roberto.
(b) Ha´ (pelo menos) dois estudantes da turma dos quais o primeiro mandou um email para o
segundo e este telefonou para aquele.
(c) Ha´ (pelo menos) dois estudantes que mandaram emails entre si ou que telefonaram para
uma mesma, terceira pessoa da turma.
3. (15 pontos) Seja m a me´dia (aritme´tica) dos nu´meros reais r1, . . . rn, onde na˜o todos os ri teˆm o
mesmo valor. Seja z o ma´ximo deste mesmo conjunto. Prove que z > m.
4. (10 pontos) Neste pergunta voceˆ na˜o precisa justificar as respostas.
(a) Encontre
⋃∞
j=1Aj e
⋂∞
j=1Aj , onde Aj = {−1j , 0, 1j }, um conjunto com treˆs elementos.
(b) Encontre
⋃∞
j=1Aj e
⋂∞
j=1Aj , onde Aj = (−1j , 1j ), um intervalo real.
5. (10 pontos) Um conjunto X e´ conta´vel ou enumera´vel se ele e´ finito ou se existe uma bijec¸a˜o
entre o conjunto N e X. Argumente que os seguintes conjuntos sa˜o conta´veis, mostrando o inı´cio
de uma enumerac¸a˜o sistema´tica dos elementos de X. Deˆ no mı´nimo os primeiros 10 elementos
da enumerac¸a˜o. Na˜o e´ preciso definir a bijec¸a˜o explicitamente.
(a) O conjunto de nu´meros racionais maior que 1.
(b) O conjunto Σ∗ de strings que podem ser formados a partir do alfabeto Σ = {x, y, z}.
6. (25 pontos) Seja P (n) =“3n < n!” onde o domı´nio consiste dos numeros naturais.
(a) Explique por que as afirmac¸o˜es ∀n : (n ≥ 6)→ P (x) e ∀n ≥ 6 : P (n) sa˜o equivalentes.
(b) Prove que P (n) e´ verdadeiro para todo nu´mero natural n ≥ 6, usando induc¸a˜o matema´tica.
7. (20 pontos) Quatro amigos foram identificados como suspeito de uma invasa˜o ao computador da
universidade. Eles fizeram as seguintes declarac¸o˜es:
(A) Alice disse: “Carlos que invadiu”.
(B) Bob disse: “Na˜o fui eu que invadiu”.
(C) Carlos disse: “Diana invadiu”.
(D) Diana disse: “Carlos mentiu ao dizer que fui eu”.
(a) Se os investigadores tambe´m sabem que apenas um dos quatro suspeitos falou a verdade,
quem cometeu a invasa˜o? Justifique.
(b) Se os investigadores tambe´m sabem que apenas um dos quatro suspeitos estava mentindo,
quem cometeu a invasa˜o? Justifique.