Prévia do material em texto
1 MATEMÁTICA DISCRETA PROFA. THILENE FALCÃO LUIZ UEZO 2 EMENTA 1 TEORIA DOS CONJUNTOS 1.1 RELAÇÃO DE PERTINÊNCIA 1.2 ALGUNS CONJUNTOS IMPORTANTES 1.3 RELAÇÃO DE INCLUSÃO 1.4 IGUALDADE DE CONJUNTOS 1.5 PERTINÊNCIA X INCLUSÃO 2 INTRODUÇÃO À LÓGICA MATEMÁTICA 2.1 PROPOSIÇÕES E CONECTIVOS LÓGICOS 2.2 OPERAÇÕES LÓGICAS SOBRE PROPOSIÇÕES 2.3 CONSTRUÇÃO DE TABELAS-VERDADE 2.4 TAUTOLOGIAS, CONTRADIÇÒES E CONTINGÊNCIAS 2.5 EQUIVALÊNCIA LÓGICA 2.6 ÁLGEBRA DAS PROPOSIÇÕES 2.7 MÉTODO DEDUTIVO 2.8 QUANTIFICADORES 3 ÁLGEBRA DE CONJUNTOS 3.1 OPERAÇÃO DE UNIÃO 3.2 OPERAÇÃO DE INTERSEÇÃO 3.3 OPERAÇÃO COMPLEMENTO 3.3.1 Propriedades de DeMorgan 3.4 OPERAÇÃO DE DIFERENÇA 3.5 CONJUNTO DAS PARTES 3.6 PRODUTO CARTESIANO 3.7 UNIÃO DISJUNTA 4 RELAÇÕES 4.1 RELAÇÃO BINÁRIA 4.2 ENDORRELAÇÃO COMO GRAFO 4.3 RELAÇÃO COMO MATRIZ 4.4 PROPRIEDADES DAS RELAÇÕES 4.5 FECHOS DE RELAÇÕES 4.6 RELAÇÃO DE ORDEM 3 4.7 RELAÇÃO DE EQUIVALÊNCIA 4.8 RELAÇÃO INVERSA 4.9 COMPOSIÇÃO DE RELAÇÕES 5 TIPOS DE RELAÇÕES 5.1 RELAÇÃO FUNCIONAL 5.2 RELAÇÃO INJETORA 5.3 RELAÇÃO TOTAL 5.4 RELAÇÃO SOBREJETORA 5.5 MONOMORFISMO 5.6 EPIMORFISMO 5.7 ISOMORFISMO 6 FUNÇÕES PARCIAIS E TOTAIS 6.1 FUNÇÀO PARCIAL 6.2 FUNÇÃO TOTAL Referências: 1) P. B. Menezes, Matemática Discreta para Computação e Informática, Sagra. 2) E. A. Filho, Iniciação à Lógica Matemática, Nobel. 3) S. Lipschtz e M. Lipson, Matemática Discreta, Coleção Schaum, Bookman. 4) E. R. Scheinerman, Matemática Discreta: Uma Introdução, Cengage Learning. 4 INTRODUÇÃO Esta disciplina tem como objetivo principal apresentar e desenvolver conceitos fundamentais da lógica matemática que servirão como ferramenta no emprego de linguagem de programação. A disciplina contém uma seleção de tópicos de Matemática os quais são essenciais para o estudo de Computação e Informática. Tal seleção é comumente chamada de Matemática Discreta. Inicialmente, relembraremos sobre a teoria dos conjuntos e suas relações. 1 - TEORIA DOS CONJUNTOS Definição de Conjunto: um conjunto é uma coleção de zero ou mais objetos distintos, chamados elementos do conjunto, os quais não possuem qualquer ordem associada. Em outras palavras, é uma coleção não-ordenada de objetos. Exemplo: A = {branco, azul, amarelo} Em um conjunto, a ordem dos elementos não importa e cada elemento deve ser listado apenas uma vez. Podemos definir um conjunto de diferentes formas: Denotação por Extensão: os elementos são listados exaustivamente. Separados por vírgulas e entre chaves. Exemplo: Vogais = {a, e, i, o, u} Denotação por Compreensão: definição de um conjunto por propriedades comuns aos objetos. De forma geral, escreve-se {x | P(x)}, onde P(x) representa a propriedade. Exemplo: Pares = {n | n é par}, que representa o conjunto de todos os elementos n, tal que n é um número par. Ainda podemos especificar um conjunto omitindo alguns elementos que estão implícitos na notação adotada. Veja exemplos: Dígitos = {0, 1, 2, 3, ..., 9} Pares = {0, 2, 4, 6, ...} 5 1.1 - Relação de Pertinência Se a é elemento de um conjunto A, então podemos escrever: a A e dizemos que a pertence ao conjunto A. Se a não é elemento de um conjunto A, então podemos escrever: a A e dizemos que a não pertence ao conjunto A. Exemplo: Considerando o conjunto Vogais = {a, e, i, o, u}, podemos dizer que: - e Vogais - m Vogais Considerando o conjunto B = {x | x é brasileiro}, temos que: - Pelé B - Bill Gates B 1.2 - Alguns Conjuntos Importantes O Conjunto Vazio é um conjunto que não possui elementos e pode ser denotado por ou { }. O Conjunto Unitário é um conjunto constituído por um único elemento. Ainda temos: - N, que representa o conjunto dos números naturais; - Z, que representa o conjunto dos números inteiros; - Q, que representa o conjunto dos números racionais; - I, que representa o conjunto dos números irracionais; - R, que representa o conjunto dos números reais; - C, que representa o conjunto dos números complexos. Definição de Alfabeto: um alfabeto é um conjunto finito, ou seja, um conjunto que pode ser denotado por extensão. Os elementos de um alfabeto são chamados de símbolos ou caracteres. 6 Definição de Palavra: uma palavra sobre um alfabeto é uma seqüência finita de símbolos do alfabeto, justapostos. significa palavra vazia significa alfabeto * significa conjunto de todas as palavras possíveis sobre o alfabeto Exemplos: - é um alfabeto; - {a, b, c, d} é um alfabeto; - N não é um alfabeto; - a, e, i, o ,u, ai, ou, ei, aeiou são exemplos de palavras sobre VOGAIS; Aplicações na Computação Chamamos de Linguagem Formal a um conjunto de palavras sobre um alfabeto. Portanto, podemos entender que uma linguagem de programação é o conjunto de todos os seus possíveis programas e que um programa é uma palavra da linguagem de programação. 1.3 - Relação de Inclusão Se todos os elementos de um conjunto A são também elementos de um conjunto B, então dizemos que: A B (A está contido em B) ou que B A (B contém A) Neste caso, podemos dizer que A é um subconjunto de B. Por outro lado, se A B e A B, ou seja, existe bB tal que bA, então dizemos que: A B (contido propriamente) ou que B A (contém propriamente) Neste caso, dizemos que A é um subconjunto próprio de B. 7 Exemplos: - {1, 2, 3} {3, 2, 1} - {1, 2} {1, 2, 3} ou {1, 2} {1, 2, 3} Definição de Conjunto Universo: denotado por U, é o conjunto que contém todos os conjuntos que estão sendo considerados, ou seja, define o contexto de discussão. Dessa forma, U não é um conjunto fixo e, para qualquer conjunto A, temos que A U. 1.4 - Igualdade de Conjuntos Dois conjuntos A e B são ditos iguais se, e somente se, possuem os mesmos elementos, ou seja: A B A B eB A Exemplos: - 0,1,2x x 0 ex 3 - x x 0 - {a, b, c} = {a, b, b, c, c, c} (não importa se houver repetições) 1.5 - Pertinência x Inclusão Os elementos de um conjunto podem ser conjuntos. Portanto, preste atenção nos conceitos de pertinência e inclusão. Exemplos: Considere o conjunto S = {a, b, c, d, , {0}, {1, 2}}. Então: - {a} S mas, a S - {a} S - S ou S - {0} S - {1,2} S - {a, b, c, d} S - {a, b, c, d} S 8 2 – INTRODUÇÃO À LÓGICA MATEMÁTICA 2.1 – Proposições e Conectivos: 2.1.1. Conceito de proposição: Def.: Chama-se sentença ou proposição todo conjunto de palavras ou símbolos que exprimem um pensamentode sentido completo. As proposições são geralmente representadas por letras minúsculas p, q, r, s... Toda proposição apresenta duas características obrigatórias: 1ª) Sendo oração tem sujeito e predicado. 2ª) É declarativa (não é exclamativa, nem interrogativa). A Lógica Matemática adota como regras fundamentais os dois seguintes princípios (ou axiomas): Princípio da não contradição: uma proposição não pode ser verdadeira e falsa ao mesmo tempo. Princípio do terceiro excluído: toda proposição ou é verdadeira o é falsa (isto é, só observamos um desses casos, nunca um terceiro). Ex: A lua é um satélite da Terra (V) Recife é a capital de Pernambuco (V) Z R (V) Não são consideradas proposições: 3 . 5 + 1 (falta o predicado) ?2 Q (pois é interrogativa) 3x – 1 = 12 (pois não pode ser classificada em verdadeira ou falsa). 2.1.2. Valores lógicos das proposições: Def.: Chama-se valores lógicos de uma proposição p a verdade se p é verdadeira e a falsidade se p é falsa. Os valores lógicos verdade ou falsidade são representados por V ou F, ou também por 1 e 0 respectivamente. Toda proposição tem um e somente um valor lógico V ou F. 2.1.3. Proposições simples e Proposições compostas: As proposições classificam-se em proposições simples ou composta. Def.1: Chama-se proposição simples aquela proposição que não contém nenhuma outra proposição como parte integrante (ou seja, nos da apenas uma informação). Def.2: Chama-se proposição composta aquela que é formada pela combinação de duas ou mais proposições. Ex: p: Carlos é alto. (prop. simples) q: Pedro é baixo. (prop. simples) r: Carlos é alto e Pedro é baixo. (prop. composta) 9 s: Carlos é alto ou Pedro é baixo. (prop. composta) 2.1.4 Conectivos: Def.: Chamamos de conectivos, palavras que se usam para formar novas proposições a partir de outras. Alguns Conectivos: “… e …” (conjunção) “… ou …” (disjunção) “se … então …” (condicional) “... se e somente se ...” (bicondicional) “não” (negação) 2.1.5. Tabela-verdade: O valor lógico de uma proposição composta depende dos valores lógicos das proposições componentes, e se determina por um dispositivo denominado tabela-verdade na qual constam todos os possíveis valores lógicos da proposição composta correspondentes a todas as possíveis combinações dos valores lógicos das proposições componentes. Com isso, observe que as possibilidades de uma proposição composta fornecida por p e q são: 1ª p: V q: V 2ª p: V q: F 3ª p: F q: V 4ª p: F q: F 2.2 – Operações Lógicas das Proposições 2.2.1. Negação de uma proposição: Chamamos de negação de uma proposição p, a proposição representada por “não p”, cujo valor lógico é V quando p é F e F quando p é V. Indicamos “não p” por “~p”. Assim podemos montar a tabela-verdade da negação: p ~p V F F V Exemplos: 1) p: 2 + 3 = 5 (V) 2) q : 3 < 4 (V) 3) r : Z Q (V) ~p: 2 + 3 5 (F) ~q : 3 4 (F) ~r : Z Q (F) 2.2.2. Conjunção de duas proposições: Chamamos de conjunção de duas proposições p e q a proposição representada por “p e q”, cujo valor lógico será verdade se as proposições p e q forem ambas verdadeiras e falsidade nos demais casos. Simbolicamente representamos por “p q”. Assim podemos montar a tabela-verdade: 10 p q p q V V F F V F V F V F F F Ex1) p : 2 > 0 (V) Ex2) p : 3 < 5 (V) q : 2 1 (V) q : 3 = 5 (F) p q : 2 > 0 e 2 1 (V) p q : 3 < 5 e 3 = 5 (F) 2.2.3. Disjunção de duas proposições: Chamamos disjunção de duas proposições p e q a proposição representada por “p ou q”, cujo valor lógico será verdade se pelo menos uma das proposições forem verdadeiras, ou seja, só será falsa se p e q forem falsas. Simbolicamente representamos por “p q”. Assim podemos montar a tabela-verdade: p q p q V V F F V F V F V V V F Ex1) p : 2 < 4 (V) Ex2) p : 3 | 4 (F) q : 2 = 4 (F) q : 4 | 10 (F) p q : 2 < 4 ou 2 = 4 (V) p q : 3 | 4 ou 4 | 10 (F) p q : 2 4 (V) 2.2.4. Condicional: Chamamos proposição condicional uma proposição representada por “se p, então q”, cujo valor lógico é a falsidade somente quando p verdadeira implicar q falsa, e verdadeira nos demais casos. Simbolicamente, a condicional de p e q: “se p então q” é representado “p q”, que se lê também: 1) p implica q; 2) p somente se q; 3) p é suficiente para q; 4) q é necessário para p; 11 Assim podemos montar a tabela-verdade: p q p q V V F F V F V F V F V V 2.2.5. Bicondicional: Chamamos proposição bicondicional uma proposição representada “p se e somente se q”, cujo valor lógico é verdade quando p e q são ambas verdadeiras ou ambas falsas. Simbolicamente representamos por “pq” que se lê também: 1) p é equivalente a q; 2) p é condição necessária e suficiente para q; 3) q é condição necessária e suficiente para p; Assim montamos a tabela-verdade: p q p q V V F F V F V F V F F V 2.2.6. Disjunção Exclusiva Na linguagem comum a palavra “ou” tem dois sentidos. Considere os exemplos abaixo: p : Carlos é médico ou professor. q : Mario á alagoano ou gaúcho. Na proposição p pode-se indicar que pelo menos uma das proposições “Carlos é médico”, “Carlos é professor” é verdadeira. Mas na proposição q, pode-se indicar que uma e somente uma das proposições “Mario é alagoano”, “Mario é gaúcho” é verdadeira, pois não é possível ocorrer “Mario é alagoano e gaúcho”. Na proposição p dizemos que “ou” é inclusivo enquanto que, na proposição q, dizemos que “ou” é exclusivo. De um modo geral, chama-se disjunção exclusiva de duas proposições p e q, a proposição representada por “p q” que se lê “ou p ou q” ou “p ou q mas não ambos”, cujo valor lógico é verdade somente quando p é verdadeira ou q é verdadeira, mas quando p e q são ambas verdadeiras ou ambas falsas o valor lógico é a falsidade. 12 Assim, a tabela-verdade de “p q”, é: p q p q V V F F V F V F F V V F 2.3 – Construção de Tabela-verdade de proposições compostas: Dadas várias proposições simples p, q, r, s, ..., podemos combiná-las mediante o uso dos conectivos: ~, , , , , E construir proposições compostas, tais como: (p ^ (~q p)) ^ ~ ((p ~q) (q ~p)) (p (q ~r)) ^ ((~p r) ~q) Então com o emprego das tabelas-verdade das operações lógicas: ~p , p q , p q , p q , p q , p q É possível construir a tabela-verdade de proposições compostas. Exemplos: 1) Construir as tabelas-verdade das proposições abaixo: a) ~(p ~q) b) ~(p q) ~(q p) c) [(p q) (q r)] (p r) d) (p q) (p r) Obs: O número de possibilidades da tabela-verdade de uma proposição composta é igual ao número de arranjos com repetição de classe n dos dois elementos V e F. (Ar) 2,n = 2 n Onde n é o número de proposiçõesque formam a proposição composta. a) ~(p ~q) p q ~q p ~q ~ (p ~q) V V F F V F V F F V F V F V F F V F V V 13 b) ~(p q) ~(q p) p q p q p q ~( p q) ~( p q) ~( p q) ~( p q) V V F F V F V F V F F F V F F V F V V V F V V F F V V V c) [(p q) (q r)] (p r) p q r p q q r (p q) (q r) p r [(p q) (q r)] (p r) V V V V F F F F V V F F V V F F V F V F V F V F V V F F V V V V V F V V V F V V V F F F V F V V V F V F V V V V V V V V V V V V d) (p q) (p r) p q r p q p r (p q) (p r) V V V V F F F F V V F F V V F F V F V F V F V F V V F F F F F F V F V F F F F F V V V F F F F F Outros símbolos para conectivos: “ “ para negação (~) “ “ para conjunção ( ) “ “ para a condicional () 14 2.4 – Tautologias, Contradições e Contingências: 2.4.1. Tautologia (Sentenças logicamente verdadeiras): Chamamos de tautologia toda a proposição composta cuja última coluna de sua tabela-verdade tem somente a letra V. Em outros termos, tautologia é toda proposição cujo valor lógico é V, quaisquer que sejam os valores lógicos das proposições que a compõem. Ex1) A proposição p ~p é uma tautologia, pois: p ~p p ~p V F F V V V Portanto dizer que uma proposição ou é verdadeira ou é falsa é sempre verdadeira (Princípio do terceiro excluído). Ex2) (p ~p) (q p) é uma tautologia. Ex3) p ~(p q) é uma tautologia. Ex4) ~(p ~p) é uma tautologia. Chamamos também as tautologias de Proposições Tautológicas. 2.4.2. Contradições (Sentenças logicamente falsas): Chamamos de contradição toda proposição cuja última coluna de sua tabela-verdade tem somente a letra F. Em outros termos, contradição é toda proposição cujo valor lógico é sempre a falsidade (F), quaisquer que sejam os valores lógicos das proposições que a compõem. Ex1) A proposição p ~p é uma contradição. Ex2) (p q) ~(p q) é uma contradição. 2.4.3. Contingência: Chamamos de contingência toda proposição composta que na última coluna de sua tabela-verdade tenham valores V e F pelo menos uma vez cada. Ou seja, contingência são proposições que não são tautologias e nem contradições, chamada também de proposições indeterminadas. 15 Ex1: “x = 3 (x y x 3)” é uma contingência. x = 3 x = y x y x 3 x y x 3 x = 3 (x y x 3) V V F F V F V F F V F V F F V V V F V V V F F F 2.5 – Implicação Lógica: 2.5.1. Implicação Lógica: Dizemos que uma proposição p implica logicamente ou apenas implica uma proposição q, se q é verdadeira todas as vezes que p é verdadeira, ou seja, não ocorre p e q com valores lógicos simultâneos respectivamente V e F, em nenhuma linha da tabela-verdade. Em particular toda tautologia implica uma tautologia e somente uma contradição implica uma contradição. Implicamos a implicação como: p q. Propriedades da Implicação Lógica: 1) Reflexiva: p p; 2) Transitiva: Se p q e q r então p r Exemplos: 1) p q ; p q ; p q p q p q p q p q V V F F V F V F V F F F V V V F V F F V p q p q e p q p q Regras de Inferência: i) p p q e q p q (adição) ii) p q p e p q q (simplificação) 2) p q , p q, q p p q p q p q q p V V F F V F V F V F F V V F V V V V F V p q p q e p q q p 16 3) (p q) ~p (p q) ~p q (Regra de Silogismo Disjuntivo) (p q) ~q p p q ~p p q (p q) ~p V V F F V F V F F F V V V V V F F F V F 4) (p q) p (p q) p q (Regra de Modus Ponens) 5) (p q) ~q e ~p (p q) ~q ~p (Regra de Modus Tollens) Tautologias e Implicação Lógica: Teorema: A proposição p implica a proposição q, isto é, p q se e somente se a condicional p q é tautológica. Obs.: Os símbolos e são distintos, pois é de operação lógica e é de relação lógica. Ex1) [(p q) (q r)] (p r) é uma tautologia. Assim temos: (p q) (q r) (p r) Ex2) [(p q) p] q é uma tautologia. Assim temos: (p q) p q 2.6 – Equivalência lógica 2.6.1. Equivalência lógica: Duas proposições p e q dizem-se logicamente equivalente ou simplesmente equivalente, se têm tabelas-verdade idênticas. Indicamos a equivalência como p q. Em particular se p e q são ambas tautologias ou são ambas contradições, então são equivalentes. Propriedades da Equivalência Lógica: 1) Reflexiva: p p 2) Simétrica: Se p q então q p 3) Transitiva: Se p q e q r então p r. 17 Exemplos: 1) ~~p p (Regra da dupla negação) 2) p p q p q (Regra da absorção) 3) p q ~p q 4) p q (p q) (q p) 5) p q (p q) (~p ~q) 6) ~(p q) ~p ~q (Regra de De Morgan) 7) ~(p q) ~p ~q (Regra de De Morgan) Tautologias e Equivalência Lógica: Teorema: A proposição p é equivalente a proposição q, isto é, p q, se e somente se a bicondicional , p q é tautológica. Exemplos: 1) (p ~q c) (p q) é uma tautologia, onde c tem valor lógico F. Assim: p ~q c p q p q c ~q p ~q p ~q c p q (p ~q c) (p q) V V F F V F V F F F F F F V F V F V F F V F V V V F V V V V V V 2) p q r p (q r) p q r p q p q r q r p (q r) V V V V F F F F V V F F V V F F V F V F V F V F V V F F F F F F V F V V V V V V V F V V V F V V V F V V V V V V 18 3) x = 1 x3 não é equivalente a ~(x < 3 x =1). 2.6.2. Proposições Associadas a uma Condicional: Dada a condicional p q, chama-se proposições associadas a p q as seguintes proposições: 1) Proposição Recíproca de p q: 2) Proposição Contrária de p q: 3) Proposição Contrapositiva de p q: Ex1) 1) p q ~q ~p 2) q p ~p ~q Ou seja, a condicional é equivalente a sua contrapositiva. Exemplos: 1) Seja T um triângulo: p q: Se T é equilátero então T é isósceles, é verdadeira. A recíproca q p:Se T é isósceles então T é eqüilátero é falsa. 2) Achar a contrapositiva da condiconal: “Se x é menor que zero, então x não é positivo”. Sejam as proposições: p: x é menor que zero. q: x é positivo A condicional na forma simbólica é: p ~q, e assim a sua contrapositiva será: ~~q ~p q ~p “Se x é positivo então é maior ou igual a zero” ou “Se x é positivo então x não é menor que zero”. 2.6.3. Negação Conjunta de duas Proposições: Def.: Chama-se negação conjunta de duas proposições p e q a proposição: q p ~p ~q ~q ~p 19 “não p e não q” simbolicamente “~p ~q” A negação conjunta de duas proposições é indicada pela notação “p q” é: p q p q p q ~p ~q ~p ~q ~p ~q V V F F V F V F F F F V V V F F V F V F F F V V F V F V F F F V F V V V p q ~p ~q 2.6.4. Negação Disjunta de duas Proposições: Def.: Chama-se negação disjunta de duas proposições p e q a proposição “não p ou não q”, simbolicamente “~p ~q”. A negação disjunta de duas proposições é indicada pela notação “p q”. Assim a tabela-verdade de p q é: p q p q V V F F V F V F F V V V p q ~p ~q Obs.: Os conectivos “ ” e “ ”, são chamados conectivos de SCHEFFER. 20 2.7 – Álgebra das Proposições Seja p, q e r proposições simples e t e c proposições simples também com valores lógicos V e F respectivamente. 2.7.1. Propriedades da Conjunção: a) Idempotente p p p b) Comutativa p q q p c) Associativa p (q r) (p q) r d) Identidade p t p (t é o elemento neutro) p c c (c é elemento absorvente) 2.7.2 Propriedades da Disjunção: e) Idempotente p p p f) Comutativa p q q p g) Associativa p (q r) (p q) r h) Identidade p t t (t é o elemento absorvente) p c p (c é o elemento neutro) Verificação: t = V c = F p t p p c c p t p t p c p c V F V V V F V F F F F F 21 p t t p c p p t p t p c p c V F V V V V V F F F V F 2.7.3 Propriedades da Conjunção e da Disjunção: i) Distributiva p (q r) (p q) (p r) p (q r) (p q) (p r) j) Absorção p (p q) p p (p q) p p q p q p (p q) p q p (p q) V V F F V F V F V V V F V V F F V F F F V V F F k) Regras de DeMorgan ~ (p q) ~p ~q ~ (p q) ~p ~q Ex.1: pq: Ele é médico e professor. ~ (p q): Ele não é médico ou não é professor. p q: Ele é médico ou é professor. ~ (p q): Ele não médico e não é professor. Ex.2: p: m.m.c (2 ,3) = 6 ou 2 . 3 = 6 ~p: m.m.c (2 , 3) 6 e 2 .3 6 22 Assim as regras de DeMorgan afirmam: 1) Negar que 02 (duas) proposições são ao mesmo tempo verdadeiras equivale afirmar que pelo menos 01 (uma) é falsa; 2) Negar que pelo menos 01 (uma) de 02 (duas) proposições é verdadeira equivale a afirmar que ambas são falsas. Obs: As regras de De Morgan dizem que é possível exprimir a conjunção e a disjunção como: ~ (~ ~ ) ~ (~ ~ ) p q p q p q p q 2.7.4 Negação da Condicional: Como ~p q p q , temos: ~ ( ) ~ (~ )p q p q ~~ ~p q Ou seja: 2.7.5 Negação da Bicondicional: Como ( ) ( )p q p q q p , temos: ~ ( ) ~ (( ) ( ))p q p q q p ~ ( ) ~ ( ) ~ ( )p q p q q p . Ou seja: ~ ( )p q ~p q ~ ( ) ( ~ ) ( ~ )p q p q q p 23 2.8 – Método Dedutivo Até aqui todas as implicações e equivalências foram demonstradas através das Tabelas-verdade. Agora vamos conhecer um método para fazer estas demonstrações mais eficiente, chamado “Método Dedutivo”, neste método é de grande importância as equivalências vistas na “Álgebra das Proposições”. 2.8.1. Algumas equivalências importantes: i) Idempotente p p p p p p ii) Comutativa p q q p p q q p iii) Associativa p (q r) (p q) r p (q r) (p q) r iv) Identidade p t p p t t t - verdadeiro p c c p c p c – falso v) Regras de DeMorgan ~ (p q) ~p ~q ~ (p q) ~p ~q ~ (~ ~ ) ~ (~ ~ ) p q p q p q p q vi) p q ~p ~q p q ~p ~q vii) ~p q p q 24 viii) Distributiva p (q r) (p q) (p r) p (q r) (p q) (p r) ix) Absorção p (p q) p p (p q) p Exemplos: Utilizando o Método Dedutivo, prove as implicações e as equivalências abaixo: 1) c p p t (onde c é Falsidade e t é Verdadeiro) 2) p q p (Simplificação) 3) p p q (Adição) 4) ( )p q p q (Modus Ponens) 5) ( ) ~ ~p q q p (Modus Tollens) 6) ( ) ~p q p q (Silogismo Disjuntivo) 7) p q p q 8) p q p 9) ~p p q 10) ( )p q p r q 11) ~p q p q c c = falso 12) ( )p q p q q 13) ( ) ( ~ ) ~p q p q p 14) ( )p q r p q r 15) ( ) ( ) ( )p r q r p q r 16) ( ) ( ) ( )p q p r p q r 17) ( ) ( ) ( ) ( )p r q s p q r s 18) ~ p p p 19) ( ) ( )p q p p q q 20) ( ) ( )p q p q p q 25 21) (( ) ) (( ) )p q p p q p p q 22) ~ p p p 23) ( ) ( )p q p q p q 24) ( ) ( )p q p p q q 25) ( )p q p q q 2.8.2. Redução do Número de Conectivos Teorema: Entre os cinco conectivos fundamentais (~, , , , ) três exprimem-se em termos de apenas dois dos pares: (1) ~ e (2) ~ e (3) ~ e Dem: (1) , , exprimem-se em termos de ~ e ~~ ~~ ~ (~ ~ )p q p q p q ~p q p q ( ) ( ) (~ ) (~ )p q p q q p p q q p ~ (~ (~ ) ~ (~ ))p q q p (2) , , exprimem-se em termos de ~ e ~~ ~~ ~ (~ ~ )p q p q p q ~p q p q ~ ( ~ )p q ( ) ( ) ~ ( ~ ) ~ ( ~ )p q p q q p p q q p (3) , , exprimem-se em termos de ~ e ~ (~ ~ ) ~ ( ~ )p q p q p q ~~ ~p q p q p q ( ) ( ) ~ (( ) ~ ( ))p q p q q p p q q p Obs: 1) Os conectivos , , exprimem-se em termos de ~ e . 2) O conectivo exprime-seem função de unicamente por ( )p q p q q . 3) Todos os conectivos exprimem-se em termos de um único: ou . 26 2.8.3. Forma Normal das Proposições Def: dizemos que uma proposição está na Forma Normal (FN) se e somente se, quando muito, contém os conectivos ~, , . Ex: Estão na Forma Normal (FN) as seguintes proposições: ~ ~p q ; ~ (~ ~ )p q ; ( ) (~ )p q q r Toda proposição pode ser levada para uma FN equivalente pela eliminação dos conectivos e , pelas substituições: ~p q p q (~ ) (~ )p q p q q p Existem duas espécies de FN Forma Normal Conjuntiva Forma Normal Disjuntiva Forma Normal Conjuntiva e Forma Normal Disjuntiva Dizemos que uma proposição está na Forma Normal Conjuntiva (FNC) e na forma Normal Disjuntiva (FND), se e somente se, são verificadas as condições: 1) Contém, quando muito, os conectivos ~, e . 2) ~ não aparece repetido (como ~ ~) 3) ~ não tem alcance sobre e (só incide sobre proposições) E mais: - Para ser uma FNC: não tem alcance sobre , ou seja, não podemos ter componentes do tipo ( )p q r . - Para ser uma FND: não tem alcance sobre , ou seja, não podemos ter componentes do tipo ( )p q r . 27 Para podermos determinar uma FNC ou uma FND de qualquer proposição, fazemos as seguintes transformações: 1) eliminamos e com as equivalências: ~ (~ ) (~ ) p q p q p q p q q p 2) eliminamos negações repetidas pela regra da dupla negação ~~ p p 3) eliminamos parênteses precedidos de ~ utilizando as Regras de De Morgan ~ (pq) ~p ~q ~ (p q) ~p ~q 4) eliminamos proposições dos tipos ( )p q r e ( )p q r utilizando a propriedade distributiva p (q r) (p q) (p r) p (q r) (p q) (p r) 2.9 - Quantificadores As sentenças formadas apenas pelos cinco operadores lógicos () têm possibilidade limitada de expressões. Por exemplo, não conseguiríamos simbolizar a sentença "Para todo x, x > 0" como sendo uma proposição verdadeira sobre os inteiros positivos. Portanto novos conceitos, como o de quantificador, deve ser introduzido. Quantificadores são frases do tipo para todo, para cada ou para algum, isto é, frases que dizem "quantos objetos" apresentam determinada propriedade. Quantificador Universal: é simbolizado por e lê-se para todo, para qualquer ou para cada. Assim, a sentença acima pode ser simbolizada por: O valor lógico da expressão (x)(x > 0) depende do domínio dos objetos sobre os quais estamos nos referindo, que chamamos de conjunto universo. Qual seria o valor lógico da expressão (x)P(x) em cada uma das seguintes interpretações? - P(x) é a propriedade que x é amarelo e o conjunto universo é o conjunto de todos os botões de ouro. 28 - P(x) é a propriedade que x é amarelo e o conjunto universo é o conjunto de todas as flores. - P(x) é a propriedade que x é positivo ou negativo e o conjunto universo é conjunto de todos os inteiros. Quantificador Existencial: é simbolizado por e lê-se existe, existe algum, para pelo menos um, para algum. Assim, a expressão pode ser lida como "existe um x tal que x é maior do que zero". A expressão (x)(y)Q(x, y) é lida como "para todo x existe um y tal que Q(x, y)". Considerando que o conjunto universo é conjuntos dos números inteiros e que Q(x, y) é a propriedade x < y, a expressão diz que para todo inteiro x existe um inteiro maior. Esta expressão é verdadeira. Entretanto, se invertermos a ordem dos quantificadores escrevendo (y)(x)Q(x, y), a mesma interpretação diz que existe um inteiro y que é maior que qualquer outro inteiro x. Neste caso, o valor lógico da expressão é falso. Isto ressalta o fato de que a ordem dos quantificadores é importante! 29 3 - ÁLGEBRA DE CONJUNTOS Entendemos que uma álgebra é constituída de operações definidas sobre um conjunto. Dessa forma, uma Álgebra de Conjuntos é constituída por operações definidas para todos os conjuntos. Podemos representar conjuntos e suas operações através de figuras geométricas, como elipses e retângulos, chamados Diagramas de Venn. Usualmente, os retângulos são utilizados para representar o conjunto universo e as elipses para representar os demais conjuntos. Por exemplo, as figuras abaixo representam: A relação de inclusão é transitiva, ou seja: Prova: Suponha A, B e C conjuntos quaisquer tal que A B e B C. Seja a A. Então, temos que a A a B pela definição de subconjunto (A B) a C pela definição de subconjunto (B C) Logo, para qualquer elemento a A , temos que a C. Assim, pela definição de subconjunto, temos que A C. 30 3.1 Operação de União Sejam A e B conjuntos. A união dos conjuntos A e B, denotada por A B , é como segue: Em outras palavras, a união de dois conjuntos A e B considera todos os elementos que pertencem ao conjunto A ou ao conjunto B, ou seja, resulta em um conjunto cujos elementos pertencem a pelo menos um dos dois conjuntos. A operação de união pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. Exemplos: - Dados os conjuntos D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} e V = {a, e, i, o, u}, temos que D V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, e, i, o, u} - Dados os conjuntos A = {x | x > 2} e B = { x | x 2 = x}, temos que A B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...} - Considere R, Q e I. Temos que R Q = R R I = R Q I = R - Para qualquer conjunto universo U e qualquer A U, temos que = U = U U A = U U U = U 3.1.1 - Propriedades da União Elemento Neutro: A = A = A Idempotência: A A = A 31 Comutatividade: A B = B A Associatividade: A (B C) = (A B) C 3.2 - Operação de Interseção Sejam A e B conjuntos. A interseção dos conjuntos A e B, denotada por A B , é como segue: Em outras palavras, a interseção de dois conjuntos A e B considera todos os elementos que pertencem ao conjunto A e ao conjunto B, ou seja, resulta em um conjunto cujos elementos pertencem aos conjuntos A e B, simultaneamente. A operação de interseção pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. Exemplos: - Dados os conjuntos D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, V = {a, e, i, o, u} e P = {0, 2, 4, 6, 8,...}, temos que D P = {0, 2, 4, 6, 8} D V = Chamamos conjuntos cuja interseção é o conjunto vazio de conjuntos disjuntos. - Dados os conjuntos A = {x | x > 2} e B = { x | x 2 = x}, temos que A B = (conjuntos disjuntos) - Considere R, Q e I. Temos que: R Q = Q R I = I Q I = 32 - Para qualquer conjunto universo U e qualquer conjunto A U, temos que = U A = A U = U U = U 3.2.1 - Propriedades da Interseção Elemento Neutro: A U = U A = A Idempotência: A A = A Comutatividade: A B = B A Associatividade: A (B C) = (A B) C Propriedades que envolvem União e Interseção a) Distributividade da Interseção sobre a União: A (B C) = (A B) (A C) b) Distributividade da União sobre a Interseção: A (B C) = (A B) (A C) 3.3 - Operação Complemento Suponha o conjunto universo U. O complemento de um conjunto A U, denotado por ~ A, é como segue: A operação complemento pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. Exemplos: - Dados o conjunto universo U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} e o conjunto A = {0, 1, 2}, temos que ~A = {3, 4, 5, 6, 7, 8, 9} 33 - Dados o conjunto universo U = N e o conjunto A = {0, 1, 2}, temos que ~A = {x N | x > 2} - Para qualquer conjuntos universo U, temos que ~= U ~U = - Considerando R como conjunto universo, temos que ~Q = I ~I = Q - Suponha U qualquer. Então para qualquer conjunto A U, temos que A ~A = U A ~A = ~ ~A = A 3.3.1 - Propriedades de DeMorgan a) ~(A B) = ~A ~B A B = ~(~A ~B) b) ~(A B) = ~A ~B A B = ~(~A ~B) 3.4 - Operação de Diferença Sejam A e B conjuntos. A diferença entre os conjuntos A e B, denotada por A B , é como segue: Em outras palavras, a diferença entre dois conjuntos A e B considera todos os elementos que pertencem ao conjunto A e que não pertencem ao conjunto B. A operação de diferença pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. 34 Exemplos: - Dados os conjuntos D = {0, 1, 2, 3, 4, 5, 6 ,7 , 8, 9}, V = {a, e, i, o, u} e P = {0, 2, 4, 6, 8,...}, temos que D - V = D D - P = {1, 3, 5, 7, 9} - Dados os conjuntos A = {x N | x > 2} e B = {x N | x = x2}, temos que A - B = {3, 4, 5, 6, 7, ...} B - A = {0, 1} - Dados os conjuntos R, Q e I, temos que R - Q = I R - I = Q Q - I = Q - Para qualquer conjunto universo U e qualquer conjunto A U, temos que - = U - = U U - A = ~A U - U = 3.5 - Conjunto das Partes Dado conjunto A, temos que: - A A - A - Se x A, então {x} A A operação unária, que aplicada a um conjunto A, resulta num conjunto constituído de todos os subconjuntos de A é denominada conjunto das partes de A e é denotada por: Exemplo: Dados os conjuntos A = {a}, B = {a, b} e C = {a, b, c}, temos que - P() = {} - P(A) = {, {a}} - P(B) = {, {a}, {b}, {a, b}} - P(C) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} Se o número de elementos de um conjunto X é n, então o números de elementos de P(X) é 2 n . 35 3.6 - Produto Cartesiano Antes de definirmos a operação produto cartesiano, vamos definir uma seqüência: uma seqüência de n elementos é definida como sendo uma n-upla ordenada, ou seja, n objetos em ordem fixa. Particularmente, dizemos que uma 2-upla é uma par ordenado e é representada por x, y ou x, y. Observação: A ordem dos elementos é importante! Logo, x, y y, x . Sejam A e B conjuntos. O produto cartesiano de A por B é como segue: Denotamos o produto cartesiano de um conjunto A por ele mesmo como AA A 2 . Exemplos: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que: Observações: - Não-comutatividade: A C C A - Não-associatividade: A BC A B C 36 Propriedades que envolvem Produto Cartesiano, União e Interseção a) Distributividade sobre a União: A B CA BA C b) Distributividade sobre a Interseção: A B CA BA C 3.7 União Disjunta Sejam A e B conjuntos. A união disjunta dos conjuntos A e B, denotada por A B , é como segue: onde os pares ordenados representam elemento,identificação . Também podemos denotar a união disjunta da seguinte forma: Exemplos: Dados os conjuntos D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, V = {a, e, i, o, u}, P = {0, 2, 4, 6,...} e A = {a, b, c}, temos que: 37 4 - RELAÇÕES 4.1 Relação Binária Dados dois conjuntos A e B, uma relação binária R de A em B é um subconjunto de um produto cartesiano AB , ou seja R AB , onde: - A é o domínio, origem ou conjunto de partida de R; - B é o contra-domínio, destino ou conjunto de chegada de R. Para R AB , se a,b R , então afirmamos que "a relaciona-se com b". Podemos denotar uma relação R da seguinte forma: R : AB e, para um elemento a,b R , podemos denotá-lo como aRb. Exemplos: Sejam A = {a}, B = {a, b} e C = {0, 1, 2}. São exemplos de relações: - é uma relação de A em B; - AB a, a > , < a, b > é uma relação de A em B; - Relação de Igualdade de A em A: a, a > - Relação "menor" de C em C: 0,1 > , < 0,2 > , < 1,2 > - Relação de C em B: 0, a > , < 1,b > - : P(B) P(B); - : C C; - : AA. Endorrelação ou Auto-Relação: dado um conjunto A, uma relação do tipo R : AA é dita uma Endorrelação ou Auto-Relação. Assim, temos que origem e destino são o mesmo conjunto e podemos denota-la por < A, R >. Exemplos: Seja A um conjunto. Então, são endorrelações: - < , - < , - < Q, - < P(A), - < P(R), 38 Uma relação binária pode ser representada no diagrama de Venn, como mostram as figuras abaixo. A seguir, algumas definições referentes ao conceito de relação: a) < a,b > R : dizemos que R está definida para a e que b é a imagem de a. b) Domínio de definição: é o conjunto de todos os elementos de A para os quais R está definida. c) Conjunto imagem: conjunto de todos os elementos de B que estão relacionados com algum elemento de A. Exemplos: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que: - para a endorelação < C,, o domínio de definição é o conjunto {0, 1} e o conjunto imagem é o conjuto {1, 2}; - para a relação : AB , o domínio de definição é o conjunto {a} e o conjunto imagem também é o conjunto {a}. 4.2 Endorrelação como Grafo Toda endorrelação R : AA pode ser representada como um grafo, onde: a) cada elemento do conjunto A é representado como um nodo do grafo; b) cada par < a,b > da relação é representada como uma aresta do grafo, com origem em a e destino em b. Exemplos: 39 4.3 Relação como Matriz Sejam A = {a1, a2, ..., an} e B = {b1, b2, ..., bm} dois conjuntos finitos. A representação da relação R : AB como matriz é como segue: a) o número de linhas é n (número de elementos do domínio); b) o número de colunas é m(número de elementos da imagem); c) a matriz resultante possui m x n células; d) cada uma das m x n células possuem um valor lógico associado; e) se < ai, bi > R, então a posição determinada pela linha i e pela coluna j da matriz contém valor verdadeiro (1); caso contrário, seu valor será falso (0). Exemplo: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que: 40 4.4 Propriedades das Relações Uma endorrelação binária em um conjunto A pode ter determinadas propriedades. A seguir serão apresentadas as propriedades que envolvem as endorrelações. 4.4.1 Relação Reflexiva Sejam A um conjunto e R uma endorrelação em A. R é uma relação reflexiva se: A negação da propriedade reflexiva é como segue: Exemplos: Dado o conjunto A = {0, 1, 2}, temos que as seguintes relações são reflexivas - < ,, pois todo elemento é igual a si mesmo; - < P(A),, pois todo conjunto está contido em si mesmo; - A2 : AA, pois esta relação contém os pares < 0,0 > , < 1,1 > e < 2,2 >; - < A,, pois todo elemento é igual a si mesmo. A matriz e o grafo de uma relação reflexiva apresentam uma característica especial: a diagonal principal da matriz contém somente valores lógicos verdadeiro (1) e qualquer nodo do grafo possui uma aresta com origem e destino nele mesmo. Veja as matrizes e grafos referentes a alguns dos exemplos apresentados acima. 4.4.2 Relação Irreflexiva Sejam A um conjunto e R uma endorrelação em A. R é uma relação irreflexiva se: 41 Exemplos: Dado o conjunto A = {0, 1, 2}, temos que as seguintes relações são irreflexivas: - < ,, pois não elemento diferente de si mesmo; - < P(A),, pois para a relação "está contido propriamente" os conjunto precisam se diferentes; - : A A, pois não há nenhum elemento do tipo a,a; - < A, R > , se R 0,1 , 1,2 , 2,1 , pois não há nenhum elemento do tipo a,a; Exemplo de relação nem reflexiva, nem irreflexiva: - A, S , se S 0,2 , 2,0 , 2,2 A matriz e o grafo de uma relação irreflexiva apresentam uma característica especial: a diagonal principal da matriz contém somente valores lógicos falso (0), e qualquer nodo do grafo não possui aresta com origem e destino nele mesmo. Veja as matrizes e grafos referentes a alguns dos exemplos apresentados acima. 4.4.3 Relação Simétrica Sejam A um conjunto e R uma endorrelação. R é uma relação simétrica se: Exemplos: Dados o conjunto A = {0, 1, 2} e X um conjunto qualquer, temos que as seguintes relações são simétricas. - X 2: X X; - X, - X, - P(X ), - : X X. 44 A matriz e o grafo de uma relação simétrica apresentam uma característica especial: na matriz, a metade acima da diagonal principal é a imagem espelhada da metade de baixo, e, no grafo, entre dois nodos quaisquer, ou não existe aresta, ou existem duas arestas, uma em cada sentido. Veja as matrizes e grafos referentes a alguns dos exemplos apresentados acima. 4.4.4 Relação Anti-Simétrica Sejam A um conjunto e R uma endorrelação em A. R é uma relação anti-simétrica se: Exemplos: Dados o conjunto A = {0, 1, 2} e X um conjunto qualquer, temos que as seguintes relações são anti- simétricas: Exemplo de relação nem simétrica, nem anti-simétrica: A matriz e o grafo de uma relação anti-simétrica apresentam uma característica especial: na matriz, para qualquer célula verdadeira (1) em uma das metades da matriz, a correspondente célula na outra metade é falsa (0); no grafo, entre dois nodos quaisquer, existe no máximo uma aresta. Veja a matriz e o grafo referentes a um dos exemplos apresentado acima. 45 4.4.5 Relação Transitiva Sejam A um conjunto e R uma endorrelação em A. R é uma relação transitiva se: Exemplos: Dado um conjunto X qualquer, temos que as seguintes relações são transitivas: Exemplos: Dado um conjunto X qualquer, temos que as seguintes relações não são transitivas: 4.5 Fechos de Relações Sejam R: A A uma endorrelação e P um conjunto de propriedades. Então, o fecho de R em relação a P é a menor endorrelação em A que contém R e que satisfaz as propriedades de P. Se a relação R já contém as propriedades de P, então ela é a seu próprio fecho em relação a P. 4.5.1 Fecho Reflexivo Suponha R: A A uma endorrelação. Então o fecho reflexivo de R é definido como segue: 46 Exemplo: Dados o conjunto A = {1, 2, 3, 4, 5} e R: A A uma endorrelação, tal que R 1,2 , 1,5 , 2,3 , 3,4 , temos que: 4.5.2 Fecho Simétrico Suponha R: A A uma endorrelação. Então o fecho simétrico de R é definido como segue: Exemplo: Dados o conjunto A = {1, 2, 3, 4, 5} e R: A A uma endorrelação, tal que R 1,2 , 1,5 , 2,3 , 3,4 , temos que: 4.5.3 Fecho Transitivo Suponha R: A A uma endorrelação. Então o fecho transitivo de R é definido como segue: a) se a,b R , então a,b Fecho transitivaR; b) se a,b Fecho transitivaRe b,c Fecho transitivaR, então a,c Fecho transitivaR. Exemplo: Dados o conjunto A = {1, 2, 3, 4, 5} e R: A A uma endorrelação, tal que R 1,2 , 1,5 , 2,3 , 3,4 , temos que: Algumas notações são importantes e podem ser utilizadas para simplificar e representar as seguintes relações: a) R + Fecho transitivaR b) R * Fecho reflexiva,transitivaR 47 Portanto, considerando o exemplo acima, temos que: 4.6 Relação de Ordem Intuitivamente, podemos pensar numa relação de ordem quando lembramos de uma fila no banco, de uma fila de alunos dispostos numa sala de aula, na relação "menor ou igual" no números naturais, etc. Ordem parcial: é toda relação binária em um conjunto A que é, simultaneamente, reflexiva, anti-simétrica e transitiva. São exemplos de relação de ordem parcial: Se R é uma relação de ordem parcial em A, então dizemos que A, R é um conjunto parcialmente ordenado. Se A é um conjunto finito, então podemos representar visualmente um conjunto parcialmente ordenado em A por um diagrama de Hasse. Cada elemento de A é representado por um ponto (vértice) do diagrama. O diagrama de Hasse pode ser construído com base num grafo, onde as arestas que representam as relações reflexivas e transitivas ficam implícitas no diagrama. Veja o exemplo a seguir. Exemplo: Dados o conjunto A = {1, 2, 3} e a relação de ordem A,, temos seus respectivos grafo e diagrama de Hasse representados abaixo. Observe que os elementos da relação são representados no diagrama em ordem crescente de baixo para cima, ou seja, como 1 2, então o elemento 1 aparece abaixo do elemento 2. As orientação das arestas torna-se, dessa forma, desnecessária, já que a disposição dos elementos no diagrama preserva essa informação. Exemplos: - Dada a relação de ordem P1,2,, seu diagrama de Hasse está representado abaixo.48 - Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", o diagrama de Hasse está representado abaixo. - Dado o diagrama de Hasse a seguir, temos que o conjunto dado pela relação de ordem é: 4.6.1 Elemento Mínimo Suponha A um conjunto e A, R uma relação de ordem. Dizemos que m é elemento mínimo de R se 4.6.2 Elemento Minimal Suponha A um conjunto e A, R uma relação de ordem. Dizemos que m é elemento minimal de R se 49 4.6.3 Elemento Máximo Suponha A um conjunto e A, R uma relação de ordem. Dizemos que m é elemento máximo de R se 4.6.4 Elemento Maximal Suponha A um conjunto e A, R uma relação de ordem. Dizemos que m é elemento maximal de R se Exemplo: Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", cujo diagrama de Hasse já foi apresentado anteriormente, temos que: - 1 é elemento mínimo, pois está relacionado com todos os outros elementos de A; - 1 é elemento minimal, pois não há elemento que relaciona-se com ele; - 12 e 18 são elementos maximais, pois não existem elementos com os quais eles relacionam-se; - não há elemento máximo, pois não há elemento que se relaciona com todos os outros elementos de A. Exemplo: Desenhe um diagrama de Hasse para um conjunto parcialmente ordenado com quatro elementos, tais que existam dois elementos minimais, dois elementos maximais, não existam elementos mínimo e máximo e cada elemento está relacionado com dois outros elementos. Um possível diagrama é o apresentado a seguir: 4.7 Relação de Equivalência A relação de equivalência nos dá a noção de igualdade semântica, ou seja, de elementos que apresentam um mesmo significado. Relação de Equivalência: é toda relação binária em um conjunto A que é, simultaneamente, reflexiva, simétrica e transitiva. São exemplos de relações de equivalência: Partição de um Conjunto: uma partição de um conjunto A é um conjunto de subconjuntos disjuntos não-vazios cuja união é igual ao conjunto A. 50 Para visualizar uma partição, suponha um conjunto A = {x /x é aluno de Matemática Discreta} e a relação xRy A, x _ sen ta _ na _ mesma _ fila _ que _ y . Ao agruparmos todos os alunos do conjunto A que estão relacionados entre si, obtemos a figura abaixo. Observe que o conjunto A foi divido em subconjuntos tais que todos os alunos da turma pertencem a um, e somente um, subconjunto. Qualquer relação de equivalência divide o conjunto onde está definida em uma partição. Os subconjuntos que compõem a partição são formados agrupando-se os elementos relacionados, como no caso dos alunos da turma de Matemática Discreta. Classes de Equivalência: se R é uma relação de equivalência em um conjunto A e se a A, denotamos por [a] o conjunto de todos os elementos relacionados a a em A e o chamamos de classe de equivalência de a. Dessa forma, podemos escrever que: Teorema: uma relação de equivalência R em um conjunto A determina uma partição de A e uma partição de A determina uma relação de equivalência em A. Exemplo: Considere o conjunto dos números naturais e a relação de equivalência ," x y _ é _ par" . Tal relação divide o conjunto N em duas partes, ou seja, em duas classes de equivalências. Se x é par, então x + y é par, para todo número par; se x é ímpar, então x + y é ímpar para todo número ímpar. Assim, todos os números pares formam uma classe de equivalência e todos os números ímpares formam uma segunda classe de equivalência. Podemos representar essa partição de N como mostra figura abaixo. Observe que as classes de equivalência podem ser representadas por qualquer objeto pertencente à ela: - classe dos pares: [2] = [6] = [1034] = {0, 2, 4, 6, ...} - classe dos ímpares: [1] = [11] = [2451] = {1, 3, 5, 7, ...} 51 Exemplo: Em A = {1, 2, 3} e R 1,1> , 2,2> , 3,3> , 1,2> , 2,1> As classes de equivalência são as seguintes: [1] = {1, 2} = [2] [3] = {3} 4.7.1 Congruência Considere o conjunto dos números inteiros Z e um número inteiro m 1. Dizemos que x é congruente a y módulo m, denotada por: se x y é divisível por m, ou seja, se x y km para algum inteiro k. 4.8 Relação Inversa Seja uma relação R: A B. Então, a relação inversa é como segue: Exemplos: - Dados os conjuntos A = {a, b} e B = {2, 3, 4} e a relação R : B A 2,a , 3,b , temos que a relação inversa de R, R -1 é dada por R -1 : AB a,2 , b,3 - Dados o conjunto C = {2, 3, 4} e a relação C,, a relação inversa pode ser visualizada no diagrama a seguir: 52 4.9 Composição de Relações Sejam A, B e C conjuntos, e R: A B e S: B C relações. A composição de R e S, denotada por R ᵒ S : AC, é tal que Ou seja, Exemplo: Dados os conjuntos A = {a, b, c, d}, B = {1, 2, 3, 4, 5} e C = {x, y, z} e as relações R : AB a,1 , b,3 , b,4 , d,5 e S : B C 1, x , 2, y , 5, y , 5, z , temos que a composição de R e S é como segue R ᵒ S a, x , d, y , d, z e pode ser visualizada no diagrama a seguir: A composição de relações é associativa, ou seja: Sejam as relações R: A B, S: B C e T: C D. Então, temos que: 4.9.1 Composição de Relações como Produto de Matrizes A composição de relações pode ser vista como o produto de matrizes. Veja o exemplo a seguir. Exemplo: Sejam R e S relações em X = {a, b, c} definidas por R a,b , a,c , b,a e 53 S a,c , b,a , b,b , c,a . Determinaremos a composição de R e S através da multiplicação das correspondentes matrizes. Abaixo, temos as correspondentes matrizes que representam as relações R e S. A multiplicação das matrizes R e S é dada como segue: Assim, temos que a composição R ᵒ S é dada pela matriz R S , ou seja, 54 5 - TIPOS DE RELAÇÕES 5.1 Relação Funcional Uma relação binária R: A B é uma relação funcional se, e somente se: Em outras palavras, temos que para uma relação ser funcional, cada elemento do conjunto origem deve estar relacionado a, no máximo, um elemento do conjunto destino. Exemplo: Dada a relação X 2 : Z Z, tal que X2 x, y > / y x2, temos que, para cada inteiro x, existe no máximo um inteiro y tal que y x 2 . A matriz de uma relação funcional tem uma característica particular: cada linha da matriz pode conter no máximo um valor lógico verdadeiro (1). Podemos também visualizar uma relação funcional no diagrama de Venn. Considerando a relação R: A A, tal que R a,a > , b,c > e A = {a, b, c}, temos que o correspondente diagrama é como segue: Observe que, de fato, cada elemento do conjunto origem está relacionado a, no máximo, um elemento do conjunto destino (o que significa que podem haver elementos da origem não relacionados a algum elemento do destino). 5.2 RelaçãoInjetora Relação injetora é o conceito inverso de relação funcional. Uma relação binária R: A B é uma relação injetora se, e somente se: Em outra palavras, temos que, para um relação ser injetora, cada elemento do conjunto destino deve estar relacionado a, no máximo, um elemento do conjunto origem. 55 A matriz de uma relação injetora tem uma característica particular: existe no máximo um valor lógico verdadeiro (1) em cada coluna. Exemplo: Dada a relação R: A B, tal que A = {1, 2}, B = {1, 2, 3} e R 1,1 , 1,2 , 2,3 , temos que cada elemento de B está relacionado a, no máximo, um elemento de A. Veja a seguir o diagrama que representa a relação R. 5.3 Relação Total Uma relação binária R: A B é uma relação total se, e somente se: Em outras palavras, temos que para uma relação ser total, todos os elementos do conjunto origem devem estar relacionados a algum elemento do conjunto destino. O domínio de definição é o próprio conjunto A. Na matriz de uma relação total, deve existir pelo menos um valor lógico verdadeiro em cada linha. Exemplo: Dada a relação R: A B, tal que A = {1, 2}, B = {1, 2, 3} e R 1,1 > , 2,2 > , 2,3 > , temos que cada elemento de A está relacionado a algum elemento de B. Veja a seguir o diagrama que representa a relação R. 5.4 Relação Sobrejetora Relação sobrejetora é o conceito dual (inverso) de relação total. Uma relação binária R: A B é uma relação sobrejetora se, e somente se: Em outras palavras, temos que para uma relação ser sobrejetora, todos os elementos do conjunto destino devem estar relacionados a algum elemento do conjunto origem. O conjunto imagem é o próprio conjunto B. Na matriz de uma relação sobrejetora, deve existir pelo menos um valor lógico verdadeiro em cada coluna. Exemplo: Dada a relação R: A B, tal que A = {a, b, c}, B = {a, b} e R a,b > , c,a > , 56 temos que cada elemento de B está relacionado a algum elemento de A. Veja a seguir o diagrama que representa a relação R. 5.5 Monomorfismo Uma relação R: A B é um monomorfismo se, e somente se, for simultaneamente uma relação total e injetora. Dessa forma, o domínio de definição é o próprio conjunto A e cada elemento de B está relacionado com no máximo um elemento de A. A matriz de um monomorfismo tem a seguinte característica: existe pelo menos um valor verdadeiro em cada linha da matriz (o que carateriza a relação total) e existe no máximo um valor lógico verdadeiro em cada coluna (o que carateriza a relação injetora). Exemplo: A relação : AB , onde A = {a} e B = {a, b}, é um monomorfismo. 5.6 Epimorfismo Epimorfismo é o conceito inverso de monomorfismo. Uma relação R: A B é um epimorfismo se, e somente se, for simultaneamente uma relação funcional e sobrejetora. Dessa forma, o conjunto imagem é o próprio conjunto B e cada elemento de A está relacionado com no máximo um elemento de B. A matriz de um epimorfismo tem a seguinte característica: existe pelo menos um valor verdadeiro em cada coluna da matriz (o que carateriza a relação sobrejetora) e existe no máximo um valor lógico verdadeiro em cada linha (o que carateriza a relação funcional). Exemplo: São exemplos epimorfismo, sendo que onde A = {a}, B = {a, b} e C = {0, 1, 2}: 57 5.7 Isomorfismo Uma relação R: A B é um isomorfismo se, e somente se, existe uma relação S: B A tal que: R ᵒ S idA R ᵒ S idB onde idA é uma endorrelação de igualdade em A < A,e idB é uma endorrelação de igualdade em B < B,, chamadas de relação identidade. Assim, se R ᵒ S idA e R ᵒ S idB, podemos afirmar que a relação R possui inversa. Ainda, se existe um isomorfismo entre dois conjuntos, podemos chamá-los de conjuntos isomorfos. Exemplo: Dados os conjuntos A = {a, b, c} e B = {e, f, g} e a relação R: A B tal que R a,e > , b, f , c, g . R é um isomorfismo, pois considerando a relação inversa de R, R1 : B A e,a > , f ,b > , g,c > , temos que R R1 a,a > , b,b > , c,c > idA R1 R e,e > , f , f > , g, g > idB Logo, a relação R possui inversa e os conjuntos A e B são conjuntos isomorfos. Teorema: Seja R: A B uma relação. Então R é um isomorfismo se, e somente se, R for simultaneamente um monomorfismo e um epimorfismo. Dessa forma, uma relação é um isomorfismo se, e somente se, for simultaneamente uma relação total, injetora, funcional e sobrejetora. 58 6 - FUNÇÕES PARCIAIS E TOTAIS Uma função parcial nada mais é do que um relação que é funcional. Se a relação funcional for também total, então a denominamos de função total. Portanto, podemos dizer que toda função total é uma função parcial e que toda função parcial é uma relação. Entretanto, nem toda relação é uma função parcial, assim como nem toda função parcial é uma função total. 6.1 Função Parcial Uma função parcial é uma relação funcional, ou seja, cada elemento do domínio está relacionado a no máximo um elemento do contra-domínio. Um elemento pertencente à função parcial a,b f pode ser representado por f ab . Exemplo: Dados os conjuntos A = {a} e B = {x, y} temos que as seguintes relações são funções parcias: - R : B A x,a> , y, a> - : B B Vale observar que a relação inversa de uma função parcial não necessariamente é uma função parcial. Se considerarmos o conjunto A = {0, 1, 2} e a função parcial f: A A tal que f 0,1> , 2,1> , temos que a relação inversa de f, f - -1 1,0> , 1,2> não é uma relação funcional e, consequentemente, não é uma função parcial. Para que a relação inversa de uma relação funcional seja uma função parcial, ela deve ser também injetora (que é o dual de funcional). 6.2 Função Total Uma função total é uma função parcial que é total. Em outras palavras, é uma função parcial definida para todos os elementos do domínio. Se uma função é total, dizemos apenas que é uma função, ou seja, sempre que mencionarmos apenas função, estamos nos referindo a funções totais. Assim, podemos verificar as seguintes propriedades: - Função Injetora = monomorfismo - Função Sobrejetora = epimorfismo - Função Bijetora = isomorfismo Ou seja, uma função bijetora é uma função injetora e sobrejetora. 59 Da mesma forma que para funções parciais, a relação inversa de uma função não necessariamente é uma função. Considerando os conjuntos A = {0, 1} e B = {0, 1, 2} e a função f : B A 0,0> , 1,1> , 2,0> , temos que a relação inversa de f, f -1 0,0> , 1,1> , 0,2> não é uma relação funcional e, portanto, não é uma função. Podemos considerar também a função g: A B, tal que g 0,0> , 1,1> . A inversa de g, g -1 0,0> , 1,1> não é uma relação total e, portanto, não é uma função. Para que a relação inversa de uma função f seja uma função, f deve ser uma função bijetora.