Práctica 4: Compacidad (Lógica y Computabilidad)

Ejercicio 01

Como Γ1UΓ2 es insatisfacible, por compacidad existe Γ0 (= Γ1UΓ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1, ... , αn a las formulas de Γ1 ∩ Γ0 y β1, ... , βm a las de Γ1 ∩ Γ0, podemos hacer α = α1 ^ ... ^ αn y β = β1 ^ ... ^ βm. Es claro que β ε C(Γ1) y que β ε C(Γ2). Ademas, α ^ β es una contradiccion. Pero α ^ β ≡ ¬(¬α v ¬β) ≡ ¬(α -> ¬β), de lo cual podemos concluir que (α -> ¬β) es una tautologia.

Ejercicio 02

Supongamos que la union fuera insatisfacible. Entonces, deberia existir un subconjunto finito Γ insatisfacible. Si α1, ... , αn son las formulas de Γ, entonces podemos considerar el conjunto I = {min j{αi ε Γj}, αi ε Γ} (los indices de los primeros conjuntos en los que aparece cada formula). Si tomamos io = max I, tenemos que todas las formulas pertenecen a Γi (por la inclusion). Entonces Γ no podia ser insatisfacible. Luego, por compacidad, la union es satisfacible.

Ejercicio 03

• 1. Sea Γ' (= Γ finito. Veamos por induccion en su cantidad de elementos que es satisfacible. Si #Γ' = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo Γ' de menos de n elementos es satisfacible. Sea Γ' con n elementos. Entonces, Γ' = {β} U Γ" (con β 62 Γ". Sea v una valuacion que satisface a Γ" (existe por HI). Sea w una valuacion que satisface a β. Construimos v' como sigue. En las variables de β, da lo mismo que w. En las demas variables, da lo mismo que v. Esta valuacion satisface a Γ'. Entonces, como todo subconjunto finito es satisfacible, Γ es satisfacible (por compacidad).
• 2. Si no queremos usar compacidad, vemos directamente que Γ es satisfacible. Para cada elemento βi hay una valuacion vi. Construimos la valuacion v que es igual a cada vi en las variables de βi, y 0 en las variables que no aparezcan en Γ. Esta bien definida por las intersecciones vacıas. v satisface a Γ.

Ejercicio 04

Veamos que si β ε C(Γ), entonces β ε C({α1}). Sea β ε Γ. Por induccion i veremos que αi es consecuencia de p1. Si i = 1, entonces es p1 y esta todo bien. Supongamos que vale para todo i < n. αn = (αn-1 v pi+1). Sea v una valuacion que satisface a p1. Por HI satisface a αn-1, y por ende a αn. Sea β ε C(Γ). Entonces, existe Γ0 β Γ finito, tal que β ε C(Γ0). Por la prueba anterior, {p1} |= Γ0. Entonces β ε C({p1}).

Ejercicio 06

Recordemos que {P} |= Q sii (P -> Q) es una tautologia. Y esto tambien es equivalente a que [P] <= [Q]. Con esto en mente, supongamos que Γ |= γ. Entonces, por compacidad, existe un subconjunto finito Γ0 = {α1, ... , αn} de Γ tal que {α1, ... , αn} |= γ . Miremos el cociente finito Γ0/ ≡. La hipotesis de que α -> β es tautologia o β -> α es tautologia se puede traducir en que este cociente se puede ordenar totalmente. Sea [α] su primer elemento. Es claro que todos los elementos de [α] son consecuencia de α. Los elementos de clases mayores tambien, pues se tiene que α -> β es tautologia para toda β que este en una clase [P] tal que [α] <= [P]. Entonces, todo Γ0 es consecuencia de α. Luego, {α} |= γ .

Ejercicio 07

Supongamos que ninguna formula de la forma β1 _· · ·_βn sea tautologıa. Esto es lo mismo que decir que ninguna formula de la forma ¬β1 ^ · · · ^ ¬βn no es contradiccion. Pero esto ultimo es lo mismo que decir que todo subconjunto finito de negaciones de formulas de Γ es satisfacible. Entonces ¬Γ = {¬β, β ε Γ} es satisfacible. Entonces, existe v valuacion tal que v(¬β) = 1 para todo β en Γ. Esto contradice la hipotesis de que v satisface al menos una formula de Γ. Entonces, tienen que existir finitas formulas β1, . . . , βn tales que su disyuncion es una tautologıa.

*Ej 7) Sea Γ con la propiedad de que cada valuación satisface al menos una fórmula de Γ. Probar que existe un número finito de fórmulas <math>\alpha_1,...,\alpha_n \in \Gamma</math> tales que <math>\alpha_1 \or ... \or \alpha_n</math> es tautología.

