revisaoav1 (1)

Prévia do material em texto

*
*
MATEMÁTICA DISCRETA – RAV1
PROFESSORA HELGA BODSTEIN, D.Sc. 
RAV1
*
*
Conteúdo
 Teoria dos Conjuntos 
 Conjuntos numéricos
 Conceitos de Permutações, Arranjos e Combinações
 Teorema Binomial, Triângulo de Pascal
 Relação Binária
 Representação gráfica de uma Relação Binária
 Propriedades em uma relação binária
 Ordem parcial em um conjunto 
 Representação gráfica de uma Relação de Ordem por um diagrama
*
*
RAV1
Introdução à Teoria dos Conjuntos
Conjuntos - Coleção não ordenada de objetos (denominados elementos ou membros do conjunto).
Conceitos
Pertinência – Notação:
Qualquer objeto que seja elemento de um conjunto é dito pertencer aquele conjunto, ou ainda, o elemento x possui o predicado P.
*
*
RAV1
Introdução à Teoria dos Conjuntos
Conceitos
Se o elemento x não pertence ao conjunto, denota-se por , que também pode ser equivalente a dizer que x não está no conjunto, ou ainda que x não possui o predicado P.
*
*
RAV1
Introdução à Teoria dos Conjuntos
Como definir um conjunto?
1. Listando (ou listando parcialmente) os elementos:
Conjunto das vogais: A = {a,e,i,o,u}
2. Indicando um padrão (normalmente para conjuntos infinitos): 
P = {2, 4, 6, 8, ...}
*
*
RAV1
Introdução à Teoria dos Conjuntos
Como definir um conjunto?
3. Descrevendo uma propriedade P que caracterize o conjunto de elementos:
A={x|x é um inteiro e 3 < x < 7}
S={x|x é solução para x2 – 4 = 0}
*
*
RAV1
Introdução à Teoria dos Conjuntos
Conjunto Universo – Notação: U 
	Chama-se Conjunto Universo ou simplesmente Universo de uma Teoria a todos os entes que são considerados como elementos nesta Teoria.
Exemplo: em geometria, o Universo é o conjunto de todos os pontos.
*
*
RAV1
Introdução à Teoria dos Conjuntos
Conjunto Potencia: P(A)
	Dado um conjunto arbitrário, é possível construir novos conjuntos cujos elementos são partes do conjunto inicial. 
Sendo A um conjunto qualquer, de nota-se por P(A) o conjunto constituído por todos os subconjuntos de A, isto é:			P(A) = { X : X ⊆ A}
*
*
RAV1
Introdução à Teoria dos Conjuntos
 Complemento:
Dado um conjunto A qualquer, 
o conjunto complementar de
 A em relação ao Universo é
formado por todos os 
elementos do Universo que não pertencem ao conjunto A.
O conjunto complementar de A será: A’ ou Ā.
*
*
RAV1
Introdução à Teoria dos Conjuntos
Conjuntos Finitos e Infinitos
	Podemos dizer que um conjunto é finito se for possível contar os seus elementos, ou seja, se for o conjunto vazio ou se for possível estabelecer uma correspondência entre os seus elementos.
*
*
RAV1
Introdução à Teoria dos Conjuntos
 Operações sobre Conjuntos
• União:
A∪B = {x | x ∈ A ou x ∈ B }
Diagrama de Venn :
*
*
RAV1
Introdução à Teoria dos Conjuntos
 Operações sobre Conjuntos
• Intersecção:
A∩B = {x | x ∈ A ou x ∈ B }
Diagrama de Venn :
*
*
RAV1
Introdução à Teoria dos Conjuntos
 Operações sobre Conjuntos
