Práctica 2: Semántica del Cálculo Proposicional (Lógica y Computabilidad)

Ejercicio 01

En los casos a, b y d, hay que hacer las tables de verdad y ver que pasa. Tambien se puede tratar de ver la formula a manopla. En el caso c hay que hacer una “tabla de verdad”. Esto es, dada una valuacion v, podemos tener v(α) = 1 o v(α) = 0, y lo mismo pasa con v(β). Esto no es una tabla de verdad en el sentido clasico, porque no estamos viendo que pasa con variables, sino con formulas, pero la idea es la misma. En el punto e, sabemos que existen v y w valuaciones tales que v(α) = 1 y w(α) = 0. Entonces, las mismas cumplen v(¬α) = 0 y w(¬α) = 1. Entonces, ¬α es una contingencia.

Ejercicio 02

Usando el metodo del teorema del apunte, para la primera nos sirve (p ^ q) ν (¬p ^ ¬q). Para la segunda, nos sirve (p ^ q ^ ¬r) ν (p ^ ¬q ^ ¬r) ν (¬p ^ ¬q ^ ¬r).

Ejercicio 03

• 1. Sea v tal que v(((p1 -> p2) ν p1)) = 1. Entonces, v(p1) = 1 o v((p1 -> p2)) = 1. En el segundo caso, lo unico que no nos sirve es v(p1) = 1 y v(p2) = 0. Si v(p1) = 1, la formula es verdadera por la segunda parte. Si es 0, es verdadera por la primera. Entonces, es una tautologıa y toda valuacion la satisface.
• 2. v(((p1 -> p2) -> p2)) = 0 sii v((p1 -> p2)) = 1 y v(p2) = 0. Entonces, v(p1) = 1 y v(p2) = 0. Ası, toda valuacion w que satisfaga w(p1) = 0 o w(p2) = 1 satisface la formula, y esas son todas.
• 3. v(((p1 -> p3) -> ¬p3)) = 1 sii v((p1 -> p3)) = 0 o v(¬p3) = 0, sii (v(p1) = 0 o v(p3) = 1) o v(p3) = 1. Entonces, las valuaciones que satisfacen la formula son aquellas que cumplen v(p1) = 0 o v(p3) = 1.

Ejercicio 04

Supongamos que existe v(α) = 1. Supongamos que Var(α) = {p1, .. , pn}. Dado i ε N. Construimos fi : {p1, .. , pn+i} -> B, caracterizada por fi(p1) = v(p1), .. , fi(pn) = v(pn), fi(pn+1) = v(pn+1), .. , fi(pn+i−1) = v(pn+i−1), fi(pn+i) = 1 − v(pn+i). Consideramos las extensiones (unicas) vi que corresponden a cada fi. Estas extensiones tienen que ser todas distintas, por como construimos las f, y como son infinitas, prueban lo que nos pidieron.

Ejercicio 05

p1 ν (p2 ^ ¬p2) ν (p3 ^ ¬p3) cumple lo pedido.

Ejercicio 06

Lo podemos resolver haciendo induccion en la complejidad de α. Si α = pi, entonces por la hipotesis, v(α) = w(α). Si α = ¬P, por HI, v(P) = w(P), entonces v(¬P) = w(¬P). Si α = (P ? Q), entonces por HI v(P) = w(P) y v(Q) = w(Q). De eso concluimos que v(α) = w(α). Generalizar a toda α ε Form es facil. Dada una formula α, existe un n tal que V ar(α) � {p1, .. , pn}, pues las formulas son listas finitas.

Ejercicio 07

• 1. V. Sea v una valuacion. v(α ^ β) = mın(v(α), v(β)) = mın(1, 1) = 1.
• 2. F. (p -> p) es una tautologıa, pero sus dos “terminos” son ambos contingencias.
• 3. F. p es una contingencia, y ¬p es una contigencia. Sin embargo, (pνq) es una tautologıa. La otra implicacion sı vale. Si ambas fueran tautologıa o contradiccion, la formula tendrıa un unico valor de verdad para cualquier

valuacion, por lo que no podrıa ser contigencia.

