Práctica 3: Consecuencia Lógica y Árboles (Lógica y Computabilidad)

Ejercicio 01

• 1. Sea v una valuacion que satisface p1 y ¬p2. Entonces, max(1 Г v(p1); v(p2)) = 0, y v no satisface (p1 -> p2).
• 2. Sea f1 tal que f1(pi) = 1 para toda variable. La valuacion v1 que extiende a f1 satisface a Г.
• 3. p1 y ¬p1 son ambas contingencias, y por ende pertenecen a Г. Pero si v satisface a p1, entonces no satisface a ¬p1. Entonces, Г es insatisfacible.
• 4. Sea v una valuacion cualquiera. v satisface a cada elemento de Г, y por ende a Г.

Ejercicio 02

• 1. Supongamos que v satisface a Г. Entonces, v(p1) = 1 y max(1 Г v(p1); v(p2)) = 1. Pero de esto deducimos v(p2) = 1), por lo cual p2 ε C(Г).
• 2. Sea f tal que f(p1) = 1, f(p2) = 0 y f(pi) = 0 para las demas variables. Sea vf su extension. Entonces, vf satisface a Г, pero no a p2. Entonces p2 ε C(Г).
• 3. En este caso, α ε C(Г) trivialmente. Como no hay valuacion que satisfaga a Г, "todas ellas" satisfacen a cualquier formula.
• 4. Sea v una valuacion que satisface a Г. v satisface a α por ser tautologia. Entonces α ε C(Г).

Ejercicio 03

• 1. Sea α ε Г. Si v satisface al conjunto Г, satisface en particular a α. Entonces α ε C(Г), lo que prueba la inclusion.
• 2. Sea α ε C(C(Г)). Esto quiere decir que si una valuacion v satisface a C(Г), entonces v satisface a α. Sea w tal que satisface a Г. Entonces, satisface a C(Г), pues satisface a todos sus elementos. Entonces w satisface a α, que entonces pertenece a C(Г). La inclusion esta dada por el inciso anterior.
• 3. Como Form es insatisfacible (pues contiene a p1 y a ¬p1, por el inciso d del ejercicio anterior, cualquier formula es consecuencia logica de el.
• 4. Sea α ε C(Г1). Sea v tal que satisface a Г2. Entonces, satisface en particular a Г2, luego a Г1, y por ende a α.

Ejercicio 04

Sea v una valuacion que satisface a Г. Entonces, satisface a cada formula de Г0, luego a Г0. La reciproca no es cierta, pues fp1g es satisfacible, y fp1g � fp1;¬p1g, y este segundo no es satisfacible

Ejercicio 05

• 1. � es falsa. Por ejemplo, Г1 = fp1; (p1 -> p2)g y Г2 = f¬p2g. C(Г1 [ Г2) = Form, pero p3 ε C(Г1) y p3 ε C(Г2). es verdadera. Si v(Г1[Г2) = 1, entonces v(Г1) = 1 y v(Г2) = 1. Entonces, si α ε C(Г1)[C(Г2), v(α) = 1.
• 2.
  • � es cierta. Para verlo, sea α ε C(Г1\Г2), y supongamos que α ε C(Г1)\(Г2). Entonces, 9v(v(Г1)^¬v(α)) o 9w(w(Г2)^¬w(α)). Si v(Г1), entonces v(Г1 \Г2), pues esta incluido en el primero. Entonces, vale tambien v(α). Esto es un absurdo. Se llega a lo mismo con w. Entonces, α esta tambien en la interseccion de las consecuencias.
  • no vale. Sean Г1 = fp1 ^ p2g y Г2 = fp1g. Г1 \ Г2 = ;, cuyas consecuencias son todas las tautologias. Ahora bien, Г1 j= p2, y trivialmente, Г2 j= p2. Entonces, p2 esta en la interseccion de las consecuencias. Sin embargo, no es una tautologia.

Ejercicio 06

( vale por el inciso 1 del ejercicio 3. Sea α ε C(Г), y sea v una valuacion que satisface a Г. Entonces, por deβnicion de consecuencia, v(α) = 1, para toda α ε C(Г). Entonces, C(Г) es satisfacible. Para responder la pregunta, probamos que 8ГP(Г) , P(C(Г)), y nos preguntan que pasa con 8Г¬P(Г) , ¬P(C(Г)), que se deduce trivialmente de lo que tenemos probado.

Ejercicio 07

Sea v una valuacion. Si v(α) = 1 o v(β) = 1, entonces v(α?β) = 1 y v(ανβ) = 1. Si v(α) = v(β) = 0, hagamos ' = α?β. Por la tercera hipotesis, sabemos que de α podemos deducir ' y de β tambien. Pero eso quiere decir que de ' podemos deducir ανβ. Si v(') fuera 1, tambien deberia serlo en ανβ. Entonces, como esto ultimo seria un absurdo, v(α ? β) tambien seria 0. Esto muestra que la estrellita es semanticamente equivalente al ν.

Ejercicio 08

Tomemos como Г el conjunto de todas las variables proposicionales. Se ve facilmente que es satisfacible, y que la unica valuacion que lo satisface es la valuacion v1 que le asigna un 1 a cada variable. Sea α una formula. Si v1(α) = 1, entonces α ε C(Г). Si no, esta su negacion da uno y es la que esta. Lo importante aqui fue que reducimos la veriβcacion de deducibilidad a mirar que pasa con una sola valuacion. Esto no siempre sera posible.

Ejercicio 09

• 1) ) 2) Sea v una valuacion. v((α ^ β) -> ) = max(1 Г v(α ^ β); v(

)). Si v(α ^ β) = 0, la valuacion da 1. Si v(α ^ β) = 1, entonces v(α) = v(β) = 1, y por la hipotesis, v( ) = 1, con lo cual la valuacion tambien da 1.

• 2) , 3) Es la deβnicion del orden que se dio en el ejercicio 15 de la practica 2.
• 3) ) 4) [α] ->� ([β] ->� [ ]) = [α] ->� [(β -> )] = [α -> (β -> )] (todas por deβnicion de [ ]) Sea v una valuacion. v(α -> (β -> )) = max(1Гv(α); v(β -> )) = max(1Гv α);max(1Гv(β); v( ))) = maxf1Гv(α); 1 Г v(β); v( )g = max(min(v(α); v(β)); v( )) = 1 por la equivalencia del inciso anterior.
• 4) ) 1) La expresion de 4) dice que α -> (β -> ) es una tautologia. Sea v tal que v(α) = v(β) = 1. Como 1 = v(α -> (β -> )) = max(1 Г v(α); v(β -> )) y v(α) = 1, la valuacion nos da v(β -> ) = max(1 Г v(β); v( )), que por el mismo argumento es v( ) = 1.

