LISTA 1 2010.2

Prévia do material em texto

Cin –UFPE 
Centro de Informática 
 
Lista de Exercícios de Matemática Discreta 2010.2 
Graduação em engenharia da computação e sistema de informação 
 
05 de outubro de 2010 
 
 
Questão 1: Prove sem utilizar a equação 78 que: 
 
A U (B ∩ C) = (A U B) ∩ (A U C); 
 
Questão 2: Dada as premissas, mostre como chegar à conclusão: 
a) Premissas: A ∨ B b) Premissa: P ∨ (Q ^ R) 
 A → C Conclusão: P ∨ Q 
 ¬D → ¬B 
 Conclusão: C ∨ D 
 
c) Premissa: L ^ M d) Premissas: (L ^ M) → ¬P 
Conclusão: ( (P → Q) → P ) → P I → P 
 M 
 I 
 Conclusão: ¬L 
Questão 3: Prove que, se A ⊆ B e C = {x: x ∈ A ^ x ∈ B}, então C = A. 
Dividindo a prova em dois passos: 
 a) Sejam as premissas: ∈ ∈ ∈ ∈ ∈ ∈ . Conclua que ∈ . 
 b) Sejam as premissas: ∈ ∈ ∈ ∈ ∈ ∈ .Conclua que ∈ . 
Questão 4: Prove usando equivalência lógica que as seguintes equações são tautologias (as 
equações 16 e 17 estão proibidas): 
 
 1) 
 
 2) 
 
Questão 5: (Paradoxo de Russel) Considere R como sendo o conjunto de todos os conjuntos 
que não contêm a si mesmos. Ou seja: R = {A: A é um conjunto e A não pertence a A }. 
Explique porque R não é um conjunto bem definido. 
Questão 6: Negue as proposições abaixo. 
 
a) ( ∈ )( ∈ ) m > n 
b) ( ∈ )( ∈ ) x + y = 0 
c) ( ∈ )( ∈ ) x + y = y + x 
 
Definição de quantificador universal único: Usamos o símbolo para designar o 
quantificador existencial único.Escrevemos: 
 ∈ ∈ ∈ ∈ 
Ou seja, existe e é único o x pertencente a A tal que p(x) é verdadeira. 
Exemplo: ∈ 
 
Questão 7: Sejam p e q duas proposições: 
 
a) Construa a tabela verdade de 
b) Determine uma proposição equivalente à ,ou seja, complete . 
Use as equivalências lógicas para provar tal equivalência. 
 
Questão 8: A diferença simétrica entre os conjuntos A e B, denotada por , é definida como 
os elementos que estão em A ou em B, porém não estão na intersecção de ambos. 
 
a) Prove que : ; 
b) Mostre que a diferença simétrica é associativa, ou seja 
 
Questão 9: Prove que A = B tendo que A – B = B – A. 
(Dica, considere as seguintes equações: ⊆ ⊆ 
 ⊆ ) 
 
 
 
 
 
Façam a lista com dedicação porque ela vai ajudá-los na prova! Bons 
Estudos! 
Monitoria de Discreta