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 )