Práctica 1: Lógica Proposicional (Lógica y Computabilidad)

Ejercicio 01

1. N, pues no tiene parentesis exteriores.
2. S, p1,p2,p3,p4,(p2 -> p3),(p1 v (p2 -> p3)).
3. S, p1,p2,¬p1,¬¬p1,(¬¬p1 -> p1).
4. N, pues no tiene parentesis exteriores.
5. S, p1,p2,p3,p5,(p2 -> p3),(p5 -> p2),(p1 v (p2 -> p3)).

Ejercicio 02

α es una f´ormula del CP sii admite una cadena de formaci´on, que por definici´on tiene longitud finita. A esa cadena le puedo agregar tantas copias de α al final omo desee, obteniendo as´ı cadenas de formaci´on para α de longitud arbitrariamente grande (siempre finita). Formalmente, supongamos que son finitas, y sea 1, . . . ,Xn la cadena de formaci´on m´as larga para una f´ormula �. Entonces, X1, . . . ,Xn,Xn tambi´en es una cadena de formaci´on para α, contradiciendo nuestra hip´otesis de finitud.

Ejercicio 03

Inducci´on en la complejidad de α. Si α es una variable proposicional, entonces s(α) = {α}. Si α = ¬P, para alguna f´ormula P, entonces s(α) = {α}Us(P). Si α = (P*Q), ntonces s(α) = {α}Us(P)Us(Q). Ojo: s(α) es el conjunto de subf´ormulas, y por ende no tiene en cuenta posibles repeticiones.

Ejercicio 04

Los conjuntos de subf´ormulas son f´aciles de calcular. S´olo hay que usar la definici´on del ejercicio anterior. Por ejemplo, para el caso 1, s(α) = {α, (p1 v (p2 -> p3)), p4, p1, (p2 -> p3), p2, p3}. Una cadena de formaci´on es minimal si no se le puede sacar ning´un eslab´on. Esto es, si se saca alguno, deja de ser cadena de formaci´on para la f´ormula. En s´ımbolos, decimos que una cadena de formaci´on X1, . . . ,Xn para Xn es minimal si X1, . . . , fXj , . . . ,Xn (la misma sin alg´un eslab´on Xj) no es una cadena de formaci´on para Xn. Intuitivamente (se formaliza en los ejercicios 6 y 7), las cadenas de formaci´on minimales van a ser aquellas que s´olo contengan subf´ormulas y no tengan repeticiones. Por eso, son permutaciones del conjunto mostrado, respetando las dependencias entre las subf´ormulas.

Ejercicio 05

Dado n, la f´ormula ¬· · · ¬p1, que tiene n−1 s´ımbolos ¬, tiene exactamente n subf´ormulas. Ve´amoslo por inducci´on en la longitud de la f´ormula. Sea long(α) = 1, entonces α = p1. Supongamos que para n−1 tenemos una f´ormula α tal que #s(α) = n − 1. Entonces, #s(¬α) = n + 1. En realidad, esta ´ultima afirmaci´on hace uso impl´ıcito de que todas las subf´ormulas de una f´ormula tienen a lo sumo su longitud. As´ı, al agregar una negaci´on (alargando la f´ormula), nos aseguramos de no estar repitiendo nada.

Ejercicio 06

Sean α y una cadena de formaci´on para ella. Hacemos inducci´on en la longitud de α. Si la longitud de α es 1, entonces α es una variable proposicional. En ese caso, su ´unica subf´ormula es ella misma, que tiene que aparecer al final de toda cadena de formaci´on para α.
Si long(α) = n > 1, α = ¬P o α = P * Q, con P y Q f´ormulas. Si α = ¬P, entonces sus subf´ormulas son α (que aparece en toda cadena) y las subf´ormulas de P. Pero P tiene que aparecer en alg´un lugar de la cadena, y si miramos una cadena hasta un determinado eslab´on, tenemos una cadena de formaci´on para la f´ormula que aparece en ese eslab´on. Entonces, por HI, todas las subf´ormulas de P est´an en la cadena, luego est´an todas las de α.
Si α = (P * Q), como empieza con un par´entesis, tiene que haber surgido de juntar dos eslabones previos con un operador binario. Por unicidad de lectura y un argumento similar al del punto anterior, todas las subf´ormulas de P y de Q est´an en la cadena. Luego, est´an todas las de α.

Ejercicio 07

Si α es una variable, su ´unica cadena de formaci´on minimal es la que s´olo la contiene a ella misma. Todo lo que aparezca antes se puede sacar. Supongamos que � no es una variable. Sea X1, . . . ,Xn una cadena de formaci´on minimal para α. Supongamos que hay un eslab´on C que no es subf´ormula de α. Consideremos el conjunto I = {i : 1 <= i <= n ^Xi no ε s(α)} (los ´ındices de todos los eslabones que no son subf´ormula). Como I C N, y est´a acotado, tiene un m´aximo. Sea i0 = m´ax(I). Miremos la cadena X1, . . . ,~Xi0 , . . . ,Xn. Si esta es una cadena de formaci´on, lo es para Xn y eso contradice la hip´otesis de minimalidad. Si no es una cadena de formaci´on, sacer Xi0 la rompi´o. Eso quiere decir que hab´ıa un eslab´on Xj = ¬Xi0 o Xj = (Xi0 * Xk) o Xj = (Xk * Xi0), con j > i0 y k < j. Pero en cualquiera de esos casos, Xi0 ε s(Xj) y por ende (por la construcci´on de I), Xi0 ε s(Xn). Pero eso es un absurdo, que provino de suponer que I != Ø.

