Baixe Matemática Discreta e outras Notas de aula em PDF para Informática, somente na Docsity! José Sousa Pinto Universidade de Aveiro, 1999 Tópicos de Matemática Discreta Texto de Apoio - 2005/2006 ♦♦ • ♦♦ Departamento de Matemática UNIVERSIDADE DE AVEIRO Índice Geral 1 Introdução à Lógica e Teoria de Conjuntos 1 1.1 Teoria (intuitiva) de Conjuntos . . . . . . . . . . . . . . . . . 1 1.1.1 Operações com conjuntos . . . . . . . . . . . . . . . . 6 1.2 Elementos de Teoria da Dedução . . . . . . . . . . . . . . . . 11 1.2.1 Conjectura e demonstração . . . . . . . . . . . . . . . 13 1.2.2 Lógica proposicional . . . . . . . . . . . . . . . . . . . 17 1.2.2.1 Tautologias e contradições . . . . . . . . . . 21 1.2.3 Teoremas e demonstrações . . . . . . . . . . . . . . . . 25 1.2.4 Lógica com quantificadores . . . . . . . . . . . . . . . 31 1.2.4.1 Variáveis e conjuntos . . . . . . . . . . . . . 32 1.2.4.2 Os quantificadores universal e existencial . . 33 1.3 Relações e Aplicações . . . . . . . . . . . . . . . . . . . . . . 42 1.3.1 Produto cartesiano de conjuntos . . . . . . . . . . . . 42 1.3.1.1 Representação de relações . . . . . . . . . . . 45 1.3.2 Partições e relações de equivalência . . . . . . . . . . . 46 1.3.3 Relações de ordem . . . . . . . . . . . . . . . . . . . . 49 1.3.4 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1.4 Álgebras de Boole . . . . . . . . . . . . . . . . . . . . . . . . 61 1.4.1 Operações booleanas fundamentais . . . . . . . . . . . 62 1.4.2 Funções booleanas . . . . . . . . . . . . . . . . . . . . 70 2 Números Naturais, Indução e Cálculo Combinatório 77 2.1 Axiomática dos Números Naturais . . . . . . . . . . . . . . . 77 2.1.1 Conceito de axiomática . . . . . . . . . . . . . . . . . 77 2.1.2 Os axiomas de Dedekind-Peano . . . . . . . . . . . . . 79 2.1.3 Aritmética dos números naturais . . . . . . . . . . . . 81 2.1.4 O conjunto ordenado (IN,≤) . . . . . . . . . . . . . . 87 2.2 Indução Matemática – Aplicações . . . . . . . . . . . . . . . . 88 iii 2.2.1 Formas equivalentes do prinćıpio de indução finita . . 92 2.3 Introdução ao Cálculo Combinatório . . . . . . . . . . . . . . 96 2.3.1 Arranjos, permutações e combinações . . . . . . . . . 103 2.3.2 O binómio de Newton . . . . . . . . . . . . . . . . . . 111 2.3.2.1 O teorema binomial de Newton . . . . . . . . 116 2.3.2.2 O teorema multinomial . . . . . . . . . . . . 120 2.4 Números Cardinais Transfinitos . . . . . . . . . . . . . . . . . 124 2.4.1 Conjuntos equipotentes . . . . . . . . . . . . . . . . . 124 2.4.2 Cardinais transfinitos . . . . . . . . . . . . . . . . . . 127 2.4.2.1 O primeiro número transfinito, ℵ0 . . . . . . 127 2.4.2.2 O segundo número transfinito, ℵ1 . . . . . . 130 2.4.2.3 Números cardinais transfinitos superiores . . 133 3 Relações de Recorrência e Funções Geradoras 135 3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 3.1.1 Relações de recorrência e equações de diferenças . . . 141 3.2 Funções Geradoras . . . . . . . . . . . . . . . . . . . . . . . . 143 3.2.1 Relações de recorrência e funções geradoras . . . . . . 153 3.2.2 Relações de recorrência lineares homogéneas . . . . . . 157 3.2.2.1 Equação caracteŕıstica com ráızes múltiplas . 161 3.2.3 Relações de recorrência lineares não homogéneas . . . 167 4 Teoria dos Grafos 173 4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 4.1.1 Definições básicas . . . . . . . . . . . . . . . . . . . . 174 4.1.2 Caminhos de um grafo . . . . . . . . . . . . . . . . . . 180 4.1.3 Graus dos vértices de um grafo . . . . . . . . . . . . . 182 4.2 Representação de Grafos por Matrizes . . . . . . . . . . . . . 185 4.2.1 Matriz de adjacência de um grafo . . . . . . . . . . . . 186 4.2.2 Matriz de incidência de um grafo . . . . . . . . . . . . 191 4.3 Caminhos Eulerianos e Hamiltonianos . . . . . . . . . . . . . 195 4.4 Árvores e Florestas . . . . . . . . . . . . . . . . . . . . . . . . 199 iv Caṕıtulo 1 Introdução à Lógica e Teoria de Conjuntos 1.1 Teoria (intuitiva) de Conjuntos A teoria dos conjuntos foi criada relativamente recentemente por Georg Can- tor (1845-1918) que definiu conjunto como sendo “uma colecção de objectos claramente distingúıveis uns dos outros, chamados elementos, e que pode ser pensada como um todo”. É claro que se não se tiver definido previamente o que se entende por “colecção” esta não será uma definição rigorosa para o termo “conjunto”. A fim de evitar definições circulares, conjunto e ele- mento de um conjunto são duas noções que não se definem; um conceito quando é definido, é-o em termos de outros conceitos mais simples e não é habitual considerar conceitos logicamente mais simples que os de “conjunto” e “elemento de um conjunto”. Conjunto e elemento de um conjunto são as- sim termos primitivos que se admite serem do conhecimento de toda a gente (pelo menos de toda a gente que estuda Matemática). Esta secção destina-se a relembrar conceitos baseados na noção de conjunto aqui considerado de forma intuitiva. Trata-se de um conceito de extraordinária importância pois grande parte da matemática dos nossos dias pode ser constrúıda a partir dele. Por este facto, o estudo da construção de conceitos de matemática a partir da noção primitiva de conjunto é muitas vezes se designado por Fundamentos de Matemática. 1 enquanto que o conjunto de todos os números inteiros positivos é um con- junto infinito. De modo semelhante, é finito o conjunto de todos os planetas do sistema solar ou o conjunto de todos os números primos menores que 1010 3 ; pelo contrário, como mais à frente se mostrará, é infinito o conjunto de todos os números primos. Se A for um conjunto finito, designar-se-á por cardinalidade de A o número dos seus elementos, o qual se representa por card(A). Um conjunto com cardinalidade igual a 1 diz-se singular. Quando um conjunto é infinito, é imposśıvel defini-lo em extensão (in- dicando explicitamente os seus elementos); logo, se um conjunto puder ser definido em extensão, então certamente será um conjunto finito. Por vezes para definir certos conjuntos infinitos usa-se uma notação parecida com a definição de um conjunto em extensão: é o caso de IN = {0, 1, 2, 3, . . .} Note-se contudo que as reticências representam a quase totalidade dos ele- mentos de IN qualquer que seja o número de elementos que aparecem no ińıcio. Igualdade de conjuntos. Dois conjuntos são iguais se e só se tiverem os mesmos elementos. Se um conjunto A for igual a um conjunto B escreve-se A = B. Para verificar se dois conjuntos são iguais basta verificar se todo o elemento de A é elemento de B e se todo o elemento de B é elemento de A. Se todo o elemento de A for também elemento de B (independentemente do facto de todo o elemento de B poder ser ou não elemento de A) dir-se-á que o conjunto A está contido no conjunto B, o que se denota por A ⊆ B; neste caso também se diz que A é subconjunto de B. Se os conjuntos A e B forem iguais então ter-se-á A ⊆ B e, simultaneamente, B ⊆ A; reciprocamente, se A ⊆ B e B ⊆ A se verificarem simultaneamente então tem-se A = B. Se for A ⊆ B e A 6= B dir-se-á que A é um subconjunto próprio ou uma parte própria de B e escreve-se A ⊂ B. De acordo com estas definições resulta que quaisquer que sejam os conjuntos A e B Ø ⊆ A, A ⊆ A, A = B se e só se [A ⊆ B e B ⊆ A ] Considere-se a prova de, por exemplo, Ø ⊆ A qualquer que seja o conjunto A. A única forma de mostrar que esta inclusão é falsa é verificar que Ø 4 possui um elemento que não pertence a A; ora como Ø não possui elementos então aquela relação verifica-se sempre. Exerćıcios 1.1.1 1. Mostrar que os conjuntos Ø, {Ø} e {{Ø}} são distintos dois a dois. 2. Mostrar que se A for um subconjunto do conjunto vazio então A = Ø. 3. Dado um conjunto arbitrário A, (a) será A membro do conjunto {A}? (b) será {A} membro do conjunto {A}? (c) será {A} um subconjunto de {A}? 4. Dados os conjuntos A = {5, 10, 15, 20, . . .} B = {7, 17, 27, 37, . . .} C = {300, 301, 302, . . . , 399, 400} D = {1, 4, 9, 16, 25, 36, 49, . . .} E = {1, 1/2, 1/4, 1/8, 1/16, . . .} indicar, para cada um deles, uma propriedade que o especifique completa- mente. 5. Indicar quais dos conjuntos que se seguem são iguais: A = {−1, 1, 2} B = {−1, 2, 1} C = {0, 1, 2} D = {2, 1,−1,−2} E = {x : x2 = 4 ou x2 = 1} 6. Determinar em extensão os seguintes conjuntos A = {x ∈ IN : 8 = x+ 3} B = {x ∈ IN : (x− 2)(x− 5) = 0} C = {x ∈ IN : x2 + 22 = 13x} D = {x ∈ IN : √ 5x− 1 + √ 3x− 2 = 3} E = {x ∈ IN : (x+ 1)(x+ 2) < 11} 7. Dizer quais dos conjuntos que se seguem são finitos e quais são infinitos. (a) O conjunto das linhas do plano que são paralelas ao eixo xx′. (b) O conjunto das letras do alfabeto. (c) O conjunto dos múltiplos de 5. (d) O conjunto dos animais existentes na Terra. (e) O conjunto das ráızes da equação x38 + 42x23 − 17x18 − 2x5 + 19 = 0 (f) O conjunto das circunferências centradas na origem. 5 1.1.1 Operações com conjuntos Sendo A,B dois conjuntos, denota-se por A ∪ B a união (ou reunião) de A com B, que é o conjunto cujos elementos são os elementos de A e os elementos de B. Mais geralmente, se A1, A2, . . . , An forem conjuntos então a sua união ∪ni=1Ai ≡ A1 ∪A2 ∪ . . . ∪An é o conjunto constitúıdo pelos elementos que pertencem pelo menos a um dos conjuntos Ai, i = 1, 2, . . . , n. Simbolicamente pode traduzir-se esta definição por ∪ni=1Ai = {x : x ∈ Ai para algum i = 1, 2, . . . , n } A intersecção de dois conjuntos A e B, denotada por A ∩B, é o conjunto cujos elementos pertencem simultaneamente a A e B. Analogamente, se Ai, i = 1, 2, . . . , n, forem conjuntos então ∩ni=1Ai ≡ A1 ∩A2 ∩ . . . ∩An = {x : x ∈ Ai para todo i = 1, 2, . . . , n } As definições de união e intersecção de conjuntos estendem-se, de forma natural, a famı́lias infinitas de conjuntos. Assim, dada uma famı́lia arbitrária de conjuntos {Aα}α∈I (onde I denota um conjunto de ı́ndices) ∪α∈IAα = {x : x ∈ Aα para algum α ∈ I } ∩α∈IAα = {x : x ∈ Aα para todo α ∈ I } Dois conjuntos A e B dizem-se disjuntos se e só se for A ∩ B = Ø, isto é, se não possuirem elementos comuns. A diferença de A e B é o conjunto A\B definido por A\B = {x : x ∈ A e x 6∈ B} ou seja é o conjunto constitúıdo pelos elementos de A que não pertencem a B. Se, em particular, se fizer A = U , o universo do discurso, então ao conjunto U\B = {x : x 6∈ B} dá-se o nome de conjunto complementar de B e denota-se por Bc. Conjunto das partes de um conjunto. Podem construir-se conjuntos cujos elementos são eles próprios, no todo ou em parte, conjuntos. Assim, 6 8. Mostrar que (a) se A ⊆ C e B ⊆ C então A ∪B ⊆ C. (b) se C ⊆ A e C ⊆ B então C ⊆ A ∩B. 9. Determinar os conjuntos das partes dos conjuntos A = {1}, B = {1, 2} c = {1, 2, 3} 10. Sendo M = {1, 2, 3, 4} determinar {x ∈M : x 6∈ Ø}. Quantos elementos terá o conjunto das partes de M? 11. Descrever os elementos do conjunto P(P(P(Ø))). 12. Mostrar que (a) A ⊇ B implica P(A) ⊇ P(B) (b) P(A ∪B) ⊇ P(A) ∪ P(B) (c) P(A ∩B) ⊆ P(A) ∩ P(B) Em que condições se verificam as igualdades nas duas últimas aĺıneas? 13. Determinar o conjunto das partes do conjunto das partes do conjunto {a}. Concluir-se-á esta secção com os dois teoremas que se seguem que rela- cionam várias das operações que se podem realizar com conjuntos. Teorema 1.3 (Propriedade distributiva.) Sendo A,B,C três conjun- tos arbitrários, ter-se-á (a) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) (b) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) Demonstração: Uma forma de mostrar a veracidade destas igualdades consiste em verificar que cada um dos seus membros está contido no outro. Far-se-á esta verificação para a primeira aĺınea deixando a outra a cargo do leitor interessado, como exerćıcio. Para mostrar que se tem A∩(B∪C) ⊆ (A∩B)∪(A∩C) é suficiente verificar que qualquer elemento t ∈ A∩ (B∪C) também pertence ao conjunto (A∩B)∪ (A∩C). De facto, da hipótese resulta que t pertence a A e a B ∪C ou seja que t pertence a A e t pertence a B ou t pertence a C. Então t pertence a A e a B, isto é, t ∈ A∩B, ou t pertence a A e a C, isto é, t ∈ A∩C. Consequentemente, t ∈ (A∩B)∪ (A∩C) e, portanto, A ∩ (B ∪ C) ⊆ (A ∩B) ∪ (A ∩ C) (1.1) como se pretendia mostrar. Suponha-se agora que s ∈ (A ∩ B) ∪ (A ∩ C). Então s ∈ A ∩ B ou s ∈ A ∩ C, ou seja, s pertence simultaneamente a A e B ou s pertence simultaneamente a A e C. Portanto, s pertence a A e pertence a B ou a C, donde resulta (A ∩B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C) (1.2) De (1.1) e (1.2) resulta a igualdade pretendida. 2 9 Exerćıcios 1.1.3 Verificar a demonstração do teorema 1.3 usando um diagrama de Venn apropriado. Teorema 1.4 (Leis de Morgan.) Sendo A e B dois conjuntos arbitrários, ter-se-á (a) (A ∩B)c = Ac ∪Bc (b) (A ∪B)c = Ac ∩Bc Demonstração: Tal como no teorema anterior, far-se-á a demonstração da primeira aĺınea deixando a segunda a cargo do leitor interessado, como exerćıcio. Para mostrar que se tem (A∩B)c ⊆ Ac ∪Bc é suficiente verificar que qualquer elemento t ∈ (A ∩ B)c também pertence ao conjunto Ac ∪ Bc. Da hipótese feita resulta que t não pertence à intersecção de A e B e, portanto, não pertence simul- taneamente a A e a B. Logo pertencerá ao complementar de A ou pertencerá ao complementar de B, isto é, tendo em conta a arbitrariedade de t ter-se-á (A ∩B)c ⊆ Ac ∪Bc (1.3) Suponha-se agora que s ∈ Ac ∪Bc. Então s ∈ Ac ou s ∈ Bc e, portanto, s 6∈ A ou s 6∈ B, donde decorre que s 6∈ A ∩B. Consequentemente, Ac ∪Bc ⊆ (A ∩B)c (1.4) De (1.3) e (1.4) resulta a igualdade pretendida. 2 Exerćıcios 1.1.4 Verificar a demonstração do teorema 1.4 usando um diagrama de Venn apropriado. Exerćıcios 1.1.5 1. Sendo P,Q,R três conjuntos, indicar quais das afirmações que se seguem são verdadeiras. (a) Se P é um elemento de Q e Q é um subconjunto de R, então P é um elemento de R. (b) Se P é um elemento de Q e Q é um subconjunto de R, então P é também um subconjunto de R. (c) Se P é um subconjunto de Q e Q é um elemento de R, então P é um elemento de R. (d) Se P é um subconjunto de Q e Q é um elemento de R, então P é um subconjunto de R. 2. Sendo P,Q,R três conjuntos, provar (a) (P\Q)\R = P\(Q ∪R) (b) (P\Q)\R = (P\R)\Q 10 (c) (P\Q)\R = (P\R)\(Q\R) 3. Chama-se diferença simétrica de dois conjuntos A e B ao conjunto con- stitúıdo pelos elementos que pertencem a A ou a B, mas não a ambos simul- taneamente. (a) Denotando por A ⊕ B a diferença simétrica de A e B , mostrar que A⊕B = (A\B) ∪ (B\A) = (A ∪B)\(A ∩B). (b) Representar num diagrama de Venn a diferença simétrica de dois con- juntos A e B quaisquer. (c) Se a diferença simétrica entre dois conjuntos A e B for igual ao conjunto A que poderá dizer-se a respeito de A e B? (d) Usando diagramas de Venn, verificar quais das igualdades que se seguem são verdadeiras e quais são falsas • A⊕ (B ∩ C) = (A⊕B) ∩ (A⊕ C) • A⊕ (B ∪ C) = (A⊕B) ∪ (A⊕ C) • A⊕ (B ⊕ C) = (A⊕B)⊕ C • A ∩ (B ⊕ C) = (A ∩B)⊕ (A ∩ C) • A ∪ (B ⊕ C) = (A ∪B)⊕ (A ∪ C) (e) Se a diferença simétrica de A e B for igual à diferença simétrica de A e C poderá concluir-se que se tem, necessariamente, B = C? 1.2 Elementos de Teoria da Dedução “... depuis les Grecs qui dit Mathématique dit Demonstration.” in Bourbaki A Matemática divide-se geralmente em partes chamadas teorias matemá- ticas. O desenvolvimento de uma qualquer daquelas teorias é constitúıdo por três etapas fundamentais: (1) a construção dos objectos matemáticos da teoria; (2) a formação de relações entre aqueles objectos; (3) a pesquisa daquelas relações que são verdadeiras, ou seja, a demonstração de teoremas. Objectos matemáticos são, por exemplo, os números, as funções ou as figuras geométricas; a Teoria dos Números, a Análise Matemática e a Geometria são, respectivamente, as teorias matemáticas que os estudam. Os objectos matemáticos (provavelmente) não existem na natureza; são apenas modelos 11 n É primo? 2n − 1 É primo? 2 sim 3 sim 3 sim 7 sim 4 não 15 não 5 sim 31 sim 6 não 63 não 7 sim 127 sim 8 não 255 não 9 não 511 não 10 não 1023 não Observando cuidadosamente a tabela parece verificar-se o seguinte: sem- pre que n é um número primo, o número 2n − 1 também é primo! Será verdade? É tentador pensar que sim, mas de momento não há qualquer razão suficientemente forte que garanta este resultado de forma indiscut́ıvel. Em matemática dá-se o nome de conjectura a este tipo de afirmações cujo valor lógico de verdade ou falsidade carece de ser provado. Assim, esta tabela suscita as duas conjecturas seguintes: Conjectura I Dado um número inteiro n superior a 1, se n for primo então o número 2n − 1 é primo. Conjectura II Dado um número inteiro n superior a 1, se n não for primo o número 2n − 1 também não é primo. Destas duas conjecturas a primeira pode refutar-se imediatamente: para tal é suficiente continuar a desenvolver a tabela para valores de n superiores a 10. Assim, para n = 11 vem 211 − 1 = 2047 = 23× 89 o que mostra que a conjectura é falsa: 11 é um número superior a 1 e é primo, mas 211−1 é um número composto. O número 11, neste caso, constitui o que se designa geralmente por contra-exemplo para a conjectura: um simples contra-exemplo é suficiente para mostrar que a conjectura é falsa. Mas há mais contra-exemplos: 23 e 29, por exemplo, são outros contra-exemplos. Considere-se agora a segunda conjectura: estendendo a tabela a ou- tros números inteiros não primos superiores a 10 não se encontra nenhum contra-exemplo. Isto, contudo, não nos permite concluir que a conjectura é verdadeira pois por muito que se prolongue a tabela nunca será posśıvel 14 experimentar todos os números compostos posśıveis: eles são em número infinito! Poderá haver contra-exemplos que sejam tão grandes que nem com os actuais meios computacionais seja posśıvel testá-los. Para demonstrar ou refutar a conjectura é necessário adoptar então outros métodos. A conjectura II é, de facto, verdadeira. Demonstração: Visto que n não é primo então existem inteiros positivos a e b maiores que 1 tais que a < n e b < n e n = ab. Sendo x = 2b − 1 e y = 1 + 2b + 22b + · · ·+ 2(a−1)b, então xy = ( 2b − 1 ) · ( 1 + 2b + 22b + · · ·+ 2(a−1)b ) = 2b · ( 1 + 2b + 22b + · · ·+ 2(a−1)b ) − ( 1 + 2b + 22b + · · ·+ 2(a−1)b ) = ( 2b + 22b + 23b + · · ·+ 2ab ) − ( 1 + 2b + 22b + · · ·+ 2(a−1)b ) = 2ab − 1 = 2n − 1 Visto que b < n pode concluir-se que x = 2b−1 < 2n−1; por outro lado como b > 1 então x = 2b − 1 > 21 − 1 = 1 donde se segue que y < xy = 2n − 1. Então 2n − 1 pode decompor-se num produto de dois números inteiros positivos x e y maiores que 1 e menores que 2n − 1 o que prova que 2n − 1 não é primo. 2 Uma vez que se provou que a conjectura II é verdadeira, esta passou a adquirir o estatuto de teorema, podendo então escrever-se: Teorema 1.5 Dado um número inteiro n superior a 1, se n não for primo então o número 2n − 1 também não é primo. Exerćıcios 1.2.1 Aproveitando as ideias usadas na demonstração anterior, 1. mostrar que 212−1 não é primo, exibindo explicitamente dois factores (maiores que 1) em que se pode decompor este número; 2. determinar um inteiro x tal que 1 < x < 232 767 − 1 por forma que o número 232 767 − 1 seja diviśıvel por x. Como se viu acima o facto de n ser um número primo não garante que 2n − 1 seja também primo. Mas para alguns inteiros n > 1 primos o número 2n− 1 é primo: aos número primos da forma 2n− 1 dá-se o nome de números primos de Mersenne. Assim, 3, 7, 31, etc., são números primos de Mersenne, mas 5 é um número primo que não é número primo de Mersenne. Com a ajuda dos computadores muitos números primos de 15 Mersenne têm sido encontrados ultimamente. Em Maio de 1994 o maior número primo de Mersenne conhecido era 2859 433−1 que tem 258 716 d́ıgitos. Em Novembro de 1996 foi obtido um novo recorde com o número 21 398 269−1 que tem 420 921 casas decimais e é o 35o¯ número primo de Mersenne co- nhecido. Contudo não se sabe ainda se há uma infinidade de números primos de Mersenne ou se, pelo contrário, o número de primos de Mersenne, em- bora eventualmente muito grande, é finito. Consequentemente, de momento, apenas se poderá conjecturar uma ou outra das hipóteses. Já o mesmo se não dirá sobre os números primos propriamente ditos: há cerca de 2400 anos, Euclides (c. 350 a.C.) provou nos seus célebres Elementos o seguinte: Teorema 1.6 Há uma infinidade de números primos. Demonstração: Suponha-se, pelo contrário (redução ao absurdo), que há apenas um número finito de números primos. Podemos então enumerá-los: seja p1, p2, . . . , pk a lista de todos os números primos e considere-se o número m = p1 · p2 · · · pk + 1 O resto da divisão de m por p1 é igual a 1 e, portanto, o número m não é diviśıvel por p1; de modo semelhante se pode concluir que m não é diviśıvel nem por p2 nem por . . . nem por pk. Usar-se-á agora o facto de todo o número inteiro maior que 1 ser primo ou poder decompor-se num produto de factores primos. Ora m é claramente maior que 1 e, portanto, m ou é um número primo ou pode decompor-se num produto de factores primos. Suponha-se que m é primo. Como m é maior que qualquer um dos números p1, . . . , pk então existiria um número primo que não faria parte da lista que se admitiu conter todos os números primos existentes. Então m não pode ser primo e, portanto, será um produto de números primos estritamente compreendidos entre 1 e m. Seja q um dos primos desta decomposição. Então m é diviśıvel por q pelo que q não pode ser nenhum dos números primos da lista de todos os números primos considerada inicialmente. De novo temos uma contradição a qual resulta de se ter admitido que era finito o número de números primos existentes. Esta hipótese, que conduz sempre a contradições, é falsa ficando, assim, provado que existe uma infinidade de números primos. 2 Os números primos de Mersenne estão relacionados com um outro tipo de números – os números perfeitos – relativamente aos quais está também por resolver outra conjectura famosa. Um número inteiro n diz-se perfeito se for igual à soma de todos os inteiros positivos menores que n que o dividem exactamente. Assim, 6 é perfeito pois 6 = 1+2+3 e 28 = 1+2+4+7+14 é o número perfeito que se lhe segue. 16 p q p ∧ q p ∨ q 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 A conjunção de duas proposições é verdadeira quando e só quando as duas proposições forem simultaneamente verdadeiras; a disjunção é verdadeira desde que pelo menos uma das proposições seja verdadeira. A conectiva “⇒” que se lê “se ..., então ...”, designada por “im- plicação”, obedece, por seu lado, à seguinte tabela de verdade: p q p⇒ q 1 1 1 1 0 0 0 1 1 0 0 1 Por fim considere-se a conectiva lógica “p se e só se q”, por vezes abreviada para “p sse q”, e geralmente denotada por “p⇔ q”. A sua tabela de verdade é dada por p q p⇔ q 1 1 1 1 0 0 0 1 0 0 0 1 A proposição “p⇔ q” é verdadeira quando “p” e “q” são ambas verdadeiras ou ambas falsas e falsa quando “p” e “q” têm valores lógicos distintos. É fácil verificar que “p⇔ q” tem o mesmo significado lógico que a proposição “(p ⇒ q) ∧ (q ⇒ p)”. Para o confirmar basta escrever a tabela de verdade para esta proposição e verificar que é idêntica à da primeira. p q p⇒ q q ⇒ p (p⇒ q) ∧ (q ⇒ p) 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 19 Na prática usa-se frequentemente esta relação: para mostrar que uma propo- sição da forma “p⇔ q” é verdadeira decompõe-se essa proposição nas duas partes “p⇒ q” e “q ⇒ p” e mostra-se separadamente que cada uma delas é verdadeira. Nota 1.8 (A implicação.) A tabela de verdade da conectiva⇒ funciona como aquela definição4 para a implicação que a experiência mostrou ser a mais adequada. No entanto há aqui um certo conflito em relação ao que se passa na conversação usual: nesta não se dirá geralmente “p implica q” quando se sabe à priori que “p” é falsa. A implicação é verdadeira quando o antecedente “p” é falso qualquer que seja o consequente “q”. Esta situação pode ilustrar-se com a implicação “se dois mais dois são cinco então a terra é um queijo” que é verdadeira uma vez que o antecedente é falso. As duas primeiras linhas da tabela da implicação não apresentam qualquer problema sob o ponto de vista intuitivo do senso comum. Quanto às duas últimas, qualquer outra escolha posśıvel apresentaria desvantagens sob o ponto de vista lógico, o que levou à escolha das soluções apresentadas: de facto, fazendo 0 na 3a¯ linha e 0 na 4a¯ linha obtém-se a tabela da conjunção, ∧; fazendo 0 na 3a¯ linha e 1 na 4a¯ linha obtém-se a equivalência. Resta a possibilidade de fazer 1 na 3 a ¯ linha e 0 na 4a¯ linha que não é também desejável pois isso equivaleria a recusar a equivalência [p⇒ q] ⇔ [¬q ⇒ ¬p] Ora esta equivalência é aconselhável, ela própria, pelo senso comum: por exemplo, a proposição “se o Pedro fala, existe” é (intuitivamente) equivalente à proposição “se o Pedro não existe, não fala”. A aceitação desta equivalência impõe a tabela considerada para a implicação. p q p⇒ q ¬q ¬p ¬q ⇒ ¬p 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 Dada uma implicação p⇒ q há outras implicações envolvendo as proposições p e q (ou as suas negações ¬p e ¬q) que estão relacionadas com aquela. A proposição ¬q ⇒ ¬p, que lhe é equivalente, como já foi referido acima, é conhecida por contra- rećıproca ou conversa da primeira. A proposição q ⇒ p designa-se por rećıproca e a proposição ¬p ⇒ ¬q designa-se por inversa ou contrária. Observe-se que, embora a contra-rećıproca seja equivalente à proposição original, o mesmo não acontece com a rećıproca (e a contrária, que lhe é equivalente) o que pode verificar- se através das respectivas tabelas de verdade. 4Outras definições para a implicação seriam, em prinćıpio, posśıveis. 20 1.2.2.1 Tautologias e contradições Chama-se tautologia a uma proposição que é sempre verdadeira quaisquer que sejam os valores atribúıdos às variáveis proposicionais que a compõem. Dito de outra forma, chama-se tautologia a uma proposição cuja tabela de verdade possui apenas 1s na última coluna. Exemplo de uma tautologia é a proposição p ∨ (¬p), o prinćıpio do terceiro exclúıdo, p ¬p p ∨ (¬p) 1 0 1 0 1 1 Se p designar a proposição “5 é uma raiz primitiva de 17” então p ∨ (¬p) é sempre verdadeira independentemente do significado (ou sentido) atribúıdo à expressão “raiz primitiva de”. Chama-se contradição à negação de uma tautologia: trata-se de uma proposição cuja tabela de verdade apenas possui 0s na última coluna. Nota 1.9 Não deve confundir-se contradição com proposição falsa, assim como não deve confundir-se tautologia com proposição verdadeira. O facto de uma tau- tologia ser sempre verdadeira e uma contradição ser sempre falsa deve-se à sua forma lógica (sintaxe) e não ao significado que se lhes pode atribuir (semântica). A tabela de verdade p q p ∨ q p⇒ (p ∨ q) p⇒ q ¬q p ∧ (¬q) (p⇒ q) ∧ [p ∧ (¬q)] 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 mostra que p⇒ (p ∨ q) é uma tautologia, enquanto que (p⇒ q) ∧ [p ∧ (¬q)] é uma contradição. Exerćıcios 1.2.3 : 1. Indicar os valores (de verdade ou falsidade) das seguintes afirmações: (a) 3 ≤ 7 e 4 é um número inteiro ı́mpar (b) 3 ≤ 7 ou 4 é um número inteiro ı́mpar (c) 5 é ı́mpar ou diviśıvel por 4 21 são verdadeiras ou falsas, mas não ambas as coisas) e 1 e 0 designam as proposições tautológica e contraditória, respectivamente. Definição 1.10 Duas proposições a e b dizem-se logicamente equivalen- tes se tiverem os mesmos valores lógicos em todas as circunstâncias, ou seja, se a proposição a⇔ b for uma tautologia. Dir-se-á que a proposição a implica logicamente a proposição b se a veracidade da primeira arrastar necessariamente a veracidade da segunda, ou seja, se a proposição a⇒ b for uma tautologia. Exerćıcios 1.2.4 : 1. Indicar quais das sentenças seguintes é que são equivalentes (a) p ∧ (¬q) (b) p⇒ q (c) ¬[(¬p) ∨ q)] (d) q ⇒ (¬q) (e) (¬p) ∨ q (f) ¬[p⇒ q] (g) p⇒ (¬q) (h) (¬p) ⇒ (¬q) 2. Mostrar que cada uma das proposições que se seguem (a) (¬p) ∨ q (b) (¬q) ⇒ (¬p) (c) ¬[p ∧ (¬q)] é equivalente à implicação p⇒ q. 3. Mostrar que (a) p ∨ (q ∧ r) não é logicamente equivalente a (p ∨ q) ∧ r. (b) p ∨ (q ∧ r) é logicamente equivalente a (p ∨ q) ∧ (p ∨ r). (c) p ∨ [¬(q ∧ r)] é logicamente equivalente a [p ∨ (¬q)] ∨ (¬r). 4. Indicar quais dos pares de sentenças que se seguem é que são logicamente equivalentes e quais não são. (a) [p ∧ [q ∨ r]]; [[p ∧ q] ∨ [p ∧ r]] (b) ¬[p ∧ q]; [(¬p) ∧ (¬q)] (c) [p ∨ [q ∧ r]]; [[p ∨ q] ∧ [p ∨ r]] (d) [p⇔ q]; [p⇒ q] ∧ [q ⇒ p] (e) [p⇒ q]; [q ⇒ p] (f) [p⇒ q]; [(¬q) ⇒ (¬p)] 24 (g) ¬[p⇒ q]; [(¬p) ⇒ (¬q)] 5. Verificar que as proposições da tabela da página 23 são, de facto, tautologias. Usando as tautologias apropriadas simplificar as seguintes proposições: (a) p ∨ [q ∧ (¬p)] (b) ¬[p ∨ [q ∧ (¬r)]] ∧ q (c) ¬[(¬p) ∧ (¬q)] (d) ¬[(¬p) ∨ q] ∨ [p ∧ (¬r)] (e) [p ∧ q] ∨ [p ∧ (¬q)] (f) [p ∧ r] ∨ [(¬r) ∧ [p ∨ q]] 6. Por vezes usa-se o śımbolo ↓ para denotar a proposição composta por duas proposições atómicas p e q que é verdadeira quando e só quando p e q são (simultaneamente) falsas e é falsa em todos os outros casos. A proposição p ↓ q lê-se “nem p nem q”. (a) Fazer a tabela de verdade de p ↓ q. (b) Expressar p ↓ q em termos das conectivas ∧, ∨ e ¬. (c) Determinar proposições apenas constitúıdas pela conectiva ↓ que sejam equivalentes a ¬p, p ∧ q e p ∨ q. 7. Determinar se a expressão composta (p ∨ q) ∨ [¬(p ∧ q)] é uma tautologia, uma contradição ou não uma coisa nem outra. 8. Expressar a proposição p⇔ q usando apenas os śımbolos ¬,∧ e ∨. 9. Mostrar que não são logicamente equivalentes os seguintes pares de proposições (a) ¬(p ∧ q); (¬p) ∧ (¬q) (b) ¬(p ∨ q); (¬p) ∨ (¬q) (c) p⇒ q; q ⇒ p (d) ¬(p⇒ q); (¬p) ⇒ (¬q) 10. Mostrar que p⇒ (q ∨ r) implica logicamente p⇒ q. 1.2.3 Teoremas e demonstrações Sejam p, q, r três proposições das quais se sabe seguramente que p e q são proposições verdadeiras. Se for posśıvel provar que a implicação (p ∧ q) ⇒ r (1.5) é verdadeira (isto é, que da veracidade de p e de q resulta sempre a veracidade de r), então pode argumentar-se que r é necessariamente verdadeira. Se, 25 numa contenda, as proposições p e q forem aceites como verdadeiras por ambas as partes assim como a implicação (1.5), então a veracidade de r resulta logicamente dos pressupostos. A uma tal proposição (composta) dá- se o nome de argumento e constitui o método usado numa discussão para convencer uma parte das razões que assistem à outra. De um modo mais geral, chama-se argumento a uma sequência finita de proposições organizadas na forma seguinte (p1 ∧ p2 ∧ . . . ∧ pn) ⇒ q (1.6) onde p1, p2, . . . , pn são designadas as premissas (ou hipóteses) e q a con- clusão (ou tese). Ao fazer-se a leitura de (1.6) é costume inserir uma das locuções “portanto”, “por conseguinte”, “logo”, etc., lendo-se, por exemplo, “p1, . . . , pn, portanto, q”. Para sugerir esta leitura usa-se, fre- quentemente, a seguinte notação p1 ... ou p1, . . . , pn/q pn q Interessa distinguir entre argumentos correctos ou válidos e argumentos incorrectos ou inválidos ou falaciosos. Definição 1.11 Um argumento p1, . . . , pn/q diz-se correcto ou válido se a conclusão for verdadeira sempre que as premissas p1, . . . , pn forem simultaneamente verdadeiras e diz-se incorrecto ou inválido ou falacioso no caso contrário, isto é, se alguma situação permitir que as premissas sejam todas verdadeiras e a conclusão falsa. Construção de demonstrações elementares. Os matemáticos são pes- soas muito cépticas5. Têm vários métodos para resolver problemas matemá- ticos que vão desde a experimentação à tentativa e erro. Mas não se con- vencem da validade das respostas obtidas a menos que possam prová-las! A prova ou demonstração é uma espécie de “puzzle” para o qual não há 5pessoa céptica – pessoa que duvida de tudo, especialmente do que é comummente aceite (Dicionário, Porto Editora, 7a¯ ed.) 26 Demonstração: Far-se-á a prova pela contra-rećıproca. Suponha-se c > 0. Então multiplicando ambos os membros da desigualdade a > b por c obter-se-á ac > bc. Consequentemente, ac ≤ bc ⇒ c ≤ 0 como se pretendia mostrar. 2 Exerćıcios 1.2.5 1. Sejam A,B,C,D quatro conjuntos e suponha-se que A\B ⊆ C ∩ D e seja x ∈ A. Mostrar que se x 6∈ D então x ∈ B. 2. Sejam a, b números reais. Mostrar que se a < b então (a+ b)/2 < b. 3. Suponha-se que x é um número real tal que x 6= 0. Mostrar que se 3 √ x+ 5 x2 + 6 = 1 x então x 6= 8. 4. Sejam a, b, c, d números reais tais que 0 < a < b e d > 0. Provar que se ac > bd então c > d. As regras que permitem passar de hipóteses feitas e resultados já demon- strados a novas proposições são conhecidas por regras de inferência. A regra de inferência mais frequentemente usada, conhecida por modus po- nens, é a seguinte: p ⇒ q p q Se forem verdadeiras a proposição p e a implicação p⇒ q, então q é neces- sariamente verdadeira. p q p⇒ q p ∧ (p⇒ q) [p ∧ (p⇒ q)] ⇒ q 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 A proposição q é logicamente implicada por p e p⇒ q o que se escreve p, p⇒ q |= q 29 De um modo geral, p1, p2, . . . , pn |= q é uma regra de inferência se e só se p1 ∧ p2 ∧ . . . ∧ pn ⇒ q for uma tautologia. Outras regras de inferência são as seguintes: p, p⇒ q |= q modus ponens p⇒ q, q ⇒ r |= p⇒ r p⇒ q,¬q |= ¬p modus tollens p |= p ∨ q p ∧ q |= p p, q |= p ∧ q Exerćıcios 1.2.6 Sendo p, q, r e s quatro proposições dadas, estabelecer a vali- dade ou invalidade dos seguintes argumentos. 1. (¬p) ∨ q, p |= q 2. p⇒ q, r ⇒ (¬q) |= p⇒ (¬r) 3. (¬p) ∨ q, (¬r) ⇒ (¬q) |= p⇒ (¬r) 4. q ∨ (¬p),¬q |= p 5. ¬p |= p⇒ q 6. (p ∧ q) ⇒ (r ∧ s),¬r |= (¬p) ∨ (¬q) 7. p⇒ q, (¬q) ⇒ (¬r), s⇒ (p ∨ r), s |= q 8. p ∨ q, q ⇒ (¬r), (¬r) ⇒ (¬p) |= ¬(p ∧ q) 9. p⇒ q, (¬r) ⇒ (¬q), r ⇒ (¬p) |= ¬p 10. p⇒ (¬p) |= ¬p 11. p ∨ q, p⇒ r,¬r |= q 12. p, q ⇒ (¬p), (¬q) ⇒ [r ∨ (¬s)],¬r |= ¬s 13. p⇒ (q ∨ s), q ⇒ r |= p⇒ (r ∨ s) 14. p⇒ (¬q), q ⇒ p, r ⇒ p |= ¬q 15. p⇒ q, r ⇒ s,¬(p⇒ s) |= q ∧ (¬r) 30 1.2.4 Lógica com quantificadores Há muitas espécies de afirmações que se fazem em matemática que não po- dem ser simbolizadas e logicamente analisadas em termos do cálculo proposi- cional. Para além das complexidades externas introduzidas pelas diferentes conectivas uma afirmação pode conter complexidades por assim dizer inter- nas que advêm de palavras tais como “todo”, “cada”, “algum”, etc. as quais requerem uma análise lógica que está para além do cálculo proposicional. Tal análise é objecto da chamada Lógica de Predicados. No exemplo que se segue mostram-se as dificuldades que poderiam apare- cer se se usasse apenas o cálculo proposicional. Exemplo 1.16 Sejam P e Q dois conjuntos. Represente-se por p a afirmação “x é um elemento de P” e por q a afirmação “x é um elemento de Q”. Analisar a sentença (p⇒ q) ∨ (q ⇒ p) em termos de cálculo proposicional. Discussão: Antes de mais considere-se a tabela de verdade da sentença dada. p q p⇒ q q ⇒ p (p⇒ q) ∨ (q ⇒ p) 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 O resultado obtido é algo surpreendente visto que a tabela de verdade indica que esta sentença é uma tautologia (sempre verdadeira). Tendo em conta o significado de p e q tem-se então que “x ∈ P implica x ∈ Q ou x ∈ Q implica x ∈ P” o que de acordo com o resultado obtido seria sempre verdadeiro. Mas “x ∈ P implica x ∈ Q ou x ∈ Q implica x ∈ P” parece afirmar que a proposição “P é um subconjunto de Q ou Q é um subconjunto de P” constitui uma afirmação sempre verdadeira.Ora, a própria experiência mostra que há outras situações posśıveis para os conjuntos P e Q, nomeadamente P pode não estar contido em Q e, por seu turno, Q pode também não estar contido em P . Esta análise assim feita conduz a um aparente paradoxo que resultou do facto de nem p nem q serem, de facto, proposições: trata-se de fórmulas abertas ou predicados. Por outro lado uma proposição do tipo “P é um subconjunto de Q” tem uma estrutura que requer o uso de quantificadores, isto é, o uso de expressões do tipo “todo” (P é um subconjunto de Q se todo o x ∈ P pertencer a Q.) 31 É claro que é sempre posśıvel supor que x é uma variável em U , para o que basta escrever ∀x [x ∈ U ⇒ [x ∈ D ⇒ p(x) ] ] No exemplo 1.17 com a fórmula “p(x) ≡ x2 + 1 > 0”, pode sempre supor-se que o universo é U ≡ C. Então, ∀x p(x) é uma proposição falsa, enquanto que ∀x [x ∈ IR ⇒ p(x) ] é uma proposição verdadeira. Supondo que D é um conjunto finito, por exemplo, D = {a1, a2, . . . , an} a fórmula (1.10) é (logicamente) equivalente à conjunção p(a1) ∧ p(a2) ∧ . . . ∧ p(an) o que mostra bem que (1.10) não tem variáveis livres, tratando-se, portanto, de uma proposição. O mesmo significado pode ser dado no caso em que D é um conjunto infinito envolvendo agora, correspondentemente, um número infinito de conjunções. Por outro lado, escreve-se ∃x p(x) (1.11) para significar que existe (no universo do discurso) pelo menos um elemento x para o qual p(x) se verifica, o que se pode ler da seguinte forma “existe pelo menos um x tal que p(x)” A fórmula (1.11) é uma abreviatura (usada normalmente) para a expressão ∃x [x ∈ U ∧ p(x) ] onde, novamente, U designa o universo do discurso. O śımbolo ∃ é chamado o quantificador existencial. Se D for um subconjunto de U e p(x) for uma fórmula com uma variável cujo domı́nio é D, então ∃x∈D p(x) ou ∃x [x ∈ D ∧ p(x)] 34 é uma fórmula com o quantificador existencial. É claro que é sempre posśıvel supor que x é uma variável em U , para o que basta escrever o seguinte ∃x [x ∈ U ∧ x ∈ D ∧ p(x)] Supondo, novamente, que D é um conjunto finito, D = {a1, a2, . . . , an} então a fórmula existêncial ∃x∈D p(x) ou ∃x [x ∈ D ∧ p(x)] é (logicamente) equivalente à disjunção p(a1) ∨ p(a2) ∨ . . . ∨ p(an) o que mostra que tal fórmula não tem variáveis livres, sendo, portanto, uma proposição. O mesmo significado pode ser dado no caso em que D é um conjunto infinito, mas envolvendo agora, correspondentemente, disjunções infinitas. O valor lógico (de verdade ou falsidade) de uma proposição quantificada depende, naturalmente, do domı́nio considerado. As duas proposições ∀x [x ∈ Q ⇒ x2 − 2 = 0 ] ∃x [x ∈ Q ∧ x2 − 2 = 0 ] são falsas enquanto que das duas seguintes ∀x [x ∈ IR ⇒ x2 − 2 = 0 ] ∃x [x ∈ IR ∧ x2 − 2 = 0 ] a primeira é falsa, mas a segunda é verdadeira. Por uma questão de generalidade interessa considerar também o caso em que o domı́nio da variável da fórmula p(x) é o conjunto vazio. Que valor lógico terão expressões da forma ∀x [x ∈ Ø ⇒ p(x) ] e ∃x [x ∈ Ø ∧ p(x) ] Na primeira expressão a implicação é sempre verdadeira quando o antecedente é falso: é o que acontece aqui. Visto que x ∈ Ø é sempre falso, então ∀x [x ∈ Ø ⇒ p(x) ] 35 é uma proposição sempre verdadeira. Quanto à segunda expressão ela tem a forma de uma conjunção de proposições, das quais uma é sempre falsa. Então, ∃x [x ∈ Ø ∧ p(x) ] é uma proposição sempre falsa. Nota 1.18 Observe-se que enquanto a fórmula p(x) tem uma variável livre, x, as fórmulas ∀x p(x) e ∃x p(x) não têm qualquer variável livre: nestas fórmulas x é sempre uma variável ligada (ou muda). Trata-se então de proposições, relativa- mente às quais se pode afirmar que são verdadeiras ou falsas (mas não ambas as coisas). Por vezes emprega-se o quantificador existêncial numa situação simultânea de unicidade, ou seja, quer-se afirmar não só que ∃x p(x) mas ainda que a fórmula p(x) se transforma numa proposição verdadeira só para um elemento do domı́nio de quantificação. Neste caso emprega-se a abreviatura ∃!x p(x) que significa “existe um e um só x tal que p(x)”. Exerćıcios 1.2.8 1. Escrever as frases que se seguem usando notação lógica na qual x designa um gato e p(x) significa “x gosta de creme”. (a) Todos os gatos gostam de creme. (b) Nenhum gato gosta de creme. (c) Um gato gosta de creme. (d) Alguns gatos não gostam de creme. 2. Sendo A,B,C três conjuntos, analise em termos lógicos, usando quantificadores, a proposição “se A ⊆ B então A e C\B são disjuntos”. 3. Traduzir em linguagem simbólica as proposições que se seguem, indicando as esco- lhas que são apropriadas para os domı́nios correspondentes. (a) Existe um inteiro x tal que 4 = x+ 2. (b) Para todos os inteiros x, 4 = x+ 2. (c) Cada triângulo equilátero é equiângulo. 36 Esta proposição é manifestamente falsa pois não existe nenhum número real y, sempre o mesmo, para o qual todo o número real x satisfaz a equação dada. Estes exemplos ilustram a não comutatividade dos dois quantificadores universal, ∀, e existencial, ∃. Mais geralmente, uma fórmula pode ter um número qualquer n ∈ IN1 de variáveis p = p(x1, x2, . . . , xn) Para transformar uma tal fórmula numa proposição são necessários n quan- tificadores. Denotando um quantificador genérico (universal ou existencial) por Q, então Q1 Q2 · · · Qn p(x1, x2, . . . , xn) é uma proposição. Dois quantificadores da mesma espécie são sempre comu- tativos enquanto que dois quantificadores de espécie diferente são geralmente não comutativos, isto é, a sua permuta conduz a proposições de conteúdo distinto.7 Negação de proposições quantificadas. Dadas as proposições com quantificadores ∀x [x ∈ U ⇒ p(x) ] e ∃x [x ∈ U ∧ p(x) ] pode ser necessário analisar (logicamente) as proposições que são a negação destas, ou seja ¬ (∀x [x ∈ U ⇒ p(x) ]) ¬ (∃x [x ∈ U ∧ p(x) ]) Suponha-se, por exemplo, que p(x) é a fórmula “x é perfeito” e H o universo dos seres humanos. Então a proposição ¬ (∃x [x ∈ H ∧ p(x) ]) 7Em certos casos muito particulares a permuta dos quantificadores universal e existen- cial não altera o valor lógico da proposição obtida. É o que se passa, por exemplo, com as proposições seguintes ∀x∈IN ∃y∈IN [x + y = x] ∃y∈IN ∀x∈IN [x + y = x] onde y é o elemento neutro da adição (y = 0). 39 corresponde a afirmar que “não é verdade que exista um ser humano que seja perfeito” ou, de modo mais coloquial, “ninguém é perfeito”. Isto equivale a afirmar que “todos os seres humanos são não perfeitos (isto é, imperfeitos)”, o que pode simbolizar-se assim ∀x [x ∈ H ⇒ ¬p(x) ] Tendo em conta que a⇒ (¬b) é equivalente a ¬(a ∧ b), então ¬ (∃x [x ∈ H ∧ p(x) ]) ⇔ ∀x ¬ [x ∈ H ∧ p(x) ] ⇔ ∀x [x ∈ H ⇒ ¬p(x) ] De modo semelhante, pode verificar-se que ¬ (∀x [x ∈ U ⇒ p(x) ]) equivale a ∃x ¬ [x ∈ U ⇒ p(x) ] ou ∃x [¬p(x) ] ou ∃x [x ∈ U ∧ ¬p(x) ] Em resumo, de um modo genérico, têm-se as equivalências ¬ (∀x p(x)) ⇔ ∃x [¬p(x) ] ¬ (∃x p(x)) ⇔ ∀x [¬p(x) ] conhecidas por Segundas Leis de Morgan. Exerćıcios 1.2.9 1. Traduzir em linguagem simbólica, escolhendo em cada caso os universos apro- priados, as seguintes afirmações: (a) “Para cada linha l e cada ponto P não pertencente a l existe uma linha l′ que passa por P e é paralela a l.” (b) “Para cada x no conjunto A existe y no conjunto B tal que f(x) = y.” (c) “Para todo o x pertencente ao domı́nio da função f e para todo o > 0 existe δ > 0 tal que |x− c| < δ implica |f(x)− L| < .” (d) “Para cada x em G existe x′ em G tal que xx′ = e”. (e) “A soma de dois números pares é par.” 2. Indicar em linguagem comum a negação de cada uma das afirmações do exer- ćıcio anterior. 3. Seja p(x, y) a fórmula “x + 2 > y” e seja IN ≡ {0, 1, 2, . . .} o conjunto dos números naturais. Escrever em linguagem comum o significado das expressões que se seguem e determinar os seus valores lógicos. 40 (a) ∀x∈IN ∃y∈IN p(x, y) (b) ∃x∈IN ∀y∈IN p(x, y) 4. Indicar o significado das proposições que se seguem, sendo a quantificação feita sobre IN. (a) ∀x ∃y (x < y) (b) ∃y ∀x (x < y) (c) ∃x ∀y (x < y) (d) ∀y ∃x (x < y) (e) ∃x ∃y (x < y) (f) ∀x ∀y (x < y) Dizer qual o valor lógico de cada uma delas. 5. Sendo IN o domı́nio da quantificação, indicar quais das proposições que se seguem são verdadeiras e quais são falsas. (a) ∀x∃y (2x− y = 0) (b) ∃y∀x (2x− y = 0) (c) ∀y∃x (2x− y = 0) (d) ∀x [x < 10 ⇒ ∀y [ y < x⇒ y < 9 ] ] (e) ∃y∃z (y + z = 100) (f) ∀x∃y [ y > x ∧ (y + x = 100) ] Fazer o mesmo exerćıcio considerando primeiro ZZ e depois IR para universos do discurso. 6. Dada a proposição A ⊆ B, (a) expressá-la em termos lógicos, (b) negar a expressão obtida, (c) traduzir em linguagem comum o resultado obtido na aĺınea anterior (que equivale a A 6⊆ B). 7. Negar a proposição “toda a gente tem um parente de quem não gosta” usando a simbologia lógica. 8. Sendo IR o universo do discurso traduzir em linguagem simbólica as seguintes afirmações: (a) A identidade da adição é o 0. (b) Todo o número real tem simétrico. (c) Os números negativos não têm ráızes quadradas. (d) Todo o número positivo possui exactamente duas ráızes quadradas. 9. Determinar que relação existe entre as duas proposições ∃x∈D [ p(x) ⇒ q(x) ] e ∃x∈D p(x) ⇒ ∃x∈D q(x) Justificar e apresentar exemplos. 41 Exemplo 1.21 Sejam dados os conjuntos A = {1, 2, 3} e B = {r, s} Então R = {(1, r), (2, s), (3, r)} é uma relação de A para B. Exemplo 1.22 Sejam A e B conjuntos de números reais. A relação R (de igual- dade) define-se da seguinte forma aRb se e só se a = b para todo o a ∈ A e todo o b ∈ B. Exemplo 1.23 Seja dado o conjunto A = {1, 2, 3, 4, 5} = B Definindo a relação R (menor que) em A: aRb se e só se a < b então R = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)} Dada uma relaçãoR do conjuntoA para o conjuntoB chama-se domı́nio e contradomı́nio de R, respectivamente, aos conjuntos assim definidos: D(R) = {x ∈ A : ∃y [y ∈ B ∧ (x, y) ∈ R]} I (R) = {y ∈ B : ∃x [x ∈ A ∧ (x, y) ∈ R]} Exemplo 1.24 Seja dado o conjunto A = {a, b, c, d} = B e a relação R definida por R = {(a, a), (a, b), (b, c), (c, a), (d, c), (c, b)} Então, R(a) = {a, b} R(b) = {c} ... D(R) = {a, b, c, d} = A I(R) = {a, b, c} 44 1.3.1.1 Representação de relações Apresentar-se-ão dois modos distintos para representar relações, um de tipo algébrico e outro de tipo geométrico. Cada um deles tem vantagens e desvan- tagens em relação ao outro, tudo dependendo da aplicação particular a que se destinam. Matriz de uma relação. SejamA = {a1, a2, . . . , am}, B = {b1, b2, . . . , bn} dois conjuntos finitos com m e n elementos respectivamente. Uma relação R de A para B pode representar-se por uma matriz R = [rij ]1≤i≤m;1≤j≤n cujos elementos são definidos por rij = { 1 se (ai, bj) ∈ R 0 se (ai, bj) 6∈ R A matriz R tem m = card(A) linhas e n = card(B) colunas. Exemplo 1.25 Dados os conjuntos A = {1, 2, 3} e B = {r, s} considere-se a relação de A para B R = {(1, r), (2, s), (3, r)} Determinar a matriz de R. Resolução: Tomando A para definir os ı́ndices de linha e B para definir os ı́ndices de coluna, vem R =  1 00 1 1 0  Reciprocamente, dados dois conjuntos A e B de cardinalidades m e n, respectivamente, uma matriz dem×n cujos elementos são 0’s e 1’s determina sempre uma relação de A para B. Exemplo 1.26 A matriz R =  1 0 0 10 1 1 0 1 0 1 0  tem 3 linhas e 4 colunas. Fazendo A = {a1, a2, a3} e B = {b1, b2, b3, b4}, aquela matriz pode representar a relação de A para B definida por R = {(a1, b1), (a1, b4), (a2, b2), (a2, b3), (a3, b1), (a3, b3)} 45 Digrafo de uma relação. Seja dado um conjunto X no qual se encon- tra definida uma relação R. Esta relação pode representar-se graficamente por um diagrama com pontos que são os elementos do conjunto X e arcos orientados que ligam dois vértices xi, xj (com a orientação de xi para xj) sempre que se tenha (xi, xj) ∈ R. A tal representação dá-se o nome de grafo orientado ou, mais simplesmente, digrafo.8 Exemplo 1.27 Seja dado o conjunto X = {x1, x2, x3, x4, x5, x6, x7} e a relação R definida sobre X por R = {(x1, x2), (x1, x4), (x1, x5), (x2, x1), (x2, x3), (x3, x5), (x4, x4), (x4, x5), (x4, x6), (x4, x7), (x5, x4), (x5, x5), (x6, x3), (x6, x6), (x6, x7)} A representação gráfica de R sobre X toma, neste caso, a forma d d d d dd d z y K x2 x1 x3 x6 x4 x7 x5 ~ R y 3 R W - 6 1.3.2 Partições e relações de equivalência Seja A um conjunto não vazio. Chama-se partição de A a uma famı́lia PA de subconjuntos não vazios de A tais que: 1. Cada elemento de A pertence a um e um só conjunto de PA. 2. Se A1 e A2 forem dois elementos distintos da partição PA então A1 ∩A2 = Ø. Os elementos de PA são designados por blocos ou células da partição. 8Do inglês “directed graph”. 46 Exemplo 1.33 Seja dado o conjunto A = {1, 2, 3, 4} e considere-se a partição P = {{1, 2, 3}, {4}}. Determinar a relação de equivalência determinada em A pela partição P. Resolução: Visto que os blocos de P são {1, 2, 3} e {4}, então R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4)} é a relação de equivalência induzida em A pela partição P. 1.3.3 Relações de ordem Seja A um conjunto não vazio e R ⊆ A2 uma relação binária qualquer definida em A. Para indicar que o par ordenado (a, b) ∈ A2 pertence à relação R escreve-se também frequentemente aRb, ou seja, aRb ⇔ (a, b) ∈ R quaisquer que sejam a, b ∈ A. Exemplo 1.34 Se A = {0, 1, 2, 3, 4, 5} ⊂ IN e R for a relação ≤ usual em IN, então ≤ = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (1, 5), (4, 4), (4, 5), (5, 5)} e escreve-se a ≤ b ⇔ (a, b) ∈ ≤ quaisquer que sejam a, b ∈ A. Definição 1.35 Chama-se relação de ordem definida no conjunto A a uma relação binária R ⊆ A2 com as seguintes propriedades: (1) reflexividade: ∀a [ a ∈ A⇒ aRa ], (2) anti-simetria: ∀a,b∈A [ [ aRb ∧ bRa ] ⇒ a = b ] (3) transitividade: ∀a,b,c∈A [ [ aRb ∧ bRc ] ⇒ aRc ] Se, adicionalmente, R satisfizer a proposição (4) dicotomia: ∀a,b [ a, b ∈ A ⇒ [ aRb ∨ bRa ] ] dir-se-á uma relação de ordem total. Se R não for uma relação de ordem total também se designa, por vezes, relação de ordem parcial. 49 Exemplo 1.36 1. Seja A uma famı́lia de conjuntos. A relação em A definida por “A é um subconjunto de B” é uma ordem parcial. 2. Seja A um subconjunto qualquer de números reais. A relação ≤ em A é uma relação de ordem total – é a chamada ordem natural. 3. A relação R definida em IN por “xRy se e só se x é múltiplo de y” é uma relação de ordem parcial em IN. Definição 1.37 Seja R uma relação de ordem definida em A; a relação R∗ ⊂ A2 definida por ∀a,b∈A [ aR∗b ⇔ [ aRb ∧ a 6= b ] ] (1.12) diz-se uma relação de ordem estrita definida em A. Definição 1.38 Chama-se conjunto ordenado a um par ordenado (A,R) onde A é um conjunto não vazio e R é uma relação de ordem (parcial ou total) em A. Se, para a, b ∈ A se tiver aRb dir-se-á que b domina a ou que a precede b. Seja R uma relação de ordem num conjunto A. Então a relação inversa R−1, definida por aR−1b ⇔ bRa quaisquer que sejam os elementos a, b ∈ A, é também uma relação de ordem (verificar!). As ordens parciais mais familiares são as relações ≤ ou ≥ em ZZ ou IR (que são inversas uma da outra). Por isso, muitas vezes se denota um conjunto ordenado simplesmente por (A,≤) ou (A,≥) embora as ordens ≤ ou ≥ possam não corresponder às relações usuais em ZZ ou IR denotadas por aqueles śımbolos. Elementos extremais de um conjunto ordenado. Sendo (A,≤) um conjunto (total ou parcialmente) ordenado dá-se o nome de máximo de A ao elemento de a ∈ A, se existir, tal que ∀x [x ∈ A ⇒ x ≤ a ] ou seja, a é o máximo de A se dominar todos os outros elementos de A. Note-se que se a ordem ≤ não for total pode acontecer que não exista um 50 elemento a ∈ A comparável com todos os elementos x ∈ A nos termos acima indicados: neste caso A não possuirá máximo. Um elemento a ∈ A diz-se maximal de (A,≤) se se verificar a condição ∀x∈A [ a ≤ x ⇒ x = a ] ou, equivalentemente, ¬∃x∈A [ a ≤ x ∧ x 6= a ] Isto é, a ∈ A é um elemento maximal de (A,≤) se não existir nenhum outro elemento em A que o domine estritamente. De modo semelhante, chama-se mı́nimo de A ao elemento b ∈ A, se existir, que satisfaz a condição ∀x [x ∈ A ⇒ b ≤ x ] ou seja, b é o mı́nimo de A se preceder todos os outros elementos de A. Tal como no caso anterior um conjunto ordenado pode não possuir mı́nimo. Um elemento b ∈ A diz-se minimal se se verificar a condição ∀x∈A [x ≤ b ⇒ x = b ] ou, equivalentemente, ¬∃x∈A [x ≤ b ⇒ x 6= b ] Isto é, b ∈ A é um elemento minimal de (A,≤) se não existir nenhum outro elemento em A que o preceda estritamente. Exemplo 1.39 (Diagramas de Hasse.) Seja A um conjunto finito com uma ordem parcial ≤ e considere-se o digrafo desta relação. Visto que ≤ é uma relação de ordem então é reflexiva e, portanto, em todos os vértices aparecerá um lacete. Para simplificar o diagrama neste caso suprimam-se todos os lacetes. Eliminando também todos os arcos que se obtêm por transitividade o digrafo resultante é o que se designa por diagrama de Hasse correspondente à ordem parcial ≤. 1. Seja A = {2, 3, 4, 6, 8, 12} e defina-se a relação ≤ pondo “x ≤ y se e só se x divide y”. Então 2 e 3 são elementos minimais e 8 e 12 são elementos maximais. O conjunto ordenado (A,≤) não possui mı́nimo nem máximo. Esta situação pode representar-se pelo diagrama de Hasse 51 (a) Descrever em extensão os conjuntos A×B, B ×A e A× C. (b) Dar exemplos de relações de A para B e de B para A com quatro ele- mentos. (c) Dar um exemplo de uma relação simétrica em C com três elementos. 3. Seja A = {1, 2, 3}. Para cada uma das relações R indicadas a seguir, deter- minar os elementos de R, o domı́nio e o contradomı́nio de R e, finalmente, indicar as propriedades que possui R. (a) R é a relação < em A. (b) R é a relação ≥ em A. (c) R é a relação ⊂ em P(A). 4. Sejam A,B,C e D conjuntos dados. Provar ou dar contra-exemplos para as seguintes conjecturas: (a) A× (B ∪ C) = (A×B) ∪ (A× C) (b) A× (B ∩ C) = (A×B) ∩ (A× C) (c) (A×B) ∩ (Ac ×B) = Ø (d) [A ⊆ B ∧ C ⊆ D] ⇒ A× C ⊆ B ×D (e) A ∪ (B × C) = (A ∪B)× (A ∪ C) (f) A ∩ (B × C) = (A ∩B)× (A ∩ C) (g) (A×B) ∩ (C ×D) = (A ∩ C)× (B ∩D) (h) A× (B\C) = (A×B)\(A× C) 5. Sejam A e B dois conjuntos e R e S duas relações de A para B. Mostrar que (a) D(R∪ S) = D(R) ∪D(S) (b) D(R∩S) ⊆ D(R)∩D(S) e dar um exemplo para mostrar que a igualdade não se verifica necessariamente. (c) I(R∪ S) = I(R) ∪ I(S) (d) I(R∩ S) ⊆ I(R) ∩ I(S) e dar um exemplo para mostrar que a igualdade não se verifica necessariamente. 6. Seja R uma relação num conjunto não vazio A. Sendo x ∈ A define-se a classe-R de x, denotada por [x]R , por [x]R = {y ∈ A : yRx} (a) Sendo A = {1, 2, 3, 4} e R = {(1, 2), (1, 3), (2, 1), (1, 1), (2, 3), (4, 2)} determinar [1]R , [2]R , [3]R e [4]R . (b) Mostrar que R é reflexiva se e só se ∀x∈A [x ∈ [x]R ]. (c) Mostrar que R é simétrica se e só se ∀x,y∈A [x ∈ [y]R ⇒ y ∈ [x]R ] 54 (d) Mostrar que ∀x∈A [ [x]R 6= Ø ⇔ I(R) = A ]. (e) Suponha-se que D(R) = A e R é simétrica e transitiva. Mostrar que ∀x,y∈A [[x]R ⊆ [y]R ⇒ xRy] Mostrar ainda que ∀x,y∈A [[x]R ⊆ [y]R ⇒ [x]R = [y]R ]. (f) Suponha-se que R é simétrica e transitiva. Mostrar que ∀x,y∈A [[x]R ∩ [y]R 6= Ø ⇒ [x]R = [y]R ] 7. Seja R uma relação de A para B e S uma relação de B para C. Então a relação composta S◦R é a relação constitúıda por todos os pares ordenados (a, c) tais que (a, b) ∈ R e (b, c) ∈ S. Sendo A = {p, q, r, s}, B = {a, b}, C = {1, 2, 3, 4}, R = {(p, a), (p, b), (q, b), (r, a), (s, a)} e S = {(a, 1), (a, 2), (b, 4)} determinar S ◦ R. 8. Seja R uma relação de A para B. Chama-se relação inversa R−1 de B para A ao conjunto de pares ordenados da forma (b, a) com (a, b) ∈ R. Mostrar que uma relação R num conjunto é simétrica se e só se R = R−1. 9. Mostrar que uma relação num conjunto é reflexiva se e só se a sua inversa for reflexiva. 10. Seja R a relação no conjunto A = {1, 2, 3, 4, 5, 6, 7} definida por (a, b) ∈ R ⇔ (a− b) é diviśıvel por 4 Determinar R e R−1. 11. Seja R a relação definida em IN1 por (a, b) ∈ R ⇔ b é diviśıvel por a Estudar R quanto à reflexividade, simetria, antisimetria e transitividade. 12. Quais das relações que se seguem são equivalências? (a) {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1)} (b) {(1, 2), (2, 2), (3, 3), (4, 4)} (c) {(1, 1), (2, 2), (1, 2), (2, 1), (3, 3), (4, 4)} 13. Seja R = {(x, y) : x, y ∈ ZZ e x− y é inteiro}. Mostrar que R é uma relação de equivalência em ZZ. 14. Seja A = {2, 3, 4, 5, . . .} um conjunto ordenado pela relação “x divide y. De- terminar todos os elementos minimais e todos os elementos maximais. 1.3.4 Funções Definição 1.44 Seja f ⊂ A × B uma relação de A para B. Se, para todo o x ∈ A existir um e um só y ∈ B tal que (x, y) ∈ f dir-se-á que f é uma 55 aplicação (ou função) de A em B; para significar que f é uma aplicação de A em B costuma escrever-se f : A → B e, neste caso, escreve-se y = f(x), dizendo-se que y ∈ B é a imagem por f de x ∈ A. Dada uma aplicação f : A → B, ao conjunto A também se dá o nome de domı́nio de f e com este significado representa-se por D(f) ≡ Df (ou, mais simplesmente, por D). Exemplo 1.45 Como exemplos de algumas relações que são funções e outras que o não são, considere-se A = {1, 2, 3, 4} B = {1, 2, 3, 4, 5} f = {(1, 2), (2, 3), (3, 4), (4, 5)} g = {(1, 2), (1, 3), (2, 4), (3, 5), (4, 5)} h = {(1, 1), (2, 2), (3, 3)} Então f , g e h são relações de A para B mas apenas f é uma função definida em A; g e h não são funções definidas em A a primeira porque tanto (1, 2) como (1, 3) são elementos de g e a segunda porque D(h) = {1, 2, 3} 6= A. A função f é particu- larmente simples, podendo ser descrita pela fórmula f(x) = x+1 qualquer que seja x ∈ A. Embora a maior parte das funções normalmente consideradas nas disciplinas de Cálculo sejam dadas de forma semelhante, em geral, não se podem especificar as funções deste modo; de facto, a maioria das funções que se podem definir não podem ser descritas de forma tão simples à custa de uma fórmula algébrica. O conjunto I(f) ≡ f(A) = {y ∈ B : [ ∃x [x ∈ A ∧ y = f(x) ] ]} designa-se por contradomı́nio da aplicação f . Se f(A) = B dir-se-á que f é uma aplicação sobrejectiva (ou aplicação sobre B); a aplicação f : A→ B diz-se injectiva (ou uńıvoca) se cada elemento de f(A) for imagem de um só elemento de A, isto é, f é injectiva se e só se ∀x,x′ [x, x′ ∈ A⇒ [x 6= x′ ⇒ f(x) 6= f(x′) ] ] o que significa que elementos distintos deA têm necessariamente imagens por f diferentes em f(A) ⊂ B. Se a aplicação f : A → B for simultaneamente 56 y1 = f(x1) e y2 = f(x2) e como x1 = x2, atendendo a que f é uma aplicação, tem-se que y1 = y2, o que mostra ser f−1 injectiva. Logo f−1 é bijectiva como se afirmou. (3) Como f : A→ B é uma bijecção então quaisquer que sejam x ∈ A e y ∈ B, y = f(x) é equivalente a x = f−1(y) donde vem ( f ◦ f−1 ) (y) = f(x) = y, ∀y∈B e( f−1 ◦ f ) (x) = f−1(y) = x, ∀x∈A o que prova a terceira parte do teorema. 2 A aplicação f−1 : B → A definida nos termos do Teorema 1.49 é chamada aplicação inversa ou rećıproca de f : A→ B. Exerćıcios 1.3.2 1. Seja A = {1, 2, 3, 4, 5, 6} e f : A→ A a função definida por f(x) = { x+ 1 se x 6= 6 1 se x = 6 (a) Determinar f(3), f(6), f ◦ f(3) e f(f(2)). (b) Determinar a pré-imagem de 2 e 1. (c) Mostrar que f é injectiva. 2. Mostrar que a função f : IR → IR dada por f(x) = x3 é injectiva e sobrejectiva enquanto que a função g : IR → IR dada por g(x) = x2 − 1 não é injectiva nem sobrejectiva. 3. Seja R uma relação de equivalência num conjunto não vazio A. Define-se uma relação α de A para A/R pondo α = {(x, [x]) : x ∈ A} (a) Mostrar que α é uma função definida em A. (b) Mostrar que α é sobrejectiva. (c) Em que condições será α injectiva? 4. Seja dada a função f : A → A que se sabe ser uma relação de equivalência. Que mais se pode dizer relativamente a f? 5. Seja f : IR → IR a função definida por f(x) = senx. (a) Mostrar que f não é injectiva. (b) Mostrar que a restrição de f ao intervalo [−π/2, π/2] é uma função injectiva. 6. Seja IR o conjunto dos números reais e f : IR → IR a função definida por f(x) = x2. (a) Qual é o domı́nio, o conjunto dos valores e o contradomı́nio de f? (b) Será f injectiva? 59 (c) Será f sobrejectiva? (d) Determinar o conjunto das pré-imagens de 4. (e) Determinar a imagem rećıproca do conjunto {t : 1 ≤ t ≤ 4}. 7. Sendo IR o conjunto dos números reais explicar porque é que as funções definidas por f(x) = 1 x− 2 e g(x) = √ x não são funções de IR em IR. 8. Sendo IN o conjunto dos números naturais e f : IN → IN a função definida por f(n) = 2n+ 5 mostrar que f é injectiva e determinar a função inversa. Será f sobrejectiva? E a função inversa será sobrejectiva? 9. Seja f : IR → IR definida por f(x) = x2 − 4. Determinar as imagens dos seguintes conjuntos (a) {−4, 4, 5} (b) {4, 5} (c) {t : t ∈ IR ∧ t ≥ 0} 10. Dar um exemplo de uma função real de variável real tal que (a) seja injectiva e sobrejectiva, (b) não seja injectiva nem sobrejectiva. 11. Seja X = {p, q, r}, Y = {a, b, c, d} e Z = {1, 2, 3, 4} e sejam g : X → Y definida pelo conjunto dos pares ordenados {(p, a), (q, b), (r, c)} e f : Y → Z definida pelo conjunto de pares ordenados {(a, 1), (b, 1), (c, 2), (d, 3)}. Escrever a função com- posta f ◦ g sob a forma de um conjunto de pares ordenados. 12. Sendo A = {p, q, r} e f : A→ A definida por f(p) = q, f(q) = p e f(r) = q. Dar a função f ◦ f sob a forma de um conjunto de pares ordenados. 13. Seja A e f como no problema anterior. Definir g = f ◦ f ◦ · · · ◦ f (nvezes) Descrever g como um conjunto de pares ordenados quando n é par e quando n é ı́mpar. 14. Sejam f : B → C e g : A→ B. Mostrar que (a) se f e g são injectivas então f ◦ g é injectiva. (b) se f e g são sobrejectivas então f ◦ g é sobrejectiva. 60 (c) suponha-se que f ◦ g é injectiva. Será f necessariamente injectiva? Será g necessariamente injectiva? (d) suponha-se que f ◦g é sobrejectiva. Será f necessariamente sobrejectiva? Será g necessariamente sobrejectiva? 15. Se f(x) = ax + b e g(x) = cx + d e f ◦ g = g ◦ f , determinar uma equação que relacione as constantes a, b, c, d. 16. Seja f : X → Y e suponha-se que A e B são subconjuntos de X. Mostrar que (a) f(A ∪B) = f(A) ∪ f(B) (b) f(A ∩B) ⊆ f(A) ∩ f(B) 17. Nas condições do problema anterior, mostrar que se f for injectiva então f(A∩B) = f(A) ∩ f(B). 18. Seja f : A → B onde A e B são conjuntos finitos com a mesma cardinalidade. Mostrar que f é injectiva se e só se for sobrejectiva. 19. Seja A um subconjunto do conjunto universal U . A função f A : U → {0, 1} definida por f A (x) = { 1 se x ∈ A 0 se x 6∈ A chama-se função caracteŕıstica do conjunto A. Sejam A e B dois subconjuntos de U . Mostrar que para todo o x ∈ U (a) f A∩B (x) = fA(x) · fB (x) (b) f A∪B (x) = fA(x) + fB (x)− fA(x) · fB (x) (c) f A (x) + f Ac (x) = 1 (d) f C (x) = f A (x) + f B (x) − 2f A (x) · f B (x) onde C designa a diferença simétrica de A e B. 1.4 Álgebras de Boole Se se observarem bem as propriedades das operações com conjuntos e as propriedades das operações lógicas do cálculo proposicional, chegar-se-á à conclusão de que, sob um ponto de vista formal, elas são muito semelhantes. (Recordar, por exemplo, a distributividade das operações ∪,∩ e a distribu- tividade das operações ∨,∧ ou as leis de Morgan relativas às operações ∪,∩ e as leis de Morgan relativas às operações ∨,∧.) Este facto mostra que a 61 e 0 que estão também trocados. Assim, numa álgebra de Boole, qualquer teorema que envolva as operações binárias tem sempre duas partes, cada uma das quais é dual da outra. Nas demonstrações de teoremas deste tipo que se seguem é suficiente provar uma (qualquer) das suas partes; a outra aparece por dualidade. Exerćıcios 1.4.1 1. Escrever as expressões duais das seguintes expressões numa álgebra booleana (a) xȳz̄ + xȳz (b) x(x̄+ y) 2. Escrever as igualdades duais das seguintes igualdades numa álgebra booleana (a) x+ xy = x (b) xȳ + y = x+ y Teorema 1.53 (Leis da idempotência.) Para todo o a ∈ B a+ a = a e a · a = a Demonstração: (a) a+ a = (a+ a) · 1 por B4 = (a+ a) · (a+ ā) por B5 = a+ (a · ā) por B3 = a+ 0 por B5 = a por B4 (b) a · a = (a · a) + 0 por B4 = (a · a) + (a · ā) por B5 = a · (a+ ā) por B3 = a · 1 por B5 = a por B4 Teorema 1.54 (Leis das identidades.) Para todo o a ∈ B a+ 1 = 1 e a · 0 = 0 64 Demonstração: (a) a+ 1 = 1(̇a+ 1) por B4 = (a+ ā) · (a+ 1) por B5 = a+ (ā · 1) por B3 = a+ ā por B4 = 1 por B5 (b) a · 0 = (a · 0) + 0 por B4 = (a · 0) + (a · ā) por B5 = a · (0 + ā) por B3 = a · ā por B4 = 0 por B5 Teorema 1.55 (Leis de absorção.) Quaisquer que sejam a, b ∈ B a+ (a · b) = a, a · (a+ b) = a Demonstração: (a) a+ (a · b) = (a · 1) + (a · b) por B4 = a · (1 + b) por B3 = a · 1 pelo teorema 1.54 = a por B4 (b) A segunda propriedade obtém-se por dualidade. 2 Teorema 1.56 (Involução.) Para todo o elemento a ∈ B (ā) = a Demonstração: (a) Seja b ∈ B qualquer. Então por B5 b̄+ b = 1 e b̄ · b = 0 Fazendo, em particular, b = ā obter-se-á (ā) + ā = 1 e (ā) · ā = 0 (1.13) Por outro lado, por B5, tem-se também a+ ā = 1 e a · ā = 0 (1.14) pelo que, comparando (1.13) com (1.14) se obtém o resultado pretendido. 2 65 Teorema 1.57 (Leis de Morgan.) Para todo o par de elementos x, y ∈ B x · y = x̄+ ȳ e x+ y = x̄ · ȳ Demonstração: Considerando, por um lado, a expressão (x · y) · (x̄+ ȳ), vem (x · y) · (x̄+ ȳ) = (x · y) · x̄+ (x · y) · ȳ por B3 = x · (y · x̄) + x · (y · ȳ) por B2 = x · (x̄ · y) + x · (y · ȳ) por B1 = (x · x̄) · y + x · (y · ȳ) por B2 = (0 · y) + (x · 0) por B5 = 0 pelo teorema 1.54 Por outro lado, considerando a expressão (x · y) + (x̄+ ȳ) (x · y) + (x̄+ ȳ) = (x̄+ ȳ) + (x · y) por B1 = [x̄+ ȳ) + x] · [(x̄+ ȳ) + y] por B3 = [x+ (x̄+ ȳ)] · [(x̄+ ȳ) + y] por B1 = [(x+ x̄) + ȳ] · [x+ (y + ȳ)] por B2 = (1 + ȳ) · (x+ 1) por B5 = 1 pelo teorema 1.54 Tem-se então (x · y) · (x̄+ ȳ) = 0 e (x · y) + (x̄+ ȳ) = 1 pelo que, tendo em conta B5, x · y = x̄+ ȳ A segunda proposição obtém-se por dualidade. 2 Exemplo 1.58 (Circuitos com interruptores.) Sejam x, y, . . . interrupto- res eléctricos e suponha-se que x, x̄ designam sempre dois interruptores com a pro- priedade de que se um está ligado o outro está desligado e vice-versa. Dois interruptores, x e y, por exemplo, podem ser ligados por fios, em série ou em paralelo, como segue • x y • • x y • o que se denota por x · y (ou, simplesmente, xy) e x + y, respectivamente. Um circuito booleano é um arranjo de fios e interruptores que pode ser montado com o uso repetido de combinações em série e em paralelo podendo, portanto, ser descrito pelo uso dos sinais + e · (ou simples justaposição). Assim, 66 Exemplo 1.61 Determinar a expressão booleana correspondente ao seguinte cir- cuito • x ȳ z u v x y z̄ ȳ u • (x+ ȳ + z)uv(yz̄ + x+ ȳu) Exerćıcios 1.4.2 1. Desenhar os circuitos com interruptores que realizam as expressões booleanas que se seguem sem efectuar qualquer simplificação prévia. (a) xyz + xy(zw + st) (b) x+ y(z + wt) + su (c) x[y(z + w) + z(u+ v)] (d) (x+ ȳ + z)(x+ yz̄) + z̄w + w(ȳ + z) (e) (xy + xȳz + xz̄)z (f) xz + ȳ + ȳz + xȳz (g) (xy + z)(y + z) + z (h) x̄z + x̄y + z̄ 2. Determinar as expressões que representam algebricamente os seguintes cir- cuitos: (a) • a b c d e f g h • (b) • a b a c ā b̄ c̄ ā b c̄ • 69 (c) • u w y x s y y x t z • Exerćıcios 1.4.3 1. Seja A um conjunto qualquer e P(A) o conjunto das partes de A. Verificar que B ≡ (P(A),∪,∩) constitui uma álgebra de Boole quando, para cada x ∈ P(A) se define x̄ = A\x. 2. Mostre que o conjunto {a, b, c, d} com as operações definidas pelas tabelas seguintes é uma álgebra de Boole. + a b c d a a b b a b b b b b c b b c c d a b c d · a b c d a a a d d b a b c d c d c c d d d d d d 3. No conjunto ZZ considere as operações +, · e complementação definidas, para a, b ∈ ZZ quaisquer, por a+ b = max{a, b} aḃ = min {a, b} ā = −a Verifique se o sistema (ZZ,+, ·) constitui ou não uma álgebra de Boole. 1.4.2 Funções booleanas Chama-se função booleana de n variáveis booleanas x1, x2, . . . , xn a uma aplicação de {0, 1}n em {0, 1}. A função de três variáveis f(x1, x2, x3) = x1 + x̄2x3 onde x1 ∈ {0, 1}, x2 ∈ {0, 1} e x3 ∈ {0, 1} e as operações são entendidas no sentido booleano, isto é, sujeitas às tabelas 70 x y xy x+y 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 e x x̄ 1 0 0 1 é um exemplo de uma função booleana de três variáveis booleanas. A função f(x1, x2, x3) tem a seguinte tabela de valores x1 x2 x3 x̄2 x̄2x3 f(x1, x2, x3) 1 1 1 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 Por vezes é conveniente expressar uma função na chamada forma canó- nica que é uma expressão constitúıda por produtos cada um dos quais contém todas as variáveis (com ou sem barra). Por exemplo, a função g(x1, x2, x3) = x1x2x̄3 + x1x2x3 é uma função booleana na forma canónica. Para converter uma dada função na forma canónica pode usar-se a lei de complementação 1 = x+ x̄ de forma adequada. Assim, considerando de novo a função f(x1, x2, x3) dada acima, tem-se o seguinte f(x1, x2, x3) = x1 + x̄2x3 = x1 · 1 + x̄2x3 = x1(x2 + x̄2) + x̄2x3 = x1x2 + x1x̄2 + x̄2x3 = x1x2(x3 + x̄3) + x1x̄2(x3 + x̄3) + (x1 + x̄1)x̄2x3 = x1x2x3 + x1x2x̄3 + x1x̄2x3 + x1x̄2x̄3 + x1x̄2x3 + x̄1x̄2x3 = x1x2x3 + x1x2x̄3 + x1x̄2x3 + x1x̄2x̄3 + x̄1x̄2x3 71 • a b c x y x y ā b̄ c̄ • Este circuito é representado pela função booleana f(x, y, a, b, c) = (xy + abc)(xy + ā+ b̄+ c̄) a qual se pode simplificar da seguinte forma f(x, y, a, b, c) = (xy + abc)(xy + ā+ b̄+ c̄) = xyxy + xyā+ xyb̄+ xyc̄+ abcxy + abcā+ abcb̄+ abcc̄ = xy + xyā+ xyb̄+ xyc̄+ abcxy = xy(1 + ā+ b̄+ c̄+ abc) = xy O circuito simplificado equivalente tem então a forma • x y • Por vezes, no processo de simplificação, é mais fácil reconhecer qual é o procedimento a seguir na função dual do que na função original. Este facto sugere um novo processo de simplificação: toma-se o dual de f , denotado por d(f), simplifica-se d(f) e finalmente tomando de novo o dual obtém-se geralmente uma forma simplificada da função original, Exemplo 1.65 Simplificar o circuito • b̄ c̄ d̄ ā b c̄ a c̄ c d̄ a b̄ c d c b • 74 Este circuito é representado pela função f(a, b, c, d) = bc+ ab̄cd+ cd̄+ ac̄+ ābc̄+ b̄c̄d̄ Sendo g(a, b, c, d) = bc+ ab̄cd+ cd̄ h(a, b, c, d) = ac̄+ ābc̄+ b̄c̄d̄ então f(a, b, c, d) = g(a, b, c, d) + h(a, b, c, d) Considerando o dual de g d(g) = (b+ c)(a+ b̄+ c+ d)(c+ d̄) = (ab+ bb̄+ bc+ bd+ ac+ b̄c+ c+ cd)(c+ d̄) = abc+ abd̄+ bcc+ bcd̄+ bcd+ bdd̄+ acc+ acd̄+ b̄cc+ b̄cd̄+ cc+ cd̄+ ccd+ cdd̄ = abc+ abd̄+ bc+ bcd̄+ bcd+ ac+ acd̄+ b̄c+ b̄cd̄+ c+ cd̄+ cd = abc+ abd̄+ bc(1 + d̄+ d) + ac(1 + d̄) + b̄c(1 + d̄) + c(1 + d̄) + cd = abc+ abd̄+ bc+ ac+ b̄c+ c+ cd = (a+ 1)bc+ abd̄+ ac+ (b̄+ 1 + d)c = bc+ abd̄+ ac+ c = (b+ a+ 1)c+ abd̄ = c+ abd̄ e tomando de novo o dual, vem g(a, b, c, d) = c(a+ b+ d̄) Por outro lado, d(h) = (a+ c̄)(ā+ b+ c̄)(b̄+ c̄+ d̄) = (aā+ ab+ ac̄+ āc̄+ bc̄+ cc̄)(b̄+ c̄+ d̄) = abb̄+ abc̄+ abd̄+ ab̄c̄+ ac̄c̄+ ac̄d̄+ āb̄c̄+ ac̄c̄+ ac̄d̄+ bb̄c̄+ bc̄c̄+ bc̄d̄+ c̄b̄+ c̄c̄+ c̄d̄ = abc̄+ abd̄+ ab̄c̄+ ac̄+ ac̄d̄+ āb̄c̄+ ac̄+ bc̄+ bc̄d̄+ b̄c̄+ c̄+ c̄d̄ = abc̄+ abd̄+ (1 + a+ ā)b̄c̄+ ac̄(1 + d̄) + bc̄(1 + d̄) + c̄(1 + d̄) = abc̄+ abd̄+ b̄c̄+ ac̄+ bc̄+ c̄ = (ab+ b̄+ a+ b+ 1)c̄+ abd̄ = c̄+ abd̄ e, portanto, tomando de novo o dual h(a, b, c, d) = c̄(a+ b+ d̄) 75 Consequentemente, tem-se f(a, b, c, d) = c(a+ b+ d̄) + c̄(a+ b+ d̄) = a+ b+ d̄ pelo que o circuito simplificado equivalente é • d̄ b a • Exerćıcios 1.4.5 Simplificar os circuitos seguintes: 1. • c x b̄ c ā c a b c x̄ • 2. • a b c a b a c b a • 76 considerada um teorema dentro da teoria (isto é, seja uma proposição ver- dadeira da teoria) torna-se necessário submetê-la a um teste designado por prova ou demonstração. Serão teoremas as proposições que satisfizerem positivamente aquele teste. Para provar uma primeira proposição, p1, os únicos argumentos que podem ser usados são os axiomas e as definições já estabelecidas; se p1 decorrer logicamente destes argumentos (isto é, se for demonstrada) então transforma-se num teorema, T1. Para provar uma nova proposição, p2, podem agora usar-se não só os axiomas e as definições esta- belecidas mas também o teorema T1; se a proposição p2 for demonstrada então transforma-se num teorema, T2. Este processo vai-se repetindo assim sucessivamente tal como já foi referido no caso das definições, isto é, uma demonstração mostra a veracidade de uma proposição por argumentos que se baseiam nos axiomas da teoria e nas definições e teoremas já estabelecidos. Note-se que, entendendo-se que uma proposição só é considerada ver- dadeira se puder ser demonstrada a partir dos axiomas da teoria e de teore- mas já demonstrados, isso significa que a veracidade de uma proposição de- pende directamente dos axiomas da teoria sob consideração; uma proposição pode ser um teorema numa certa teoria e não o ser noutra (por exemplo, em geometria euclidiana plana a proposição “a soma dos ângulos de um triângulo é igual a um ângulo raso” é um teorema, mas deixa de o ser no contexto de outras geometrias diferentes daquela). Neste sentido, numa teoria axiomática, a questão que se põe relativamente a uma dada proposição não é a de saber se ela traduz algum tipo de “verdade” mas sim a de saber se aquela proposição é ou não uma consequência lógica dos axiomas da referida teoria. 2.1.2 Os axiomas de Dedekind-Peano Como exemplo t́ıpico e relativamente bem conhecido de uma teoria axio- mática apresenta-se a Axiomática de Dedekind-Peano para os números natu- rais que servirá de base para a demonstração de algumas das suas con- sequências elementares. A construção axiomática de Dedekind-Peano do conjunto dos números na- turais parte de três termos primitivos – zero, número natural e sucessor – e de cinco axiomas que os relacionam: N1 O zero é um número natural e representa-se por 0. N2 Cada número natural n tem um e um só sucessor, represen- tado por suc(n), que é também um número natural. 79 N3 O zero não é sucessor de nenhum número natural. N4 Se m,n são dois números naturais tais que suc(m) = suc(n) então m = n. N5 Seja A um conjunto de números naturais. Se A for tal que (1) 0 ∈ A, e (2) ∀n [ n ∈ A ⇒ suc(n) ∈ A ], então A é o conjunto constitúıdo por todos os números naturais que é denotado por IN. O axioma N5 é a base de todas as demonstrações feitas pelo método de indução matemática (ou método de indução finita) que pode formular-se da seguinte maneira: Suponha-se que a cada número natural n ∈ IN se pode associar uma proposição denotada por p(n); suponha-se ainda que (a) p(0) é uma proposição verdadeira, e que (b) para todo o j ∈ IN, p (suc(j)) é verdadeira sempre que p(j) o seja. Então a proposição p(n) é verdadeira qualquer que seja o número natural n ∈ IN. De facto, seja X o conjunto dos números naturais n para os quais p(n) é uma proposição verdadeira. O conjunto X contém 0 por (a) e por (b) contém suc(j) qualquer que seja j ∈ X. Então, de acordo com o axioma N5, tem-se que X = IN o que significa que p(n) é uma proposição verdadeira qualquer que seja n ∈ IN como se afirmou. De acordo com esta axiomática são então números naturais os seguintes 0, suc(0), suc (suc(0)) , suc (suc (suc(0))) , . . . os quais, por comodidade de escrita, têm as seguintes designações mais usuais: 1 ≡ suc(0), 2 ≡ suc (suc(0)) = suc(1), . . .1 Exemplo 2.1 Mostrar, a partir da axiomática de Dedekind-Peano, que todo o número natural diferente do zero é sucessor de um número natural. Sendo A = {n ∈ IN : n = 0 ∨ ∃m [m ∈ IN ∧ n = suc(m) ] } então 1Denotar-se-á por IN1 o subconjunto de IN igual a IN\{0} e, de um modo mais geral, para qualquer p ∈ IN, denotar-se-á por INp o conjunto INp ≡ {n ∈ IN : n ≥ p}. 80 1. 0 ∈ A (pela definição do conjunto A) 2. Suponha-se que n ∈ A, n 6= 0. Então n = suc(m) para algum m ∈ IN. Consequentemente, suc(n) = suc(suc(m)) e como, por N2, suc(m) ∈ IN então suc(n) ∈ A. Dos dois argumentos precedentes, tendo em conta N5, vem A = IN ficando provada a afirmação. 2.1.3 Aritmética dos números naturais A aritmética dos números naturais baseia-se em duas operações: a adição e a multiplicação. Nenhuma destas operações recebe uma menção expĺıcita na Axiomática de Dedekind-Peano o que significa que as mesmas podem ser definidas em termos das noções já introduzidas. Tal modo de proceder apresenta, no entanto, um acréscimo de dificuldades pelo que se adoptará aqui o ponto de vista que consiste em introduzir as definições de adição e multiplicação em IN de forma axiomática podendo depois deduzir-se toda a aritmética dos números naturais fazendo repetido apelo ao prinćıpio da indução matemática. A adição de números naturais é uma operação interna, denotada pelo śımbolo +, que é definida recursivamente por A1 ∀n [n ∈ IN ⇒ [ n+ 0 = n ] ], A2 ∀n,m [m,n ∈ IN ⇒ [ n+ suc(m) = suc(n+m) ] ] podendo mostrar-se que existe uma e só uma operação interna definida sobre IN que satisfaça A1 e A2. Podem agora provar-se novas propriedades satisfeitas pelos elementos de IN partindo apenas das proposições aceites como verdadeiras até este momento. Teorema 2.2 A adição em IN é associativa. Demonstração: Seja X o conjunto de números definido por X ≡ {p ∈ IN : ∀m,n [m,n ∈ IN ⇒ [ (m+ n) + p = m+ (n+ p) ] ]} Como de A1 resulta (m + n) + 0 = m + n = m + (n + 0), para todo o m,n ∈ IN tem-se então que 0 ∈ X (2.1) 81 M1 ∀n [n ∈ IN ⇒ [ n · 0 = 0 ] ] M2 ∀n,m [m,n ∈ IN ⇒ [ n · suc(m) = n ·m+ n ], sendo, também neste caso, posśıvel provar que existe uma e uma só operação interna definida sobre IN0 que satisfaça M1 e M2. Teorema 2.6 A multiplicação em IN é distributiva à direita relativamente à adição, isto é, m(n+ p) = mn+mp quaisquer que sejam os números m,n, p ∈ IN. Demonstração: Seja X o conjunto de números definido por X ≡ {p ∈ IN : ∀m,n [m,n ∈ IN ⇒ [m(n+ p) = mn+mp ] ]}. Tendo em conta A1 e M1 tem-se para todos m,n ∈ IN que m(n + 0) = mn = mn+ 0 = mn+m0 o que mostra que 0 ∈ X. (2.9) Seja agora q ∈ X arbitrariamente fixado. Então quaisquer que sejam os números m,n ∈ IN, vem m(n+q) = mn+mq e, portanto, tendo em conta A2, M2, a hipótese de indução e o teorema 2.2, obtém-se sucessivamente m(n+ suc(q)) = m · suc(n+ q) = m(n+ q) +m = (mn+mq) +m = mn+ (mq +m) = mn+m · suc(q) donde resulta que ∀q [ q ∈ X ⇒ suc(q) ∈ X ] (2.10) De (2.9) e (2.10), tendo em conta o axioma N5, conclui-se que X = IN, ficando provado o teorema. 2 Teorema 2.7 A multiplicação em IN é associativa. Demonstração: Seja X o conjunto de números definido por X ≡ {p ∈ IN : ∀m,n [m,n ∈ IN ⇒ [ (mn)p = m(np) ] ]} Então, visto que quaisquer que sejam m,n ∈ IN, atendendo a M1, se tem, (mn)0 = 0 = m · 0 = m(n · 0) conclui-se que 0 ∈ X (2.11) 84 Seja q um elemento qualquer de X. Pela definição de X então tem-se que (mn)q = m(nq) quaisquer que sejam m,n ∈ IN e portanto, atendendo a M2, hipótese de indução e ao teorema 2.6, tem-se sucessivamente (mn) · suc(q) = (mn)q +mn = m(nq) +mn = m(nq + n) = m(n · suc(q)) o que prova que ∀q [ q ∈ X ⇒ suc(q) ∈ X ] (2.12) De (2.11) e (2.12), atendendo ao axioma N5 obtém-se X = IN, ficando provado, deste modo, o teorema. 2 Teorema 2.8 A multiplicação em IN é distributiva à esquerda relativamente à adição, isto é, (m+ n)p = mp+ np quaisquer que sejam os números m,n, p ∈ IN. Demonstração: Seja X o conjunto de números definido por X ≡ {p ∈ IN : ∀m,n [m,n ∈ IN ⇒ [(m+ n)p = mp+ np ] ]} De A1 e M1 tem-se, quaisquer que sejam m,n ∈ IN, que (m+ n)0 = 0 = 0 + 0 = m0 + n0 o que mostra que 0 ∈ X (2.13) Seja agora q ∈ X qualquer. Então, da definição de X, tem-se que (m + n)q = mq+ nq e, portanto, tendo em conta M2, hipótese de indução, teoremas 2.2 e 2.3, sucessivamente, vem (m+ n) · suc(q) = (m+ n)q + (m+ n) = (mq + nq) + (m+ n) = mq + (nq + (m+ n)) = mq + ((nq + n) +m) = mq + (n · suc(q) +m) = mq + (m+ n · suc(q)) = (mq +m) + n · suc(q) = m · suc(q) + n · suc(q) o que mostra que ∀q [ q ∈ X ⇒ suc(q) ∈ X ] (2.14) De (2.13) e (2.14), atendendo ao axioma N5, X = IN, ficando o teorema completa- mente demonstrado. 2 Teorema 2.9 A multiplicação em IN é comutativa. 85 Demonstração: (a) - Provar-se-á em primeiro lugar que qualquer que seja m ∈ IN se tem 0m = m0. Seja M≡ {m ∈ IN0 : 0m = m0}. Como 0 · 0 = 0 · 0 então tem-se imediatamente que 0 ∈M (2.15) Seja n ∈M qualquer. Então da definição de M resulta que 0 ·n = n · 0 e portanto, tendo em conta M1 e M2, a hipótese de indução o lema 2.4 e o teorema 2.8, vem sucessivamente 0 · suc(n) = 0 · n+ 0 = n · 0 + 1 · 0 = (n+ 1) · 0 = suc(n) · 0 donde resulta ∀n [ n ∈M⇒ suc(n) ∈M ] (2.16) Consequentemente de (2.15) e (2.16) e axioma N5 fica completamente provada a afirmação em (a). (b) - Para demonstrar o caso geral torna-se necessário provar primeiramente o seguinte resultado preliminar Lema 2.10 Qualquer que seja m ∈ IN tem-se 1 ·m = m. Demonstração: Seja M o conjunto de números M ≡ {m ∈ IN : 1 ·m = m}. De M1 resulta que 1 · 0 = 0 e portanto 0 ∈M (2.17) Seja n ∈ M qualquer. Então da definição de M tem-se que 1 · n = n e portanto tendo em conta também M2 vem 1 · suc(n) = 1 · n + 1 = n+ 1 = suc(n), o que mostra que ∀n [ n ∈M⇒ suc(n) ∈M ] . (2.18) De (2.17) e (2.18) e axioma N5 fica provado o lema. 2 Seja agora X o conjunto de números definido por X ≡ {n ∈ IN : [ ∀m [m ∈ IN ⇒ [m · n = n ·m ] ]} De (a) tem-se imediatamente 0 ∈ X. (2.19) Seja p ∈ X qualquer. Então da definição de X tem-se que mp = pm qualquer que seja m ∈ IN. Consequentemente, de M2, lema 2.10, hipótese de indução, lema 2.4 e teorema 2.8, vem m · suc(p) = mp+m = pm+ 1 ·m = (p+ 1)m = suc(p) ·m o que significa que ∀p [ p ∈ X ⇒ suc(p) ∈ X ] (2.20) De (2.19), (2.20) e axioma N5 fica provado o teorema. 2 86 2. ∀n∈Z [n ≥ p ⇒ [n ∈ A ⇒ n+ 1 ∈ A ] ] então, A = {n ∈ ZZ : n ≥ p} O prinćıpio de indução matemática usual é um caso particular deste enun- ciado no qual p = 0. Este prinćıpio é usado frequentemente em Matemática para provar propo- sições da forma ∀n [n ∈ INr ⇒ p(n) ] onde INr = {n ∈ ZZ : n ≥ r} e p(n) é uma fórmula com uma variável livre cujo domı́nio é INr. Considere-se, por exemplo, a seguinte proposição ∀n [ n ∈ IN1 ⇒ 1 + 2 + 3 + · · ·+ n = n(n+ 1) 2 ] cuja prova se pode fazer apelando ao prinćıpio de indução matemática gene- ralizado. Seja p(n) a fórmula 1 + 2 + 3 + · · ·+ n = n(n+ 1) 2 e A ⊆ IN o conjunto de verdade de p(n). Fazendo n = 1 é imediato comprovar que p(1) é uma proposição ver- dadeira e, portanto, 1 ∈ A. Suponha-se agora que n ∈ A, ou seja, que para um dado inteiro n > 1, fixado arbitrariamente, se verifica a proposição p(n) – hipótese de indução. Vejamos o que se passa com p(n+ 1). Ora 1 + 2 + 3+ · · · +n+ (n+ 1) = (1 + 2 + 3 + · · ·+ n) + (n+ 1) = n(n+ 1) 2 + (n+ 1) = (n+ 1) ( 1 2 n+ 1 ) = (n+ 1)(n+ 2) 2 e, portanto, da validade da proposição p(n) resulta a validade da proposição p(n + 1). Isto significa que se n ∈ A então n + 1 ∈ A. Pelo prinćıpio de indução pode concluir-se que A = IN1 o que significa que p(n) se verifica para todo o n = 1, 2, . . .. 89 Exemplo 2.12 Sendo x ≥ 0 um número real pretende-se mostrar que ∀n [n ∈ IN1 ⇒ (1 + x)n ≥ 1 + xn ] Por uma questão de comodidade denote-se por p(n) a fórmula (1 + x)n ≥ 1 + xn e aplique-se a p(n) o método de indução. Para n = 1 obtém-se 1 ≥ 1 o que mostra que p(1) é uma proposição verdadeira. Suponha-se, hipótese de indução, que para n > 1, arbitrariamente fixado, p(n) se verifica e considere-se então p(n+ 1): (1 + x)n+1 = (1 + x)n(1 + x) ≥ (1 + xn)(1 + x) = 1 + x+ xn + xn+1 ≥ 1 + xn+1 Então da validade de p(n) resulta a validade de p(n+1) e, portanto, pelo prinćıpio de indução matemática pode afirmar-se que p(n) se verifica qualquer que seja n = 1, 2, 3, . . .. Exemplo 2.13 Sendo n ∈ IN, n ≥ 13 pretende-se verificar que n2 < ( 3 2 )n (2.21) Designe-se por p(n) a fórmula (2.21). Fazendo n = 13, vem 132 = 169 < 194 < 1594323 8192 = ( 3 2 )13 e, portanto, p(13) é verdadeira. Suponha-se agora, hipótese de indução, que para n > 13, fixado arbitrariamente, se tem n2 < (3/2)n: então (n+ 1)2 = ( 1 + 1 n )2 n2 < ( 1 + 1 13 )2 n2 = 196 169 n2 < 3 2 n2 < 3 2 ( 3 2 )n = ( 3 2 )n+1 verificando-se, portanto, p(n + 1) sempre que se verifica p(n). Tendo em conta o prinćıpio de indução generalizado, pode concluir-se que n2 < ( 3 2 )n para todo o n ≥ 13. 90 Exerćıcios 2.2.1 1. Provar as seguintes proposições (a) ∀n [n ∈ IN ⇒ 12 + 22 + · · ·+ n2 = n(n+ 1)(2n+ 1)/6 ] (b) ∀n [n ∈ IN ⇒ 13 + 23 + · · ·+ n3 = (n(n+ 1)/2)2 ] (c) ∀n [n ∈ IN ⇒ 1 + 3 + 5 + · · ·+ (2n− 1) = n2 ] (d) ∀n [n ∈ IN ∧ n ≥ 2 ⇒ ∀x,y [xn − yn = (x − y)(xn−1 + xn−2y + · · ·+ xyn−2 + yn−1) ] ] (e) ∀n [n ∈ IN ⇒ 2 divide n(n+ 1) ] (f) ∀n [n ∈ IN ⇒ Dnx xn = n! ] (g) ∀n [n ∈ IN ⇒ 2n > n ] (h) ∀n [n ∈ IN ⇒ ∀a,b [ a, b ∈ IR ∧ a > b > 0 ⇒ an > bn ] ] (i) ∀n [n ∈ IN ⇒ 11·3 + 1 2·4 + · · ·+ 1 n(n+2) = 3n2+5n 4(n+1)(n+2) ] (j) 1 · 2 + 2 · 3 + 3 · 4 + · · ·+ n · (n+ 1) = n(n+ 1)(n+ 2)/3 (k) 11·2 + 1 2·3 + 1 3·4 + · · ·+ 1 n·(n+1) = n n+1 (l) n3 + 2n é diviśıvel por 3 qualquer que seja n ∈ IN (m) 7n − 1 é diviśıvel por 6 qualquer que seja n ∈ IN (n) 11n − 6 é diviśıvel por 5 qualquer que seja n ∈ IN (o) 6 · 7n − 2 · 3n é diviśıvel por 4 qualquer que seja n ∈ IN (p) 3n + 7n − 2 é diviśıvel por 8 qualquer que seja n ∈ IN 2. A sucessão (an)n∈IN é definida por{ a1 = 1 an+1 = an + 8n Descobrir uma fórmula fechada para an e prove a sua validade por indução. 3. Seja (an)n=1,2,... uma sucessão definida recursivamente por{ a1 = 1 an = an−1 + 2 √ an−1 + 1, n ≥ 2 Mostrar que an é um número inteiro qualquer que seja n ∈ IN. 4. Descobrir e provar por indução uma fórmula para[ 1 1 0 1 ]n 91