• Diferença:
A-B = {x | x ∈ A ou x  B }
Diagrama de Venn :
*
*
RAV1
Introdução à Teoria dos Conjuntos
Relações entre conjuntos
Continência - Notação: ⊆
Se todo o elemento de A também for elemento de B (independentemente do fato de todo o elemento de B poder ser ou não elemento de A) podemos dizer que o conjunto A está contido no conjunto B.
*
*
RAV1
Conjunto do números Naturais - N
Como decorrência da necessidade de contar objetos surgiram os números naturais que é simbolizado pela letra N e é formado pelos números 0, 1, 2, 3, …, ou seja:
N = {0; 1; 2; 3; …}
*
*
RAV1
Conjunto do números Naturais - N
Subconjuntos:
N* ={1, 2, 3, 4, 5, ..., n, ...} - conjuntos dos números naturais positivos
Np={0, 2, 4, 6, ..., 2n, ...} n  N - conjunto dos números naturais pares
Ni={1, 3, 5, 7, ..., 2n+1, ...} n  N- conjunto dos números naturais ímpares
*
*
RAV1
Conjunto dos Números Inteiros – Z
Chama-se o conjunto dos números inteiros, representado pela letra Z, o seguinte conjunto:
Z = {…, -3; -2; -1; 0; 1; 2; 3; …}
Introdução dos números negativos!
*
*
RAV1
Conjunto dos Números Inteiros – Z
Subconjuntos
Z+ = {0; 1; 2; 3; …} - conjunto dos inteiros não negativos
Z- = {…; -3; -2; -1; 0}- conjunto dos inteiros não positivos:
Z* = {…, -3; -2; -1; 1; 2; 3; …} - Conjunto dos inteiros não nulos
 Z+* = {1; 2; 3; …} - Conjunto dos inteiros positivos
 Z-* = {…; -3; -2; -1} - Conjunto dos inteiros negativos
*
*
RAV1
Conjunto dos Números Racionais – Q
O conjunto dos números racionais, simbolizado pela letra Q, é o conjunto dos números que podem ser escritos na forma de uma fração p/q, com p e q inteiros quaisquer e q diferente de zero:
*
*
RAV1
Conjunto dos Números Racionais – Q
Subconjuntos
Q* (conjunto dos números racionais não nulos), 
Q+ (conjunto dos números racionais não negativos) e 
Q- (conjunto dos números racionais não positivos).
*
*
RAV1
Conjunto dos Números Irracionais – I
Os números irracionais são decimais infinitas não periódicas, ou seja, os números que não podem ser escritos na forma de fração (divisão de dois inteiros). 
Exemplos:
O número 0,212112111... não é dízima periódica, pois os algarismos após a vírgula não se repetem periodicamente.
*
*
RAV1
Conjunto dos Números Reais – R
O conjunto dos números reais, simbolizado pela letra R, é o formado por todos os números racionais e por todos os números irracionais:
R = {x | x é racional ou x é irracional}
*
*
RAV1
Conjunto dos Números Reais – R
Desse modo todos os conjuntos numéricos (N, Z e Q), bem como o conjunto dos números irracionais são subconjuntos de R.
*
*
RAV1
Cardinalidade de um Conjunto
Define-se a cardinalidade de um conjunto A como ao número de elementos que pertencem ao conjunto A . 
	Denotamos a cardinalidade de um conjunto A por card(A) ou o(A) , e se lê “cardinalidade de A” ou “número de elementos de A”. 
*
*
RAV1
Princípio Fundamental da Contagem - PFC 
Suponhamos que uma ação seja constituída de duas etapas sucessivas:
→ A primeira etapa pode ser realizada de p maneiras distintas. Para cada uma dessas possibilidades, a 2ª etapa pode ser realizada de q maneiras distintas. 
Então, o número de possibilidades de se efetuar a ação completa é dado por p x q.
*
*
RAV1
Princípio Multiplicação 
Uma lanchonete oferece a seus clientes
 apenas dois tipos de sanduíches: hot dog e hambúrger. 
Como sobremesa, há três opções: 
sorvete, torta ou salada de frutas. 
Pergunta-se: quantas são as possibilidades de uma pessoa fazer uma refeição incluindo um sanduíche e uma sobremesa? 
*
*
RAV1
*
*
RAV1
Princípio da casa dos Pombos
Teorema : Se n + 1 pombos voam em direção a n casas e todos os pombos entram em uma casa, haverá pelo menos uma casa com pelo menos dois pombos.		
*
*
RAV1
Princípio da casa dos pombos
Exemplo: Entre um grupo
 de 367 pessoas, pelo menos
 duas possuem o mesmo
 dia de nascimento, 
