MetodosdeProva FTC

Prévia do material em texto

Fundamentos de Teoria da 
Computação
Métodos de Prova
Rodrigo Yoshikawa Oeiras
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Definição
• Técnicas de demonstração: diretas, contraposição, 
por absurdo e indução.
• Nestas técnicas, precisamos provar que existe 
argumentos verdadeiros sob certos contextos. Na 
computação: algoritmos de grafos, álgebra de Boole, 
etc.
• Usando o conceito de FBF’s, os métodos de provas 
procuram mostrar a verdade de PQ.
Definição
• Vimos anteriormente que a FBF PQ é válida se é 
verdeira em todas as interpretações possíveis.
• Em muitos casos, PQ é verdadeira em certos 
contextos. 
• Se nestes contextos temos que se P é verdadeiro, 
então Q também é verdadeiro, neste caso PQ é um 
teorema naquele contexto.
• Desta forma, PQ pode representar uma verdade 
sobre algum assunto em específico.
• Podemos adicionar fatos adicionais para provar um 
teorema. Estes fatos seriam equivalentes à hipóteses 
adicionais (tal como vimos no método dedutivo).
• Não existe uma fórmula, um programa de computador 
ou um algoritmo geral e prático para a prova de 
teoremas.
• Para fazer as provas devemos usar o raciocínio.
• Queremos ganhar familiaridade com os métodos de 
prova, pois podem ser usados em várias áreas da 
computação.
Definição
• Os teoremas podem ser enunciados e demonstrados 
de forma menos formal do que os vistos de lógica de 
proposições e de predicados, com uma linguagem do 
dia-a-dia.
• Entretanto, a demonstração de um teorema deve 
apresentar a possibilidade de ser escrito de uma 
forma formal, pois assim teremos uma garantia que o 
teorema está correto.
• A seguir abordaremos os principais métodos de prova.
Definição
O que é uma prova?
• Suponha que queremos provar que PQ. 
• Para isso, podemos observar os valores lógicos 
fornecidos para P e Q.
• Com base nestas observações, se PQ é sempre 
verdadeiro, então PQ é válido no contexto em que 
você observou os valores de P e Q.
• O procedimento descrito caracteriza o raciocínio 
indutivo, que é baseado na conclusão de algo baseado 
na experiência.
• O uso de um raciocínio dedutivo é uma forma de 
verificar se a suposição sobre P e Q é verdadeira.
• Neste raciocínio, pode-se produzir um demonstração 
formal (ou informal) de PQ. 
• Caso não seja possível fazer a demonstração, teremos 
um contra-exemplo, mostrando que a conjectura 
(suposição) inicial é falsa.
• OBS: Mesmo sem um contra-exemplo conhecido a FBF 
PQ pode ser falsa. 
O que é uma prova?
Exemplo
Suposição: Para todo o inteiro positivo n, temos que:
 n! ≤ n2.
OBS: n! = n.(n-1).(n-2)...(1)
 
Exemplo
Suposição: Para todo o inteiro positivo n, temos que
 
n! ≤ n2
n! = n.(n-1).(n-2)...(1)
 
n n! n2 n!≤n2
1 1 1 Sim
2 2 4 Sim
3 6 9 Sim
4 24 16 Não
Falso!!
Contra-
exemplo
Suposições: 
1) Todos os animais vivendo no oceano são peixes.
2) Todo o inteiro menor do que 10 é maior do que 5.
Contra-exemplos:
1) Existem mamíferos vivendo no oceano, baleia.
2) Não, 4 é menor do que 10 e é menor do que 5.
Exemplo 2
Demonstração Exaustiva
• Dado uma coleção finita, podemos testar uma suposição 
para cada um dos elementos da coleção e mostrar que 
a suposição é verdadeira para esta coleção finita.
• Esta é uma demonstração por exaustão.
• Se a suposição for falsa, para algum elemento da 
coleção, a suposição é falsa. 
• Se for verdadeira, não haverá um elemento da coleção 
que não satisfaça a suposição.
Exemplo
• Prove a suposição: Para qualquer x que é um inteiro 
positivo menor do que 6, temos x2 ≤ 10 + 5x
Os elementos são: 1 2 3 4 5.
x x2 10+5x X2≤10+5x
1 1 15 Sim 
2 4 20 Sim
3 9 25 Sim
4 16 30 Sim
5 25 35 Sim
Demonstração Direta
• Vamos supor que devemos mostrar que PQ é 
verdadeira, isto é, devemos partir de P e chegar em Q.
• Neste caso temos a demonstração direta.
• Quando fazemos a demonstração direta, podemos ter 
uma demostração formal e uma demostração 
informal.
Exemplo
• Para exemplificar, suponha a seguinte suposição:
 (x)(y)[P(x)P(y)  P(x*y)], 
