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 formula del CP sii admite una cadena de formacion, que por definicion tiene longitud finita. A esa cadena le puedo agregar tantas copias de α al final omo desee, obteniendo ası cadenas de formacion para α de longitud arbitrariamente grande (siempre finita). Formalmente, supongamos que son finitas, y sea 1, .. ,Xn la cadena de formacion mas larga para una formula α. Entonces, X1, .. ,Xn,Xn tambien es una cadena de formacion para α, contradiciendo nuestra hipotesis de finitud.

Ejercicio 03

Induccion en la complejidad de α. Si α es una variable proposicional, entonces s(α) = {α}. Si α = ¬P, para alguna formula P, entonces s(α) = {α}Us(P). Si α = (P*Q), ntonces s(α) = {α}Us(P)Us(Q). Ojo: s(α) es el conjunto de subformulas, y por ende no tiene en cuenta posibles repeticiones.

Ejercicio 04

Los conjuntos de subformulas son faciles de calcular. Solo hay que usar la definicion del ejercicio anterior. Por ejemplo, para el caso 1, s(α) = {α, (p1 v (p2 -> p3)), p4, p1, (p2 -> p3), p2, p3}. Una cadena de formacion es minimal si no se le puede sacar ningun eslabon. Esto es, si se saca alguno, deja de ser cadena de formacion para la formula. En sımbolos, decimos que una cadena de formacion X1, .. ,Xn para Xn es minimal si X1, .. , fXj , .. ,Xn (la misma sin algun eslabon Xj) no es una cadena de formacion para Xn. Intuitivamente (se formaliza en los ejercicios 6 y 7), las cadenas de formacion minimales van a ser aquellas que solo contengan subformulas y no tengan repeticiones. Por eso, son permutaciones del conjunto mostrado, respetando las dependencias entre las subformulas.

Ejercicio 05

Dado n, la formula ¬· · · ¬p1, que tiene n−1 sımbolos ¬, tiene exactamente n subformulas. Veamoslo por induccion en la longitud de la formula. Sea long(α) = 1, entonces α = p1. Supongamos que para n−1 tenemos una formula α tal que #s(α) = n − 1. Entonces, #s(¬α) = n + 1. En realidad, esta ultima afirmacion hace uso implıcito de que todas las subformulas de una formula tienen a lo sumo su longitud. Ası, al agregar una negacion (alargando la formula), nos aseguramos de no estar repitiendo nada.

Ejercicio 06

Sean α y una cadena de formacion para ella. Hacemos induccion en la longitud de α. Si la longitud de α es 1, entonces α es una variable proposicional. En ese caso, su unica subformula es ella misma, que tiene que aparecer al final de toda cadena de formacion para α.
Si long(α) = n > 1, α = ¬P o α = P * Q, con P y Q formulas. Si α = ¬P, entonces sus subformulas son α (que aparece en toda cadena) y las subformulas de P. Pero P tiene que aparecer en algun lugar de la cadena, y si miramos una cadena hasta un determinado eslabon, tenemos una cadena de formacion para la formula que aparece en ese eslabon. Entonces, por HI, todas las subformulas de P estan en la cadena, luego estan todas las de α.
Si α = (P * Q), como empieza con un parentesis, 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 subformulas de P y de Q estan en la cadena. Luego, estan todas las de α.

Ejercicio 07

Si α es una variable, su unica cadena de formacion minimal es la que solo 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 formacion minimal para α. Supongamos que hay un eslabon C que no es subformula de α. Consideremos el conjunto I = {i : 1 <= i <= n ^Xi no ε s(α)} (los ındices de todos los eslabones que no son subformula). Como I C N, y esta acotado, tiene un maximo. Sea i0 = max(I). Miremos la cadena X1, .. ,~Xi0 , .. ,Xn. Si esta es una cadena de formacion, lo es para Xn y eso contradice la hipotesis de minimalidad. Si no es una cadena de formacion, sacer Xi0 la rompio. Eso quiere decir que habıa un eslabon 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 construccion de I), Xi0 ε s(Xn). Pero eso es un absurdo, que provino de suponer que I != Ø.

Ejercicio 08

• 1. Induccion 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(α) <= #VarR(α).
• 3. Induccion 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 formulas {β1, .. , βn}, y la formula α, 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 induccion 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 induccion 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 induccion en la complejidad de α. Con las consideraciones del ejercicio anterior, tenemos que si

α = pi, entonces γ tambien 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 tambien 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 formulas α ε Form que cumplen α¬ ε Form. Las variables proposicionales estan en el conjunto. Si α es una formula que esta en el conjunto, entonces ¬α tambien, pues es α¬, que esta en el conjunto. Si P y Q estan, entonces (P * Q)¬ tambien, pues es (P¬ * Q¬), que estan en el conjunto. Entonces, todas las formulas cumplen lo pedido.