Lógica para Computação - Provas por indução sobre a complexidade - aula5 log cin

Prévia do material em texto

Lógica Matemática 
Para Computação 
Provas por indução sobre a complexidade 
da fórmula 
 Para toda fórmula   PROP, o número total de 
símbolos de  é no mínimo igual ao número de 
operadores de . 
 
 Seja t a função que calcula o número total de 
símbolos e o o número de operadores. 
 
 Vamos provar que t()  o() por indução sobre a 
complexidade de . 
 
 
Para toda fórmula   PROP, o número total de símbolos 
de  é no mínimo igual ao número de operadores de . 
1 + o() + o() 
o(()) = 1 + o() + o() 
o(()) = 1 + o() + o() 
o(()) = 1 + o() 
o() = 0, se  for atômica 
 
o(()) = 3 + t() + t() 
t(()) = 3 + t() + t() 
t(()) = 3 + t() + t() 
t(())= 3 + t() 
t() = 1, se  for atômica 
 
t(()) = 
o: PROP   ( n. total de operadores ) t: PROP   ( n. total de símbolos ) 
Provas por indução sobre a complexidade 
da fórmula 
 Para toda fórmula   PROP, o número de parênteses 
à esquerda de  é igual ao número de parênteses à 
direita de . 
 
 Seja e a função que calcula o número de parênteses 
à esquerda e d o número de parênteses à direita. 
 
 Vamos provar que e() = d() por indução sobre a 
complexidade de . 
 
 
Para toda fórmula   PROP, o número de parênteses à 
esquerda de  é igual ao número de parênteses à direita de 
. 
1 + e() + e() 
e(()) = 1 + e() + e() 
e(()) = 1 + e() + e() 
e(()) = 1 + e() 
e() = 0, se  for atômica 
 
e(()) = 1 + d() + d() 
d(()) = 1 + d() + d() 
d(()) = 1 + d() + d() 
d(())= 1 + d() 
d() = 0, se  for atômica 
 
d(()) = 
e: PROP   ( n. de par. à esq.) 
 
d: PROP   ( n. de par. À dir. ) 
Provas por indução sobre a complexidade 
da fórmula 
 Para toda fórmula   PROP, o número de 
subfórmulas de  é no máximo, duas vezes o número 
de operadores de  mais 1. 
 
 Seja s a função que calcula o conjunto das 
subexpressões de . E, o a função que calcula o 
número de operadores de  . 
 
 Vamos provar que |s()|  2.o() + 1 por indução 
sobre a complexidade de . 
 
 
Para toda fórmula   PROP, o número de subfórmulas 
de  é no máximo, duas vezes o número de operadores de 
 mais 1. 
 
{ () }  s()  s() 
s(()) = {()}  s()  s() 
s(()) = {()}  s()  s() 
s(()) = {()}  s() 
s() = { } , se  for atômica 
 
s(()) = 1 + o() + o() 
o(()) = 1 + o() + o() 
o(()) = 1 + o() + o() 
o(())= 1 + o() 
o() = 0, se  for atômica 
 
o(()) = 
s: PROP  (PROP) (subfórmulas) 
 
o: PROP   ( n. operadores ) 
Provas por indução sobre a complexidade 
da fórmula 
 
 Para toda fórmula   PROP, o posto (altura da árvore 
sintática) de  é no máximo igual ao número total de 
símbolos de . 
 
 Seja p a função que calcula o posto de . E, t a função 
que calcula o número de símbolos de  . 
 
 Vamos provar que p()  t(). 
 
 
 
Para toda fórmula   PROP, o posto (altura da árvore 
sintática) de  é no máximo igual ao número total de 
símbolos de . 
 
 
1 + max(p() ,p()) 
p(()) = 1 + max(p(),p()) 
p(()) = 1 + max(p(),p()) 
p(()) = 1 + p() 
p() = 0 , se  for atômica 
 
p(()) = 3 + t() + t() 
t(()) = 3 + t() + t() 
t(()) = 3 + t() + t() 
t(())= 3 + t() 
t() = 1, se  for atômica 
 
t(()) = 
p: PROP   (posto) 
 
t: PROP   ( n. símbolos )