Upload
universidade-de-pernambuco
View
575
Download
0
Embed Size (px)
Citation preview
Matemática DiscretaMirele Moutinho
Sistemas de Informação
Bibliografia
Fundamentos Matemáticos p/ a Ciência da Computação – Gersting, Judith. Ed. LTC.
Matemática Discreta – Scheinerman, Edward. Ed. Thomson.
Álgebra Moderna – Iezzi, Gelson. Ed. Atlas.
Conteúdo Programático
ConjuntosRelações FunçõesNúmeros inteiros: divisibilidade,
congruência, PBO, PIF.Estrut. algébricas: grupos, anéis,
corpos.Grafos e árvores
Conjuntos Uma coleção de objetos.
Notação: A, B, etc.(letras maiúsculas).
a A, ou seja a pertence ADescrição dos elementos de um conj.:1. Listar (parcial)seus elementos.2. Usar recorrência pra indicar como
gerar seus elementos.3. Descrever uma propriedade P que
caracteriza seus elementos.
Exemplos
A = {1,3 5,7,9,11, ...}
B = {n | n é um inteiro positivo ímpar}.
C é tal que
1 C e se n C então n + 2 C
Exemplos conhecidos
IN = conj. dos inteiros não-negativos
Z = conj. de todos os inteiros
Q = conj. dos números racionais
IR = conj. dos números reais
A = {x | y, y {0,1,2} e x = y3}
Dessa forma, A = {0,1,8}.B = {x | x IN e y, y IN e x ≤ y}
B = IN
Se definirmos
B = {x | x IN e y, y IN x ≤ y}
então B = {0}
B= {x | x IN e y, y IN x < y},
então B = ou B ={ }
Exerc.: Descreva os conj. abaixo, listando seus elementos
A = {x | xIN e y, y {2,3,4,5} x y}
B={x | y, z, y{1,2}, z{2,3} e x = y+z}
C = {x | xIN e y, y par x y}
Exerc.: Descreva os conj. abaixo, definindo uma propriedade
A = {1,2,3,4,5}.B = {1,3,5,7,9,11,...}C =
{0,1,10,11,100,101,110,111,1000,...}
Relações entre Conjuntos
A é um subconjunto de B se
x, x A x B Notação: A B Se B tem algum elemento que não está
em A, ou seja A B, então A é
subconjunto próprio de B. Notação: A B
Cardinalidade: Quantidade de elementos de um conjunto.
Conjuntos de Conjuntos
Dado um conjunto A, podemos formar o conjunto de todos os subconjuntos de A, dito conjunto das partes de A.
Notação: (A).
Exemplo: A = { 0, 1}
(A) = {, {0}, {1}, {0,1}}.
Obs.: (A) tem cardinalidade 2n quando A tem n elementos.
Operações entre Conjuntos Dados A e B:
A B = {x | x A ou x B}, dito união.
A B = {x | x A e x B}, interseção.São ditos disjuntos os conj. Que têm
A B =
Dado A S, denotamos por A’, o complemento de A em S:A’ = {x | x S e x A}.
Dados A, B S , definimos a diferença entre conjuntos como:
A – B = {x | x A e x B}.
O produto cartesiano de A e B é:
AxB = {(x,y) | x A e y B}.
Atividades:
Pesquise sobre as propriedades básicas dos conjuntos.
Resolva os exercícios 9, 10, 11 da pág. 142 do livro texto.
Mais Operações
Uma operação num conjunto A é
binária se, para todo par de elementos de A, (x,y), tivermos x y
A e único.
Ex.: A subtração não é uma operação binária em IN, pois se x = 1 e y = 2, temos que x – y IN.
Mais Operações
Para que # seja uma operação unária em um conjunto A, x # tem que existir e ser único em A.
Ex.: Se x # = - x , para x 1 e x # = x
para x ≤ 1 então não temos uma operação unária por 2 motivos. Descubra-as.