pois existem apenas 
366 possibilidades.
*
*
RAV1
ARRANJO SIMPLES
 Dado um conjunto com n elementos distintos, chama-se arranjo dos n elementos, tomados p a p, a qualquer seqüência ordenada de p elementos distintos, escolhidos entre os n existentes. 
Temos um Arranjo quando os 
agrupamentos conseguidos 
ficam diferentes ao se inverter
 a posição dos seus elementos.
*
*
RAV1
ARRANJO SIMPLES
Exemplo: Quantos números de três dígitos distintos escolhidos entre 1, 2, 3, 4, 5, 6 e 7, podemos formar?
	
 		
*
*
RAV1
PERMUTAÇÃO SIMPLES
Permutações simples é uma técnica combinatória utilizada quando desejamos contar as possibilidades de formação de uma fila ou seqüência em que não há repetição de elementos e todos esses elementos são utilizados no problema.
*
*
RAV1
PERMUTAÇÃO COM ELEMENTOS REPETIDOS
Se entre os n elementos de um conjunto, existem a elementos repetidos, b elementos repetidos, c elementos repetidos e assim sucessivamente, o número total de permutações que podemos formar é dado por:  
				
	
*
*
RAV1
PERMUTAÇÃO SIMPLES
Exemplo: Quantos anagramas podem ser formados com a palavra LIVRO começando com vogal?
				___ ___ ___ ___ ___
	 O ou A4 letras 
			
	
*
*
RAV1
COMBINAÇÃO SIMPLES
Combinação simples é uma ferramenta combinatória utilizada quando desejamos contar as possibilidades de formação de um subgrupo de elementos a partir de um grupo dado. 
	São as possibilidades de formação de um subconjunto formado a partir do conjunto dado.
*
*
RAV1
COMBINAÇÃO SIMPLES
Exemplo: Dentre 9 Cd’s distintos que estão em oferta em uma loja, João deseja escolher 5 para comprar. De quantos modos diferentes João pode escolher os 5 Cd’s?
*
*
RAV1
Coeficientes Binomiais
	Dados dois números naturais, n e p, com n ≥ p, definimos o coeficiente binomial n sobre p, e indicamos por:
			 ou 
onde n é dito numerador e p chamado denominador.
*
*
RAV1
Triângulo de Pascal
O triângulo de Pascal é uma sequência de números binomiais, isto é, inteiros da forma C(n, p), dispostos em uma tabela em forma de triângulo, como na figura abaixo:
*
*
RAV1
Triângulo de Pascal
	Representação no Triângulo
C (0,0)
C (1,0) C (1,1)
C (2,0) C (2,1) C (2,2) 
C (3,0) C (3,1) C (3,2) C (3,3)
C (4,0) C (4,1) C (4,2) C (4,3) C (4,4)
C (5,0) C (5,1) C (5,2) C (5,3) C (5,4) C (5,5)
C (6,0) C (6,1) C (6,2) C (6,3) C (6,4) C (6,5) C (6,6)
*
*
RAV1
Triângulo de Pascal
	Propriedade: Em uma mesma linha, os coeficientes binomiais equidistantes dos extremos são iguais.
Aplicando a fórmula de combinação para a linha 5, por exemplo:
		 = = = = = =
		 1 5 10 10 5 1
