Mat Disc AULA05

Prévia do material em texto

Matemática Discreta - AULA05 - Prof. Rafael Matos 
 
Bibliografia utilizada: 
ROSEN, K. H. Matemática Discreta e suas aplicações. 
 
Tema: 
Quantificadores, predicados e validade. Apenas uma visão geral. 
Demonstração: procura por contra-exemplo, exaustão, direta. 
Demonstração: por contraposição, por absurdo. Exercícios de fixação. 
 
Notas: 
 
Demonstração 
 
A demonstração de um teorema é demonstrar que a implicação é uma tautologia. Não se trata 
de demonstrar que a conclusão é verdadeira, mas somente que a conclusão é verdadeira caso 
todas as suas componentes sejam verdadeiras. 
 
Em geral toda demonstração deve começar com as hipóteses, seguidas das tautologias e 
regras de inferência necessárias, até chegar à conclusão. 
 
Um ​teorema​ é uma proposição que é garantida por uma prova. 
Um ​axioma é uma proposição que se assume como verdadeira e que não precisa de prova. 
Uma ​conjectura​ é uma proposição que ainda não foi provada e nem refutada. 
 
Exemplo: 
Definição de par e ímpar: 
– n é par ⇔ ∃ (e existe) um inteiro k tal que ;kn = 2 
– n é ímpar ⇔ ∃ (e existe)um inteiro k tal que ;kn = 2 + 1 
 
