Indução Matemática e Definições Indutivas

Prévia do material em texto

LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 1 - Indução
1
Indução
Definições Indutivas
Prova por indução
Referência: Language, Proof and Logic
Jon Barwise e John Etchemendy, 1999
Capítulo: 16
Indução-2
Indução
n Métodos de prova já vistos
– relacionam-se directamente com as propriedades das conectivas e
quantificadores
n Excepções
– Prova por contradição: usa-se para qualquer tipo de fórmula
– Provas para afirmações numéricas
n Provar afirmações da forma
∀x [P(x) → Q(x)]
– Prova condicional geral já usada para este efeito
– Indução necessária quando P(x) tem definição indutiva
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 2 - Indução
Indução-3
Métodos indutivos e indução matemática
n No raciocínio científico:
– indução usada para retirar uma conclusão geral a partir de um
número finito de observações
n em termos lógicos: inferência não é justificada
n novas observações podem invalidar a conclusão
n Indução matemática
– Conclusão geral, válida para um número infinito de instâncias, é
justificada com uma prova finita
n Aplicação mais usual:
– Domínio dos inteiros
– indução aplicável porque a definição dos inteiros é naturalmente
indutiva
n Uso não restrito a este domínio
Indução-4
Imagem para a indução
n Cadeia de dominós
– quando se derruba o primeiro: todos caem
n Arranjo dos dominós -- definição indutiva
n Fazer cair todos -- provar teorema por indução
n Requisitos para que os dominós caiam todos:
– posições tais que quando um cai faz cair o seguinte (passo indutivo)
– o primeiro cai (passo de base)
n Número de peças que uma peça faz cair: sem restrições
– podem montar-se esquemas complexos
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 3 - Indução
Indução-5
Definições indutivas
n Exemplos anteriores
– definição de wff
– definição de termos aritméticos
n Esquema geral
– dizer como são os elementos “simples”
– dizer como gerar novos elementos partindo dos que já se têm
n Exemplo: definir ambig-wff
A1, A2, …, An símbolos proposicionais
¬ ∧ ∨ → ↔ conectivas
(1) Cada símbolo proposicional é uma ambig-wff
(2) Se p é ambig-wff, também ¬p é ambig-wff
(3) Se p e q são ambig-wff, p∧q, p∨q, p→q, p↔q também o são 
(4) As únicas ambig-wff são as geradas por aplicação repetida de (1), (2) e (3)
Indução-6
Definição indutiva
Cláusula de base
especifica os elementos básicos do conjunto a
definir
 Uma ou mais cláusulas indutivas
descrevem a forma de gerar novos elementos
 Cláusula final
