Conjuntos, Elementos, Pertinência, Igualdade e Inclusão

Prévia do material em texto

Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos, elementos, pertineˆncia,
igualdade e inclusa˜o
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Marc¸o de 2011
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Suma´rio
• Conjuntos, elementos, pertineˆncia.
• Conjuntos finitos, conjuntos infinitos.
• Definic¸a˜o de conjunto: por lista, por propriedade.
• Conjuntos nume´ricos.
• Igualdade, inclusa˜o.
• Propriedades ba´sicas.
• Problemas e algoritmos.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Christos Papadimitriou
• Autor dos livros Elementos da Teoria da Computac¸a˜o,
Otimizac¸a˜o Combinato´ria: algoritmos e complexidade,
Complexidade Computacional, entre outros.
• Preˆmio Knuth, em 2002 for longstanding and seminal
contributions to the foundations of computer science.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos, elementos, pertineˆncia
Os conceitos
ser um conjunto e ser um elemento de um conjunto
sa˜o considerados como primitivos, i.e., na˜o sa˜o definidos
formalmente.
O nosso entendimento sobre eles e´ guiado pela familiaridade e
a intuic¸a˜o que temos sobre
conjuntos e elementos.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos de elementos
Um problema e´ que a nossa intuic¸a˜o sobre elementos e
conjuntos, geralmente, esta´ errada!
Por exemplo, conjuntos podem ser elementos.
• Podemos considerar o conjunto dos alunos da Turma A2
da disciplina Matema´tica Discreta.
Cada um dos alunos que compo˜em a turma e´ um
elemento deste conjunto.
Bruno e´ um elemento deste conjunto.
• Podemos considerar o aluno Bruno como um conjunto de
o´rga˜os.
Corac¸a˜o e´ um elemento de Bruno.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos de conjuntos
Esta situac¸a˜o e´, na verdade, corriqueira.
• Podemos considerar o conjunto das pastas da pasta
Meus documentos do desktop da Profa. Renata.
Cada pasta armazenada nesta pasta e´ um elemento deste
conjunto.
Assim, um mesmo objeto pode tanto ser considerado como um
elemento ou um conjunto, dependendo do contexto.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
• Bruno ∈ Turma A2
• Jogos 6∈ Meus Documentos
notac¸a˜o leitura
a ∈ b a e´ elemento de b
a ∈ b a pertence a b
a 6∈ b a na˜o e´ elemento de b
a 6∈ b a na˜o pertence a b
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos finitos
Um conjunto e´ finito se possui um nu´mero (natural) bem
determinado de elementos.
• O conjunto cujo u´nico elemento e´ o time carioca que ja´ foi
campea˜o mundial.
• O conjunto das ce´lulas de memo´ria deste computador.
• O conjunto dos gra˜os de areia da praia de Copacabana.
• O conjunto dos a´tomos do universo.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos infinitos
Um conjunto e´ infinito se quando retiramos qualquer
quantidade finita de elementos dele, ele continua tendo
infinitos elementos.
• O conjunto dos nu´meros naturais.
• O conjunto dos nu´meros racionais.
• O conjunto dos pontos do Plano Cartesiano.
• O conjunto das curvas que podemos desenhar no espac¸o.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Definic¸a˜o de conjuntos
Um conjunto e´ denotado pela apresentac¸a˜o de sua definic¸a˜o
entre chaves: { , }.
Vamos estudar duas maneiras de definir um conjunto:
• por lista ou indicac¸a˜o de uma lista,
• por propriedade.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Definic¸a˜o por lista
Para definir um conjunto por lista, apresentamos uma lista dos
“nomes” dos elementos do conjunto.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
Um conjunto definido por lista e´ denotado pela apresentac¸a˜o
dos nomes dos seus elementos separados por v´ırgulas e
encerrados entre chaves.
Meus Documentos =
{Artigos , Orientac¸o˜es , Aulas , Apresentac¸o˜es , Projetos}
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Definic¸a˜o por indicac¸a˜o de lista
A definic¸a˜o por lista e´ adequada apenas para conjuntos finitos
“pequenos”.
No caso de conjuntos finitos “grandes” ou de conjuntos
infinitos, podemos apresentar uma indicac¸a˜o da lista dos
elementos do conjunto.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
Um conjunto definido por indicac¸a˜o de lista e´ denotado pela
apresentac¸a˜o dos nomes de alguns dos seus elementos
separados por v´ırgulas e encerrados entre chaves e sa˜o usadas
reticeˆncias para substituir os nomes de elementos do conjunto
que na˜o sa˜olistados.
Devem ser listados nomes de elementos em quantidade
suficiente para que o leitor possa inferir quais nomes foram
substitu´ıdos pelas reticeˆncias.
D = {Andre , Bruno , Carlos , Daniel , . . . , Walter}
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
No caso de conjuntos infinitos, podem ser usados
nomes gene´ricos que indiquem a forma dos elementos do
conjunto.
N = {0, 1, 2, . . . , n , . . .}
P = {0, 2, 4, . . . , 2n , . . .}
Ha´ ainda outras formas mais complicadas, dependendo do que
se passa na cabec¸a do autor da definic¸a˜o do conjunto.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Definic¸a˜o por propriedade
Para definir um conjunto por propriedade, devemos apresentar
um conjunto universo e uma propriedade que se aplica a
elementos desse universo.
Os elementos do conjunto definido sa˜o os elementos do
conjunto universo que possuem a propriedade.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
Um conjunto definido por propriedade e´ denotado do seguinte
modo:
{x ∈ U : P(x)},
onde U e´ o nome do conjunto universo e P(x) e´ uma
especificac¸a˜o da propriedade, envolvendo a varia´vel x .
Apesar de ser estranho, a expressa˜o
{x ∈ U : P(x)}
costuma ser lida como
o conjunto dos x pertencentes a U tais que x e´ P.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
Outra maneira de denotar um conjunto definido por
propriedade e´:
{x : x ∈ U e P(x)},
ou ainda de formas mais complicadas, dependendo do que se
passa na cabec¸a do autor da definic¸a˜o do conjunto.
Por exemplo, o conjunto
P = {x ∈ N : x e´ par}
tambe´m pode ser denotado por
P = {x : existe y ∈ N tal que x = 2y}
ou, ainda, por
P = {2y : y ∈ N}
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Conjuntos nume´ricos
Do ponto de vista da matema´tica, os conjuntos mais
importantes sa˜o:
N, o conjunto dos nu´meros naturais.
Z, o conjunto dos nu´meros inteiros.
Q, o conjunto dos nu´meros racionais.
R, o conjunto dos nu´meros reais.
C, o conjunto dos nu´meros complexos.
Observe que todos estes conjuntos sa˜o infinitos.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Pre´ requisitos
Assumimos como conhecidas todas as propriedades dos
conjuntos nume´ricos, que sa˜o abordadas no Ensino Me´dio.
Isso na˜o significa que voceˆ tem que saber todas elas de cor
mas, sim, que voceˆ deve estar preparado para usa´-las e na˜o ter
medo de fazer isso, quando for preciso.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Igualdade
A relac¸a˜o de igualdade entre conjuntos e´ regulada pelo seguinte
princ´ıpio:
Princ´ıpio da Extensionalidade
Dois conjuntos sa˜o iguais se, e somente se, possuem
exatamente os mesmos elementos.
Por exemplo, considere os conjuntos:
A = {x ∈ Z : x e´ natural},
B = {x ∈ Z : x e´ soma de 4 quadrados}.
Temos que A e B sa˜o iguais.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Traduc¸a˜o
notac¸a˜o leitura
= e´ igual a
∀ para todo
∈ pertence
⇐⇒ se, e somente se
Em s´ımbolos:
A = B se, e somente se, ∀x(x ∈ A⇐⇒ x ∈ B).
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Ordem e repetic¸o˜es
Para saber se dois conjuntos A e B sa˜o iguais, precisamos
saber apenas quais sa˜o os elementos de A e de B.
Na˜o importa a ordem em que os elementos sa˜o apresentados.
{1, 2, 3} = {3, 2, 1}
Na˜o importa se ha´ repetic¸a˜o na apresentac¸a˜o dos elementos.
{1, 2, 2, 3} = {1, 1, 2, 3, 3, 3}
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Representac¸o˜es e universos
Na˜o importa a maneira como os elementos sa˜o apresentados.
{1, 2, 2, 2, 3} = {3, 3, |
√
4|, 1}
Na˜o importa o universo em que os objetos sa˜o tomados.
{x ∈ N : 1 < x < 3} = {x ∈ R : x2 − 4x + 4 = 0}
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Propriedades ba´sicas da igualdade
Estamos interessados nas propriedades da igualdade que valem
para todos os conjuntos, independente da natureza dos seus
elementos.
Para todos os conjuntos A, B e C ,
para todos os objetos x ∈ U , temos que:
(1) A = A.
(2) Se A = B, enta˜o B = A.
(3) Se A = B e B = C , enta˜o A = C .
(4) Se A = B e x ∈ A, enta˜o x ∈ B.
Se A = B e A ∈ C , enta˜o B ∈ C .
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Verificando igualdades
Como verificar se dois conjuntos dados A e B sa˜o iguais?
{x ∈ Z : x e´ soma de 3 quadrados} = N?
– Verificando se:
– todo elemento de A e´ tambe´m elemento de B,
– todo elemento de B e´ tambe´m elemento de A.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Inclusa˜o
Definic¸a˜o
Sejam A e B conjuntos. Dizemos que A esta´ contido em B se,
e somente se, todos os objetos que sa˜o elementos de A sa˜o
tambe´m elementos de B.
Por exemplo, o conjunto das pessoascom deficieˆncia esta´
contido no conjunto dos seres humanos.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Traduc¸a˜o
notac¸a˜o leitura
⊆ esta´ contido em
∀ para todo
∈ pertence
=⇒ se ... enta˜o
Em s´ımbolos:
A ⊆ B se, e somente se, ∀x(x ∈ A =⇒ x ∈ B).
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Notac¸a˜o
notac¸a˜o leitura
a ⊆ b a esta´ contido em b
a ⊆ b a e´ subconjunto de b
a 6⊆ b a na˜o esta´ contido em b
a 6⊆ b a na˜o e´ subconjunto de b
Observe a semelhanc¸a entre o s´ımbolo ≤, utilizado quando
comparamos nu´meros, e o s´ımbolo ⊆, utilizado quando
comparamos conjuntos.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Propriedades ba´sicas da inclusa˜o
Estamos interessados nas propriedades da inclusa˜o que valem
para todos os conjuntos, independente da natureza dos seus
elementos.
Para todos os conjuntos A, B e C , temos que:
(1) A ⊆ A.
(2) Se A ⊆ B e B ⊆ A, enta˜o A = B.
(3) Se A ⊆ B e B ⊆ C , enta˜o A ⊆ C .
(4) Se A = B e C ⊆ A, enta˜o C ⊆ B.
Se A = B e A ⊆ C , enta˜o B ⊆ C .
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Uma propriedade que falta
Observe que as propriedades listadas da relac¸a˜o ⊆, sobre
conjuntos, sa˜o inteiramente ana´logas a propriedades da
relac¸a˜o ≤, sobre nu´meros.
Mas, neste contexto, a semelhanc¸a pa´ra por a´ı.
Por exemplo, para nu´meros, vale
∀x , y(x ≤ y ou y ≤ x),
mas existem conjuntos A e B tais que
A 6⊆ B e B 6⊆ A.
Por exemplo, os conjuntos A = {1} e B = {2}.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Problemas
Um problema computacional e´ uma questa˜o geral a ser
respondida, possuindo determinado paraˆmetros.
Por exemplo,
• ‘multiplicar duas matrizes’,
• ‘determinar se um nu´mero natural e´ primo’.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Especificac¸o˜es
Um problema e´ especificado quando damos (1) uma indicac¸a˜o
dos paraˆmetros considerados no problema, (2) o universo no
qual os paraˆmetros tomam valores e (3) a questa˜o a ser
respondida.
Por exemplo:
• O problema da multiplicac¸a˜o de matrizes pode ser
especificado como:
Dados: Duas matrizes A e B de nu´meros reais, tais que o
nu´mero de colunas de A e´ igual ao nu´mero de linhas de B;
Questa˜o: Calcular o produto AB.
• O problema dos nu´meros primos pode ser especificado
como:
Dados: Um nu´mero natural n, na˜o nulo e maior do que 1;
Questa˜o: n e´ primo?
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Problemas de decisa˜o
Um problema e´ de decisa˜o quando a questa˜o pode ter como
resposta sim ou na˜o.
• Multiplicar matrizes na˜o e´ um problema de decisa˜o.
• O problema de determinar se um nu´mero natural e´ primo e´
de decisa˜o.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Algoritmos
Um algoritmo que resolve um problema de decisa˜o e´ um
procedimento que sempre pa´ra e responde corretamente com
sim ou na˜o a` questa˜o do problema, para quaisquer dados de
entrada.
• Voceˆ conhece um algoritmo para multiplicar duas
matrizes?
• Voceˆ conhece um algoritmo para determinar se um
nu´mero e´ primo?
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Problemas de inclusa˜o
Exerc´ıcio
Projetar algoritmos para decidir se A ⊆ B, nos casos em que A
e B sa˜o apresentados como segue.
A B A ⊆ B ?
listagem listagem Algoritmo ?
listagem propriedade Algoritmo ?
propriedade listagem Algoritmo ?
propriedade propriedade Algoritmo ?
Escrever os algoritmos o mais detalhadamente poss´ıvel, usando
as notac¸o˜es introduzidas nesta aula.
Conjuntos,
elementos,
pertineˆncia,
igualdade e
inclusa˜o
Renata de
Freitas e
Petrucio
Viana
Conjuntos,
elementos,
pertineˆncia
Conjuntos
finitos e
infinitos
Definic¸a˜o de
conjuntos
Conjuntos
nume´ricos
Igualdade e
inclusa˜o
Problemas e
algoritmos
Mais exerc´ıcios
1. Exerc´ıcios do Cap´ıtulo 1 do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Cap´ıtulo 2, pp. 55-56, itens 1, 3 e 9, do
Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo,
2006).
3. Exerc´ıcios da Lista 1.
	Conjuntos, elementos, pertinência
	Conjuntos finitos e infinitos
	Definição de conjuntos
	Conjuntos numéricos
	Igualdade e inclusão
	Problemas e algoritmos