Matemática Discreta: Conjuntos e Quantificação

Prévia do material em texto

Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Conjuntos, Quantificação e 
Técnicas de Prova
Prof Edjard Mota
edjard@icomp.ufam.edu.br
1
Baseado nas Notas de aula do professor
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Variáveis e Conjuntos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
○ Todos os coelhos têm pêlo
○ Alguns animais são coelhos
○ Alguns animais têm pelo
	Considere	as	premissas	e	uma	possível	conclusão	
Animais
Coelhos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Variáveis e Conjuntos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
○ Todos	os	coelhos	têm	pêlo	
○ Alguns	animais	são	coelhos	
○ Alguns	animais	têm	pelo
	Considere	as	premissas	e	uma	possível	conclusão	
Animais
Coelhos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
○ Todos	os	peixes	são	mamíferos	
○ Moby	Dick	é	um	peixe	
○ Moby	Dick	é	um	mamífero
Matemática Discreta
Variáveis e Conjuntos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
○ Todos	os	coelhos	têm	pêlo	
○ Alguns	animais	são	coelhos	
○ Alguns	animais	têm	pelo
	Considere	as	premissas	e	uma	possível	conclusão	
Peixes	&	Mamíferos
Moby	Dick
Animais
Coelhos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Variáveis e Conjuntos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
○ Todos	os	coelhos	têm	pêlo	
○ Alguns	animais	são	coelhos	
○ Alguns	animais	têm	pelo
	Considere	as	premissas	e	uma	possível	conclusão	
Animais
CoelhosCoelhos
Moby	Dick
○ Todos	os	peixes	são	mamíferos	
○ Moby	Dick	é	um	peixe	
○ Moby	Dick	é	um	mamífero
Peixes	&	Mamíferos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Variáveis e Conjuntos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
○ Todos	os	coelhos	têm	pêlo	
○ Alguns	animais	são	coelhos	
○ Alguns	animais	têm	pelo
	Considere	as	premissas	e	uma	possível	conclusão	
