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.