Matemática Discreta

Prévia do material em texto

Alguns Conceitos Primitivos 
No estudo de Conjuntos, trabalhamos com alguns conceitos como: 
 
 
 
 
Algumas Notações Para Conjuntos 
Muitas vezes, um conjunto é representado com os seus elementos dentro de duas chaves e através de duas formas 
básicas e de uma terceira forma geométrica: 
 
 
 
Subconjuntos 
Dados os conjuntos A e B, diz-se que A está contido em B, denotado por A B, se todos os elementos de A também 
estão em B. Algumas vezes diremos que um conjunto A está propriamente contido em B, quando o conjunto B, além 
de conter os elementos de A, contém também outros elementos. O conjunto A é denominado subconjunto de B e o 
conjunto B é o superconjunto que contém A. 
 
 
 
 
 
 
 
 
 
 
 
Relação Entre Lógica E Teoria Dos Conjuntos 
Conforme já comentamos, a Lógica Proposicional é fundamental no estudo da teoria dos Conjuntos. 
Existe uma relação direta entre os operadores lógicos e algumas operações sobre conjuntos. A tabela seguinte 
mostra tal analogia: 
 
Conjuntos Contáveis e Não Contáveis 
 
 
 
 
 
 
 
 
 
 
O conjunto dos números naturais possui alguns subconjuntos importantes: 
 
 
 
 
 
Conjunto dos Números Racionais (Q) 
 
 
 
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). 
Vejamos alguns exemplos: 
 
 
 
Conjunto dos Números Reais (R) 
 
 
 
 
 
 
 
Cardinalidade De Um Conjunto 
Define-se a cardinalidade de um conjunto A conforme o 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”. 
 
 
 
 
 
 
 Arquivos salvos. 
 
 
 
 
 
Análise Combinatória 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Par Ordenado 
É uma coleção de dois objetos que tem uma ordem definida. Existe o primeiro elemento (ou primeira coordenada) e 
o segundo elemento (ou segunda coordenada). Um par ordenado — simbolizado por (a, b) — precisa ser 
apresentado em uma determinada ordem, e dois pares ordenados só são iguais quando os primeiros elementos são 
iguais e os segundos elementos são iguais. Ou seja, 
(a, b) ≠ (b, a) 
Por exemplo, (2, 3) é um par ordenado de números reais cuja primeira coordenada é igual a dois e a segunda 
coordenada é igual a três. 
 
 
 
Produto Cartesiano 
 
 
Atenção 
O produto cartesiano não é comutativo, isto é, A x B ≠B x A 
 
Exercício 
Encontre o conjunto B x A e compare com o conjunto A x B: 
 
 
 
 
 
 
Relação Binária sobre um conjunto A 
Dado um conjunto A, uma relação binária sobre A, é um subconjunto do produto cartesiano (A x A), ou seja, um 
subconjunto de pares ordenados de elementos de A. 
Generalização do conceito de Relação Binária 
Dados n conjuntos A1, A2, ..., An, n> 2, uma relação n-ária em A1x A2x A3x ... An é um subconjunto do produto 
cartesiano (A1x A2x ... x An). 
Exemplo de Relação Ternária 
R = {(x, y, z)| x, y e z estão relacionados} 
Em uma aplicação prática, podemos ter o conjunto das ternas ordenado que descreva a seguinte situação: 
(x, y, z) = (número de um voo, ponto de partida, destino) 
 
Classificação de uma Relação Binária 
Seja R uma relação binária do conjunto A para o conjunto B. 
 
 
Classificação de uma Relação Binária 
Apresentação gráfica da classificação de uma relação binária: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Relações Binárias Reflexivas, Simétricas, Antissimétricas e Transitivas 
 
 
 
 
 
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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Notação 
 
 
 
 
 
Relação de ordem total 
 
 
 
 
 
 
 
 
 
 
 
 
 
Diagrama de Hasse 
 
 
 
Elemento maximal e elemento minimal para um conjunto PO 
 
Teorema 
Num conjunto A parcialmente ordenado pela relação R, se houver elemento máximo de A então é elemento 
maximal e não há outros; se houver elemento mínimo de A então é elemento minimal e não há outros. 
 
 
Atenção 
Não há elemento ‘maior’ que um elemento maximal nem há elemento ‘menor’ que um elemento minimal. 
 
 
 
 
 
 
Objetivos desta aula 
Nesta aula, você irá: 
 
1. Entender que funções são casos particulares de relações binárias de um conjunto S em um conjunto T. 
 
