4Semestre matematica discreta

Prévia do material em texto

4ºSemestre
Matematica discreta
Professor Elcio Assis Cardoso Junior
· Teoria dos conjuntos
O conceito de conjunto é amplamente utilizado em computação. 
“um conjunto é uma coleção de zero ou mais objetos distintos, chamados elementos do conjunto, os quais não possuem qualquer ordem associada”. Estes objetos no conjunto são chamados de elementos (ou membros) do conjunto.
Os conjuntos podem ser de duas formas: 
• Denotação por extensão: neste caso, os elementos pertencentes ao conjunto são listados (em qualquer ordem), separados por vírgula, entre chaves
» Dias da semana = {domingo, segunda, terça, quarta, quinta, sexta, sábado};
• Denotação por compreensão: neste caso, o conjunto é definido por suas propriedades. 
» Dias da semana = {d | d são os sete dias da semana};
∉ = não pertence
∈=pertence
Conjuntos 
• U – conjunto universo. O conjunto universo possui como elementos todos os conjuntos que existem, considerando a teoria de conjuntos; 
• ∅ – conjunto vazio. Este conjunto não possui elementos. por exemplo, D o conjunto de dinossauros vivos no planeta Terra nos dias atuais. Este é um conjunto vazio, pois não existem dinossauros. Agora, pense no conjunto C de todos os cachorros com mais de 70 anos. Também não existem elementos
• Conjunto unitário – é o conjunto formado por apenas um elemento, qualquer que seja. Geralmente é representado por 1. Você, por exemplo, faz parte de um conjunto unitário, pois não existe mais ninguém no mundo exatamente igual a você.
· Subconjuntos
Os subconjuntos apresentam todos os seus elementos incluídos em outro conjunto. Por esse motivo, a relação entre eles e o outro conjunto é de inclusão.
· Conjuntos finitos e infinitos
• Conjunto finito: possui um número finito de elementos, ou seja, contável, mesmo que isso dê muito trabalho.
• Conjunto infinito: como o próprio nome já indica, possui um número infinito de elementos que não podem ser contados.
· Diagramas de venn 
o diagrama de Venn consiste em uma linha fechada (que não se entrelaça) na qual “colocamos” os elementos do conjunto em questão, logo, podemos representar um ou vários conjuntos de maneira simultânea.
· Operações entre conjuntos
As operações algébricas entre conjuntos podem ser classificadas como reversíveis (podem ser alteradas) e não-reversíveis (não podem ser alteradas).
Operações não-reversíveis 
União = A união entre dois conjuntos A e B
Algumas propriedades da operação de união de conjuntos: 
a) Idempotência: propriedade que algumas operações possuem de poderem ser aplicadas inúmeras vezes sem alteração do valor do resultado após a aplicação inicial. Neste caso, temos: para um conjunto qualquer A, A ∪ A = A; 
b) Associativa: considere três conjuntos quaisquer A, B e C. Neste caso, temos: A ∪ (B ∪ C) = (A ∪ B) ∪ C; 
c) Elemento neutro: o conjunto vazio (∅) é o elemento neutro da união. Logo, temos, para um conjunto A: A ∪ ∅ = ∅ ∪ A; 
d) Comutativa: neste caso, A ∪ B = B ∪ A.
Intersecção= A intersecção entre dois conjuntos A e B
As propriedades referentes à união entre conjuntos também podem ser aplicadas à intersecção: 
a) Idempotência: A ∩ A = A; 
b) Associativa: A ∩ (B ∩ C) = (A ∩ B) ∩ C; 
c) Elemento neutro: neste caso, o elemento neutro é o conjunto universo. Logo, temos: A ∩ U = U ∩ A = A; 
d) Comutativa: A ∩ B = B ∩ A.
Operações reversíveis 
Complemento 
A operação de complemento é classificada como reversível e também é unária (operação com apenas um operando). Consideramos o complementar absoluto ou o complementar de um conjunto, todos os elementos que não pertencem a ele e pertencem ao conjunto universo U.
Conjunto das partes 
A operação referente ao conjunto das partes consiste na determinação de todos os subconjuntos que podem ser formados a partir de um conjunto A qualquer. É denotada por P (A)
O produto cartesiano entre dois conjuntos A e B (denotado por A × B) quaisquer é uma operação binária que consiste numa sequência de pares ordenados.
A união disjunta de dois (ou mais) conjuntos é um conjunto que "praticamente" contém cópias disjuntas dos conjuntos originais.
· Princípios de logica matemática
Uma proposição nada mais é que uma afirmação que declara algo, exprimindo um pensamento com sentido completo. Uma proposição pode ser verdadeira ou falsa, mas nunca ambas ao mesmo tempo.
Simples ou primitivas: exprimem apenas um pensamento com sentido completo.
Compostas: combinação de duas ou mais proposições.
Para unir ou ligar duas ou mais proposições, podemos usar os chamados conectivos lógicos, que podem ser: e, ou, não, se...então, se...somente...se, entre outros. Cada um desses conectivos é responsável pelas seguintes operações lógicas básicas, respectivamente: conjunção, disjunção, negação, condição e bicondição. Vamos estudar cada uma dessas operações separadamente.
· Relações
uma relação consiste em uma comparação entre pares de objetos. Definiremos agora como se dá uma relação entre conjuntos. Considerando dois conjuntos A e B quaisquer, uma relação R de A em B consiste em um subconjunto obtido mediante a aplicação da operação reversível produto cartesiano A×B.
* Em uma relação, também podemos estabelecer quais elementos se relacionam entre si.
* Uma relação pode relacionar entidades de um mesmo conjunto. Nesse caso, teremos uma endorrelação. Matematicamente, dizemos que: R: A → A (“R é uma relação em A”).
· Representação de relações
Pares ordenados-Exemplo: R1={(4, 4), (5, 4), (5, 5)}. É a forma mais comum de representação de relações. 
Relações no plano cartesiano- É a representação da relação no plano cartesiano.
Matrizes- Relações e endorrelações entre conjuntos finitos podem também ser representadas através de matrizes.
Exemplo: Considere, primeiramente, dois conjuntos A = {0, 1, 2, 3, 4} e B = {a, b, c, d, e}. A relação : A B → é igual a R1={(0, a), (1, b), (2, c), (4, e)}. Nesse caso, para representar essa relação na forma matricial, as linhas da matriz devem representar o conjunto A e as colunas, o conjunto B. Se o elemento a ∈ B estiver relacionado com o elemento b ∈ B, deve-se colocar o valor 1 (verdadeiro) naquela determinada posição da matriz. Se não, deve ser colocado o valor 0 (falso).
Diagrama de flechas- Essa representação consiste em desenhar diagramas de Venn representando cada conjunto envolvido na relação e representá-la por meio de flechas. No caso de endorrelações, basta desenhar o mesmo conjunto duas vezes e ligar os elementos relacionados com flechas.
Relações duais Considere dois conjuntos A e B quaisquer, relacionados por RAB: A → B. A relação dual (também chamada de oposta ou inversa) de RAB consiste na relação de B em A, ou seja, basta inverter os elementos dos pares ordenados da relação RAB. 
Composição de relações
Considere três conjuntos quaisquer A, B e C. Seja R uma relação de A em B e S uma relação de B em C. Ao realizar a composição das duas relações, denotada por S o R , temos uma relação de A em C ( S o R : A→B ). 
Tipos de endorrelações
Existem alguns tipos especiais de endorrelações, ou seja, relações definidas em um conjunto qualquer A.
Relações reflexivas: Considere um conjunto qualquer A. Uma relação é dita reflexiva se todo elemento a se relaciona com ele mesmo (aRa), para todo a∈A. Ou seja, se existir (a, a) na relação, para todo elemento a∈A, essa relação será reflexiva.
Relações irreflexivas Uma relação irreflexiva R em um conjunto A ocorre se, para qualquer elemento a ∈ A, o par ordenado (a, a) ∉ R, ou seja, nenhum elemento se relacione consigo mesmo.
Relações simétricas e antissimétricas Temos uma relação simétrica quando, para quaisquer elementos a e b de um conjunto A qualquer, temos uma endorrelação R em que (a, b) e (b, a) ∈ R. Caso contrário, a relação é dita assimétrica. A relação de igualdade em um conjunto A, por exemplo, é considerada simétrica, pois, para quaisquer elementos a e b pertencentes a A, se a = b, então b = a.
Relações transitivas Uma endorrelação R em um conjunto A qualquer é dita transitiva para todo elemento a∈A, b∈A e c∈A se aRb e também bRc implicar aRc. Ou seja, se existir aRb e bRc, mas não existiraRc, então a relação R não é transitiva . Uma observação: neste caso, os elementos a, b e c não precisam ser, necessariamente, distintos. As relações de ≤ e =, por exemplo, são transitivas no conjunto |R.
Relações de equivalência Uma relação de equivalência, considerando um conjunto qualquer A não vazio, é uma endorrelação em A que possui, simultaneamente, as seguintes propriedades: simetria, reflexividade e transitividade. Um exemplo de relação de equivalência em sobre qualquer conjunto A é a relação de igualdade. Em outras palavras, a relação deve respeitar os seguintes princípios.
Relações de equivalência e partições: Uma partição de B nada mais é do que a subdivisão de B em conjuntos disjuntos e não vazios, sendo uma coleção {Ai} de subconjuntos e respeitando os seguintes critérios.
Relações de ordem parcial: Há dois tipos de relação de ordem parcial- ordem parcial ampla e ordem parcial estrita. Diz-se que uma endorrelação R sobre um conjunto A qualquer é chamada de ordem parcial ampla de A se R for reflexiva, antissimétrica e transitiva. Já uma endorrelação R em A é chamada de ordem parcial estrita se for irreflexiva, antissimétrica e transitiva. 
· Funções e Análise Combinatória
uma função nada mais é do que um tipo de relação entre dois conjuntos A e B, na qual cada elemento de A se relaciona com apenas um elemento de B (f: A → B). Nesse caso, o conjunto A é chamado de domínio da função e o conjunto B é chamado de contradomínio da função. O conjunto imagem de A é o conjunto formado por todos os elementos de B que se relacionam com A por meio da função. Em outras palavras, o conjunto imagem nada mais é do que um subconjunto do contradomínio, pois, para que haja função, nem todos os elementos do contradomínio devem estar necessariamente relacionados com algum elemento do domínio.
Uma função injetora quando cada elemento do domínio possuir uma imagem distinta, se a ≠ b então f(a) ≠ f(b). Considerando a visualização em um diagrama de flechas, por exemplo, nenhum elemento do conjunto imagem pode receber mais de uma flecha.
uma função é sobrejetora se o seu conjunto imagem for igual ao seu contradomínio. Todo elemento do contradomínio deve estar ligado a um elemento do domínio, respeitando a regra de formação da função. Pensando em um diagrama de flechas, neste caso, nenhum elemento do contradomínio pode ficar sem receber uma flecha.
uma função é considerada bijetora se for injetora e sobrejetora ao mesmo tempo.
· Composição de funções
A composição de funções é realizada de forma análoga a uma composição entre relações. Suponha que tenhamos as funções f: A → B e g: B → C. Você pode perceber que o contradomínio de f é o domínio de g. Quando isso ocorre, podemos fazer uma composição de f e g da seguinte forma: 
· Funções totais e parciais
Todas as funções que tratamos até o momento são consideradas funções totais. É costume omitir o termo “total” quando falamos de uma função cuja definição conhecemos no início desta unidade. Uma função parcial é apenas uma relação do tipo funcional. Uma relação funcional pode ser total ou parcial.
Uma função parcial é definida da seguinte forma: cada elemento pertencente ao seu domínio está relacionado com, no máximo, um elemento do contradomínio.
· Analise combinatória
A análise combinatória é o ramo da matemática responsável pelo estudo de técnicas e métodos que possibilitem identificar a quantidade de arranjos ou combinações possíveis dentro de um conjunto finito de elementos
Regra de soma: como funciona a regra da soma, pense na seguinte situação hipotética: suponha que você tenha que realizar duas tarefas. A primeira, você pode realizar de m formas e a segunda, de n formas. Além disso, você não pode realizar as duas tarefas ao mesmo tempo, ou seja, você realiza uma ou outra. Nesse caso, segundo a regra da soma, você poderá realizar as tarefas de m + n formas.
Regra do produto: A regra do produto também é conhecida como princípio fundamental da contagem. Para exemplificar essa regra, vamos pensar em outra situação hipotética. Suponha que um evento S possa ocorrer de m formas diferentes. Além disso, suponha que outro evento independente desse, o evento P, possa ocorrer de n maneiras diferentes. Logo, podemos dizer que ambos os eventos podem ocorrer de formas.
· Função fatorial
A função fatorial é uma fórmula matemática representada pelo sinal de exclamação “!”. Na fórmula fatorial devem-se multiplicar todos os números inteiros e positivos que existem entre o número que aparece na fórmula e o número 1.
Exemplo: 
· Arranjo simples
Os arranjos são tipos de agrupamentos nos quais a ordem de escolha dos objetos é importante. 
a restarão An1p formas de preencher o segundo lugar, e assim por diante, até o último. Representado por , o número de arranjos simples considerando n objetos agrupados p a p é dado por: 
exemplo:
Considerando os dígitos 1, 3, 5, 7 e 9, quantos números de 4 algarismos distintos podem ser formados? Solução – Esse é um exemplo clássico de arranjo simples, pois a ordem que cada elemento n (no caso, cada dígito) ocupará no número é importante. Por exemplo, o número 1.357 é diferente do número 3.175. Se a ordem dos elementos não tivesse importância, esses dois números contariam como um agrupamento, apenas, pois são os mesmos dígitos, porém ordenados de forma diferente. Esse problema mostra, portanto, um arranjo simples de 5 elementos agrupados 4 a 4. Aplicando-se, então, a fórmula para cálculo de arranjo simples, temos: Portanto, existem 120 maneiras de agrupar os dígitos 1, 3, 5, 7 e 9 em grupos de 4 algarismos.
· Permutações
Uma permutação simples é um arranjo simples de n objetos tomados n a n. Logo, podemos calcular uma permutação da seguinte forma:
Exemplo: Em uma sala de aula há 10 carteiras. De quantas maneiras diferentes 10 alunos podem ocupar essas carteiras? Solução – Nesse exemplo, temos mais um caso de permutação simples, pois tratamos de um arranjo de 10 alunos tomados 10 a 10. Pense da seguinte forma: se um aluno ocupa uma das cadeiras, sobram ainda outros nove para ocupar a segunda, oito para a terceira, e assim por diante. Logo: Portanto, existem 3628800 maneiras de 10 alunos ocuparem as 10 cadeiras.
· Combinações
No caso das combinações simples, a ordem de escolha dos elementos não é importante. Trata-se de um agrupamento de n elementos tomados p a p, que podemos calcular da seguinte forma:
Exemplo:
Uma empresa necessita de uma equipe com 6 integrantes, sendo três homens e três mulheres. Ela dispõe de 9 funcionários, cinco homens e quatro mulheres. De quantas maneiras diferentes essa equipe pode ser formada? Solução – Temos que resolver esse problema por partes. Primeiramente, vamos considerar a escolha das três mulheres. Existem quatro mulheres disponíveis e devemos agrupá-las em grupos de três. Será que, nesse caso, a ordem de escolha é importante? Suponha que as quatro mulheres sejam Ana, Paula e Joana. Se escolhermos Paula primeiro ao invés de Ana, fará diferença? Não! Logo, trata-se de um problema de combinação simples. Logo, o número de combinações possíveis para o grupo de mulheres é: Logo, existem 4 combinações possíveis para o grupo de mulheres. Agora, seguindo os mesmos conceitos, as combinações de grupos de homens serão: Portanto, existem 10 combinações possíveis para o grupo de homens. Mas o exercício ainda não terminou. Neste momento, temos que determinar de quantas maneiras diferentes a equipe pode ser formada. Bem, nesse caso, podemos utilizar o princípio fundamental da contagem, pois temos 4 combinações de mulheres e 10 combinações de homens. Portanto, para calcular a quantidade total de combinações, temos: 
C = 4 (mulheres) ⋅ 10 (homens) = 40 
Logo, teremos 40 combinações possíveis de homens e mulheres para essa equipe.
· Indução e provas matemáticas
A indução é um processo que vai do particular ao geral, isso é, partimos de uma preposição que se aplica a um corte específico a fim de gerar uma regra que valha para um contexto maior.
Indução finita: O princípio de indução finita trabalha no conjunto dos númerosnaturais, Adotaremos a letra n como índice nesse conjunto para as propriedades que queremos provar. Assim, algumas proposições feitas com n podem ser verdadeiras ou falsas – e é isso o que queremos provar! Se quisermos propor algo que envolva o número sucessor de n, usaremos a notação n + 1; e se quisermos o seu antecessor, n − 1. Com essa notação, podemos indicar as proposições da indução N.
Método de Indução: é quando queremos provar que uma certa propriedade é verdadeira para todos os números naturais, frequentemente usamos o método de indução matemática que se dá através dos seguintes passos: Para uma proposição aberta sobre N 
• Base de Indução: mostrar que P(0) é verdade; 
• Hipótese de indução: supor que, para algum n ϵ N, P(n) é verdade; 
• Passo de indução: mostrar que P(n + 1) é verdade.
a prova indutiva é uma técnica de demonstração que tem como base o princípio de indução, e não a lógica pura. É uma técnica que tenta provar se uma conjectura é correta.
· Recursão: Funções e Conjuntos Recursivos
a recursão é quando uma função chama ela mesma para resolver problemas menores até que se chegue ao resultado final. Um exemplo clássico na matemática seria o cálculo do fatorial de um número. Você deve estar familiarizado com esse conceito. Para se encontrar um fatorial de um determinado número natural, devemos realizar múltiplas multiplicações de um número pelo seu antecessor até que se chegue ao número.
· Provas matemáticas
A prova de um teorema parte de uma conjectura, que é uma definição que ainda não possui prova.
A prova de um teorema parte de uma conjectura, que é uma definição que ainda não possui prova.
A forma direta de se demonstrar um teorema parte de uma hipótese p e usa-se uma sequência de proposições lógicas (provadas por indução, por exemplo) até que seja obtida a tese q. Essa é uma sequência de passos direta que demonstra a implicação p->q.]
· Estratégias de Provas Matemáticas
Negação (ou Contrapositiva): O método da negação, como o próprio nome diz, trata o caminho direto da lógica, mas demonstrando o contrário do que se deseja provar. Ou seja, supondo que a negação da tese seja verdadeira (¬q), procura-se uma sequência de deduções que comprovem que a negação da hipótese (¬p) também seja verdadeira. Teríamos assim que (¬p) (¬q), o que traz uma conclusão logicamente correta de que p->q.
Condicional (ou “se e somente se”) Esse método de prova deseja demonstrar que uma hipótese leva a uma tese se, e somente se, a tese pode comprovar a hipótese ou, em termos matemáticos, p<->q. Para isso, dividimos a prova em duas partes, sendo a primeira p->q e a segunda q->p, para que a prova seja a união das duas: (p->q) ^ (q->p).
Supressão do Quantificador: Algumas provas utilizam o chamado quantificador universal, ou seja, algo do tipo: (∀x ϵ D)P(x) – o que pode ser lido como: para qualquer x pertencente a D, tem-se a hipótese P(x). Nesse caso, x é um elemento arbitrário do conjunto D e a ideia da prova é suprimir o quantificador na prova. Se conseguirmos suprimi-lo e ainda assim provar a condição, temos uma demonstração válida.
Implicação com Hipótese Disjuntiva: Suponha que tenhamos que provar uma condição do tipo: (p ∨ q)-: r. Nesse caso, temos uma hipótese como disjunção de duas afirmações (lê-se p ou q). Na disjunção, é preciso que ao menos uma das hipóteses seja verdadeira para que a condição seja verdadeira.