onde 
P(x) é “x é um número par”. 
• Como provar?
• Com uma sequência de demonstração formal.
• A sequência de demonstração formal deste exemplo tem 
24 passos.
● (x)(y)[P(x)P(y)  P(x*y)]
onde P(x) é “x é um número par”.
Podemos fazer uma sequência de demonstração formal:
1. (x)[P(x) (k)(k é um inteiro x=2k)] Fato sobre números
i.e. (k=1, x=2)(k=2,x=4)(k=3,x=6) .... 
2. P(x) (k)(k é um inteiro x=2k) 1, pu
3. P(y) (k)(k é um inteiro y=2k) 1, pu
4. P(x)  P(y) hip, temp
5. P(x) 4,simp
Exemplo
Exemplo
1 (x)[ P(x) (k)(k é um inteiro x=2k) ] Fato sobre números
2 P(x) (k)(k é um inteiro x=2k) 1, pu
3 P(y) (k)(k é um inteiro y=2k) 1, pu
4 P(x)  P(y) Hip. temp.
5 P(x) 4, simp
6 (k)(k é um inteiro x=2k) 2,5,mp
7 m é um inteiro x=2m 6, pe
8 P(y) 4, simp
9 (k)(k é um inteiro  y=2k) 3,8, mp
10 n é um inteiro  y=2n 9, pe
11 x=2m 7, simp
12 y=2n 10, simp
Exemplo
13 xy=(2m)(2n) Multiplicando 11 e 12
14 xy=2(2mn) Fato da multiplicação
15 m é inteiro 7,simp
16 n é inteiro 10, simp
17 2mn é inteiro 15, 16, fato sobre números
18 xy=2(2mn)2mn é inteiro 14,17, conj
19 (k)(k é um inteiroxy=2k) 18,ge e 2mn=k
20 (x)[ (k)(k é um inteirox=2k)P(x) ] fato sobre números
21 (k)(k é um inteiroxy=2k)P(xy) 20, pu
22 P(xy) 19, 21, mp
23 P(x)P(y) P(xy) hip. Temp.+22 Retirar hip. Temp. (passo 4)
24 (x)(y)(P(x)P(y) P(x*y)) 23, gu duas vezes
Exemplo
• (x)(y)( P(x)I(y)  P(x*y) )
onde P(x) é “x é um número par” e I(y) é “y é um número 
ímpar”.
Prova informal:
Suponha que x=2m e y=2n+1, onde n e m são números 
inteiros. 
Fazendo x*y=(2m)*(2n+1)=2(2mn+m)=2(2mn)+2m
 2(2mn)+2m= um número par somado a um numero par
Logo, xy é par.
Contraposição
• Uma técnica para provar PQ através da análise do 
valor lógico de Q’P’. 
• Isso é possível porque pode-se usar a relação 
tautológica: (PQ)↔(Q’P’).
O termo (Q’P’) é contrapositiva de (PQ). Por este 
motivo, temos que esta técnica de demonstração é 
chamada de demonstração por contraposição.
(QP) (P’Q’)
(PQ) (Q’P’)
Exemplo
• Prove: “se o quadrado de um inteiro é ímpar, então o 
inteiro tem que ser ímpar”.
Exemplo
• Prove: “se o quadrado de um inteiro é ímpar, então o 
inteiro tem que ser ímpar”.
Seja,
I(x): “x é um inteiro ímpar”;
P(x): “x é um inteiro par”.
 
O que devemos provar: I(n2)I(n).
Exemplo
• Prove: “se o quadrado de um inteiro é ímpar, então o 
inteiro tem que ser ímpar”.
Seja,
I(x): “x é um inteiro ímpar”;
P(x): “x é um inteiro par”.
 
O que devemos provar: I(n2)I(n).
Vamos supor que n é par, isso nos permite escrever: 
P(n) P(n2)
Usando a regra de contraposição:
[P(n) P(n2)]  {[P(n2)]’[P(n)]’}  I(n2)I(n)
(PQ) (Q’P’)
Exemplo
• Prove que se n+1 senhas diferentes forem distribuídas 
para n alunos, então algum aluno recebe 2 ou mais 
senhas.
• A contrapositiva da frase acima: Se n alunos recebem 
um número de senhas menor do que 2, então não foram 
distribuídas n+1 senhas.
Logo, por contraposição, se n+1 foram distribuídas, então 
um aluno recebeu 2 ou mais senhas.
Se e somente se
• Uma recíproca ocorre quando temos duas expressões 
parecidas, mas com argumentos “trocados”:
A  B é reciproca de B  A.
• Muitos teoremas são enunciados usando a frase “se e 
somente se”. Isso significa que deve-se demonstrar o 
condicional e sua recíproca.
Exemplo
• Prove que o produtoxy é ímpar se e somente se x e y 
são inteiros ímpares.
I(xy)I(x)I(y)
Onde I(x) é “x é ímpar”.
Devemos provar:
1. I(xy)I(x)I(y)
2. I(x)I(y)  I(xy)
Exemplo
1. I(xy)I(x)I(y)
[I(x)I(y)]’  [I(xy)]’
Exemplo
1. I(xy)I(x)I(y)
[ I(x)  I(y) ]’  [I(xy)]’
[I(x)]’  [I(y)]’  [I(xy)]’
Exemplo
1. I(xy)I(x)I(y)
[I(x)  I(y)]’  [I(xy)]’
[I(x)]’  [I(y)]’  [I(xy)]’
 P(x)  P(y)  P(xy)
