Tecnicas_Demonstracao

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
CENTRO DE DESENVOLVIMENTO TECNOLÓGICO – CDTec 
CURSO CIÊNCIA DA COMPUTAÇÃO 
CURSO DE ENGENHARIA DE COMPUTAÇÃO 
 
 
Sistemas Discretos I 
Prof. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum Loreto 
**************************************************************************************** 
TÉCNICAS DE DEMONSTRAÇÃO 
Teorema 
Um teorema é uma afirmação declarativa sobre matemática, para a qual existe uma prova. 
Uma prova é uma dissertação que mostra, de maneira irrefutável, que uma afirmação é 
verdadeira. 
 
Obs.: 
- Afirmação declarativa: uma sentença que expressa uma idéia sobre como alguma coisa é, 
como: Vai chover amanhã, ou o Internacional ganhou do Corinthians ontem a tarde. 
 
Os matemáticos fazem afirmações, tais afirmações se enquadram em três categorias: 
1) Afirmações que sabemos serem verdadeiras porque podemos prová-las – que 
chamamos de teoremas; 
2) Afirmações cuja veracidade não podemos garantir – que chamamos conjeturas; 
3) Afirmações falsas – que chamamos erros. 
 
Designações para um Teorema: 
A palavra teorema não deve ser confundida com teoria. 
� Um teorema é uma afirmação específica que pode ser provada. 
� Uma teoria é um conjunto mais amplo de idéias sobre um assunto em particular. 
 
Há designações alternativas que os matemáticos usam em lugar de teorema. 
A palavra teorema tem a conotação de importância e generalidade. 
 
Designações: 
� Resultado: uma expressão modesta, genérica para um teorema. 
� Fato: um teorema de importância bastante limitada. A afirmação “6 + 3 = 9” é um 
fato. 
� Proposição: um teorema de importância secundária. Uma proposição é mais 
importante ou mais geral do que um fato, mas não tem tanto prestígio quanto um 
teorema. 
� Lema: um teorema cujo objetivo principal é ajudar a provar outro teorema mais 
importante. Alguns teoremas exigem demonstrações complicadas. Frequentemente, 
podemos decompor em partes menores o trabalho de provar um teorema complicado. 
 2
Os lemas são as partes, ou instrumentos, usados para elaborar uma prova mais 
complicada. 
� Corolário: resultado com uma prova rápida, cujo passo principal é o uso de outro 
teorema provado anteriormente. 
� Alegação: análogo ao lema. Uma alegação é um teorema cuja afirmação em geral 
aparece dentro da prova de um teorema. O objetivo de uma alegação é ajudar a 
organizar os passos-chave de uma prova. 
 
Teorema e a Lógica 
Um teorema é uma proposição do tipo: 
p → q 
 
a qual prova-se ser verdadeira sempre (tautologia), ou seja, que: 
p ⇒ q 
 
As proposições p e q são denominadas hipótese e tese, respectivamente. 
 
 
Obs.: Teoremas são fundamentais em Computação e Informática e, em particular, no estudo 
da Matemática Discreta (ou Sistemas Discretos). 
 
Por exemplo: Um teorema permite verificar se uma determinada implementação é correta. Em 
outras palavras, um teorema pode ser visto como um algoritmo que, prova-se, sempre 
funciona. 
 
Em uma demonstração é fundamental identificar a hipótese e a tese, onde de fato p ⇒ q, a 
hipótese p é suposta verdadeira, consequentemente, a hipótese não deve ser demonstrada. 
Todas as teorias possuem um conjunto de premissas (hipóteses) que são supostas verdadeiras 
e sobre as quais todo o raciocínio é construído. 
 
É usual que um teorema seja apresentado na forma p ↔ q, entretanto sabe-se que 
p ↔ q ⇔ (p → q) ∧ (q → p). 
 
Dessa forma, uma técnica usual para demonstrar que p ↔ q é provar em separado a “ida” 
p → q e a “volta” q → p. 
 
Para um determinado teorema p → q, existem diversas técnicas para provar (demonstrar) 
que, de fato, p ⇒ q. 
 
Algumas Técnicas de demonstração: 
a) Prova Direta; 
b) Prova por Contraposição; 
c) Prova por Redução ao Absurdo ou simplesmente Prova por Absurdo; 
d) Prova por Indução. 
 
 
Obs.: A prova por indução é uma aplicação particular da Indução Matemática. 
 3
 
Para qualquer técnica de demonstração, deve-se ter atenção aos quantificadores. 
Por exemplo, para provar a proposição 
 