Ejercicio 08

• 1. Inducci´on en la complejidad de α. Si α es una variable, sale trivialmente. Si α = ¬P, #VarR(α) =

1. VarR(P) = cb(P) + 1 = cb(α) por HI. Si α = (P * Q), #VarR(α) = #VarR(P) + #VarR(Q) = cb(P) + 1 + cb(Q) + 1 = cb(P) + cb(Q) + 1 + 1 = cb(α) + 1.

• 2. Es trivial a partir del inciso anterior, pues #Var(α) <= #V arR(α).
• 3. Inducci´on en la complejidad de α. Si α es una variable, 1 = #s(α) <= 1 = c(α) + #VarR(α). Si α = ¬P,

1. s(α) = 1+#s(P) <= c(P)+#VarR(P)+1 = c(P)+1+#VarR(P) = c(α)+#VarR(α). Si α = (P * Q), #s(α) <= 1 + #s(P) + #s(Q) <= c(P) + #VarR(P) + c(Q) + #VarR(Q) + 1 = #c(P) + #c(Q) + 1 +
2. VarR(P) + #VarR(Q) <= #c(α) + #VarR(Q) + #VarR(P) = #c(α) + #VarR(α).

Ejercicio 09

Dadas las f´ormulas {β1, . . . , βn}, y la f´ormula α, tal que V ar(α) C= {p1, . . . , pn}, defino α(β1, . . . , βn) inductivamente como sigue: pi(β1, . . . , βn) = βi. Si α = ¬P, α(β1, . . . , βn) = ¬P(β1, . . . , βn). Si α = (P * Q), α(β1, . . . , βn) = (P(β1, . . . , βn) * Q(β1, . . . , βn)).

Ejercicio 10

• 1. La reflexividad es trivial, basta sustituir en � sus mismas variables proposicionales.

Hacemos la simetr´ıa por inducci´on en la complejidad de α. Si α = pi, y α ~ β, es porque β = βi. Entonces, β(p1, . . . , pn) = pi = α. Si α = ¬P, por unicidad de lectura β = ¬Q = ¬P(β1, . . . , βn). Entonces, P ~ Q y por HI, Q ~ P. Entonces, ¬P = ¬Q(p1, . . . , pn) = β(p1, . . . , pn). Supongamos que α = (P * Q). β = (P(β1, . . . , βn) * Q(β1, . . . , βn)) = (R * S) (por unicidad). Entonces, tenemos que R ~ P y S ~ Q (por HI). Entonces, α = (P * Q) = (R(p1 . . . , pn) * S(p1 . . . , pn) = β(p1 . . . , pn).
Para la transitividad, supongamos que α ~ β y β ~ γ (las variables son pi, βi y γi). Digo que α ~ γ, pues α(γ1, . . . , γn) = γ. Para verlo, vamos de nuevo con inducci´on en la complejidad de α. Si α es una variable, α(β1, . . . , βn)(γ1, . . . , γn) = βi(γ1, . . . , γn) = γi = α(γ1, . . . , γn). Si α = ¬P, β = ¬Q y γ = ¬R, y por HI P ~ R. Entonces, (¬P)(β1, . . . , βn)(γ1, . . . , γn) = ¬R = γ. Si α = (P * Q), por argumentos similares, β = (R * S) y γ = (T * U), todo es equivalente con todo, y γ = α(γ1, . . . , γn).

• 2. Hacemos inducci´on en la complejidad de α. Con las consideraciones del ejercicio anterior, tenemos que si

α = pi, entonces γ tambi´en es una variable y las tres magnitudes son cero en los dos casos. Si α = ¬P, γ = ¬Q, con P ~ Q. Luego, por HI, las tres magnitudes coinciden en P y Q. A manopla se ve que tambi´en el α y γ. Por ´ultimo, si α = (P * Q), entonces γ = (R * S), con R ~ P y S ~ Q. Luego, por HI, las magnitudes coinciden en P y R, y en Q y S. Nuevamente, a mano se ve que entonces coinciden en α y γ.

Ejercicio 11

• 1. Si α = pi, α¬ = pi; si α = ¬P, α¬ = P¬; si α = (P * Q), α¬ = (P¬ * Q¬).
• 2. Analizo el conjunto de f´ormulas α ε Form que cumplen α¬ ε Form. Las variables proposicionales est´an en el conjunto. Si α es una f´ormula que est´a en el conjunto, entonces ¬α tambi´en, pues es α¬, que est´a en el conjunto. Si P y Q est´an, entonces (P * Q)¬ tambi´en, pues es (P¬ * Q¬), que est´an en el conjunto. Entonces, todas las f´ormulas cumplen lo pedido.