Problema 1
De Lógica matemática y fundamentos (2012-13)
Revisión del 21:31 18 feb 2013 de Jalonso (discusión | contribuciones) (Página creada con '== Enunciado == Definir por recursión sobre fórmulas las siguientes funciones <ul> <li>nv(F) que calcula el número variables proposicionales que ocurren en la fórmula F. Por...')
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)