estabelece que os elementos ou são básicos ou
gerados pelas cláusulas indutivas
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 4 - Indução
Indução-7
Inferência sobre definições indutivas
n A1 ∨ A2 ∧¬A3 é ambig-wff
n Prova:
A1, A2 e A3 são ambig-wff pela cláusula (1)
¬A3 é ambig-wff pela cláusula (2)
A2 ∧¬A3 é ambig-wff pela cláusula (3)
A1 ∨ A2 ∧¬A3 é ambig-wff pela cláusula (3)
Indução-8
Inferência com indução sobre definição indutiva
n Proposição 1: Toda a ambig-wff tem pelo menos 1 símbolo
proposicional
n Prova:
– Base:
n Cada símbolo proposicional contém 1 símbolo proposicional
– Indução:
n p e q são ambig-wff que contêm pelo menos 1 símbolo proposicional
n as ambig-wff geradas por (2) e (3) a partir destas também têm pelo
menos 1 símbolo proposicional:
n ¬p tem os símbolos proposicionais de p
n p∧q, p∨q, p→q, p↔q têm os símbolos proposicionais de p e de q
– Cláusula (4) justifica a conclusão: nada é ambig-wff excepto os
elementos base e as coisas geradas a partir deles aplicando (2) e (3)
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 5 - Indução
Indução-9
Prova por indução
n Forma da afirmação: condicional geral
n Antecedente: definido indutivamente
∀p [(p é ambig-wff) → Q(p)]
n Forma da prova
– Passo base: os elementos base satisfazem Q
– Passo indutivo: se alguns elementos base satisfazem Q, então o
mesmo acontece com os que são gerados pelas cláusulas indutivas
Indução-10
Uso de indução
n Proposição 2:
Nenhuma ambig-wff tem o símbolo ¬ imediatamente antes de
uma das conectivas ∧, ∨, →, ↔
∀p [(p é ambig-wff) → Q(p)]
Q: não ter ¬ imediatamente antes de uma conectiva binária
n Prova:
–Passo base: Q(p) verifica-se para as ambig-wff dadas por (1)
–Passo indutivo:
n Caso 1: por (2), se p tem propriedade Q, também ¬p
n Caso 2: por (3) se p tem propriedade Q, também p∧q, p∨q, p→q,
p↔q
n Problema: nenhum dos casos se pode provar
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 6 - Indução
Indução-11
Paradoxo do inventor
n Caso 1: não se pode provar
– →A1 verifica Q e ¬ →A1 não verifica
n Caso 2: não se pode provar
– A1¬ e A2 verificam Q e A1¬ ∨A2 não verifica
n Caso em que uma prova indutiva encrava
– Afirmação a provar é verdadeira
– Para prová-la tem de se provar algo mais forte
n Nova condição na Proposição 2:
– Q’: não começar por conectiva binária, não terminar em ¬ nem ter
¬ imediatamente antes de uma conectiva binária
– Caso 1: óbvio
– Caso2: por considerações acerca das propriedades de p e q
Indução-12
Cláusula final da definição indutiva
n Qual o estatuto da cláusula
(4) Nada é ambig-wff a menos que seja gerado por aplicações
sucessivas de (1), (2) e (3)
– Refere, para além de objectos que estão a ser definidos, as outras
cláusulas da definição
– usa noção de “aplicação repetida”
n Expressão em LPO:
– Directa para as cláusulas (1), (2) e (3)
� ...
� (2) ∀p [ambig-wff(p) → ambig-wff(concat(‘¬‘, p))]
� ...
– Não existe tradução deste tipo para (4)
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 7 - Indução
Indução-13
Definições indutivas em Teoria de Conjuntos
n Definições indutivas: podem exprimir-se na linguagem da
Teoria de Conjuntos
n Ambig-wff
– O conjunto S das ambig-wff é o menor conjunto que verifica
– (1) Cada símbolo de proposição está em S
– (2) Se p está em S, ¬p está em S
– (3) Se p e q estão em S, p∧q, p∨q, p→q, p↔q também estão
n (4) foi substituída pela referência a “o menor conjunto que
satisfaz (1), (2) e (3)”
Indução-14
Menor conjunto que ...
n Menor conjunto que verifica propriedade
– subconjunto de qualquer conjunto que verifica a propriedade
n Como sabemos se existe?
n Lema 3: Se S é a intersecção de uma colecção χ de conjuntos, cada um dos
quais verifica (1)-(3), S verifica (1)-(3)
n Prova:
– Base: cada conjunto em χ tem os símbolos proposicionais; então a sua
intersecção S também
– Passo indutivo:
n Considerar p pertencente a S; p está em cada conjunto de χ
n Cada conjunto em χ satisfaz (2), então ¬p está em cada conjunto de χ
n Sejam p e q de S; se p e q estão em S estarão em cada um dos conjuntos de χ
n Cada conjunto satisfaz (3), logo p∧q, p∨q, p→q, p↔q estão em S
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 8 - Indução
Indução-15
Provas
n Para provar que todas as ambig-wff estão em Q
– conjunto S das ambig-wff é subconjunto de Q S ⊆ Q
– Se Q satisfaz (1) - (3)
– S ⊆ Q pela definição
n Problema na prova da Proposição 2
– Q não satisfaz (2) ou (3)
– Q’ é conjunto mais restrito, verifica (1) - (3)
– S ⊆ Q’ ⊆ Q 
– logo S ⊆ Q : resultado pretendido
Indução-16
Indução sobre os naturais
n Definição indutiva dos números inteiros
1. 0 é um número natural
2. Se n é natural , n+1 é natural
3. Nada é um natural excepto os resultados da aplicação repetida de
(1) e (2)
n Em teoria de conjuntos
ℵ, o conjunto dos naturais, é o conjunto mais pequeno que satisfaz
(1) 0 ∈ ℵ
(2) Se n ∈ ℵ, n+1 ∈ ℵ
n Prova indutiva sobre ℵ
∀x [(x ∈ ℵ → x ∈ Q]
De:
(1) 0 ∈ Q
(2) Se n ∈ Q, n+1 ∈ Q
Pode concluir-se ℵ ⊆ Q
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 9 - Indução
Indução-17
Exemplo
n Proposição 4: Para todo o número natural n, a soma dos n
primeiros naturais é n(n+1)/2
n Prova:
∀n [n ∈ ℵ → n ∈ Q]
Q(n): a soma dos n primeiros naturais é n(n+1)/2
Caso base: a soma dos 0 primeiros naturaisé 0
Passo indutivo: Seja um número natural k para o qual Q(k) se verifica
Soma dos k primeiros naturais é k(k+1)/2
Soma dos primeiros k+1 naturais:
k(k+1)/2 + k+1= (k+1)(k/2 +1) = (k+1)(k+2)/2
Indução-18
Provar propriedades de programas
n Programa
void Function(int n)
{int x,y,z;
x = n;
z = 1;
y = 0;
 while( x>0 ) {
y = z+y;
z = z+2;
x = x-1;}
 printf(‘‘n^2 = %d, 2n+1 = %d’’, y, z);
}
n Provar: quando executado, o programa imprime os valores de n2 e 2n+1 para
uma entrada n
LEIC-FEUP 2001-2002
Teoria da Computação 2
Cristina Ribeiro/ Gabriel David 10 - Indução
Indução-19
Prova
n Para provar a propriedade do programa
n Lema 5: Dada uma entrada n, haverá exactamente n
iterações do ciclo while
– Prova: por indução
∀n [(n é entrada → Q(n)]
Q: há exactamente n iterações do ciclo
Caso base: n= 0 para x=0 não se entra no ciclo while
Passo indutivo: Seja um número natural k para o qual Q(k) se verifica
Se a entrada for k+1: x fica com k+1
Entra-se no ciclo, é executado 1ª vez e x decrementado
Agora x=k e o ciclo é executado k vezes
No total: ciclo executado k+1 vezes
Indução-20
Prova
n Lema 6: Depois de k iterações do ciclo while, y e z têm os
valores k2 e 2k+1, respectivamente
– Prova: por indução
∀k [k ∈ ℵ → Q(k)]
Q: depois de k iterações do ciclo while, y e z têm os valores k2 e 2k+1
Caso base: k= 0 ciclo não é executado, y=0= k2 e z=1=2k+1
Passo indutivo: Seja um número natural k para o qual Q(k) se verifica
Após mais uma iteração do ciclo while:
y = z+y = k2 + 2k+1 = (k+1)2
z = z+2 = 2k+1 +2 = 2(k+1) +1