*
*
RAV1
Teorema Binomial
O teorema binomial fornece uma fórmula para a potência de um binômio, isto é, uma fórmula que permite calcular diretamente uma expressão do tipo (a + b)n, onde n é um inteiro positivo.
Para n = 0  (a + b)0 = 1
Para n = 1  (a + b)1 = a + b
Para n = 2  (a + b)2 = a2 + 2ab + b2
Para n = 3  (a + b)3 = a3 + 3 a3b + 3ab3 + b3
Para n = 4  (a + b)4 = ( a + b)3 (a + b) = a4 + 4a3 b + 6a2b2 + 4ab3 + b4
*
*
RAV1
Teorema Binomial
Fórmula do teorema binomial:
*
*
RAV1
1º termo: 		= 1.a5.1 = a5
2º termo:		= 5.a4.b 
3º termo:		= 10.a3.b2 
4º termo:		= 10.a2.b3 
5º termo:		= 5.a1.b4 
6º termo:		= 5.a0.b5 = 5b5
(a + b)5 = a5 + 5.a4.b + 10.a3.b2 + 10.a2.b3 + 5.a1.b4 + 5b5
(a + b)5 = ?
*
*
RAV1
Produto Cartesiano
Dados dois conjuntos A e B, chama-se produto cartesiano de A em B ao conjunto formado por todos os pares ordenados cuja primeira coordenada seja pertencente a A, e a segunda coordenada seja pertencente a B. O símbolo do produto cartesioano é x. 
O produto cartesiano de dois conjuntos A e B é o conjunto de todos os pares ordenados:
A x B = {(x, y) | x  A e y  B}
*
*
RAV1
Produto Cartesiano
Por exemplo, dados os conjuntos A = {1, 2, 5} e B = {2, 4, 9}, o produto cartesiano de A em B é o conjunto (A x B) descrito a seguir:
 
A x B = {(1,2), (1,4), (1,9), (2,2), (2,4), (2,9), (5,1), (5,4), (5,9)}
*
*
RAV1
Relações Binárias
Dados dois conjuntos quaisquer A e B, uma relação binária entre A e B é um subconjunto obtido do produto cartesiano AxB destes conjuntos.
Uma relação binária de A em B é um conjunto R de pares ordenados, onde o 1º elemento de cada par vem de A e o 2º vem de B, ou seja R  A x B.
*
*
RAV1
Relações Binárias
Exemplo: Sejam os conjuntos A = {1, 2, 5} e B = {2, 4, 9}.
 O conjunto R= {(1,2), (2,4), (2,9)} é um subconjunto (A x B), logo é define uma Relação Binária de A em B.
*
*
RAV1
Relações Binárias
Dado um conjunto A, uma relação binária sobre A, é um subconjunto do produto cartesiano (AxA), ou seja, um subconjunto de pares ordenados de elementos de A.
O produto cartesiano do conjunto A com ele mesmo, denotado por (A x A) ou A2, é o conjunto de todos os pares ordenados de elementos de A. 
*
*
RAV1
Relações Binárias
Uma relação binária R sobre um conjunto A nada mas é do que um subconjunto de (AxA) que pode ser descrita na forma abreviada por:
x R y ↔ (x, y) R
*
*
RAV1
Domínio e Contradomínio:
Em uma Relação Binária de A para B, o conjunto A é chamado de domínio da relação e o conjunto B é chamado de contradomínio da relação.
Exemplo: Na relação, R= {(2, 3), (3, 4), (4, 5), (5, 6)}
O Domínio é o conjunto {2, 3, 4, 5} 
O Contra-Domínio é o conjunto {3, 4, 5, 6}.
*
*
RAV1
Domínio e Contradomínio:
Representação gráfica:
A = {a,b,c,d}
B = {1,2,3}
R = {(a,3), (b,3), (c,2), (c,3), (d,2), (d,3)}
*
*
RAV1
Classificação das Relações Binárias
Seja R uma relação binária do conjunto A para o conjunto B. R pode ser classificada como uma das relações:
um para um
um para muitos
muitos para um
muitos para muitos
*
*
RAV1
Relações no Plano Cartesiano (R x R) ou R2
- Plano Cartesiano
O plano cartesiano ortogonal é constituído por dois eixos x e y perpendiculares entre si e que se cruzam num ponto O chamado de origem dos eixos. 
O eixo horizontal é chamado de eixo das abscissas (eixo OX) e o eixo vertical é chamado de eixo das ordenadas (eixo OY).
*
*
RAV1
Relações no Plano Cartesiano (R x R) ou R2
Os eixos x e y dividem o plano cartesiano em quatro regiões distintas chamadas de quadrantes:
*
*
RAV1
*
*
RAV1
Exemplo: Seja X = {0, 1, 2, 3, 4}. Então, x R y  y = x2.
R = {(0,0), (1,1), (2,4), (3,9), (4,16)}
*
*
RAV1
Relações Binárias
Endorrelação ou auto-relação
Considere um conjunto A não vazio. Uma relação binária R sobre A ou endorrelação ou auto-relação é qualquer subconjunto do produto cartesiano A×A, isto é, 
R ⊆ A ×A (leia-se: R é subconjunto de A x A)
Podemos chamar relação de A em A de 
Relação Interna sobre o conjunto A.
*
*
RAV1
Relações Internas
Exemplo: Considere o conjunto A = {1, 2, 3} e a relação binária sobre A: R = {(1,1), (2,1), (3,3)} ⊆A×A.
A relação R pode, por exemplo, ser representada pelo diagrama a seguir: 
*
*
RAV1
Propriedades das Relações Binárias
Relação Reflexiva
Seja R uma relação sobre o conjunto A. A relação R é dita REFLEXIVA se todo elemento de um conjunto A está relacionado consigo mesmo, ou seja:
 (x,x)  R,  x  A