Exemplos: 
(a) 0 é par? Sim, pois ;0 = 2 * 0 
(b) −301 é ímpar? Sim: ;01 − 51)− 3 = 2 * ( 1 + 1 
(c) Se a e b são inteiros, é par? Sim, mas por que? ;a b6 + 2 a b 3a b)6 + 2 = 2 * ( + 2 
(d) Se a e b são inteiros, então é ímpar. Por que? 0a b1 + 8 + 1 
;0a b 5a b)1 + 8 + 1 = 2 * ( + 4 + 1 
 
Técnicas de prova comuns 
 
A existência de um número sem fim de casos que verifique certas condições não constitui 
prova. Pode existir até um único caso que desfaça a prova proposta. 
 
Prova direta: conclusão é estabelecida através da combinação lógica dos axiomas, definições e 
teoremas já existentes. Toda demonstração direta deve começar com as premissas, seguidas 
das tautologias e regras de inferência necessárias, até chegar à conclusão; cada passo deve 
estar acompanhado de sua respectiva justificativa. 
 
Exemplo: 
 
Demonstrar que, se e , então .xx2 + 2 = 3 ax = 2 − 1 a2 = 1 
 
Considere então: 
xp : x2 + 2 = 3 
ar : x = 2 − 1 
q : a2 = 1 
 
O que deve-se demonstrar é que é proposição verdadeira ( V ).p )( ⋀ r → q 
Com efeito: 
1. xp : x2 + 2 = 3 - premissa. 
2. ar : x = 2 − 1 - premissa. 
3. e r (2a )p : (2a )− 1 2 + 2 − 1 = 3 - substituição. 
4. e rp : 4a2 = 4 - tautologia. 
5. q : a2 = 1 
6. Portanto, acabamos de mostrar que .p )( ⋀ r → q 
 
Assim, a demonstração direta consiste em demonstrar ou deduzir uma conclusão partir das 
premissas preexistentes, aplicando as equivalências tautológicas e as regras de inferência. 
 
Demonstração direta por contra-exemplo: 
 
As demonstrações deste tipo utilizam a equivalência lógica: 
 
"Não é verdade que, para todo elemento x que cumpra a propriedade , existe algum (x)p 
elemento x que não cumpre a propriedade ".(x)p 
 
Isto é, para demonstrar que não é verdade que se cumpra para todo x, é necessário, e (x)p 
suficiente, mostrar que existe pelo menos um x tal que não se cumpra .(x)p 
 
Exemplo: 
Demonstrar que, para todo natural n, tem-se .n + 1 = 5 
 
Demonstração: 
Assumindo que o argumento é falso, deve-se achar um número natural n tal que não 
cumpra .n + 1 = 5 
Se, por exemplo, considerar , logo , ou seja, realmente existe um número n = 6 6 + 1 = 5 
natural n tal que não seja verdade.n + 1 = 5 
Portanto, não é verdade que, para todo natural n, seja verdade que .n + 1 = 5 
 
Exemplo: 
Para um inteiro positivo n, prove ou encontre um contra-exemplo para a conjectura 
"para todo inteiro positivo , ".n !n ≤ n2 
 
Através da tabela de contra-exemplo com os valores: 
n !n n2 
1 1 1 
2 2 4 
3 6 9 
4 24 16 
 
 
Prova por indução: um caso base é provado e uma regra de indução é usada para provar uma 
série de outros casos (normalmente infinita). 
 
Exemplo: 
Prove por indução matemática que , ... 2n )1 + 3 + 5 + . + ( − 1 = n2 n ≥ 1 
 
Resposta: 
(a) Passo base: Para , . Portanto, o passo base é verdadeiro.n = 1 1 = 12 
(b) Passo indutivo: se a fórmula é verdadeira para , para então deve ser n = k k ≥ 1 
verdadeira para .n = k + 1 
 
– Hipótese indutiva: , ;.. 2k )1 + 3 + 5 + . + ( − 1 = k2 k ≥ 1 
– Deve-se mostrar que: , ;.. 2k ) 2k )1 + 3 + 5 + . + ( − 1 + ( + 1 = (k )+ 1 2 k ≥ 1 
Sabe-se então que: ;.. 2k ) 2k ) 2k )1 + 3 + 5 + . + ( − 1 + ( + 1 = k2 + ( + 1 = (k )+ 1 2 
 
Prova por contradição: é mostrado que se algum enunciado fosse verdadeiro, ocorreria uma 
contradição lógica, e portanto o enunciado deve ser falso. 
 
Demonstração de contradição por ​absurdo​: na demonstração por absurdo, assume-se o 
oposto do que se quer provar e, ao chegar a uma contradição, a prova é finalizada. 
Exemplo: Demonstrar por absurdo a proposição: “Se um número somado a ele mesmo 
é igual a ele mesmo, então esse número é 0”. Representando x por um número qualquer: 
 
A hipótese é e a conclusão é .x + x = x x = 0 
 
Para demonstrar por absurdo, supomos que e .x + x = x =x / 0 
 
Então, e . Se dividir ambos os lados da equação. por , obtém-se x2 = x =x / 0 x2 = x x 
, uma contradição. Portanto, é somente válido se .2 = 1 x + x = x x = 0 
 
Prova por exaustão: a conclusão é estabelecida dividindo o problema em um número finito de 
casos e provando cada um separadamente. 
 
Quando temos uma conjectura sobre uma coleção finita, ela pode ser provada verificando se 
ela é válida para cada elemento da coleção. Uma demonstração por exaustão significa que 
foram testados todos os casos possíveis. 
 
Exemplo: Provar a conjectura: "Se um inteiro entre 1 e 20 é divisível por 6, então também é 
divisível por 3." Como existe um número finito de casos, a conjectura pode ser provada 
mostrando que é verdadeira para todos os inteiros de 1 a 20, por exemplo, usando uma tabela. 
 
Prova pela negativa: a conclusão é uma refutação que prova ser falso o problema especificado 
(ou seja, é uma negação matemática). 
 
Prova por impossibilidade: a conclusão, neste caso, não significa responder se o problema do 
caso é verdadeiro ou falso e sim determinar se o problema pode ser resolvido ou se ele jamais 
terá uma resposta geral que o solucione. 
 
Prova por construção: consiste em construir um exemplo concreto com determinada 
propriedade para mostrar que existe algo com tal propriedade.