(∀x∈A)p(x) 
 
é necessário provar p(x) para todo x∈A. Logo, mostrar um determinado elemento a∈A não é 
uma prova, mas sim um exemplo, o que, neste caso, não constitui uma prova válida para 
todos os elementos de A. 
 
Entretanto, para o caso: 
 
(∃x∈A)p(x) 
 
basta provar que existe pelo menos um a∈A tal que p(a) é verdadeira, ou seja, um exemplo é 
uma prova. 
 
 
 
 
 
 
 
 
 
 
Uma prova é uma argumentação que mostra, de maneira indiscutível, que uma afirmação é 
verdadeira. 
 
 
a)Prova Direta 
 
Definição: Uma prova é dita Prova Direta ou Demonstração Direta quando pressupõe 
verdadeira a hipótese e, a partir desta, prova ser verdadeira a tese. 
 
Exemplo: Considere o teorema: a soma de dois números pares é um número par, 
ou seja, reescrevendo na forma de p →q: 
 
se n e m são dois números pares quaisquer, 
então n + m é um número par 
 
Inicialmente, sabe-se que qualquer número par n pode ser definido como n= 2r, para algum 
natural r. 
Suponha que n e m são dois números pares. Então existem r, s ∈ N tai que: 
 
n = 2r e m = 2s 
 
Então: 
n + m = 2r + 2s = 2(r+s) 
Como a soma de dois números naturais r +s é um número natural, vale n + m = 2(r+s). 
Logo, n + m é um número par. 
O que é uma Prova? 
Em ciência, a verdade surge da experimentação. Na lei, a verdade é avaliada por um 
julgamento e decidida por um juiz e/ou júri. No esporte, a verdade é a decisão dos 
juízes decorrente de sua capacidade. Em matemática temos a prova. 
 4
 
b)Prova por Contraposição 
A prova por contraposição baseia-se no seguinte resultado (denominado de contraposição): 
 
p → q ⇔ ¬q → ¬p. 
 
Definição: Uma prova é dita Prova por Contraposição ou Demonstração por Contraposição 
quando, para provar p → q, prova-se ¬q → ¬p, pois são formas equivalentes. 
Para provar ¬q → ¬p basta, a partir de ¬q, obter ¬p (prova direta). 
 
Exemplo: Para demonstrar o seguinte teorema: 
 
n! > (n+1) → n > 2 
 
pode-se, equivalentemente, demonstrar por contraposição que: 
 
n ≤ 2 → n! ≤ n+1. 
 
Para provar que n ≤ 2 → n! ≤ n+1, basta testar a proposição para os casos n=0, n=1 e 
n=2. 
 
 
c) Prova por Redução ao Absurdo 
 
A prova por redução ao absurdo baseia-se no resultado (denominado de redução ao absurdo): 
 
p → q ⇔ (p ∧ ¬q) → F 
 
Definição: Uma prova é dita Prova (Demonstração) por Redução ao Absurdo ou 
simplesmente Prova (Demonstração) por Absurdo quando a prova de p → q consiste em 
supor a hipótese p, supor a negação da tese ¬q e concluir uma contradição 
(em geral, q ∧¬q). 
 
Obs.: A técnica de demonstração conhecida como prova por contra-exemplo, é uma 
demonstração por absurdo. 
 
Exemplo: Considere o seguinte teorema: 
 
0 é o único elemento neutro da adição em N 
 
ou seja, reescrevendo na forma de p → q: 
 
se 0 é elemento neutro da adição em N. 
então 0 é o único elemento neutro da adição em N. 
 
Uma prova por redução ao absurdo é como segue: 
 
a)Suponha que (hipótese) 0 é elemento neutro da adição em N e que (negação da tese) 0 não 
é o único elemento neutro da adição em N. Seja e um elemento neutro da adição em N tal que 
e ≠ 0 (se 0 não é o único, então existe um outro, diferente de 0); 
 
 5
b) Então: 
- como 0 é elemento neutro, para qualquer n ∈ N, vale n = 0+ n = n + 0. Em particular, para 
n = e, vale e = 0 + e = e + 0 
- como e é elemento neutro, para qualquer n ∈ N, vale n = n + e = e + n. Em particular, 
para n =0, vale 0 = 0 + e = e + 0 
- portanto, como e = 0 + e = e + 0 e 0 = 0+ e = e + 0, pela transitividade da igualdade, 
vale e = 0, o que é uma contradição, pois foi suposto que e ≠ 0. 
Logo, é absurdo suporque o elemento neutro da adição em N não é único. Portanto, 0 é o 
único elemento neutro da adição em N. 
 
 
Lógica x Álgebra dos Conjuntos 
 
