M0-MDL-DEMAT-UFRRJ-03-2011v2.pptx

Prévia do material em texto

3/21/11	
  
1	
  
Priscila Machado Vieira Lima 
Março/2011 
Departamento de Matemática 
Instituto de Ciências Exatas 
Universidade Federal Rural do Rio de Janeiro 
Matemática Discreta e Lógica – 
Módulo 0 
Roteiro 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 2 
  Motivação 
  Resolução de Problemas 
  Estrutura do Curso 
  Avaliação 
  Bibliografia 
3/21/11	
  
2	
  
Responda rápidamente 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 3 
 O que veio primeiro: o ovo ou a galinha? 
 É fresquinho porque vende muito ou 
Vende muito porque é fresquinho? 
 Teoria ou Prática? 
Matemática (e Lógica) 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 4 
 Teoria? Argh?! 
 Para que estudar, então? 
 MODELAGEM DE PROBLEMAS 
 (e de soluções) 
3/21/11	
  
3	
  
Matemática Discreta (e Lógica) 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 5 
 Ramo da Matemática que lida com 
 Valores Discretos (ex: Inteiros) 
  em oposição a Valores Contínuos 
 Combinatória 
 Teoria de Grafos 
 Teoria da Computação 
… 
 Lógica – relação com Matemática Discreta 
Roteiro 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 6 
  Motivação 
  Resolução de Problemas 
  Estrutura do Curso 
  Avaliação 
  Bibliografia 
3/21/11	
  
4	
  
Resolvendo Problemas 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 7 
  Forme uma dupla: 
  Um membro da dupla responsável por resolver o problema 
  O outro responsável por explicar como o problema foi resolvido 
Problema1: Ciganas e Moças 1/2 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 8 
  Sabendo que cada cigana leu a mão de apenas uma das 4 moças, 
descubra qual cigana leu a mão de qual moça: 
  Azul: “Eu adivinhei o futuro de uma 
morena.” 
  Laranja: “Eu li a mão de Norma.” 
  Verde: (nada a declarar) 
  Vermelha: (nada a declarar) 
3/21/11	
  
5	
  
Problema1: Ciganas e Moças 2/2 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 9 
1.  (nada a declarar) 
2.  “Célia e Lea são morenas.” 
3.  “A cigana vermelha não previu o futuro de Lea e nem o meu.” 
4.  “Eu não sou Célia e Marta usa cabelo preso no alto da cabeça.” 
(Adaptado de Apostila de Lógica Matemática _ ILTC ) 
(1) (2) (3) (4) 
Problema2: A dona da Zebra 1/2 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 10 
  Na calçada par de uma rua da cidade de Ondenópolis existem 5 
casas adjacentes. Casa casa possui uma cor diferente e é habitada por 
uma mulher de nacionalidade diferente. A dona de cada casa tem um 
animal de estimação diferente, bebe uma bebida diferente e exerce 
uma profissão diferente das demais vizinhas. Por uma razão não 
revelada aqui, um detetive foi encarregado de descobrir qual mulher 
bebe água e qual delas possui uma zebra. O detetive apurou o 
seguinte: 
1.  A inglesa mora na casa vermelha. 
2.  A espanhola possui um cachorro. 
3.  Bebe-se café na casa verde. 
4.  A ucraniana bebe chá. 
5.  A casa verde fica imediatamente à direita da casa marfim. 
6.  A engenheira possui um caracol. 
3/21/11	
  
6	
  
Problema2: A dona da Zebra 1/2 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 11 
7.  A diplomata vive na casa amarela. 
8.  Bebe-se leite na casa do meio. 
9.  A norueguesa vive na primeira casa da esquerda para a direita. 
10.  A médica vive ao lado da dona da raposa. 
11.  A diplomata vive ao lado da dona do cavalo. 
12.  A professora bebe suco de laranja. 
13.  A carpinteira é japonesa. 
14.  A norueguesa vive ao lado da casa azul. 
http://www.math.uwaterloo.ca/navigation/ideas/Zeno/zenologic.shtml#zebra 
Problemas3: Bal e Da 1/3 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 12 
  Numa ilha de localização obscura no Triângulo das 
Bermudas (pertinho da Ilha de Lost), seus habitantes foram 
expostos a um misterioso fenômeno que fez com que 
exatamente metade da população fale SEMPRE mentiras 
enquanto a outra metade fala SEMPRE a verdade. 
  Não é possível distinguir os indivíduos do grupo dos Troos 
(falam verdade) daqueles do grupo dos Fals (falam 
mentira). 
3/21/11	
  
7	
  
Problemas3: Bal e Da 2/3 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 13 
  Pessoas de ambos os grupos entendem bem várias línguas, 
mas só respondem numa língua desconhecida. 
  Em particular, observou-se que as palavras Bal e Da 
significam resposta afirmativa e negativa. Contudo, não se 
apurou qual delas corresponde a SIM e qual a NÃO. 
Problemas3: Bal e Da 3/3 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 14 
1.  Ao perguntar a um nativo: “Bal significa SIM?”, ele 
respondeu: “Bal”. 
a)  É possível inferir o que Bal significa? 
b)  É possível inferir a que grupo o nativo pertence? 
2.  Qual pergunta pode ser feita a um nativo para saber o que Bal 
significa? 
3.  E qual pergunta pode ser feita a um nativo para saber se ele é 
um Troo ou um Fal? 
R. SMULLIAN, What’s the name of this book?, Penguin Books, 1990. 
3/21/11	
  
