Matemática Discreta - Conjuntos [EDITADO POR MIM]

Prévia do material em texto

Matemática Discreta
Profª Malga
Conjuntos
Introdução e conceitos Básicos
Conjuntos são fundamentais para a formalização de qualquer teoria. Uma teoria é normalmente construída a partir de um conjunto de pressupostos básicos (axiomas), os quais fazem referência a um conjunto de elementos primitivos (que não precisam ser definidos). A partir destes elementos, e utilizando um conjunto de regras de inferência (tais como as leis e propriedades da Lógica Matemática), é criado um conjunto de propriedades, enunciados e provados através de teoremas. 
2
Conjuntos
Introdução e conceitos Básicos
Em particular, em Informática e Ciência da Computação, a Teoria de Conjuntos apresenta-se das mais diversas formas:
 Como fundamento para a construção das Álgebras Booleanas, cerne da Computação Digital;
 Como fundamento teórico para o desenvolvimento e validação da Teoria de Bancos de Dados;
 Como fundamento teórico para o desenvolvimento de Linguagens Formais; 
Etc.
3
Conjuntos
Introdução e conceitos Básicos
Mas em Ciência da Computação também, os conjuntos de dados, sejam eles numéricos ou não, podem ser úteis, por exemplo, em armazenamento de dados, no momento de trabalhar com classificação ou regressão em um algoritmo inteligente, ao trabalhar com visão computacional, entre outras inúmeras aplicações.
4
Conjunto, Elemento & Relação de Pertinência
Os conceitos primitivos da Teoria de Conjuntos são:
 Conjunto
 Elemento 
 Relação de Pertinência
Note que não se pode definir um destes conceitos sem fazer referência aos demais. 
5
Conjunto, Elemento & Relação de Pertinência
 Um conjunto é uma reunião de elementos segundo uma característica comum;
 Um elemento é uma entidade que pertence a um conjunto; 
 A relação de pertinência indica se um elemento pertence a um conjunto ou não. 
Assim se o elemento pertence ao conjunto é porque possui a característica de define aquele conjunto, e vice-versa. 
6
Conjunto - Notações
A seguinte notação é a usual em Teoria de Conjuntos:
 
Elementos: são normalmente representados por letras latinas minúsculas 
Exemplos: a, b, c, ... 
Conjuntos: são normalmente representados por letras latinas MAIÚSCULAS 
Exemplos: A, B, C, ...
Relação de Pertinência: é representada pelo símbolo ∈, criado por Georg Cantor. 
7
Conjuntos: Formas de Representação
Há diversas formas de representação de conjuntos. Algumas são mais adequadas para a compreensão de propriedades e características. Outras, são necessárias para a demonstração de teoremas, comprovação de propriedades, ou mesmo, para simplificação da representação. 
8
Conjuntos: Formas de Representação
Por extensão:
Consiste em descrever, um a um, todos os elementos do conjunto. Em conjuntos com muitos ou mesmo infinitos elementos podem ser usadas expressões indicando a lei de formação dos elementos pertencentes ao conjunto. 
Por Exemplo:
A= {C++, Delphi, Java, Python, ...}
B= {Análise, Projeto, Implementação, Teste, Correção, Término}
C= {a, e, i, o, u}
D= { (1,a), (3, b), (5, c)}
9
Conjuntos: Formas de Representação
Conjuntos Numéricos - Relembrar
10
Conjuntos: Formas de Representação
Conjuntos Numéricos - Relembrar
11
Conjuntos: Formas de Representação
Conjuntos Numéricos - Relembrar
12
Conjuntos: Formas de Representação
Por compreensão:
Consiste em descrever o conjunto através de uma propriedade lógica (uma proposição) comum a todos seus elementos. 
Por Exemplo:
A= {x / x  N ˄ x é ímpar  x < 5}
B= {z / z é múltiplo de 4}
C = {(x,y) / x R ˄ y = x+1}
D= { x /x =  m  Z ˄ n  Z* }
13
Conjuntos: Formas de Representação
Por compreensão:
Pontos positivos: sucinta, fácil de manipular, formal e útil para o desenvolvimento de raciocínios. Permite representar conjuntos com muitos (ou infinitos) elementos. 
Pontos negativos: não permite a visualização direta dos elementos, exige a determinação formal de uma proposição para a propriedade que define o conjunto.
14
Conjuntos: Formas de Representação
Por gráfico:
Consiste em descrever o conjunto através de gráficos cartesianos.
Por Exemplo:
A = { x ∈ R / -1 ≤ x < 2 }
B = { ( x, y ) / x ∈ Z ∧ y ∈ R }
Bolinha aberta: Não pertence
Bolinha fechada: Pertence
15
Conjuntos: Formas de Representação
Por diagrama de Venn:
Diagramas de Venn são representações esquemáticas de conjuntos.
Por Exemplo:
a) A = { 1, 2, 3 }
b) B = { 1, 2, 4 }
 C = { 2, 3, 4, 6 }