• 4. F. p es una contigencia, pero (p -> p) es una tautologıa.
• 5. F. (p -> p) es una tautologıa, pero p es una contingencia.
• 6. V. Sea v una valuacion. v((α -> β)) = max(1 − v(α), v(β)) = 0. Esto pasa sii v(α) = 1 y v(β) = 0. Como esto se tiene que cumplir para toda valuacion, α es una tautologıa y β una contradiccion.

Ejercicio 08

Si α es contradiccion o β es tautologia, max(1-v(α), v(β)) = 1 para toda valuacion v, sin importar que pasa con las variables. Si permitimos que tengan variables en comun, el inciso v del ejercicio anterior nos muestra que la otra implicacion es falsa. Supongamos, entonces, que (α -> β) es una tautologıa, y que Var(α) \ Var(β) = Ø. Supongamos que э v valuacion tal que v(α) = 1 y que э w valuacion tal que w(β) = 0. Defino f : Var -> B como sigue. Si pi ε Var(α), f(pi) = v(pi). Si pi ε Var(β), f(pi) = w(pi). Si pi no esta en ninguno de los dos conjuntos de variables, f(pi) = 0. Esta funcion esta bien definida, porque asigna uno y solo un valor a cada variable. Aqui usamos la interseccion vacıa. Sea vf la valuacion que extiende a f. Entonces, vf ((α -> β)) = 0, lo cual es un absurdo. Entonces, α es contradiccion o β es tautologia.

Ejercicio 09

• 1. Supongamos que α sea una contradiccion. Sea v valuacion tal que v((α^β)) = 1. Entonces, mın(v(α), v(β)) = mın(0, v(β)) = 0. Entonces α no puede ser una contradiccion. Supongamos que α sea una tautologıa. Sea v una valuacion. Entonces mın(v(α), v(β)) = mın(0, v(β)) = v(β). Como (α ^ β) es una contigencia, hay una

valuacion para la cual v(β) = 1 y hay alguna para la cual v(β) = 0. Entonces, β es una contingencia.

• 2. Con un procedimiento similar al del ejercicio 8, creamos una valuacion que da 1 y otra que da 0. Con eso probamos que la formula es una contingencia.

Ejercicio 10

Usamos α = (p1 ν ¬p1) ν p2 ν · · · ν pn. Construimos las 2n funciones que asignan a p1, .. , pn todos los posibles valores, y al resto de las variables les asignan 0. Consideramos las valuaciones que extienden estas funciones. Son 2n, y si nos dan una valuacion que cumple con las condiciones pedidas, entonces es una de estas.
Para k entre 1 y 2n, una tabla de verdad que tenga todas las posibles asignaciones de valores a las variables, y le ponemos 1 a la ultima columna de las k primeras filas. Construimos una formula que tenga esa tabla de verdad, y procedemos como en el punto anterior.
Para formalizar la construccion de las tablas anteriores, sean l, i naturales (i � 1), notamos |l|i al i-esimo dıgito en la expresion binaria de l (1 indica el dıgito menos significativo). Para nuestro primer problema, para 1 ≤ j ≤ 2n, definimos fj : Var -> B, fj(pi) = |j|i para todas las variables pi. Construimos las 2n valuaciones vfj y tenemos lo pedido.
Para el segundo punto, armamos la funcion booleana de n variables f, dada por 0 ≤ j ≤ k−1, f(|j|n, .. , |j|1) = 1Ø k ≤ j ≤ 2n −1, f(|j|n, .. , |j|1) = 0. Sea P una formula que tiene esta funcion como tabla de verdad. De las 2n valuaciones que dan 0 en el resto de las variables, y algo en las primeras n, solo k haran verdadera a estar formula. A saber, las k que cumplen Pnl =1 v(pl) < k.

Ejercicio 11

Mirando un poco, se ve que para toda valuacion v, y para toda variable pi que aparece en α, v(α) = 1 ^ v(pi) = 0, o bien v(α) = 0 ^ v(pi) = 1. Entonces, para toda variable pi, α � ¬pi. Pero entonces solo puede haber una variable. Si no, variables distintas serıan semanticamente equivalentes, lo cual es un absurdo.

Ejercicio 12