*
*
RAV1
Propriedades das Relações Binárias
Relação Simética
A relação R é dita SIMÉTRICA se quando x está relacionado com y, implicar em y estar relacionado com x, ou seja: 
(x, y)  R (y, x)  R, para x, y  A
*
*
RAV1
Propriedades das Relações Binárias
Relação Transitiva
A relação R é dita TRANSITIVA se quando x está relacionado com y e y está relacionado com z, implicar em x estar relacionado com z, ou seja: 
(x, y) R e (y, z) R(x, z)  R, para x, y, z  A.
*
*
RAV1
Propriedades das Relações Binárias
Relação Antiassimétrica
A relação R é dita ANTISSIMÉTRICA se quando x está relacionado com y e y está relacionado com x somente quando x = y.
(x, y)R e (y, x) R x = y, para x e y  A
*
*
RAV1
Propriedades das Relações Binárias
Exemplo: Seja S= {a, b, c}, classifique a relação R = {(a,a), (b,b), (c,c), (a,b), (a,c)}
R é reflexiva, todo elemento tem um laço
R é antissimétrica, existem flechas sem duas pontas
*
*
RAV1
Propriedades das Relações Binárias
- RELAÇÃO DE EQUIVALÊNCIA
Uma relação R sobre um conjunto A não vazio é chamada relação de equivalência sobre A se, e somente se, R é reflexiva, simétrica e transitiva.
Exemplo: Seja o conjunto A={a,b,c}, então a relação R sobre A descrita por:
 R = {(a,a), (b,b),(c,c),(a,c),(c,a)} é de equivalência.
*
*
RAV1
*
*
RAV1
Propriedades das Relações Binárias
RELAÇÃO DE ORDEM PARCIAL
Exemplo: A relação no conjunto dos números reais:
 x R y se e só se x ≤ y é uma relação de ordem parcial.
→ É reflexiva (aRa), antissimétrica (se aRb e bRa, então a=b) e transitiva (se aRb e bRc, então aRc).
*
*
RAV1
Propriedades das Relações Binárias
Relação de ordem total
É uma relação de ordem onde todo elemento do conjunto está relacionado a todos os outros elementos.
Exemplo: S = {a, b, c}
 
R = { (a,a), (b,b), (c,c), (a,b), (b,c),(a,c)}
*
*
RAV1
Propriedades das Relações Binárias
Diagramas de Hasse de Conjuntos munidos de uma Relação de Ordem
– Conjuntos munidos de uma relação de ordem são uma relação e portanto pode-se desenhar seugrafo.
– No entanto, muitas arestas não precisam estar presentes em virtude das propriedades da relação de ordem (reflexiva e transitiva).
*
*
RAV1
Propriedades das Relações Binárias
Diagramas de Hasse de Conjuntos munidos de uma Relação de Ordem
– Para simplificar a representação, retira-se de seus grafos as arestas que sempre devem estar presentes.
– As estruturas obtidas desta forma são chamadas de DIAGRAMAS DE HASSE da relação de ordem.
*
*
RAV1
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*
*
RAV1
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*
*
RAV1
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*
*
RAV1
Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", monte o diagrama de Hasse:
*