Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIVERSIDADE FEDERAL DE PELOTAS CENTRO DE DESENVOLVIMENTO TECNOLÓGICO CURSO DE CIÊNCIA DA COMPUTAÇÃO CURSO DE ENGENHARIA DE COMPUTAÇÃO Sistemas Discretos I Prof. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum Loreto MATEMÁTICA DISCRETA ou SISTEMAS DISCRETOS I Introdução Praticamente, qualquer estudo em Computação e Informática, teórico ou aplicado, exige como pré-requisito conhecimentos de diversos tópicos de Matemática. Tal fato é normalmente explicitado na maioria dos livros de Computação e Informática, sendo que alguns possuem um capítulo específico no qual tais tópicos são brevemente ou resumidamente introduzidos. A importância da Matemática é explicitada nas Diretrizes Curriculares do MEC para cursos de Computação e Informática, como segue (a matéria Matemática é integrante da área de Formação Básica): “A formação básica tem por objetivo introduzir as matérias necessárias ao desenvolvimento tecnológico da computação. O principal ingrediente desta área é a ciência da computação, que caracteriza o egresso como pertencente à área de computação. A maioria das matérias tecnológicas são aplicações da ciência da computação. São matérias de formação básica dos cursos da área de computação: a ciência da computação, a matemática, a física e eletricidade e a pedagogia.”(MEC 2004) Especificadamente, em relação à Matemática, o texto destaca que: “A Matemática, para a área de computação, deve ser vista como uma ferramenta a ser usada na definição formal de conceitos computacionais (linguagem, autômatos, métodos, etc.). ...... Considerando que a maioria dos conceitos computacionais pertence ao domínio do discreto, a Matemática Discreta (ou também chamada Álgebra Abstrata, Sistemas Discretos) é fortemente empregada. ....” Uma questão importante para o entendimento do que segue é a origem do termo Matemática Discreta. Intuitivamente falando, qualquer sistema de computador possui limitações finitas em todos os seus principais aspectos como, por exemplo, tamanho da 2 memória, número de instruções que pode executar, número de símbolos diferentes que pode tratar, etc. Assim, o estudo dos conjuntos finitos é fundamental. O fato de um sistema de computador possuir limitações finitas não implica necessariamente uma limitação ou pré-fixação de tamanhos máximos. Por exemplo, no que se refere à capacidade de armazenamento, um computador pode possuir unidades auxiliares como discos removíveis, fitas, etc. Portanto, para um correto entendimento de diversos aspectos computacionais, freqüentemente não é possível pré-fixar limites, o que implica tratar tais questões em um contexto infinito. Entretanto, qualquer conjunto de recursos computacionais, finito ou infinito, é contável ou discreto (em oposição ao termo contínuo), no sentido em que seus elementos (recursos) podem ser enumerados ou seqüenciados (segundo algum critério) de tal forma que não existe um elemento entre quaisquer dois elementos consecutivos da enumeração. Por exemplo, o conjunto dos números naturais é obviamente contável. Um importante contra-exemplo é o conjunto dos números reais, o qual é não-contável ou não-discreto. Isso significa que existem conjuntos infinitos contáveis e conjuntos infinitos não- contáveis. Assim, a Matemática Discreta possui como ênfase os estudos matemáticos baseados em conjuntos contáveis, finitos e infinitos. (Paulo Blauth Menezes, Matemática Discreta para Computação e Informática) O que é Matemática Discreta? a) Grandezas físicas discretas x grandezas físicas contínuas Ex: Discretas: número de alunos de uma sala de aula, número de carros em um estacionamento; Contínuas: temperatura, distância percorrida, quantidade (número de litros) num tanque de gasolina. Exemplo Prático: Relógios de Pulso A matemática contínua corresponde aos relógios analógicos � – o tipo que separa os ponteiros das horas, minutos e segundos. Os ponteiros se movem suavemente ao longo do tempo. Do ponto de vista de um relógio analógico, entre 12:02 pm e 12:03 pm há um número infinito de diferentes tempos possíveis, na medida em que o ponteiro dos segundos percorre o mostrador. A matemática contínua estuda conceitos infinitos em seu objetivo, em que um objeto pode combinar-se suavemente com o próximo. O sistema dos números reais está no cerne da matemática contínua e – tal como o relógio -, entre dois números reais quaisquer, há uma infinidade de números reais. A matemática discreta é comparável a um relógio digital , em que há apenas um número finito possível de tempos diferentes entre 12:02 pm e 12:03 pm. Um relógio digital não reconhece frações de segundos. Não há tempo algum entre 12:02:03 e 12:02:04. O relógio salta de um instante para o próximo. Um relógio digital só pode mostrar um número finito de tempos diferentes, e a transição de um tempo para o próximo é bem 3 definida e sem ambigüidade. Assim, como o sistema de números reais desempenha papel central na matemática contínua, os inteiros são o instrumento principal da matemática discreta. A matemática discreta é o instrumento de escolha em uma diversidade de aplicações, dos computadores ao planejamento de chamadas telefônicas, e das atribuições de pessoal à genética. b) Conjuntos Discretos x ContinuUm Um conjunto é dito discreto se for finito ou infinito enumerado (conjunto dos números naturais) e todos seus elementos são isoláveis. Ex: IN, Z, {1, 2, 3, 4, 5} Um conjunto é dito um continuum se de modo análogo ao que ocorre com um intervalo, uma superfície ou um sólido, seus elementos formam uma ordenação ininterrupta. Ex: o intervalo [0,1]; IR Obs: O conjunto dos números racionais {Q} não é discreto mas também não é um continuUm. c) Matemática Discreta: É a parte da matemática que se restringe a objetos definidos em termo de conjuntos discretos. Campos da Matemática Discreta: - Álgebra Discreta - Geometria Discreta - Estatística Discreta - Probabilidade Discreta. 1- Conceitos Básicos de Teoria dos Conjuntos � Conjuntos. É uma coleção de zero ou mais objetos distintos, chamados elementos do conjunto os quais não possuem qualquer ordem associada. Exemplos: a) As vogais a, e, i o, u; b) Os dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9; c) Todos os brasileiros; d) Os números pares 0, 2, 4, 6,... . A definição de um conjunto listando todos os seus elementos é denominada denotação por extensão e é dada pela lista de todos os seus elementos, sem repetição, em qualquer ordem (separados por vírgula) e entre chaves, como por exemplo: Vogais= {a, e, i, o, u} 4 A definição de um conjunto por propriedades é denominada denotação por compreensão como, por exemplo: Pares= {n׀ n é número par} (conjunto de todos os elementos n tal que n é número par) Assim a forma geral de definição de um conjunto por propriedade é: {x׀ p(x)} de maneira que um determinado elemento a é elemento desse conjunto se a propriedade p é verdadeira para a, ou seja, se p(a) é verdadeira. Por exemplo, para o conjunto: B={x׀ x é brasileiro} Pelé é elemento de B e Bill Gates não é elemento de B. Embora seja possível definir qualquer conjunto por compreensão, freqüentemente é conveniente especificar conjuntos da forma: Dígitos={0, 1, 2, 3,..., 9} Pares={0, 2, 4, 6,...} Nos quais os elementos omitidos podem ser facilmente deduzidos do contexto. � Pertinência. Se um determinado elemento a é elemento de um conjunto A, tal fato é denotado por: a∈A (a pertence ao conjunto A). Caso contrário, afirma-se que a não pertence ao conjunto A: a∉A. Exemplos: a) Vogais = {a, e, i, o, u} a∈Vogais h∉Vogais b) B = {x׀ x é brasileiro}Pelé∈B Bill Gates∉B Conjuntos Importantes N Conjunto do Números Naturais Z Conjunto dos Números Inteiros Q Conjunto dos Números Racionais I Conjunto dos Números Irracionais ℜℜℜℜ Conjunto dos Números Reais � Conjunto vazio: é o conjunto que não contém elementos e é representado por { } ou φ . 5 Exemplos: a) O conjunto de todos os números que são simultaneamente pares e ímpares; b) A = {x∈R ׀ x2 + 1 = 0}. � Conjunto Unitário: é o conjunto constituído por um único elemento. Exemplos: a) O conjunto de todos os números que são simultaneamente pares e primos; b) A = {x∈N ׀ x + 2 = 8}. � Conjunto Universo. Normalmente denotado por U, contém todos os conjuntos que estão sendo considerados. O conjunto universo define o contexto de discussão (e, portanto, U não é um conjunto fixo). Exemplos: a) A = {x∈R ׀ 41 << x }, U = R , é um conjunto infinito; b) B = { x∈N ׀ 41 << x }, U = N, é um conjunto finito = {2, 3}. � Subconjunto. Um conjunto A é subconjunto de B ou, A está contido em B ou, B contém A, se todo elemento que pertence a A, pertence, também a B. A⊆⊆⊆⊆B ou B⊇⊇⊇⊇A A negação de A⊆⊆⊆⊆B é indicada por A⊆⊆⊆⊆B. Obs.: Nesse caso (A⊆⊆⊆⊆B ou B⊇⊇⊇⊇A) afirma-se que A é subconjunto de B. Simbolicamente: A⊆⊆⊆⊆B ( )( )BxAxx ∈→∈∀↔ A⊆⊆⊆⊆B ( ) ( )BxAxx ∉∧∈∃↔ Observações: • Como B⊆⊆⊆⊆B, B é subconjunto de B, qualquer que seja o conjunto B. • Como ⊆φ B, φ é subconjunto de qualquer que seja o conjunto B. • B e φ são subconjuntos triviais de B. • Se A⊆⊆⊆⊆B mas existe b ∈ B tal que b ∉A, então afirma-se que A está contido propriamente em B, ou que A é subconjunto próprio de B, e denota-se por: A ⊂ B. Ou, alternativamente, que B contém propriamente A, denota-se por B ⊃ A. Exemplo: Seja B = {1, 2, 3}. Subconjuntos de B = φ , {1}, {2}, {3}, {1,2}, {1, 3}, {2, 3}, {1, 2, 3} onde φ e {1, 2, 3} são subconjuntos triviais e {1}, {2}, {3}, {1, 2}, {1, 3} e {2, 3} são subconjuntos próprios. 6 � Igualdade de Conjuntos. Dois conjuntos A e B dizem-se iguais se e somente se, todo elemento pertencente a um deles também pertence ao outro, ou seja, A⊆⊆⊆⊆B e B⊆⊆⊆⊆A. Simbolicamente: A = B : ( )( )BxAxx ∈↔∈∀ ou A = B ABBA ⊆∧⊆↔ . Exemplos: a) {1,2,3} ={x ∈ Nx > 0 e x < 4} b) N = {x ∈ Zx ≥0} c) {1,2,3} = {3,3,3,2,2,1} É importante distinguir entre ⊆ e ∈. A notação x ∈A significa que x é um elemento (ou membro) de A. A notação A⊆B significa que todo elemento de A é também elemento de B. Exemplificando, considere o conjunto A={1,2,3,4}, então ∅⊆{1,2,3} é verdadeiro, mas ∅∈{1,2,3} é falso. A diferença entre ∈ e ⊂ é análoga à diferença entre x e {x}. O símbolo x se refere a um objeto e a notação {x} significa o conjunto cujo único elemento é x. Correto escrever x ∈{x}, mas não é correto escrever x = {x} ou x ⊆ {x}. Exemplos: Considere o conjunto A = {1,2,3,∅, {a}, {b,c}}. Então: a) {1} ∉A, {1} ⊆A b) ∅∈A, ∅⊆A c) {a} ∈A, {b,c} ∈A d) {1,2,3}∉A, {1,2,3}⊆A � Conjunto das Partes de um Conjunto (ou Conjunto Potência). A partir de um conjunto A, é o conjunto cujos elementos são todos os subconjuntos (ou partes) de A. Indicamos por P(A). Simbolicamente: P(A) = {X ׀ X⊆A} Exemplos: 1) B = {a, b}, P(B) = {φ , {a}, {b}, {a,b}} 2) B = φ , P(B) = {φ } Observação: Se A tem n elementos, então P(A) tem n2 elementos (subconjuntos). Obs.: Os símbolos ⊆ e ∈ possuem significados relacionados, porém diferentes. Não podem ser permutados! 7 � Conjuntos Finitos e Infinitos Um conjunto pode possuir um número finito ou infinito de elementos. Informalmente, um conjunto é dito: a) Conjunto finito se pode ser denotado por extensão, ou seja, listando exaustivamente todos os seus elementos; b) Conjunto infinito, caso contrário. Exemplos: a) Os seguintes conjuntos são finitos: ∅, {ε}, Vogais={a, e, i, o, u} Dígitos={0, 1,2, 3, 4, 5, 6, 7, 8, 9} A={ x ∈ N | x >0 e x< 4} B={x x é brasileiro} b) Os seguintes conjuntos são infinitos: Z R {x ∈ Z x ≥0} Pares={y y=2x e x ∈ N} � Alfabetos, Palavras e Linguagens A noção de conjunto permite definir linguagem, um dos conceitos mais fundamentais em Computação. • Alfabeto: é um conjunto finito. Os elementos de um alfabeto são usualmente denominados de símbolos ou caracteres. O conjunto vazio é um alfabeto, e um conjunto infinito não é um alfabeto. • Palavra, Cadeia de Caracteres, Sentença: Uma Palavra ou Cadeia de Caracteres ou Sentença sobre um alfabeto é uma sequência finita de símbolos (do alfabeto) justapostos. Uma cadeia sem símbolos é uma palavra válida, e o símbolo: ε denota a cadeia vazia, palavra vazia ou sentença vazia; ∑ representa um alfabeto; ∑* denota o conjunto de todas as palavras possíveis sobre ∑. Exemplos: a) Os conjuntos ∅ e {a, b, c} são alfabetos; b) O conjunto N não é um alfabeto; c) ε é uma palavra sobre o alfabeto {a, b, c}; d) a, e, i, o, u, ai, oi, ui, e aeiou são exemplos de palavras sobre Vogais; e) 1 e 001 são exemplos de palavras distintas sobre Dígitos; f) {a,b}*= {ε, a, b, aa, ab, ba, bb, aaa,...}. 8 � Linguagem Formal Uma Linguagem Formal, ou simplesmente Linguagem, é um conjunto de palavras sobre um alfabeto. Exemplos: Suponha o alfabeto ∑ = {a,b}. Então: a) O Conjunto vazio e o conjunto formado pela palavra vazia são linguagens sobre ∑, obviamente ∅ ≠ ε; b) O conjunto de palíndromas (palavras que tem a mesma leitura da esquerda para a direita e vice-versa) sobre ∑ é um exemplo de linguagem (finita); Palíndromos = {ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, ....}. c) Linguagens de Programação: as linguagens de programação como Pascal, C e Java são linguagens sobre o alfabeto constituído por letras, dígitos e alguns símbolos especiais (como espaço, parênteses, pontuação, etc.). Nesse caso, cada programa na linguagem corresponde a uma palavra sobre o alfabeto. Ou seja, uma linguagem de programação é definida por todos os seus programas possíveis. Portanto, Pascal, C, Java, bem como qualquer linguagem de programação de propósitos gerais, são conjuntos infinitos. 2- Noções de Lógica Algumas considerações: Lógica Matemática é básica para qualquer estudo em Computação e Informática e, em particular, para o estudo da Matemática Discreta (Sistemas Discretos). As Diretrizes Curriculares do MEC para Cursos de Computação e Informática destacam que: Lógica Matemática é uma ferramenta fundamental na definição de conceitos computacionais. E, para algumas disciplinas da Área de Formação Tecnológica, como Inteligência Artificial, esse texto destaca, enfaticamente que: Com base ao estudo da Inteligência Artificial são imprescindíveis conhecimentos de Lógica Matemática... Lógica permite definir a noção de teorema. Em computação, um teorema freqüentemente pode ser visto como um problema a ser implementado computacionalmente, e sua correspondente demonstração, pode ser vista como uma solução computacional, ou seja, um algoritmo. Adicionalmente, o algoritmo que soluciona o problema, prova-se, sempre funciona. Fonte: Livro de Matemática Discreta para Computação e Informática Paulo Blauth Menezes 9 Lógica Entende-se por Lógica Booleana ou Lógica de Boole o estudo dos princípios e métodos usados para distinguir sentenças verdadeiras de falsas. a) Proposição. É uma construção (sentença, frase, pensamento) à qual se pode atribuir juízo do tipo verdadeiro-falso. Em Lógica Matemática, a forma tradicional de tratar com a “verdade” é considerardois valores-verdade V e F (verdadeiro e falso, respectivamente) e estipular que as proposições só podem assumir esses dois valores. Para uma dada proposição p, denota-se por: V(p) o valor verdade de p. Exemplos: a) Proposições: Brasil é um país 3 + 4 > 5 7 – 1 =5 Para cada uma dessas proposições, o valor verdade é: V(Brasil é um país) = V V(3 + 4>5) = V V(7-1=5) = F b) Não são proposições: Vá tomar banho. Que horas são? b) Conetivos Lógicos: ou operadores lógicos, são utilizados para construir proposições mais complexas através da composição de proposições (proposições compostas). ~ : negação ∧ : e ∨ : ou → : se... então ↔ : se e somente se Sejam p e q proposições. O valor lógico (ou valor verdade) das proposições compostas obtidas do uso dos conetivos, depende dos valores lógicos das proposições p e q. *Negação (~p). A negação de uma proposição é construída, introduzindo-se a palavra não de forma apropriada o prefixando-se a proposição por “não é fato que” (ou expressão equivalente). 10 Exemplos: Considere as seguintes proposições: a) Brasil é um país. b) 3 + 4 >5 A negação dessas proposições é como segue, respectivamente: aa) Brasil não é um país. bb) Não é fato que 3 + 4>5. Notação: p denota uma proposição; A negação de p é ¬p ou ~p a qual é lida como “não p”. Interpretação: - se p é verdadeira, então ~p é falsa; - se p é falsa, então ¬p é verdadeira. Tabela Verdade: é uma tabela que descreve os valores lógicos de uma proposição em termos das possíveis combinações dos valores lógicos das proposições componentes e dos conetivos usados. Para cada combinação de valores verdade e de conetivos, a tabela verdade fornece o valor verdade da expressão resultante. p ~p V F F V Figura1: Tabela verdade - negação *Conjunção (p∧ q) . Reflete uma noção de simultaneidade para se verdadeira. A proposição composta p ∧ q é: - verdadeira, apenas quando p e q são simultaneamente verdadeiras; - falsa, em qualquer outro caso. p q p∧q V V V V F F F V F F F F Figura 2: Tabela Verdade - conjunção Obs.: Em relação a tabela verdade acima, observamos que para expressar todas as combinações possíveis de valores lógicos das proposições p e q, foram necessárias quatro linhas. Exemplos: V: Windows é um sistema operacional, e Pascal é uma linguagem de programação; F: Windows é um sistema operacional, e Pascal é uma planilha eletrônica; F: Windows é um editor de texto, e Pascal é uma linguagem de programação; F: Windows é um editor de texto, e Pascal é uma planilha eletrônica. 11 *Disjunção (p∨q). Reflete a noção de que pelo menos uma (eventualmente duas) das proposições componentes deve ocorrer para que a resultante seja verdadeira. A proposição composta p∨q é; - verdadeira, quando pelo menos uma das proposições é verdadeira; - falsa, somente quando simultaneamente p e q são falsas. Figura 3: Tabela Verdade - disjunção Exemplos: V: Windows é um sistema operacional, ou Pascal é uma linguagem de programação; V: Windows é um sistema operacional, ou Pascal é uma planilha eletrônica; V: Windows é um editor de texto, ou Pascal é uma linguagem de programação; F: Windows é um editor de texto, ou Pascal é uma planilha eletrônica. *Condição (p →q ). A partir de uma premissa verdadeira, obrigatoriamente deve-se chegar a uma conclusão verdadeira para que p→q seja verdadeira. Entretanto, partindo de uma premissa falsa, qualquer conclusão pode ser verdadeira. Lê-se: “se p então q” Partindo de uma premissa falsa, qualquer conclusão pode ser considerada. Assim, a proposição composta p→q é: - falsa, quando p é verdadeira e q é falsa; - verdadeira, caso contrário. p q p→q V V V V F F F V V F F V Figura 4: Tabela Verdade: condição Exemplos: V: se Windows é um sistema operacional, então Pascal é uma linguagem de programação; F: se Windows é um sistema operacional, então Pascal é uma planilha eletrônica; V: se Windows é um editor de texto, então Pascal é uma linguagem de programação; V: se Windows é um editor de texto, então Pascal é uma planilha eletrônica. *Bicondição (p ↔ p). Reflete a noção de condição nos dois sentidos, portanto, considerando a noção de condição, deve-se ter ambas verdadeiras ou ambas falsas para que p ↔ p seja verdadeira. p q p∨q V V V V F V F V V F F F 12 Lê-se: “p se e somente se q”. A noção de condição “nos dois sentidos” considera, simultaneamente: - sentido de “ida: p é premissa e q é conclusão; - sentido de “volta”: q é premissa e p é conclusão. Figura 5: Tabela Verdade - bicondição Exemplos: V: Windows é um sistema operacional se e somente se Pascal é uma linguagem de programação; F: Windows é um sistema operacional se e somente se Pascal é uma planilha eletrônica; F: Windows é um editor de texto se e somente se Pascal é uma linguagem de programação; V: Windows é um editor de texto se e somente se Pascal é uma planilha eletrônica. c)Fórmulas, Linguagem Lógica e Tabelas Verdade Fórmulas Lógicas ou simplesmente Fórmulas são as palavras da Linguagem Lógica, ou seja, uma sentença lógica corretamente construída sobre o alfabeto cujos símbolos são conetivos (∧, ¬, ∨, →, ↔), parênteses, identificadores (p, q, r, etc.), constantes, etc. Se uma fórmula contém variáveis, então esta não necessariamente possui valor verdade associado. Ou seja, seu valor lógico depende do valor verdade das sentenças que substituem as variáveis na fórmula. Exemplos: Suponha que p, q e r são sentenças variáveis. Então, são fórmulas: a) Os valores verdade constantes V e F b) p, q e r c) ¬p, p ∧ q, p ∨ q, p → q, p ↔ q d) p ∨ (¬q) e) (p ∧ ¬q) → F ���� Atenção! Ordem de procedência dos conetivos: 1. Conetivos entre parênteses, dos mais internos para os mais externos; 2. Negação (¬) 3. Conjunção (∧) e disjunção (∨) 4. Condição (→) 5. Bicondição (↔). p q p↔q V V V V F F F V F F F V 13 Exemplos: a)p ∨ (¬q) é equivalente a p ∨ ¬q b) (p ∧ ¬q) → F é equivalente a p ∧ ¬q → F Tabela Verdade: deve explicitar todas as combinações possíveis dos valores lógicos das fórmulas atômicas componentes. Observe que; - cada fórmula atômica não constante pode assumir dois valores lógicos: V ou F; - para n fórmulas atômicas (não constantes), são necessárias 2n linhas na tabela verdade para expressar todas as combinações possíveis de valores lógicos. Exemplos: Construa as tabelas verdade das seguintes fórmulas: a) p ∧ ¬q b) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p∨ r) d)Tautologia e Contradição Definição: Seja w uma fórmula. Então: a) w é dita uma Tautologia se w é verdadeira, ou seja, se for verdadeira para todas as combinações possíveis de valores de sentenças variáveis; b) w é dita uma Contradição se w é falsa, ou seja, se for falsa para todas as combinações possíveis de valores de sentenças variáveis. Exemplo: Suponha p uma fórmula. Considere a tabela verdade abaixo: Figura 6: Tabela verdade - tautologia e contradição a) A fórmula p ∨∨∨∨ ¬¬¬¬p é uma tautologia. b) A fórmula p ∧∧∧∧ ¬¬¬¬p é uma contradição. e)Implicação e Equivalência Os conetivos de condição e bicondição induzem as relações de implicação e de equivalência entre fórmulas, respectivamente. a) Relação de implicação: está diretamente relacionada com o conceito de teorema; b) Relação de equivalência: permite definir a noção de “mesmo significado” entre duas fórmulas (sintaticamente) diferentes. Relação de Implicação: Sejam p e qduas fórmulas. Então p implica q, denotado por: p ⇒ q se e somente se p → q é uma tautologia. p ¬¬¬¬p p ∨∨∨∨ ¬¬¬¬p p ∧∧∧∧ ¬¬¬¬p V F V F F V V F 14 Exemplo: Considere a tabela verdade da Figura 7. Então, valem as seguintes implicações: a) Adição: p ⇒ p ∨ q b) Simplificação: p ∧ q ⇒ p p q p∨q p→(p∨q) p∧q (p∧q)→p V V V V V V V F V V F V F V V V F V F F F V F V Figura 7: Tabela Verdade - adição e simplificação Relação de Equivalência: Sejam p e q duas fórmulas. Então p é equivalente a q, denotado por p ⇔ q se e somente se p ↔ q é uma tautologia. Exemplo: Considere a fórmula p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p∨ r) e respectiva tabela verdade: Figura 8: Tabela verdade Observando a tabela verdade, vale a relação de equivalência p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p∨ r) onde mostra que a distributividade do conetivo ou sobre o conetivo e é verdadeira sempre. Exemplos Importantes: Exemplo 1: Bicondição x Condição Considere a seguinte fórmula p ↔q ⇔ (p→q) ∧ (q→p) e respectiva tabela verdade: Figura 9: Tabela Verdade – bicondição x condição Este exemplo mostra formalmente por que a bicondição pode ser expressa por duas condições: ‘ida” e “volta”. p q r q∧r p∨(q∧r) p∨q p∨r (p∨q)∧(p∨r) p∨(q∧r)↔(p∨q)∧(p∨r) V V V V V V V V V V V F F V V V V V V F V F V V V V V V F F F V V V V V F V V V V V V V V F V F F F V F F V F F V F F F V F V F F F F F F F F V p q p↔q p→q q→p (p→q)∧(q→p) (p↔q)↔(p→q)∧(q→p) V V V V V V V V F F F V F V F V F V F F V F F V V V V V 15 Exemplo 2: Contraposição Considere a fórmula p →q ⇔ ¬q → ¬p e respectiva tabela verdade: Figura 10: Tabela Verdade – contraposição Exemplo 3: Redução ao Absurdo Considere a fórmula p→q ⇔ p∧ ¬q → F. Pela tabela verdade, verifica-se que a relação de equivalência é válida (conhecida por redução ou absurdo). Figura 11: Tabela Verdade – redução ao absurdo. f) Quantificadores Proposição Sobre um Conjunto Definição: Uma Proposição Sobre A é uma proposição cujo valor lógico depende do elemento x ∈ A considerado. Exemplos: São proposições sobre o conjunto N: a) n >1 b) n! <10 c) n+1 > n d) 2n é par Quais proposições são verdadeiras para qualquer n ∈ N? Uma proposição p a qual descreve alguma propriedade de um elemento x ∈ A é usualmente denotada por p(x). Toda proposição p sobre A determina dois conjuntos, como segue: a) Conjunto verdade de p {x ∈ A p(x) é verdadeira} b) Conjunto falsidade de p { x ∈ A p(x) é falsa}. p q ¬p ¬q p→q ¬q→¬p p→q ↔ ¬q→ ¬p V V F F V V V V F F V F F V F V V F V V V F F V V V V V P q ¬q p→q p∧ ¬q p∧ ¬q →F p→q ↔ p∧ ¬q → F V V F V F V V V F V F V F V F V F V F V V F F V V F V V 16 Exemplos: Suponha os conjuntos N. Então: a) Para a proposição n >1: {2, 3, 4, ...} é o conjunto verdade; {0,1} é o conjunto falsidade; b) Para a proposição n!<10: {0,1,2,3} é o conjunto verdade; {n ∈ N n>3} é o conjunto falsidade; c) Para a proposição n + 1 >n: N é o conjunto verdade (é o próprio conjunto universo); ∅ é o conjunto falsidade; d) Para a proposição “2n é ímpar”: ∅ é o conjunto verdade; N é o conjunto falsidade (é o próprio conjunto universo). OBS.: Uma proposição p sobre A é uma: a) Tautologia se p(x) é verdadeira para qualquer x ∈ A, ou seja, o conjunto verdade é A; b) Contradição se p(x) é falsa para qualquer x ∈ A, ou seja, o conjunto falsidade é A. Exemplos: Suponha o conjunto universo N. Então: a) A fórmula n!<10 não é uma tautologia nem contradição. De fato, por exemplo: Para n = 0, a fórmula é verdadeira Para n = 4, a fórmula é falsa b) A fórmula n + 1> n é uma tautologia. De fato, o conjunto verdade é o conjunto universo N; c) A fórmula “2n é ímpar” é uma contradição. De fato, o conjunto falsidade é o próprio conjunto universo N. Quantificador Para uma determinada proposição p(x), é desejável quantificar os valores de x que devem ser considerados. Os seguintes quantificadores são usados em Lógica (suponha uma proposição p(x)): a) Quantificador universal, simbolizado por ∀, o qual, associado a uma proposição p(x), é denotado alternativamente como segue: (∀ x ∈ A) (p(x)) (∀ x∈A)p(x) ∀x∈A, p(x) b) Quantificador existencial, simbolizado por ∃, o qual associado a uma proposição p(x), é denotado alternativamente como segue: (∃x ∈A)(p(x)) (∃x ∈A) p(x) ∃x ∈A,p(x) Quando é claro sobre qual conjunto de valores a proposição está definida, uma expressão quantificada (∀x∈A) p(x) (respectivamente, (∃x∈A)p(x)) pode ser simplesmente denotada como segue, respectivamente: (∀x)(p(x)) (∀x)p(x) ∀x,p(x) (∃x)(p(x)) (∃x)p(x) ∃x, p(x) 17 Uma leitura de uma proposição quantificada (∀x∈A)p(x) (respectivamente, (∃x∈A)p(x)), é como segue, respectivamente: “qualquer x, p(x)” ou “para todo x, p(x)” “existe pelo menos um x tal que p(x)” ou “existe x tal que p(x)” Como a leitura induz, o valor verdade de uma proposição quantificada é como segue: a) (∀ x∈A)p(x) é verdadeira, se p(x) for verdadeira para todos os elementos de A; b) (∃x ∈A) p(x) é verdadeira, se p(x) for verdadeira para pelo menos um elemento de A. Definição: Quantificador Universal, Quantificador Existencial Seja p(x) uma proposição lógica sobre um conjunto A. Então: a) Quantificador Universal: a proposição (∀ x∈A)p(x) é: - verdadeira, se o conjunto verdade for igual ao conjunto A; - falsa, caso contrário. b) Quantificador Existencial: a proposição (∃x ∈A) p(x) é: - verdadeira, se o conjunto verdade for não-vazio; - falsa, caso contrário. Exemplos: Procure justificar o valor verdade de cada uma das seguintes proposições quantificadas: a) (∀ n∈ N)(n <1) é falsa (∃n ∈ N)(n<1) é verdadeira b) (∀ n∈ N)(n! <10) é falsa (∃n ∈ N)(n!<10) é verdadeira c) (∀ n∈ N)(n+1>n) é verdadeira (∃n ∈ N)(n+1>n) é verdadeira d) (∀ n∈ N)(2n é par) é verdadeira (∃n ∈ N)(2n é par) é verdadeira A noção de uma proposição p(x) sobre um conjunto pode ser generalizada, resultando em uma proposição p a qual descreve alguma propriedade de elementos x1 ∈ A1, x2 ∈ A2, ..., xn ∈ An. Tal proposição é usualmente denotada por: p(x1, x2, ...,xn). Cada um dos elementos x1, x2, ...,xn pode ser individualmente quantificado. Neste caso, a ordem dos quantificadores existencial e universal pode alterar o valor verdade da proposição. Por exemplo, para o conjunto universo N, vale: (∀ n) (∃m)(n <m) é verdadeira (∃m)(∀n)(n<m) é falsa 18 De fato: a) Para (∀ n) (∃m)(n <m), dado qualquer valor n, é possível encontrar (existe) pelo menos um m que satisfaz a desigualdade. Por exemplo, basta tomar m= n+1. Assim, para qualquer número natural n, vale a proposição n<n+1, que é verdadeira; b) A proposição (∃m)(∀n)(n<m) afirma que existe um número natural maior que qualquer outro. Sabe-se que tal número natural não existe. Portanto, a proposição é falsa. Obs.: Existe pelo menos um x Existe um único É comum quantificar existencialmente de forma única, ou seja, de tal forma que existe um elemento e este é único. Portanto, não é uma quantificação existencial usual na qual pode existir mais de um. Tal quantificador é usualmente simbolizado por ∃!. Exemplo: (∃!n ∈ N)(n<1) é verdadeira (∃!n ∈ N)(n!<10) é falsa (∃!n ∈ N)(n+1>n) é falsa (∃!n ∈ N)(2n é par) é falsa. Prova-se que o quantificador ∃! pode equivalentemente ser representado usando os quantificadores universal e existencial e os conetivos usuais: (∃! x) p(x) ⇔ (∃x)p(x) ∧ (∀x)(∀y)(p(x)∧p(y) → x=y)) Negação de ProposiçõesQuantificadas A negação de uma proposição quantificada é intuitiva. Suponha a seguinte proposição quantificada: (∀ x∈A)p(x) cujo valor verdade é: (∀ x∈A)p(x) é verdadeira, se p(x) for verdadeira para todos os elementos de A. A negação significa que não é verdadeira para todos os elementos de A, ou seja, que existe pelo menos um x tal que não é fato que p(x), e portanto: (∃x ∈A) ¬p(x) Logo, ¬((∀ x∈A)p(x)) ⇔ (∃x) ¬p(x) A negação de uma proposição quantificada universalmente (respectivamente, existencialmente) é a negação da proposição quantificada existencialmente (respectivamente, universalmente). 19 Exemplos: a) ¬((∀ n∈ N)(n <1)) ⇔ (∃n ∈ N) (n≥1)⇔V ¬((∃n ∈ N)(n<1) ) ⇔ (∀ n∈ N)(n ≥1) ⇔ F b) ¬((∀ n∈ N)(n! <10)) ⇔ (∃n ∈ N)(n! ≥10)⇔ V ¬((∃n ∈ N)(n!<10)) ⇔ (∀ n∈ N)(n!≥10)⇔ F c) ¬((∀ n∈ N)(n+1>n)) ⇔ (∃n ∈ N)(n +1≤n) ⇔ F ¬((∃n ∈ N)(n+1>n)) ⇔ (∀ n∈ N)(n+1≤n) ⇔ F d) ¬((∀ n∈ N)(2n é par)) ⇔ (∃n ∈ N) (2n não é par) ⇔ F ¬((∃n ∈ N)(2n é par)) ⇔ é verdadeira (∀ n∈ N)(2n não é par) ⇔ F. 3 – Álgebra de Conjuntos � Operações Não Reversíveis e Reversíveis As operações sobre conjuntos são classificadas em reversíveis e não reversíveis. Embora as não reversíveis sejam as mais usuais, as reversíveis são especialmente importantes para Computação e Informática. As seguintes operações são definidas sobre conjuntos: a) Não Reversíveis - União; - Intersecção; b) Reversíveis - Complemento; - Conjunto das Partes; - Produto Cartesiano; - União Disjunta. Adicionalmente, é introduzida a operação de diferença, do tipo não reversível, a qual é derivada a partir da composição das operações complemento e intersecção. 3.1 Operações Não Reversíveis São as operações mais comuns. � União: A união de dois conjuntos A e B é constituída de todos os elementos que pertencem a A ou a B. xBA {=∪ ׀ }BxAx ∈∨∈ ( )BA união Relacionando com a Lógica, a união corresponde à noção de disjunção. Ou seja, A ∪ B considera todos os elementos que pertencem ao conjunto A ou ao conjunto B. 20 Propriedades: Sejam os conjuntos A, B e C. 1) AA =∪φ (Elemento Neutro) 2) AAA =∪ (Idempotência) 3) ABBA ∪=∪ (Comutativa) 4) ( ) )( CBACBA ∪∪=∪∪ (Associativa) 5) UUA =∪ (Conjunto universo) Exemplos: a) Suponha os conjuntos: Dígitos = {0,1,2,3,4,5,6,7,8,9} Vogais = {a, e, i ,o,u} Dígitos ∪ Vogais = {0,1,2,3,4,5,6,7,8,9,a,e,i,o,u} b) Suponha os conjuntos A={x ∈ N x >2} e B = {x ∈ N x2 = x} A ∪ B = {0,1,3,4,5,6,...} � Intersecção: A intersecção de dois conjuntos A e B é constituída de todos os elementos que pertencem a A e a B. xBA {=∩ ׀ }BxAx ∈∧∈ ( )BA ointersecçã Se φ=∩ BA , então A e B são ditos conjuntos disjuntos, conjuntos independentes ou conjuntos mutuamente exclusivos. Relacionando com a Lógica, a intersecção corresponde à noção de conjunção. Ou seja, A ∩ B considera todos os elementos que pertencem ao conjunto A e ao conjunto B. Propriedades: Sejam os conjuntos A, B e C. 1) φφ =∩A (Elemento Neutro) 2) AAA =∩ (Idempotência) 3) ABBA ∩=∩ (Comutativa) 4) ( ) )( CBACBA ∩∩=∩∩ (Associativa) 5) AUA =∩ (Conjunto universo) Propriedades Distributivas 1) ( ) ( ) ( )CABACBA ∪∩∪=∩∪ (da união em relação a intersecção) 2) ( ) ( ) ( )CABACBA ∩∪∩=∪∩ (da intersecção em relação a união) Propriedade Absorção: A ∩(A ∪ B) = A A ∪(A ∩ B) = A 21 Exemplos: a) Suponha os conjuntos: Dígitos = {0,1,2,3,4,5,6,7,8,9} Vogais = {a, e, i ,o,u} Dígitos ∩ Vogais = ∅ b) Suponha os conjuntos A={x ∈ R x >2} e B = {x ∈ N x2 = x} A ∩ B = ∅ 3.2 Operações Reversíveis Entende-se por operação reversível uma operação a partir de cujo resultado é possível recuperar os operandos originais. � Conjunto Complementar. Seja A um subconjunto de um conjunto U (isto é, A⊆ U). O conjunto complementar de A em relação a U é formado pelos elementos de U que não pertencem a A. Representa-se por ACU (~A ou A’). Simbolicamente: xACU { = ׀ AxUx ∉∧∈ }. A operação de complemento é uma operação unária a qual é definida em relação a um conjunto universo. Relacionando com a Lógica, o complemento corresponde à noção de negação. Ou seja, considera todos os elementos do universo que não pertencem ao conjunto original. Exemplos: 1) X = {1, 2, 3, 4, 5}, A = {1, 2}, AC X = {3, 4, 5} 2) X = { Nx ∈ ׀ x é divisível por 5} A = { Nx ∈ ׀ x termina por 5} ~A = NxACX ∈= { ׀ x termina por 0} Complemento, união e Intersecção Suponha que U é o conjunto universo. Então, para qualquer conjunto A ⊆ U, vale: A ∪ ~A = U A ∩ ~A = ∅ Observações: - a união de um conjunto com o seu complemento sempre resulta no conjunto universo (compare com o fato de que p ∨¬p é uma tautologia); - a intersecção de um conjunto com o seu complemento sempre resulta no conjunto vazio (compare com o fato de que p ∧¬p é uma contradição). Propriedades: - Duplo Complemento: para um dado conjunto A ⊆ U, vale: ~~A = A. Esta propriedade está diretamente relacionada com a dupla negação da Lógica: 22 - para um conjunto A, considera-se todos os elementos x tais que x ∈ A; - para o ~A, considera-se todos os elementos x tais que x ∉ A, ou seja, tais que ¬(x ∈ A); - consequentemente, para ~~A, considera-se todos os elementos x tais que ¬¬(x ∈ A), ou seja, tais que x ∈ A. - DeMorgan: envolve as operações de união e intersecção: ~(A ∪ B) = ~A ∩ ~B ¬(p ∨ q) ⇔¬p ∧ ¬q ~(A ∩ B) = ~A ∪ ~B ¬(p ∧ q) ⇔¬p ∨ ¬q Essa propriedade permite concluir que a intersecção (respectivamente, a união) pode ser calculada em termos das operações de complemento e de união (respectivamente, de intersecção): A ∩ B = ~(~A ∪ ~B) A ∪ B = ~(~A ∩ ~B). � Diferença. A diferença de dois conjuntos A e B é constituída de todos os elementos que pertencem a A e não pertencem a B. xBA {=− ׀ }BxAx ∉∧∈ ou A – B = A ∩ ~B. Observação: Se φ=∩ BA , então ABA =− . Exemplos: a) Suponha os conjuntos: Dígitos = {0,1,2,3,4,5,6,7,8,9} Vogais = {a, e, i ,o,u} Dígitos - Vogais = Dígitos b) Suponha os conjuntos A={x ∈ N x >2} e B = {x ∈ N x2 = x} A – B = {3, 4, 5, 6,...} B – A = {0,1}. � Produto Cartesiano. Sejam A e B conjuntos. O produto cartesiano de A por B é o conjunto formado por todos os pares ordenados ),( ba com a∈A e b∈B. A×B ={(a, b)׀ a∈A e b∈B} É usual denotar um produto cartesiano de um conjunto com ele mesmo como A×A= 2A . Um par ordenado no qual a primeira componente é x e a segunda é y é denotado na forma (x, y) ou 〉〈 yx , 23 e não deve ser confundido com o conjunto {x, y}: em um par ordenado a ordem é importante, pois são distinguidas as componentes. O conceito de par ordenado pode ser generalizado para n-upla ordenada denotada na forma ( )nxxxx ,...,,, 321 ou 〉〈 nxxxx ,...,,, 321 Exemplos: Sejam A = {a}, B = {a, b} e C = {0, 1, 2}. Então: a) )},( ),,{( baaaBA =× b) })2,( ),1,( ),0( ),2,( ),1,( ),0,{( bbb,aaaCB =× c) )},2( ),,1( ),,0( ),,2( ),,1( ),,0{( bbbaaaBC =× d) )},( ),,( ),,( ),,{(2 bbabbaaaB = e) ),...}3,( ),2,( ),1,( ),0,{( aaaaNA =× f) )}2),,(( ),1),,(( ),0),,(( ),2),,(( ),1),,(( ),0),,{(()( bababaaaaaaaCBA =×× g) ))}2,(,( )),1,(,( )),0,(,( )),2,(,( )),1,(,( )),0,(,{()( bababaaaaaaaCBA =×× h) φφ=×A Relativamente ao exemplo anterior, observe que: - Os conjuntos BCCB ×× e são diferentes. Portanto, a operação produto cartesiano é não-comutativa. - Os conjuntos )( e )( CBACBA ×××× são diferentes, pois as componentes de cada par ordenado são distintas. Logo, a operação produto cartesiano é não-associativa. Propriedade da Distributividade: O produto cartesiano se distribui sobre a união e sobre a intersecção. a) Distributividade do produto cartesiano sobre a união. A x (B ∪ C) = (A x B) ∪ (A x C) b) Distributividade do produto cartesiano sobre a intersecção. A x (B ∩ C) = (A x B) ∩ (A x C) Reversibilidade: A reversibilidade do produto cartesiano pode ser obtida como: o primeiro operando (respectivamente, o segundo operando) é o conjunto constituído por todos os elementos da primeira (respectivamente, da segunda) componente dos pares do produto cartesiano. Exemplos: Reversibilidade do Produto Cartesiano a) Resultante: {(a,a), (a,b)} Operandos: {a} e {a,b} b) Resultante: {(a,a), (a,b), (b,a), (b,b)} Operandos: {a,b} e {a,b} c) Resultante: {((a,a),0), ((a,a),1), ((a,a), 2), ((a,b),0), ((a,b),1), ((a,b),2)} Operandos: {(a,a), (a,b)} e {0,1,2}. 24 � União Disjunta: tem por finalidade distinguir elementos com uma mesma identificação, ou seja, um tipo de união no qual é garantido que não existem elementos em comum. Sejam A e B conjuntos. A União Disjunta dos conjuntos A e B, denotada por: A + B é com segue: A + B = { (a, A) a ∈ A} ∪ {(b, B) b ∈ B} A + B = {(a, 0) a ∈ A} ∪ {(b,1)b ∈ B} A + B = {aA a ∈ A} ∪ {bB b ∈ B}. Exemplos: a) Suponha os conjuntos Silva={João, Maria, José} e Souza={Pedro, Ana, José}. Então: Silva+Souza={<João, Silva>, <Maria,Silva>,<José, Silva>, <Pedro, Souza>, <Ana, Souza>, <José, Souza>}. b) Suponha os conjuntos D={0,1,2,...,9} V={a, e, i, o ,u} P={0,2,4,6,...} Então: D+V = {0D, 1D, 2D, ..., 9D, aV, eV, iV, oV, uV} D+P ={0D, 1D, 2D, …, 9D, 0P, 2P, 4P, ….}. c) Suponha os conjuntos A={x ∈ N x >2} e B = {x ∈ N x2 = x}. Então: A + B = {0B, 1B, 3A, 4A, 5A, 6A,...}. d) Considere o conjunto A= {a, b, c}. Então: ∅ + ∅ = ∅ A + ∅ = {(a, A), (b, A), (c, A)} A + A = {(a,0), (b,0), (c,0),(a,1),(b,1),(c,1)}. Exemplos: Reversibilidade da União Disjunta Para cada um dos itens abaixo, é apresentado o conjunto resultante de uma união disjunta e os correspondentes operandos originais: a) Resultante: {0D, 1D, 2D, ..., 9D, aV, eV, iV, oV, uV} Operandos: {0,1,2,...,9} e {a, e, i, o u} b) Resultante: {0D, 1D, 2D, ..., 9D, 0N, 1N, 2N, 3N, ...} Operandos: {0,1,2,...,9} e N c) Resultante: ∅ Operandos: ∅ e ∅ d) Resultante: {(a,0), (b,0)} Operandos: {a,b} e ∅ 25 Representação através do Diagrama de Venn. União Intersecção Diferença 3.3 Relação entre lógica e Álgebra de Conjuntos Atenção para a relação direta entre os conetivos lógicos e as operações sobre conjuntos: Conetivo Lógico Operação sobre Conjuntos Negação Complemento Disjunção União Conjunção Intersecção Adicionalmente, as relações lógicas introduzidas também podem ser associadas com as relações sobre conjuntos: Relação Lógica Relação sobre Conjuntos implicação Continência equivalência igualdade Observação: A equivalência (respectivamente, igualdade de conjuntos) pode ser definida em termos de uma dupla implicação (respectivamente, dupla continência, ou seja, a “ida” e a “volta”). Conetivo Lógico Operação sobre Conjuntos Idempotência: ∧ e ∨ Idempotência: intersecção e união Comutativa: ∧ e ∨ Comutativa: intersecção e união Associativa: ∧ e ∨ Associativa: intersecção e união Distributiva: ∧ sobre ∨ ∨ sobre ∧ Distributiva: intersecção sobre união União sobre intersecção Dupla negação Duplo complemento DeMorgan DeMorgan Absorção Absorção A B A B A B 26 Propriedade Lógica Teoria dos Conjuntos Idempotência p ∧ p ⇔ p p ∨ p ⇔ p A ∩ A A ∪ A Comutativa p ∧ q ⇔ q ∧ p p ∨ q ⇔ q ∨ p A ∩ B = B ∩ A A ∪ B = B ∪ A Associativa p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r A ∩ (B ∩ C) = (A ∩B) ∩ C A ∪ (B ∪ C) = (A ∪B) ∪ C Distributiva p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p∧ r) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p∨ r) A ∩ (B ∪ C) = (A ∩B)∪ (A∩ C) A ∪ (B ∩ C) = (A ∪B)∩(A ∪ C) Negação/Complemento ¬¬ p ⇔ p p∧ ¬p ⇔ F p∨ ¬p ⇔ V ~~A = A A ∩ ~A = ∅ A ∪ ~A = U DeMorgan ¬(p ∨ q) ⇔ ¬p ∧ ¬q ¬(p ∧ q) ⇔ ¬p ∨ ¬q ~(A ∪ B) = ~A ∩ ~B ~(A ∩ B) = ~A ∪ ~B Elemento Neutro p ∧ V ⇔ p p ∨ F ⇔ p A ∩ U = A A ∪ ∅ = A Elemento absorvente p ∧ F ⇔ F p ∨ V ⇔ V A ∩ ∅ = ∅ A ∪ U = U Absorção p ∧ (p ∨ q) ⇔ p p ∨ (p ∧ q) ⇔ p A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A
Compartilhar