Prévia do material em texto
ELEMENTOS DA TEORIA DOS CONJUNTOS
Prof. Dr. Antonio Gil V. de Brum - acompanha o arquivo conjuntos.pdf
(ref.: GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. 5 ed., Rio de Janeiro, LTC, 2004;)
CONJUNTOS Coleção de objetos que, em geral, têm algo em comum.
Notação: A, B, C, D, X, Y, W, ... (em maiúsculas)
Obs.: a, b, c, x, y, w, ... => elementos de um conjunto (em minúsculas)
Exemplo 1.
(relação de pertinência)
Se A = {1, 2, 3, 4}, então 1 A e 5 A
Se X = {verde, amarelo, azul, branco}, então azul X e vermelho X
=> Observe as "chaves", { }: elas identificam os conjuntos.
SÍMBOLOS E NOTAÇÕES GERAIS:
IGUALDADE
de Conjuntos
"Dois conjuntos A e B são iguais se (e
só se) contém os mesmos elementos."
Veja (em lógica de predicados) =>
A = B significa
(x) [(xA xB) (xB xA)]
P.: - Como descrever um conjunto? R.: - Basta identificar seus elementos!
B = {5, 6, 7, 8} é um conjunto finito; S = {2, 4, 6, 8, ...} é um conjunto infinito.
Outras maneiras
de descrever o
conjunto S:
S é o conjunto de todos os inteiros positivos pares;
S = {xZ | x é par}
S = {x | x é um inteiro positivo par}
em 2 passos (por recorrência): 1) 2 S
2) Se n S, então (n+2) S.
Assim, para descrevermos um conjunto podemos:
- Listar (ou listar parcialmente) seus elementos;
- Usar recorrência para descrever como gerar seus elementos;
- Descrever uma propriedade P que caracteriza seus elementos.
=> A NOTAÇÃO p/ um conjunto cujos elementos são caracterizados por uma propriedade P é: {x | P(x)}
Portanto, S = {x | P(x)} significa (x)[(xS P(x)) (P(x) xS)] ,
isto é, todos os elementos de S têm a propriedade P e tudo o que tem a propriedade P pertence a S.
Problema
Prático 1.
Descreva cada um dos conjuntos a seguir listando seus elementos.
a. {x | x é inteiro e 3 < x 7}
b. {x | x é um mês com exatamente 30 dias}
c. {x | x é a capital do Brasil}
Problema
Prático 2.
Descreva cada um dos conjuntos a seguir através de uma propriedade que caracterize seus elementos.
a. {1, 4, 9, 16}
b. {o açougueiro, o padeiro, o produtor de castiçais}
c. {2, 3, 5, 7, 11, 13, 17, ...}
NOTAÇÃO
PADRÃO
N = conjunto dos inteiros não negativos (aqui: incluído o zero, 0N)
Z = conjunto de todos os inteiros
Q = conjunto de todos os números racionais
= conjunto de todos os números reais (união de Q com os conj. dos n
os
Irracionais)
C = conjunto dos números complexos
Exercício. Descreva os conjuntos Z e Q acima a partir de uma propriedade de seus elementos.
Use o fato N = {0, 1, 2, 3, ...}.
Conjunto VAZIO
(conj. sem elementos)
A = ou A = { } ou, ainda,
A = {x | xN e x < 0}
Obs.: A , A é um conjunto, então
A
Exemplo 2: Suponha que o conjunto A é dado por:
Para
Escolhendo y = 0, obtemos x = 0; escolhendo y = 1, obtemos x
= 0 ou x = 1; escolhendo y = 2 obtemos x = 0, ou x = 1 ou x = 2;
etc. Percebe-se, assim, que B consiste em todos os inteiros não
negativos, isto é, B = N.
Para Percebe-se que o único número natural que é menor ou
igual a qualquer número natural é o zero.
Assim, C = {0}.
Problema
Prático 3.
Descreva cada um dos conjuntos a seguir.
Problema
Prático 4.
,
que se lê:
___________________.
Problema
Prático 5.
Use a notação da lógica formal para definir A B.
("A é um subconjunto próprio de B": significa que os elementos de A estão em B,
mas A B, isto é, há pelo menos um elemento de B que não está em A).
Exemplo 3:
Sejam
Então, as seguintes
proposições, dentre
outras, são
verdadeiras:
Problema
Prático 6:
Sejam
Quais das proposições a seguir são verdadeiras?
Exemplo 4:
Sejam
Mostre que A B.
Obs.: Para nós, isso é verdade se e só se
todo elemento de A é também elemento
de B.
Problema
Prático 7:
Sejam
Mostre que A B.
Obs.: Isso é verdade se e só se todo el. de A é
também elemento de B, mas há pelo menos um
el. de B que não pertence a A.
Exemplo 5: Provar que
Obs.: Isso é verdade se e só se todo
el. de A é também elemento de B e
todo el. de B é também el. de A.
Prova em duas partes: i) Ída: mostrar que A B; ii) volta: mostrar que B A.
Exemplo 6: Conjunto da partes de um conjunto.
Problema Prático 8:
Problema Prático 9:
OPERAÇÕES
EM
CONJUNTOS
Obs.:
A/B A-B;
A' A
c
Conjunto
Universo
(S ou U)
Define o contexto dos objetos em questão, que são seus subconjuntos.
Por exemplo, se S = N, então todos os subconjuntos de S conterão apenas naturais.
Exemplo 7 - Seja S o conjunto de todos os estudantes da UFABC.
Então os elementos de (S) são conjuntos de estudantes.
Seja A o conjunto de estudantes de ciência da computação e seja B o conjunto de
estudantes de engenharia. Ambos A e B pertencem a (S).
Nesse contexto, novos conjuntos de estudantes podem ser definidos. Por exemplo,
C = A U B é o conjunto de todos os alunos que estudam ciência da computação ou
engenharia (ou ambos).
Exemplo 8 -
Problema
Prático 10:
Exemplo 9 -
Uma pesquisa
do tipo:
Exemplo 10 -
Problema
Prático 11:
Problema Prático 12:
Sobre o produto
cartesiano A x B:
Identidades
Básicas
Envolvendo
Conjuntos.
Exempl
o 11 -
Problema Prático 13:
Verifique as identidades 3b e 4a formalmente e com uso dos diagramas de Venn-
Euler.
Seja U um superconjunto
de A e B (isto é, A e B são
subconjuntos de U) e
considere a operação de
complementar relativo a U.
Então,
Exercício: i) verifique as
leis de De Morgan com
diagramas de Euler-Venn;
ii) prove-as formalmente.
Solução: (i) faça você; (ii) segue:
a) use os diagramas de Euler-Venn para provar que (AB)' = A'
B';
b) prove algebricamente a lei de De Morgan, do item anterior.
Resolução:
a) lado esquerdo: (AB)':
=>
<= Apresentação final
de (AB)'
lado direito: A'
B':
Conclusão: percebe-se que os diagramas finais são idênticos (a menos da cor). Assim, (AB)' = A'
B'.
b) Prova algébrica: Utilizaremos o fato que
dois conjuntos A e B são iguais se, e só se, todo elemento de A também é elemento de B
e todo elemento de B também é elemento de A.
Em termos de lógica matemática: A = B <=> (x) [(xA xB) (xB xA)]
Temos que provar que (AB)' = A'
B'.
Para tanto, dividimos a prova em duas partes:
i) ída: onde mostramos que todo elemento x de (AB)' é também elemento de A'
B';
ii) volta: onde mostramos que todo elemento x de A'
B' é também elemento de (AB)' .
Vejamos:
i) ída:
Tomemos x (AB)' => x(AB) => xA ou xB (ou xA e xB) => xA' ou xB' => x(A'
B')
ii) volta:
Tomemos x(A'
B') => xA' ou xB' => xA ou xB => x(AB) => x (AB)'
Fim da demonstração.