'''Solución''': Pruebo por absurdo.

Supongo que <math>\forall \alpha_1,...,\alpha_n \in \Gamma, \alpha_1 \or ... \or \alpha_n</math> no es una tautología. Entonces <math>\exists v / v(\alpha_1 \or...\or \alpha_n)=0 \Rightarrow v(\alpha_i)=0, 1 \le i \le n</math> (*)

Defino Γ <math> = \{ \neg \alpha : \alpha \in \Gamma\}.</math>
Como <math>v(\neg\alpha) = 1 \Leftrightarrow v(\alpha) = 0</math>, si pruebo que Γ es satisfacible <math>\Rightarrow \exists v / v(\neg\alpha) = 1 \forall \alpha \in \Gamma \Rightarrow v(\alpha) = 0 \forall \alpha \in \Gamma </math>.

Sea Φ ⊆ Γ finito / <math>\Phi = \{\neg \alpha_1,...,\neg \alpha_n\} \forall \alpha_i \in \Gamma, 1 \le i \le n</math>.
Φ es satisfacible si y sólo si <math> \exists v / v(\neg\alpha_i) = 1 \forall 1 \le i \le n \Leftrightarrow \exists v(\alpha_i) = 0 \forall 1 \le i \le n </math>. Esta valuación existe por hipótesis (*). Entonces, por el [[Teorema de Compacidad | teorema de compacidad]], Γ es satisfacible. Absurdo puesto que Γ tiene la propiedad de que toda valuación satisface al menos una de sus fórmulas.

Ejercicio 08

Probaremos por induccion que cada Γi es satisfacible. Si i = 0, sabemos que es satisfacible por la construccion. Supongamos que todos los Γi con i < n son satisfacibles. Miramos Γn. Sea v una valuacion que satisface a Γn−1. Sea p ε (S 2ΓVar( ))\Var(β). Entonces p o ¬p aparece como literal en β. Si aparece p, construimos v0, que asigna los mismos valores que v a todas las variables, y 1 a p. Si aparece ¬p, en lugar de 1 le asigna 0. Ası, un literal que contiene a p sera satisfecho por v0, y por ende tambien lo sera β. Γn−1 tambien es satisfecho por v0. Entonces, por el ejercicio 2, Γ es satisfacible.

Ejercicio 09

Sabemos que tenemos que empezar por una formula que no sea contradiccion. Por ejemplo, p1. Si vamos agregando las negaciones de las demas variables proposicionales, tenemos un conjunto que sirve. Otro ejemplo, hacemos β = p1 ^ ¬p2. Vamos agregando p2i _ ¬p2i+1.

Ejercicio 10

• 1. Si Γ1 = ;, la afirmacion es trivialmente verdadera. Si no, usamos la sugerencia. Sea v una valuacion. Si v satisface a Γ1, entonces existe β0 ε Γ2 tal que v la satisface. Entonces, v satisface a β -> β0 para cualquier β ε Γ1. Supongamos que v no satisface a Γ1. Entonces, existe una formula β0 ε Γ1 tal que v no la satisface.

Entonces v satisface a β0 -> β para cualquier β ε Γ2. De lo anterior, concluimos que toda valuacion satisface al menos una formula del conjuto Γ1 -> Γ2. Entonces, existen finitas formulas en Γ1 -> Γ2 tales que su disyuncion es una tautologıa. Tomamos T β (β1 -> β1) _ · · · _ (βn -> βn) β (¬β1 _ β1) _ · · · _ (¬βn _ β1) β (¬β1 _ · · · _ ¬βn) _ (β1 _ · · · _ βn) β ¬(β1 ^ · · · ^ βn) _ (β1 _ · · · _ βn) β (β1 ^ · · · ^ βn) -> (β1 _ · · · _ βn). Si tomamos S = {β1, . . . , βn}, lo que vimos muestra que S |=D Γ2.

• 2. Esta afirmacion es falsa. Si tomamos Γ1 = Γ2 = Var (el conjunto de todas las variables), ningun subconjunto finito de Γ1 va a cumplir lo pedido.