Se x=2k, temos xy=(2k)y=2(ky).
Logo, xy é par.
Se y=2k, temos xy=x(2k)=2(xk).
Logo, xy é par.
P(x) “x é um número par.”
Exemplo
2. I(x)I(y)  I(xy)
Exemplo
2. I(x)I(y)  I(xy)
x=2m+1 (um número par mais 1)
y=2n+1 (um número par mais 1)
Exemplo
2. I(x)I(y)  I(xy)
x=2m+1
y=2n+1
xy=(2m+1)(2n+1)=4mn+2m+2n+1
Exemplo
2. I(x)I(y)  I(xy)
x=2m+1
y=2n+1
xy=(2m+1)(2n+1)=2(2mn + m + n)+1
Logo, xy é ímpar
Exemplo
• Prove que o produto xy é ímpar se e somente se x e y 
são inteiros ímpares.
I(xy)I(x)I(y)
Onde I(x) é “x é ímpar”.
Tem que ser provado:
1. I(xy)I(x)I(y)
2. I(x)I(y)  I(xy)
Desta forma, foram provadas os dois lados da expressão 
I(xy)I(x)I(y).
Prova por Absurdo (indireta)
• Vamos supor que queremos provar PQ, neste caso 
basta que provemos que PQ’0, onde consideramos 
que P e Q’ são verdadeiros. Portanto, temos algo 
verdadeiro levando a uma conclusão falsa, i.e., VF. 
• Assim, 
(PQ’0) leva a (PQ)
Exemplo
• Se um número somado a ele mesmo é igual a ele 
mesmo, então este número é igual a 0.
• Escrito de outra forma, isso significa que x+x=x. Logo, 
x=0.
(x+x=x)(x=0)
Para provar por absurdo, podemos reescrever como:
(x+x=x)(x=0)’0
Exemplo
• Se um número somado a ele mesmo é igual a ele 
mesmo, então este número é igual a 0.
• Isso significa que x+x=x. Logo, x=0.
(x+x=x)(x=0)
(x+x=x)(x=0)’0
(x+x=x)(x0)0
Se (x0) é verdadeiro, então podemos fazer:
x+x=x  2x=x  2=x/x  2=1 (obviamente é falso)
Então está provado !!
Exemplo 2
• Prove que 2 não é um número racional. O número 
racional é aquele que pode ser escrito na forma p/q, 
onde p e q são números inteiros e não possuem 
fatores em comum.
• 2=p/q 
• 2=p2/q2
• 2q2=p2
• Logo, o p2 tem que ser divisível por 2. Isso significa que 
o p deve ser um múltiplo de 2, p=2x e p2=4x. 
• Assim, temos que 2q2=4x o que nos leva a q2=2x (x é 
um inteiro).
Tanto p quanto q são múltiplos de 2.
Exemplo 2
• Prove que 2 não é um número racional. O número 
racional é aquele que pode ser escrito na forma p/q, 
onde p e q são números inteiros e não possuem 
fatores em comum.
• 2=p/q 
logo a raiz de 2 não pode ser um racional por absurdo.
Exercícios
1. Se n=25, 100 ou 169, então n é um quadrado perfeito e é uma 
soma de dois quadrados perfeitos.
2. Se n é um número inteiro par, 4≤n≤12, então n é uma soma de 
dois números primos.
3. Para 2 ≤ n ≤ 4, n2 ≥ 2n.
4. Use a prova direta para provar que a soma de dois inteiros pares é 
par.
5. Use a aprova por absurdo para provar que a soma de dois inteiros 
pares é par.
6. A soma de um inteiro par com um inteiro ímpar é um inteiro ímpar.
7. Prove que para todo o inteiro n, o número 3(n2+2n+3)-2n2, é um 
quadrado perfeito.
8. Use a prova por contraposição para mostrar que se um número x é 
positivo, então número x+1 também é positivo.
9. Se os números x e y são positivos, x<y se e somente se x2<y2.
10. Se o produto de dois inteiros não é divisível por um inteiro n, então 
nenhum dos inteiros é divisível por n.
11. O valor de A é a média dos n números x1,x2,..., xn. Prove que pelo
 menos um dos números x1,x2,..., xn é maior ou igual a A.
FIM
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41