8	
  
Problema4: Tio-Sobrinho 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 15 
  Um homem contou aos amigos que tem um tio e um 
sobrinho ambos chamados Rui. Ao contrário de certas 
famílias que costumam homenagear importantes parentes 
mais velhos com o mesmo nome, o tio e o sobrinho do 
homem eram a mesma pessoa! 
  Explique como isso é possível sem envolver nem relacões 
incestuosas nem casamentos entre primos. 
Adaptado de http://www.math.uwaterloo.ca/navigation/ideas/Zeno/zenologic.shtml#incest 
Problema5: O Homem do Elevador 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 16 
  Um homem, que vive no décimo andar de um prédio sem 
porteiro na praia de Icaraí, toma o elevador todo dia para 
ir praticar jogging na praia. Na volta, ele sobe até o sétimo 
andar de elevador e sobe os três andares restantes pela 
escada, a menos que alguém também vá tomar o elevador. 
Se alguém toma o elevador junto com o homem na subida, 
ele sobe direto até o décimo andar. 
  Você poderia explicar tal comportamento? 
  (dica: use seu Pensamento Lateral) 
Adaptado de http://brainden.com/forum/index.php?/topic/56-the-man-in-the-elevator/ 
3/21/11	
  
9	
  
Problema6: Quem é o assassino? 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 17 
  Três pessoas, A, B e C, cruzavam o deserto do Saara em 
caravana. Secretamente A e B odiavam C. Uma noite, A 
envenenou a água do cantil de C. De forma independente, 
B furou o cantil de C, que acabou morrendo de sede algum 
tempo depois. 
  Qual dos dois seria o assassino de C? 
R. SMULLIAN, What’s the name of this book?, Penguin Books, 1990. 
Resolvendo Problemas 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 18 
  Observe que a estratégia de resolução dos problemas foi 
variando (e aumentando em complexidade): 
  Problemas 1 e 2 – dependem de tabelas de possibilidades (V/F). 
  Problemas 3 – dependem de organização das verdades em 
sentenças (V/F e modelagem das correlações). 
  Problema 4 – depende de correlações entre componentes dos 
fatos. 
  Problema 5 – depende de conhecimento externo ao fornecido na 
formulação do problema. 
  Problema 6 – depende de legislação e discussão sobre ética. 
3/21/11	
  
10	
  
Roteiro 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 19 
  Motivação 
  Resolução de Problemas 
  Estrutura do Curso 
  Avaliação 
  Bibliografia 
Estrutura 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 20 
 4,0 créditos 
 Aulas teóricas 
 Terças e Quintas 13 – 15hs 
 Local: Prédio P1 
 Sala: 46 
3/21/11	
  
11	
  
Tópicos 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 21 
  Lógica 
  Proposicional 
  Primeira Ordem 
  Sistemas Dedutivos 
  Álgebra 
  Conjuntos 
  Relações, Funções 
  Reticulados 
  Álgebra Booleana (rapidamente) – vista em Sistemas Digitais  Matemática Combinatória 
Roteiro 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 22 
  Motivação 
  Resolução de Problemas 
  Estrutura do Curso 
  Avaliação 
  Bibliografia 
3/21/11	
  
12	
  
Avaliação (1) 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 23 
 Duas provas (P1 e P2, 
) 
 Um trabalho (T1) em dupla 
 Média M = (2P1 +2 P2 + T1) / 5 
 SE M ≥ 5,0 ENTÃO: 
 SENÃO: 
Obs: A optativa pode substituir a nota de P1 ou P2. 
Avaliação (2) 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 24 
 Datas (Prováveis) 
  P1: 12/05 
  P2: 05/07 
 Entrega de T1: 07/07 
 Optativa: 19/07 
3/21/11	
  
13	
  
Monitoria/Dúvidas 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 25 
 Não há monitor para a disciplina 
 Contactar a professora sempre que houver dúvidas. 
 Horário reservado: quintas 11-12hs (em princípio) 
 ou, a combinar 
 email: priscilamvl@ufrrj.br (preferível) 
 priscilamvl@gmail.com 
Roteiro 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 26 
  Motivação 
  Resolução de Problemas 
  Estrutura do Curso 
  Avaliação 
  Bibliografia 
3/21/11	
  
14	
  
Bibliografia 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 27 
  ROSEN, K. H.: Matemática Discreta e Suas Aplicações. 
6a edição, Mc Graw Hill, 2009. 
  MENEZES, P.B.; Matemática discreta para Computação 
e Informática. 3ª edição, Bookman - Série Livros 
Didáticos, número 16, 2010. 
Bibliografia Complementar 
Março/2011 DEMAT/ICE/UFRRJ – Priscila M. V. Lima 28 
  GERSTING, J. L. Fundamentos matemáticos para a 
ciência da computação. 5ª ed., Rio de Janeiro: LTC, 
2004. 
  SCHEINERMAN, E. R.: Matemática Discreta Uma 
Introdução. Thomson Pioneira, 2003.