Hacemos induccion en la complejidad de α. Si es variable, es trivial. Nuestra HI va a ser que para toda formula de complejidad menor a la de α, que tiene a lo sumo una aparicion de cada variable, se cumple que la formula es una contingencia. Si es α = ¬P, por HI P es una contingencia, luego α tambien lo es. Si α = (P ^ Q), armamos una valuacion v que nos de v(P) = v(Q) = 1 y otra w que nos de w(P) = 1 − w(Q) = 0. Para construir v y w, observamos que Var(P) \Var(Q) = Ø, y usamos el procedimiento del ejercicio 8. v y w nos muestran que α es una contingencia. Un procedimiento analogo se puede aplicar para los conectivos ν y ->.

Ejercicio 13

Supongamos que α es una tautologıa. Sea w una valuacion. Construyo v valuacion tal que v(pi) = w(βi). Esta valuacion esta bien definida. Haciendo induccion en la complejidad de α, se ve que para toda valuacion w, w(α(β1, .. , βn)) = v(α). Entonces, la formula con el reemplazo es tambien tautologıa, pues v(α) = 1. Para la vuelta, basta tomar βi = pi.

Ejercicio 14

Sea f1 : Var -> B tal que f1(pi) = 1 para toda variable. Sea v1 la valuacion que extiende a f1.

• 1. Supongamos que α sea una formula construida usando solo variables, ^ y ->. Veamos que v1(α) = 1, por induccion en la complejidad de α. Si α = pi, v1(α) = v1(pi) = 1. Si α = (P ^Q), v1(α) = mın(v1(P), v1(Q)) = mın(1, 1) = 1 por HI. Si α = (P -> Q), v1(α) = max(1 − v1(P), v1(Q)) = max(0, 1) = 1. Entonces, ninguna formula construida ası puede ser semanticamente equivalente a ¬p1. Entonces, el conjunto no es adecuado.
• 2. Idem inciso anterior.
• 3. Idem inciso anterior.
• 4. El conjunto sı es adecuado. Sea α una formula, daremos inductivamente otra semanticamente equivalente αν¬, pero que solo contiene variables, ν y ¬. Si α = p1, esa misma nos sirve. Si α = ¬P, αν¬ = ¬Pν¬. Si α = (P ν Q), αν¬ = (Pν¬ ν Qν¬). Si α = (P ^ Q), αν¬ = ¬(¬Pν¬ ν ¬Qν¬). Si α = (P -> Q), αν¬ = (¬Pν¬ ν Qν¬).

Resta ver que las formulas ası construidas son efectivamente semanticamente equivalentes a las originales. Veamoslo por induccion en la complejidad de α. Si es una variable, no cambiamos nada, ası que esta todo bien. Si α = ¬P, αν¬ = ¬Pν¬ � ¬P = α (por HI). Si α = (P νQ), αν¬ = (Pν¬ νQν¬) � (P νQ) = α (por HI). Si α = (P ^ Q), αν¬ = ¬(¬Pν¬ ν ¬Qν¬) � ¬(¬P ν ¬Q) � α (por HI y de Morgan). Si α = (P -> Q), αν¬ = (¬Pν¬ ν Qν¬) � (¬P ν Q) � α (por HI y reglas de las valuaciones).

• 5. No lo es, por un argumento similar al de incisos anteriores. Notar que toda formula construida con este conectivo ternario contiene solo variables, ν y ->. Ya mostramos que esos conectivos no eran suficientes para expresar ¬p1.

Ejercicio 15

• 1. Para ver que esta bien definida, sean [α] ≤ [β], y sean ε [α] y δ ε [β]. Queremos ver que ( -> δ) es una tautologıa. Sea v una valuacion. v(( -> δ)) = max(1−v( ), v(δ)) = max(1−v(α), v(β)) = v((α -> β)) = 1. Entonces, es una tautologıa y la relacion esta bien definida.
• 2. Tenemos que ver que es
  • Reflexiva Ya vimos en algun ejercicio anterior que (α -> α) es una tautologıa.
  • Antisimetrica Tenemos (α -> β) y (β -> α) ambas tautologıas. Sea v una valuacion. Sabemos que max(1−v(α), v(β)) = max(1−v(β), v(α)) = 1. Supongamos que v(α) = 1 6= v(β). Entonces, el primer max da 0. Supongamos que v(α) = 0 6= v(β). Entonces, el segundo max da 0. Entonces v(α) = v(β), y [α] = [β].
  • Transitiva Tenemos que (α -> β) y (β -> ) son ambas tautologıas. Sea v una valuacion. max(1 − v(α), v(β)) = max(1 − v(β), v( )) = 1 y v((α -> )) = max(1 − v(α), v( )). Si v(α) = 1, v(β) = 1 por el primer max, y v( ) = 1 por el segundo max. Entonces, si v(α) = 1, max(1 − v(α), v( )) = 1, y si v(α) = 0, max(1 − v(α), v( )) = 1, por lo que [α] ≤ [ ].

Ejercicio 16

Ante todo, tenemos que probar que las operaciones que nos dan estan bien definidas. Esto no presenta mayores dificultades. Es muy similar a lo que hicimos en el ejercicio anterior. Una vez que tenemos bien definidas las operaciones, tenemos que mostrar que

• ν* y ^* son asociativas, conmutativas y distributivas respecto de la otra. Estas tres propiedades se heredan de las de los conectivos logicos, a partir de la definicion que aquı se les da.
• > ^* [α] = [α] ^* > = [α].
• ? ν* [α] = [α] ν* ? = [α].
• [α], ¬*[α] ν* [α] = > y ¬[α] ^* [α] = ?.

Todas estas propiedades son mas o menos directas a partir de la definicion de las operaciones, pasando por los conectivos del CP. El orden natural esta dado por [α] ≤* [β] , [α] = [α] ^* [β]. Veamos que coincide con el del ejercicio anterior. Supongamos que [α] ≤ [β], sii (α -> β) es tautologıa. Sea v una valuacion. max(1−v(α), v(β)) = 1. Eso ocurre sii v(α) = 0 o v(β) = 1. Si v(α) = 0, mın(v(α), v(β)) = 0, de lo cual v(α) = v((α ^ β)). Si v(β) = 1, mın(v(α), v(β)) = v(α). Entonces, [α] ≤ [β] sii α � (α ^ β) sii [α] = [(α ^ β)] = [α] ^* [β] sii [α] ≤* [β].

Ejercicio 17

Probar que todo vale es igual que en el ejercicio anterior. Para la finitud, en la teorica se vio un metodo para “convertir” cualquier formula en una que esta en forma normal disyuntiva. Eso nos permite afirmar que toda formula en las variables {p1, .. , pn} es sematicamente equivalente a otra en f.n.d. Ahora bien, supongamos que, por ejemplo, la variable pn no aparezca en una clausula (x1 ^ · · · ^ xj ). Si reemplazamos esa clausula por las dos clausulas (x1 ^ · · · ^ xj ^ pn) y (x1 ^ · · · ^ xj ^ ¬pn), estamos reemplazando una clausula por dos que, unidas por un ν son semanticamente equivalentes. Esto nos muestra que podemos reescribir todas las clausulas que esten incompletas, y obtener formulas en f.n.d que son semanticamente equivalentes, pero que tienen solo clausulas completas. Estas son todas semanticamente distintas entre sı, por sus tablas de verdad (i.e. si alguna clausula esta en una y no en otra, entonces habra un 1 en la ultima columna de la que esta, y un 0 en la que no esta). Ademas, toda formula es equivalente a una de ellas. Como hay n variables, hay 2n clausulas (por las negaciones). Como cada clausula puede o no estar en una formula, hay exactamente 22n formulas en f.n.d. completa, y estas dan lugar cada una a una clase de equivalencia.

Ejercicio 18

Sean δ ε [α] y ε [β], con [α] ->* [β]. Sea v una valuacion. Si v((α -> β)) = 1, sii v(α) = 0 o v(β) = 1 sii v(δ) = 0 o v( ) = 1 sii v((δ -> )) = 1. Entonces [δ -> ] = [α -> β], y la operacion esta bien definida.

• 1. [α] ->* [β] = [α -> β] = [¬α ν β] = ¬*[α] ν* [β].
• 2. ? ->* [α] = [((p1 ^ ¬p1) -> α)] = > (pues esta ultima formula es una tautologıa).
• 3. [α] ->* ? = [(α -> (p1 ^ ¬p1))] = [¬α] = ¬*[α].
• 4. > ->* [α] = [((p1 ν ¬p1) -> α)] = [α].
• 5. [α] ->* > = [(α -> (p1 ν ¬p1))] = >.
• 6. [α] ->* [β] = [(α -> β)] = > sii (α -> β) es tautologıa, sii [α] ≤ [β].