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 05
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 2Var( ))\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.