• Ej 9) o simil ej2 del parcial del 21/5/04

Sea Γ satisfacible, probar que Error al representar (error de sintaxis): {\displaystyle \{\alphaν1, ..., \alphaνn \} \models \gamma \Leftrightarrow \{(\alphaν1 \land ... \land \alphaνn)\} \models \gamma, \forall \alphaνi \in \Gamma} .

Pruebo la ida¬ Como Γ es satisfacible, existe una valuación v tal que v(α) = 1 y v(γ) = 1 para todo α en Γ. Entonces v(Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alphaν1 \land ... \land \alphaνn } ) = 1 y v(γ) = 1. Luego {(Error al representar (error de sintaxis): {\displaystyle \alphaν1 \land ... \land \alphaνn } ), γ } es satisfacible por v. Por el teorema de la deducción vale Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{(\alphaν1 \land ... \land \alphaνn)\} \models \gamma}

Vuelta¬ Por el teorema de la deducción sabemos que Error al representar (error de sintaxis): {\displaystyle \{(\alphaν1 \land ... \land \alphaνn)\} \models \gamma \Leftrightarrow (\alphaν1 \land ... \land \alphaνn) \rightarrow \gamma} es tautología. Esto es cierto si y sólo si Error al representar (error de sintaxis): {\displaystyle (\alphaν1 \land ... \land \alphaνn)} es contradicción o γ es tautología.

• • Si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\alphaν1 \land ... \land \alphaνn)} es contradicción, absurdo-> pues por hipótesis Γ es satisfacible y existe una valuación v tal que v(α) = 1 ∀ α ∈ Γ.
  • Si γ es tautología entonces $\emptyset \models$ γ. En particular Error al representar (error de sintaxis): {\displaystyle \{\alphaν1 , ..., \alphaνn\} \models \gamma} .

Ejercicio 10

• 1. Digo que Г = fp1; ¬ ¬ ¬ ; pkg es independiente. Para cualquier i, sea vi la valuacion que cumple v(pj) = 1Г�i;j . Esto nos da una valuacion que satisface a Гnfpig, pero que no satisface a pi.
• 2. Cualquier conjunto inβnito de variables proposicionales es independiente, por un argumento como el anterior.

Ejercicio 11

• 1. Supongamos que � no fuera independiente. Entonces, 9α ε � tal que α ε C(�nfαg). Sea v una valuacion que satisface a Гnfαg. Entonces, satisface tambien a �nfαg. Esto quiere decir que tambien satisface a α. Entonces, α ε C(Гnfαg), que es un absurdo.
• 2. Sea α la tautologia. Cualquier valuacion que satisfaga a Гnfαg satisface trivialmente a α. Entonces α ε C(Гnfαg)
• 3. C(Г) siempre contiene a todas las tautologias, con lo cual se aplica el inciso anterior.

Ejercicio 12

Sea Г como en el enunciado. Sean fp1; ¬ ¬ ¬ ; png las variables que aparecen en Г. Supongamos que Г sea satisfacible, con v una valuacion que lo satisface. Asumamos que v(pn+1) = 0 (si v no da eso, puedo construir una que si). Construyo � = Г [ fpn+1g. v satisface a �nfpn+1g = Г, pero no a pn+1. Entonces pn+1 no esta en C(�nfpn+1g). Sea α ε Г. Sea v una valuacion tal que v(Гnfαg), pero no vale v(α). Armo v0 tal que de lo mismo en las variables de Г, 1 en pn+1 y 0 en el resto de las variables. Entonces, v0 satisface a �nfαg, pero no a α. Entonces, mostre que � es una base. Pero como es estrictamente mayor que Г, tengo un absurdo, que provino de suponer que Г era satisfacible.
Bases inβnitas satisfacibles son por ejemplo, los conjuntos que tengan a todas las variables proposicionales o a sus negaciones (pero esta la variable, o bien esta la negacion, pero no ambas).

Ejercicio 13

(para despues)

Ejercicio 14

(para despues)

Ejercicio 15

(para despues)

Ejercicio 16

(para despues)

Ejercicio 17

• 1. Es falso. El unico arbol de la formula p1 es ella misma, que es un arbol abierto. Sin embargo, la formula no es una tautologia.
• 2. Es falso. El arbol (p1 ^ ¬p1) para esa misma formula no es cerrado, pero la formula es una contradiccion. El asunto es que el arbol no esta completo.
• 3. Esta si es verdadera, y esta demostrada en algun lado del apunte.