2. Saber que o conceito de função é bastante comum em contextos não técnicos. 
 
3. Saber que uma definição completa de uma função necessita que se dê o domínio, o contradomínio e a 
associação, no qual a associação pode ser dada por uma descrição verbal, um gráfico, uma equação ou um 
conjunto de pares ordenados. 
 
4. Reconhecer as principais propriedades de funções. 
 
5. Identificar alguns tipos de funções elementares do plano cartesiano. 
 
6. Construir, analisar e extrair informações dos gráficos representativos das funções elementares. 
 
7. Saber que funções compostas são funções em que o conjunto imagem de uma delas serve como domínio 
para a outra. 
 
8. Gerar funções compostas. 
 
 
 
 
Tipos especiais de funções em (R x R) ou R2 
 
 
 
 
 
Estudar o sinal de uma função qualquer y = f(x) é determinar os valores de x para os quais y é positivo, os valores de 
x para os quais y é zero e os valores de x para os quais y é negativo. 
Consideremos a função do primeiro grau y = ax + b e vamos estudar o seu sinal. Sabemos que essa função se anula 
para x = -b/a (que é a raiz). Há dois casos possíveis. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Funções injetoras 
 
 
Funções injetoras 
 
 
 
 
 
 
 
 
Função composta das funções f (x) e g(x). 
 
 
 
Atenção 
Existem várias maneiras de se criar funções compostas. Podemos fazer f(g(x)), f(f(x)) etc. 
Note que o conjunto imagem de uma função serve sempre de domínio para a outra. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FUNÇÃO POTÊNCIA 
 
 
 
 
 
 
 
 
 
Gráfico da função logarítmica 
 
 
 
 
 
 
 
 
 
 
Os atributos sublinhados indicam a chave primária de cada relação, enquanto que os assinalados em vermelho 
constituem chaves estrangeiras. 
 
MODELO RELACIONAL 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 
Sejam as relações 
 
 
 
 
 
 
 
 
 
 
Álgebra relacional: operações relacionais derivadas da teoria dos conjuntos 
 
 
 
 
 
 
 
 
União 
- Notação: R ∪ S. 
- Entrada: Tabela (R) e Tabela (S). 
- Propósito: gerar linhas de acordo com um critério. 
- Saída: Contém todas as linhas de R e de S. 
- Duplicidade é eliminada. 
 
 
 
Diferença 
 
Interseção 
 
 
Divisão 
 
Relação em um banco de dados: produto cartesiano 
Uma relação em um banco de dados é o subconjunto do produtocartesiano (D1 x D2 x ...x Dn ), onde Di é o domínio 
do atributo. 
Suponha que uma determinada empresa precisa obter o nome completo, a data de admissão e o salário de cada 
funcionário cadastrado. Para essa consulta temos um fato novo, que é a referência a colunas de mais de uma tabela, 
uma vez que o nome e a data de admissão fazem parte da relação funcionário, enquanto que o salário existe apenas 
em cargos. Isso é problemático, pois as duas operações que conhecemos até o momento são unárias, e temos 
necessidade de combinar os dados de mais de uma relação. Para situações como essa existe uma operação chamada 
Produto Cartesiano. 
 
Outras operações 
 
 
Renomeação 
Na álgebra relacional, o operador de renomeação é utilizado para alterar o nome das colunas de uma tabela. 
Utilizado para relacionamentos onde possam surgir nomes iguais para as colunas, como num relacionamento da 
tabela com ela mesma. 
 
Atribuição 
Armazena o resultado de uma expressão algébrica em uma variável de relação permite o processamento de uma 
consulta complexa em etapas 
 Notação: nomeVariável ← expressãoÁlgebra 
 
 
 
 
 
Introdução 
Uma relação binária em um conjunto S é, formalmente, um subconjunto de S x S; a relação satisfeita pelos pares 
ordenados tem, muitas vezes, uma descrição verbal. 
As operações com relações binárias em um conjunto incluem união, interseção e complemento. 
Conjuntos parcialmente ordenados finitos podem ser representados graficamente. 
Relações matemáticas em um banco de dados são tabelas utilizadas para modelar informações e relações em um 
empreendimento. 
Ordens parciais e relações de equivalência 
O quadro abaixo apresenta as relações de ordens parciais e relações de equivalência com suas respectivas 
características importantes. 
 
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. 
 
Funções injetoras 
 
 
 
 
 
 
 
 
 
Funções bijetoras 
O quadro abaixo apresenta um resumo informal da terminologia de funções: