Lógica matemática y fundamentos (2012-13) Lógica matemática y fundamentos (2012-13)

Enunciado

Definir por recursión sobre fórmulas las siguientes funciones

• nv(F) que calcula el número variables proposicionales que ocurren en la fórmula F. Por ejemplo,

  nv(p → p ∨ q) = 3.

• prof(F) que calcula la profundidad del árbol de análisis de la fórmula F. Por ejemplo,

  prof(p → p ∨ q) = 2.

Demostrar por inducción, que para toda fórmula F, nv(F) ≤ 2^prof(F)