16
Conjunto Vazio & Conjunto Universo
Outros elementos primitivos da Teoria de Conjuntos são:
O conjunto universo;
O conjunto vazio.
O conjunto universo é definido como o conjunto que contém todos os conjuntos. Isto é, é um conjunto do qual são tirados todos os elementos usados para a criação dos conjuntos com os quais se está trabalhando. Sua existência é fundamental para garantir a coerência da Teoria de Conjuntos. 
Conjunto Universo: usualmente representado pelo símbolo U. 
Conjunto universo – Contém tudo com a característica que eu determinei (Conjunto que contém todos os conjuntos) – Simbolo U
17
Conjunto Vazio & Conjunto Universo
O conjunto vazio é definido como um conjunto que não possui elementos. Sua existência também é fundamental para a definição das operações entre conjuntos.
Conjunto Vazio: usualmente representado pelos símbolos ∅ ou { }. 
Conjunto vazio – Não possui elementos - Símbolos ∅ ou { }
18
Intervalos
Intervalos são conjuntos de números reais. Devido a sua importância e para facilitar sua escrita, foi adotada a seguinte notação: 
[ a;b ] – Ambos incluídos
( a;b ] – Apenas o b incluido
] a;b ] – Apenas o b incluído
[ a;b ) – Apenas o a incluido
[ a;b [ – Apenas o a incluído
( a;b ) – Nenhum incluido
] a;b [ – Nenhum incluido
19
Relações entre Conjuntos
O relacionamento entre conjuntos é o que torna a Teoria de Conjuntos útil. Por hora, será suficiente compreender as relações básicas apresentadas a seguir. No entanto, é fundamental compreender que o relacionamento entre conjuntos é sempre feito através de proposições. Isto é, uma relação entre dois entes sempre gera uma proposição. 
20
Relações entre Conjuntos
Relação de Inclusão
Dados dois conjuntos, A e B, diz-se que A está contido em B se e somente se qualquer elemento de A for também elemento de B. Nestas condições escreve-se A ⊆ B. 
Em notação lógica: 
A ⊆ B ⇔ (∀x) (x ∈ A → x ∈ B)
21
Relações entre Conjuntos
Na Relação de Inclusão valem as propriedades:
∅ ⊆ A 
A ⊆ A 	Prop. Reflexiva 
( A ⊆ B ) ∧ ( B ⊆ C ) ⇒ A ⊆ C Prop. Transitiva
22
Relações entre Conjuntos
Outras Relações
Considere os conjuntos A = {a,b,c,d,e}, B = {c,d,e} e C = {d,e,f }. Podemos dizer que:
a  A (o elemento a pertence ao conjunto A)
a  B (o elemento a não pertence ao conjunto B)
A  B (o conjunto A contém o conjunto B)
B  A (o conjunto B está contido em A)
C  A (o conjunto C não está contido em A)
A C (o conjunto A não contém C)
23
Exercícios
1) Considerando os conjuntos A = { y, x, y, z } , B={ z, y, z, x } , C={ z, y, x, y } e D={z, z, x, y } , escolha a alternativa correta:
O conjunto A é igual ao B e o conjunto C é igual ao 
Todos os conjuntos (A, B, C e D) são iguais.
O conjunto A é igual ao C e o conjunto B é igual ao D.
Apenas os conjuntos A, B e D são iguais.
2) Marque a opção que apresenta uma representação de conjunto correta:
A=[ 1,2,3] .
b={ A,B,C} .
B=x.y.z.
T={ a,b,c,d} 
B: x,y,z.
3) Considere o conjunto A = {{ 1, 2, 3} , { 4, 5} , { 6, 7, 8}} . A opção correta que lista os elementos de A é:
A tem oito elementos: 1, 2, 3, 4, 5, 6, 7, 8.
A tem três elementos, os conjuntos { 1, 2, 3} , { 1, 2, 3, 4, 5} e { 6, 7, 8} .
A tem dois elementos, os conjuntos { 1, 2, 3} , { 4, 5, 6, 7, 8} .
A tem três elementos, os conjuntos { 1, 2, 3} , { 4, 5} e { 6, 7, 8}
A tem oito elementos, os conjuntos { 1} , { 2} , { 3} , { 4} , { 5} , { 6} , { 7} , { 8} .
24
É
/