Animais
CoelhosCoelhos
○ Todos	os	cavalos	são	mamíferos
○ Todos	os	cavalos	são	vertebrados
○ Todos	os	mamíferos	são	vertebrados
Moby	Dick
○ Todos	os	peixes	são	mamíferos	
○ Moby	Dick	é	um	peixe	
○ Moby	Dick	é	um	mamífero
Peixes	&	Mamíferos
Animais
mamíferos
cavalos
vertebrados≠
São coleções de objetos!!!!
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática
IA
Limitação da LP
Lógica Proposicional representa o mundo em termos 
de fatos - sentenças que podem ser V ou F.
Precisamos de uma lógica para coleções de
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática
IA
Limitação da LP
Lógica Proposicional representa o mundo em termos 
de fatos - sentenças que podem ser V ou F.
pessoas
jogos
cursosnúmeros
Precisamos de uma lógica para coleções de
✦ Objetos simples: pessoas, 
jogos, números, Russel, Alan, 
cursos, …(informação 
atômica)
Conjuntos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática
IA
Limitação da LP
Lógica Proposicional representa o mundo em termos 
de fatos - sentenças que podem ser V ou F.
pessoas
jogos
cursosnúmeros
Precisamos de uma lógica para coleções de
✦ Objetos simples: pessoas, 
jogos, números, Russel, Alan, 
cursos, …(informação 
atômica)
✦ Objetos compostos:
pontos (2D e 3D), 
formas, etc.
Conjuntos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Variáveis e Conjuntos
Conjunto	é	uma	abstração	matemática	que	visa	capturar	o	
conceito	de	coleção.	Define	uma	propriedade	satisfeita	pelos	
elementos.
Conjunto Lógica Significado
a ∈ A A(a) a pertence ao conjunto	A
a ∉ A ¬A(a) a não pertence ao conjunto	A
Lê-se:	O	conjunto	de	todo	os	valores	x	que	tornam	p(x)	
Verdadeiro		(ou	“todo	x	em	U	tal	que	p(x)”)
Conjunto	verdade	de	p(x),	onde	x	é	uma	variável,	é	o	
conjunto	de	todos	os	valores	x	que	tornam	p(x)	
verdadeiro	(V).	Escrevemos	p(x) = {x | p(x) é verdadeiro}
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Variáveis e Conjuntos
Exemplos:
p(x) ={x | x foi escrito por Jorge amado} = {tiêta, …}
p(x) ={x | x é um número primo que é par} = {2}
p(x) ={x | x é unidade da UFAM} = {IComp, FT, …}
Notações mais comuns
‣ { x | P(x) }, e.g. { k | k = 2n+1 e n ∈ ℕ } 
‣ { x | x ∈ A e P(x) }, e.g. { k ∈ ℝ | 0 ≤ k ≤ 1 }
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
Representar Quantificação
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
✦ Quantificar é selecionar
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
Representar Quantificação
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
Algumas pessoas 
são atletas
✦ Quantificar é selecionar
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
Algumas pessoas 
são cientistas.
Representar Quantificação
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
Algumas pessoas 
são atletas
✦ Quantificar é selecionar
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
Algumas pessoas 
são cientistas.
Representar Quantificação
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
Algumas pessoas 
são atletas
Todos cientistas 
ensinam.
ensina
mãe
gosta
amigo etc
<
✦ Quantificar é selecionar
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
Algumas pessoas 
são cientistas.
Representar Quantificação
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
Algumas pessoas 
são atletas
Todos cientistas 
ensinam.
ensina
mãe
gosta
amigo etc
<
✦ Quantificar é selecionar
Algumas pessoas 
jogam videogame.
joga
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Existe uma pessoa 
que ensina 
matemática e 
joga PS4
Representar Quantificação
ensina
mãe
gosta
amigo etc
<
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
✦ Quantificar é selecionar
joga
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Lógica Quantificável 
∀ : para todo,∃: existe
Existe uma pessoa 
que ensina 
matemática e 
joga PS4
Representar Quantificação
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
✦ Quantificar é selecionar
Toda pessoa que joga 
videogame pontua
ensina
mãe
gosta
amigo etc
<
pontua
joga
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Lógica Quantificável 
∀ : para todo,∃: existe
Existe uma pessoa 
que ensina 
matemática e 
joga PS4
Representar Quantificação
✦ Conjuntos e relações: pessoas, números, mãe, gosta, <, etc.
✦ Objetos simples: pessoas, jogos, 
números, Russel, Alan, cursos, …
✦ Quantificar é selecionar
Toda pessoa que joga 
videogame pontua
ensina
mãe
gosta
amigo etc
<
pontua
joga
∀x∀y∀n(pessoa(x) ∧ videogame(y) ∧ joga(x,y)→ pontua(x,y,n)
∃x(pessoa(x) ∧ ensina(x, matemática))
∃x(pessoa(x) ∧ atleta(x))
∀x(pessoa(x) ∧ cientista(x)) → ∃y disciplina(y) ∧ ensina(x,y)
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard MotaMatemática Discreta
Equivalência entre ∀ e ∃
Lei da Negação de Quantificação
¬∃x p(x) ⇔ ∀x ¬p(x)
¬∀x p(x) ⇔ ∃x ¬p(x)
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tipos e conjuntos e importantes
Conjunto
vazio:		∅
unitário,	e.g. {2}
finito,		e.g.
infinito {1, 2 , …}
Números
ℕ:	naturais
ℤ:	inteiros
ℝ:	reais
ℚ:	racionais
Relações básicas
subconjunto	(A	⊆ B)
subconjunto	próprio		
(A	⊂ B)
Todo	conjunto	contem	∅	
Notação em Lógica
∀x (x ∈ A → x ∈ B)
A	⊆ B
∅	⊆ A
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Operações sobre conjuntos
Operação Notação em Lógica
A ∪ B	(união) {x | x ∈ A ∨ x ∈ B)
A ∩ B	(interseção) {x | x ∈ A ∧ x ∈ B)
A \ B (diferença) {x | x ∈ A ∧ x ∉ B)
A B
A B
A B
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
`
Definição
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Exemplos
● {1,3,5,7} e {2,4,6,8}
Conjuntos disjuntos
A B
Dois conjuntos A e B são disjuntos 
se, e somente se A ∩ B	=	∅, isto é 
¬∃x (x ∈ A ∧ x ∈ B)
1 23 45 67 8
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
`
Definição
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Exemplos
● {1,3,5,7} e {2,4,6,8}
Conjuntos disjuntos
A B
Dois conjuntos A e B são disjuntos 
se, e somente se A ∩ B	=	∅, isto é 
¬∃x (x ∈ A ∧ x ∈ B)
1
2
3 45 67
8
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
`
Definição
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Exemplos
● {1,3,5,7} e {2,4,6,8}
● A\B e B\A,
A={1,3,5,7} e A ={2,4,6,8}
● ℕ e ℤ−
Conjuntos disjuntos
A B
Dois conjuntos A e B são disjuntos 
se, e somente se A ∩ B	=	∅, isto é 
¬∃x (x ∈ A ∧ x ∈ B)
1
2
3 45 67
8
1
2 3
4
56
8
1 2 3 4 5-5 -4 -3 -2 -1 0
ℕℤ− ?
Edjard De Souza Mota
8
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Equivalências, Generalizações
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
A ∪ B ⇔ B ∪ A
A ∩ B ⇔ B ∩ A
A ∩ (B ∪ C) ⇔ (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) ⇔ (A ∪ B) ∩ (A ∪ C)
A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)
União de n 
conjuntos
Interseção de n 
conjuntos
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Partição
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Uma partição de um conjunto A é uma família de 
conjuntos {A1, A2, …, An} tal que
1. Ai ≠ ∅, em que 1 ≤ i < n
2. Ai ∩ Aj = ∅, em que 1 ≤ i < n, 1 ≤ j < n e i ≠ j
3. �1 ≤ i < n �Ai = A
A2 A1 A5A3A4
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Qual P		({1,2,3})	?
{ ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
Se |A| denota a quantidade de elementos de A, 
(conhecido como cardinalidade) qual é o valor de |P (A)|?
|P		(A)| = 2|A|
Conjunto potência
O conjunto potência de um conjunto A, P (A), é uma 
família de conjuntos {A1, A2, …, An} tal que cada Ai é 
subconjunto de A, isto é P (A)	= { X | X ⊆ A}.
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
● ∅ × {1,2} =	∅
● {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}	
● |A × B| = |A|.|B|, se	A	e	B	são finitos
● An = A × A × ... × A (n	vezes)
Produto cartesiano
O produto cartesiano entre dois conjuntos A e B, escrito 
A × B, é formado por todos os pares ordenados 
possíveis de serem formados com elementos de A e B, 
nesta ordem, isto é A × B = { (a, b) | x ∈ A ∧ x ∈ B}.
Um par ordenado de dois objetos a e b é um objeto 
composto, escrito (a, b), cuja posição de suas 
coordenadas importa. Isto é (a, b) ≠ (b, a).
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Prova de Teoremas
• O que é uma Prova? Um método para
estabelecer a verdade
★ Juri: grupo de pessoas decidem o veredicto
★ Ciência experimental: assume-se uma verdade (hipótese)
e busca-se sua confirmação ou não
★ Amostragem: verdade obtida através de análise
estatística com pequenas evidências.
★ Subjetivas: intimidação, auto-convicção, palavra de Deus.
★ “Ideologia”: “as provas factuais são ideologicamente 
falsas, logo não servem como prova para o que quero
provar. Portanto, o que creio está provado.”
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Prova de Teoremas
Prova Matemática: é a verificação de uma proposição 
através de uma seqüência de deduções lógicas a 
partir de uma base de axiomas. (e.g. resolução)
Exemplos:
Proposição 1. 2 + 3 = 5.
É uma verdade fácil de verificar: II + III = IIIII
Proposição 2. “todo número inteiro maior que 2 é a 
soma de dois números primos” (Goldbach, 1742). Até 
hoje sem prova! Exemplo: 24 = 11 + 13, 26 = 13 + 13.
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Prova de Teoremas
Por que problemas como este são importantes?
Áreas de curvas elípticas dependem dessas 
equações.
Fatoração de números inteiros muito grandes 
depende da área de curvas elípticas. 
Sistemas criptográficos dependem da fatoração de 
inteiros muito grandes. 
Sistemas seguros de comunicação se baseiam em 
criptografia.
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Técnicas de Prova
T1. (Direta) Supor Premissas verdadeiras e provar 
conclusão. Provar que p → q, assumir p e provar q.
Proposição. 
Suponha a e b reais. Prove que se 0 < a < b, então a2 < b2
Técnica Dados Meta
0 - a, b ∈ ℝ (0 < a < b) → (a2 < b2)
1 T1 a, b ∈ ℝ,
(0 < a < b)
a2 < b2
Multiplicando ambos lados de a < b por a	temos a2 < ab. 
Analogamente, (a < b)×b	temos ab < b2. Portanto, como 
temos a2 < ab < b2, por transitividade a2 < b2. ?
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Técnicas de Prova
T2. (Contra-positivo) Para provar que p → q, assumir ¬q 
e provar ¬p.
Proposição. Suponha que a, b e c são reais e a > b. Provar que 
se ac ≤ bc, então temos que c ≤ 0
Técnica Dados Meta
0 - a, b,c ∈ ℝ e a > b. (ac ≤ bc) → (c ≤ 0)
1 T2 a, b,c ∈ ℝ e a > b.
¬(c ≤ 0) = c > 0 ¬(ac ≤ bc) = ac > bc
Multiplicando ambos lados de a > b por c	temos ac > bc. ?
Aula 05 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Técnicas de Prova
T2. (Contradição/prova por absurdo) Para provar que ¬p, 
reescrever ¬p ou assumir p e chegar a uma contradição.
[Prova] Assumimos que 	 é racional. Então 	 = a ⁄ b, onde a e 
b são inteiros, b > 0, a ⁄ b é uma fração não redutível. 
Elevando ambos os lados ao quadrado temos 	 = a2⁄ b2. 
Multiplicando ambos os lados por b2 temos 	 b2 = a2. Isso 
implica que a é par, e a2 é múltiplo de 4. Então b2 também 
é par, e por isso b também é par. Porém a ⁄ b não é 
redutível, logo isso é uma contradição. Portanto 	�não 
pode ser racional. ?
� �
�
Proposição. 2 é um número não racional (ou irracional).