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 no ε 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 Г', luego a Г'. La reciproca no es cierta, pues {p1} es satisfacible, y {p1} C {p1;¬p1}, y este segundo no es satisfacible

Ejercicio 05

• 1. (= es falsa. Por ejemplo, Г1 = {p1; (p1 -> p2)} y Г2 = {¬p2}. 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)UC(Г2), v(α) = 1.
• 2.
  • (= es cierta. Para verlo, sea α ε C(Г1∩Г2), y supongamos que α ε C(Г1)∩(Г2). Entonces, э v(v(Г1)^¬v(α)) o э w(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 = {p1 ^ p2} y Г2 = {p1}. Г1∩Г2 = {}, cuyas consecuencias son todas las tautologias. Ahora bien, Г1 |= p2, y trivialmente, Г2 |= 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 definicion de consecuencia, v(α) = 1, para toda α ε C(Г). Entonces, C(Г) es satisfacible. Para responder la pregunta, probamos que ∀ГP(Г) , P(C(Г)), y nos preguntan que pasa con ∀Г¬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 verificacion 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 definicion de [ ]) Sea v una valuacion. v(α -> (β -> γ )) = max(1-v(α); v(β -> γ)) = max(1-v(α);max(1-v(β); v(γ))) = max{1-v(α); 1-v(β); v(γ)} = 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 <math>\{\alpha v1, ..., \alpha vn \} \models \gamma \Leftrightarrow \{(\alpha v1 \land ... \land \alpha vn)\} \models \gamma, \forall \alpha vi \in \Gamma</math>.
Pruebo la ida¬ Como Γ es satisfacible, existe una valuación ''v'' tal que v(α) = 1 y v(γ) = 1 para todo α en Γ. Entonces v(<math>\alpha   v1 \land ... \land \alpha  vn </math>) = 1 y v(γ) = 1. Luego
{(<math>\alpha  v1 \land ... \land \alpha  vn </math>), γ } es satisfacible por ''v''. Por el teorema de la deducción vale <math>\{(\alpha  v1 \land ... \land \alpha vn)\} \models \gamma</math>

Vuelta¬ Por el teorema de la deducción sabemos que <math>\{(\alpha v1 \land ... \land \alpha vn)\} \models \gamma \Leftrightarrow (\alpha v1 \land ... \land \alpha vn) \rightarrow \gamma</math> es tautología. Esto es cierto si y sólo si
<math>(\alpha v1 \land ... \land \alpha vn)</math> es contradicción o γ es tautología.

**Si <math>(\alpha v1 \land ... \land \alpha vn)</math> 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 <math>\emptyset \models</math> γ. En particular <math>\{\alpha v1 , ..., \alpha vn\} \models \gamma</math>.

Ejercicio 10

• 1. Digo que Г = {p1; .. ; pk} es independiente. Para cualquier i, sea vi la valuacion que cumple v(pj) = 1-δi;j . Esto nos da una valuacion que satisface a Г\{pi}, pero que no satisface a pi.
• 2. Cualquier conjunto infinito de variables proposicionales es independiente, por un argumento como el anterior.

Ejercicio 11

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

Ejercicio 12

Sea Г como en el enunciado. Sean {p1; .. ; pn} 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 Σ = Г U {pn+1}. v satisface a Σ\{pn+1} = Г, pero no a pn+1. Entonces pn+1 no esta en C(Σ\{pn+1}). Sea α ε Г. Sea v una valuacion tal que v(Г\{α}), 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 Σ\{α}, 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 infinitas 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.