Problema 1

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)

Soluciones colaborativas

--Pedro G. Ros

-- Primero definimos los operadores como tipo:

data F = Const Bool

          |Vari Char
          |Nega F
          |Conj F F
          |Impl F F

--Ahora las funciones: nv:: F -> Int nv (Vari a) = 1 nv (Impl a b) = (nv a) + (nv b) nv (Nega p) = 1 + (nv p) nv (Conj c d)= (nv c) + (nv d)

-- *Main> nv (Impl (Vari 'p') (Conj (Vari 'p') (Vari 'q'))) -- 3

prof::F-> Int prof (Vari a) = 0 prof (Impl a b) = 1 + (prof a) + (prof b) prof (Nega b) = 1 + (prof b) prof (Conj a b) = 1+ (prof a) + (prof b)

-- *Main> prof (Impl (Vari 'p') (Conj (Vari 'p') (Vari 'q'))) --2

{- La demostración por inducción es sencilla: Caso base: nv (Vari a) = 1 ≤ 2^(prof (Vari a)) = 2^0 = 1

Supongamos cierta la hipótesis para m y n dos proposiciones, y pongamos los casos:

nv (Nega m) = 1 + (nv m) ≤ 1+ 2^(prof m) y obviamente: prof (Nega m) = 1+ (prof m)≤ 1+ 2^(prof m)

Ya que estamos practicando la inducción haré que n ≤ 2^n. (i) Se cumple trivialmente en el 1. (ii) Suponemos cierto que se cumple en n. (iii) n≤ 2^n -> 2n≤2^(n+1), luego si (n+1)≤2n ya hemos acabado, cosa obvia si 1≤n.

nv (Impl m n) = (nv m) + (nv n) ≤ 2^(prof m) + 2^(prof n) prof (Impl m n) = 1+ (prof m) + (prof n), y también es trivial ver que 2^(prof Impl m n) es una cota superior a la dada por la hipótesis de inducción.

nv (Conj m n) == nv (Impl m n)

Por lo que hemos acabado y queda demostrado para todo tipo de fórmula F.

-}