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

Ejercicio 01

Como 􀀀1[􀀀2 es insatisfacible, por compacidad existe 􀀀0 � 􀀀1[􀀀2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una f´ormula de 􀀀1 y una de 􀀀2. Si no, ser´ıa satisfacible. Si llamamos �1, . . . , �n a las f´ormulas de 􀀀1 \ 􀀀0 y �1, . . . , �m a las de 􀀀1 \ 􀀀0, podemos hacer � = �1 ^ · · · ^ �n y � = �1 ^ · · · ^ �m. Es claro que � 2 C(􀀀1) y que � 2 C(􀀀2). Adem´as, � ^ � es una contradicci´on. Pero � ^ � � ¬(¬� _ ¬�) � ¬(� ! ¬�), de lo cual podemos concluir que (� ! ¬�) es una tautolog´ıa.

Ejercicio 02

Supongamos que la uni´on fuera insatisfacible. Entonces, deber´ıa existir un subconjunto finito 􀀀 insatisfacible. Si �1, . . . , �n son las f´ormulas de 􀀀, entonces podemos considerar el conjunto I = {m´ınj{�i 2 􀀀j}, �i 2 􀀀} (los ´ındices de los primeros conjuntos en los que aparece cada f´ormula). Si tomamos io = m´ax I, tenemos que todas las f´ormulas pertenecen a 􀀀i (por la inclusi´on). Entonces 􀀀 no pod´ıa ser insatisfacible. Luego, por compacidad, la uni´on es satisfacible.

Ejercicio 03

• 1. Sea 􀀀0 � 􀀀 finito. Veamos por inducci´on en su cantidad de elementos que es satisfacible. Si #􀀀0 = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo 􀀀0 de menos de n elementos es satisfacible. Sea 􀀀0 con n elementos. Entonces, 􀀀0 = {�} [ 􀀀00 (con � 62 􀀀00. Sea v una valuaci´on que satisface a 􀀀00 (existe por HI). Sea w una valuaci´on que satisface a �. Construimos v0 como sigue. En las variables de �, da lo mismo que w. En las dem´as variables, da lo mismo que v. Esta valuaci´on satisface a 􀀀0. 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 valuaci´on vi. Construimos la valuaci´on v que es igual a cada vi en las variables de �i, y 0 en las variables que no aparezcan en 􀀀. Est´a bien definida por las intersecciones vac´ıas. v satisface a 􀀀.

Ejercicio 04

Veamos que si � 2 C(􀀀), entonces � 2 C({�1}). Sea � 2 􀀀. Por inducci´on i veremos que �i es consecuencia de p1. Si i = 1, entonces es p1 y est´a todo bien. Supongamos que vale para todo i < n. �n = (�n−1 _ pi+1). Sea v una valuaci´on que satisface a p1. Por HI satisface a �n−1, y por ende a �n. Sea � 2 C(􀀀). Entonces, existe 􀀀0 � 􀀀 finito, tal que � 2 C(􀀀0). Por la prueba anterior, {p1} |= 􀀀0. Entonces � 2 C({p1}).

Ejercicio 06

Recordemos que {P} |= Q sii (P ! Q) es una tautolog´ıa. Y esto tambi´en 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 hip´otesis de que � ! � es tautolog´ıa o � ! � es tautolog´ıa 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 tambi´en, pues se tiene que � ! � es tautolog´ıa para toda � que est´e en una clase [P] tal que [�] � [P]. Entonces, todo 􀀀0 es consecuencia de �. Luego, {�} |= .

Ejercicio 07

Supongamos que ninguna f´ormula de la forma �1 _· · ·_�n sea tautolog´ıa. Esto es lo mismo que decir que ninguna f´ormula de la forma ¬�1 ^ · · · ^ ¬�n no es contradicci´on. Pero esto ´ultimo es lo mismo que decir que todo subconjunto finito de negaciones de f´ormulas de 􀀀 es satisfacible. Entonces ¬􀀀 = {¬�, � 2 􀀀} es satisfacible. Entonces, existe v valuaci´on tal que v(¬�) = 1 para todo � en 􀀀. Esto contradice la hip´otesis de que v satisface al menos una f´ormula de 􀀀. Entonces, tienen que existir finitas f´ormulas �1, . . . , �n tales que su disyunci´on 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 inducci´on que cada 􀀀i es satisfacible. Si i = 0, sabemos que es satisfacible por la construcci´on. Supongamos que todos los 􀀀i con i < n son satisfacibles. Miramos 􀀀n. Sea v una valuaci´on que satisface a 􀀀n−1. Sea p 2 (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 ser´a satisfecho por v0, y por ende tambi´en lo ser´a �. 􀀀n−1 tambi´en es satisfecho por v0. Entonces, por el ejercicio 2, 􀀀 es satisfacible.

Ejercicio 09

Sabemos que tenemos que empezar por una f´ormula que no sea contradicci´on. Por ejemplo, p1. Si vamos agregando las negaciones de las dem´as variables proposicionales, tenemos un conjunto que sirve. Otro ejemplo, hacemos � = p1 ^ ¬p2. Vamos agregando p2i _ ¬p2i+1.

Ejercicio 10

• 1. Si 􀀀1 = ;, la afirmaci´on es trivialmente verdadera. Si no, usamos la sugerencia. Sea v una valuaci´on. Si v satisface a 􀀀1, entonces existe �0 2 􀀀2 tal que v la satisface. Entonces, v satisface a � ! �0 para cualquier � 2 􀀀1. Supongamos que v no satisface a 􀀀1. Entonces, existe una f´ormula �0 2 􀀀1 tal que v no la satisface.

Entonces v satisface a �0 ! � para cualquier � 2 􀀀2. De lo anterior, concluimos que toda valuaci´on satisface al menos una f´ormula del conjuto 􀀀1 ! 􀀀2. Entonces, existen finitas f´ormulas en 􀀀1 ! 􀀀2 tales que su disyunci´on 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 afirmaci´on es falsa. Si tomamos 􀀀1 = 􀀀2 = Var (el conjunto de todas las variables), ning´un subconjunto finito de 􀀀1 va a cumplir lo pedido.