Existe uma relação direta entre álgebra de conjuntos e os conetivos lógicos: 
 
Conetivo Lógico Operação sobre Conjuntos 
Negação Complemento 
Disjunção União 
conjunção Intersecção 
 
As relações lógicas podem ser associadas com as relações sobre conjuntos: 
 
Relação Lógica Relação sobre Conjuntos 
implicação Continência 
equivalência Igualdade 
 
Para reforçar esse relacionamento entre lógica e teoria dos conjuntos, observe que a 
equivalência (respectivamente, igualdade de conjuntos) pode ser definida em termos de uma 
dupla implicação (respectivamente, dupla continência, ou seja, a “ida” e a “volta”). 
 
Da mesma forma, as propriedades sobre os conetivos lógicos na lógica são válidas na teoria 
dos conjuntos, substituindo cada conetivo pela correspondente operação sobre conjuntos, com 
destaque para as seguintes: 
 
Conetivo Lógico Operação sobre Conjuntos 
Idempotência: ∧ e ∨ Idempotência: intersecção e união 
Comutativa: ∧ e ∨ Comutativa: intersecção e união 
Associativa: ∧ e ∨ Associativa: intersecção e união 
Distributiva: ∧ sobre ∨ 
∨ sobre ∧ 
Distributiva: intersecção sobre união 
União sobre intersecção 
Dupla negação DeMorgan 
Absorção Absorção 
 
Obs.: 
 Propriedades: 
- Idempotência: em matemática, um objeto é idempotente quando ele é o resultado de sua 
composição consigo mesmo, no sentido que se torna mais preciso. 
- Dois conjuntos X e Y são iguais se X ⊆ Y e Y ⊆ X. Nas provas, observe a analogia que 
existe entre as relações lógicas e as relações sobre conjuntos, como na tabela abaixo. As 
relações sobre conjuntos são traduzidas como relações sobre lógica, quando são trabalhadas, 
usando resultados lógicos construídos e retraduzidas com relações sobre conjuntos. 
 6
 
 
Relação Lógica Teoria dos Conjuntos 
Implicação/continência p ⇒ q A ⊆ B 
Equivalência/igualdade p ⇔ q A = B 
Exemplo: 
Prove as seguintes propriedades da operação de união (suponha A e B conjuntos): 
 
Elemento Neutro. A ∪ ∅ = ∅ ∪ A = A 
 
 Solução: Devemos provar essas duas igualdades. Pela transitividade da igualdade, os três 
termos serão iguais. 
Seja x ∈ A ∪ ∅. Então: 
x ∈ A ∪ ∅ ⇒ definição de união 
x ∈ A ∨ x ∈ ∅ ⇒ comutatividade da disjunção 
x ∈ ∅ ∨ x ∈ A ⇒ definição de união 
x ∈ ∅ ∪ A 
portanto, A ∪ ∅ ⊆ ∅ ∪ A (1) 
 
Seja x ∈ ∅ ∪ A. Então: 
x ∈ ∅ ∪ A ⇒ definição de união 
x ∈ ∅ ∨ x ∈ A ⇒ comutatividade da disjunção 
x ∈ A ∨ x ∈ ∅ ⇒ definição de união 
x ∈ A ∪ ∅ 
portanto, ∅ ∪ A ⊆ A ∪ ∅ (2) 
 
De (1) e (2), concluímos A ∪ ∅ = ∅ ∪ A. (3) 
 
Seja x ∈ A ∪ ∅. Então: 
x ∈ A ∪ ∅ ⇒ definição de união 
x ∈ A ∨ x ∈ ∅ ⇒ x ∈ ∅ é sempre F (F é elemento neutro 
da disjunção) 
x ∈ A 
portanto, A ∪ ∅ ⊆ A (4) 
 
Seja x ∈ A. Então: 
x ∈ A ⇒ adição: p ⇒ p ∨ q 
x ∈ A ∨ x ∈ ∅ ⇒ definição de união 
x ∈ A ∪ ∅ 
portanto, A ⊆ A ∪ ∅ (5) 
 
De (4) e (5), concluímos A ∪ ∅ (6) 
De (3), (6) e pela transitividade da igualdade, concluímos A ∪ ∅ = ∅ ∪ A = A.