02-Metodos_de_Prova

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Métodos e Estratégias de Prova
Prof. Eric Fernandes de Mello Araújo - DCC/UFLA
24 de março de 2011
1 Provas Diretas
Para provar que um argumento é válido, ou que sua conclusão decorre logi-
camente das hipóteses, devemos adotar uma metodologia onde é preciso (1)
assumir que as hipóteses são verdadeiras e (2) usar as regras de inferência e as
equivalências lógicas para determinar que a conclusão é verdadeira.
Exemplo 1: Consideremos, por exemplo, o seguinte argumento lógico:
�Se os cavalos voam ou as vacas comem alcachofras, então o mosquito é uma
ave nacional. Se o mosquito é uma ave nacional, então manteiga de amendoim
fica boa no cachorro quente. Mas manteiga de amendoim não fica boa no ca-
chorro quente. Portanto, vacas não comem alcachofras.�
1. Atribuir variáveis proposicionais para os componentes proposicionais do
argumento:
F: Cavalos voam
A: Vacas comem alcachofras
M: Mosquitos são aves nacionais
P: Manteiga de amendoim fica boa no cachorro quente
2. Represente o argumento formalmente utilizando as variáveis
1. (F ∨A)→M
2. M → P
3. ¬P
∴ ¬A
3. Use as hipóteses 1, 2 e 3 e as regras de inferência bem como quaisquer
equivalências lógicas para construir a prova
Afirmações Razões
1.(F ∨A)→M Hipótese 1
2.M → P Hipótese 2
3.(F ∨A)→ P passos 1 e 2 e silogismo hipotético
4. ¬P Hipótese 3
5. ¬(F ∨A) passos 3 e 4 e modus tollens
6. ¬F ∧ ¬A passo 5 e De Morgan
7. ¬A ∧ ¬F passo 6 e comutatividade de 'and'
8. ¬A passo 7 e simplificação
1
Q.E.D.
Exemplo 2: Se 6x + 9y = 101, então x ou y não são inteiros.
Prova: Assuma que 6x + 9y = 101 é verdade. A partir das regras de
álgebra, 3(2x + 3y) = 101. Mas 101/3 não é um número inteiro, o que nos leva
a conclusão de que 2x, 3y ou ambos não é um inteiro. Logo, um dos valores de
x ou y não é um inteiro. Q.E.D.
2 Provas Indiretas
Provas que não começam considerando as hipóteses verdadeiras e culminando na
conclusão são conhecidas como provas indiretas. Exemplos de provas indiretas
são as provas por contraposição, por contradição, entre outras.
Queremos provar a veracidade do seguinte teorema:
P → Q
sendo que P pode ser a conjunção de várias hipóteses. Dizemos que P → Q
é uma conjectura até que seja provada.
2.1 Prova Trivial
Se sabemos que Q é verdade, então P → Q é verdade.
Exemplo: Se está chovendo hoje, então o conjunto vazio é um subconjunto
de qualquer conjunto.
A afirmação é trivialmente verdadeira independetemente da verdade de P.
2.2 Prova por Vacuidade
Se sabemos que uma das hipóteses em P é falsa, então, por vacuidade, P → Q
é verdadeira.
Exemplo: Se eu sou rico e pobre, então o tsunami no Japão foi apenas uma
marolinha.
Isso poderia ser colocado na forma (P ∧ ¬P ) → Q, onde a hipótese é uma
contradição. Logo, Q decorre da hipótese por vacuidade.
2.3 Prova por Contraposição:
A prova por contraposição é a prova direta da contrapositiva. Para isso, deve-se
(1) considerar a equivalência lógica P → Q ≡ ¬Q→ ¬P , e (2) usar as regras de
inferência, axiomas e quaisquer equivalências lógicas para provar a veracidade
da contrapositiva.
Exemplo: Um número perfeito é aquele que é dado pela soma de todos os
seus divisores, exceto ele. Por exemplo, 6 é perfeito, uma vez que 6 = 3 + 2 + 1.
28 também é um número perfeito, pois 28 = 14 + 7 + 4 + 2 + 1.
Teorema: Um número perfeito não é primo.
2
Prova:
�Se p é um número perfeito (P), então p não é primo(Q)�.
P → Q ≡ ¬Q→ ¬P
Ou seja, queremos provar que �Se p é primo, então p não é perfeito�.
Então, assumimos que o número p é primo e mostramos que o mesmo não é
perfeito.
Porém os únicos divisores de um número primo são 1 e ele mesmo.
Assim, a soma dos divisores menos o número p é 1, e não é igual a p.
Portanto, p não pode ser perfeito. Q.E.D.
2.4 Prova por contradição ou Reductio ad Absurdum
Para provar por contradição, supomos P e ¬Q e prosseguimos com um raciocínio
válido até chegarmos a uma situação impossível. Queremos provar que �Se P,
então Q�. Para isso, mostramos que é impossível P ser verdadeiro enquanto Q
é falso. Queremos mostrar que P → ¬Q é impossível! Para isso (1) assuma
que a conclusão Q é falsa, ou seja, admitimos ¬Q, e (2) aceitamos a hipótese
P. Enfim, queremos provar que (P ∧ ¬Q) → Contradi¸ca˜o, o que é logicamente
equivalente a provar P → Q.
Teorema: Nenhum inteiro é ao mesmo tempo par e ímpar.
Prova: Reapresentando o teorema, pode-se dizer que �se x é um inteiro,
então não pode ser simultaneamente par e ímpar�.
Seja x um inteiro.
Suponhamos, por contradição, que x seja ao mesmo tempo par e ímpar.
Como x é par, sabemos que existe um inteiro k tal que x = 2k.
Como x é ímpar, sabemos que existe um inteiro z tal que x = 2z + 1.
Portanto, 2k = 2z + 1, ou k = z + 12 , de forma que k − z = 12 .
Note que k − z é inteiro, uma vez que ambos são inteiros, mas 12 não o é.
Isso é impossível. Chegamos, assim, a uma contradição, e nossa suposição
(de que x seja ao mesmo tempo par e ímpar) é falsa. Portanto, x não é simul-
taneamente par e ímpar, e a proposição está provada. Q.E.D.
2.5 Prova por casos
Quebra-se a premissa P → Q em uma disjunção equivalente na forma:
P1 ∨ P2 ∨ . . . ∨ Pn
Utiliza-se a tautologia
[(P1 → Q) ∧ (P2 → Q) ∧ . . . ∧ (Pn → Q)]↔ [(P1 ∨ P2 ∨ . . . ∨ Pn)→ Q]
onde cada uma das implicações Pi → Q é um caso. Nesse caso, deve-se
convencer o leitor de que os casos são inclusivos, ou seja, eles cobrem todas as
possibilidades, e estabelecer todas as implicações.
Exemplo: Seja
⊗
o operador que define o máximo em um conjunto de
inteiros:
3
Se a ≥ b então a⊗ b = max{a, b} = a = b⊗ a.
Teorema: A operação
⊗
é associativa.
Para todo a, b, e
(a
⊗
b)
⊗
c = a
⊗
(b
⊗
c).
Prova:
Sejam a, b e c inteiros arbitrários.
Então, um dos 6 casos a seguir deve manter (os casos são exaustivos):
1. a ≥ b ≥ c
2. a ≥ c ≥ b
3. b ≥ a ≥ c
4. b ≥ c ≥ a
5. c ≥ a ≥ b
6. c ≥ b ≥ a
Caso 1: a
⊗
b = a, a
⊗
c = a, e b
⊗
c = b.
Portanto,
(a
⊗
b)
⊗
c = a = a
⊗
(b
⊗
c).
Logo, a igualdade sustenta o primeiro caso.
Para os demais casos, segue-se o mesmo raciocínio.
Q.E.D.
2.6 Prova de Existência
Deseja-se estabelecer a verdade de:
∃xP (x).
2.6.1 Prova de existência construtiva
Define que P(c) é verdade para algum valor c no universo. Dessa forma, ∃xP (x)
é verdade pela generalização existencial (GE)
1
.
Exemplo: Existe uma solução inteira para a equação x2 + y2 = z2.
Prova: Escolha x=3, y=4 e z=5.
1
P(c) é verdade para algum elemento c ∴ ∃xP (x)
4
2.6.2 Prova de existência não-construtiva
Assume-se que não existe c que torne P(c) verdadeira e derive a contradição.
Exemplo:
Teorema: Números irracionais existem.
Prova: Assume-se que não existam números irracionais. Logo, todos os
números são racionais.
Logo, o conjunto de todos os números deve ser contável.
Então o conjunto dos números reais no intervalo [0, 1] é um conjunto contável.
Mas nós sabemos que esse conjunto não é contável.
Dessa forma, temos uma contradição.
Portanto, deve existir um número irracional. Q.E.D.
2.6.3 Prova por contra-exemplo
Lembremos que ∃x¬P (x)↔ ¬∀xP (x).
Para mostrar que ¬∀xP (x) é verdadeiro (ou que ∀xP (x) é falso) encontre
um c tal que ¬P (c) é verdadeiro ou P (c) é falso.
Nesse caso, c é chamado de contra-exemplo.
2.6.4 Prova de não-existência
Deseja-se verificar a verdade de ¬∃xP (x) (equivalente a ∀x¬P (x)). Para isso,
utilize uma prova por contradição, assumindo que existe um c tal que P(c) é
verdade.
2.7 Provas de Argumentos com Quantificador Universal
Deseja-se, aqui, verificar a verdade de
∀xP (x).
Assume-se que x é um elemento arbitrário do Universo, e mostramos que
P(x) deve ser verdade. Utilizando a Generalização Universal (GU)
2
.
Exemplo: Para o universo dos inteiros, x é par se e somente se
x2 é par.
Prova: O argumento quantificado é: ∀x[x é par ↔ x2é par]
Assumimos um x arbitrário.
Lembramos que P ↔ Q é equivalente a (P → Q) ∧ (Q→ P ).
Caso 1: Mostramos que se x é par, então x2também é par usando uma prova
direta.
Se x é par, então x = 2k para algum inteiro k.
Logo, x2 = 4k2 = 2(2k2).
2
Regra usada para concluir que P(c) é verdade para todos os elementos c do domínio.
Utilizamos a GU quando queremos mostrar que ∀xP (x) é verdade tomando um elemento
aleatório do domínio e mostrando que P(c) é verdade. Dessa forma, c deve ser arbitrário, ou
seja, devemos mostrar que não temos controle sobre a escolha de c, apenas que o mesmo se
encontra no domínio. ∀xP (x).P (x) ∴ ∀xP (x)
5
Ou seja, x2 também é divisível por 2.
Caso 2: Mostramos que se x2 é par, então x também é par.
Utilizando prova indireta:
Assumimos que x2 não é par. Se não é par, então é ímpar.
Logo, x = 2k + 1.
Então,
x2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1
que é um número ímpar.
Dessa forma, mostramos que x é par se e somente se x2 é par. Uma vez que
x foi arbitrário, o resultado decorre por GU. Q.E.D.
6