Consecuencia y Equivalencia Semántica

RESUMEN
En esta clase estudiaremos la Consecuencia y Equivalencia Semántica en la lógica proposicional, lo cual es una continuación natural de lo que hemos visto previamente. Aprenderemos cómo obtener la noción de consecuencia semántica a partir de las asignaciones de valores de verdad y cómo esta idea se relaciona con el teorema de deducción. Además, veremos ejemplos prácticos del uso de las tablas de verdad para obtener propiedades útiles como la Eliminación de la Conjunción y la Introducción de la Disyunción. También exploraremos la noción de Equivalencia Semántica y veremos cómo se relaciona con las propiedades que ya conocemos. Finalmente, mostraremos cómo el uso de modelos y técnicas de deducción nos permiten simplificar el estudio de problemas de consecuencia y equivalencia semántica.

OBJETIVOS DE APRENDIZAJE:
Al finalizar esta clase el estudiante será capaz de

Comprender la noción de consecuencia semántica.
Comprender las diferentes interpretaciones del símbolo ⊨.
Comprender la demostración del teorema de deducción en su versión semántica y su uso en el estudio de la consecuencia y equivalencia semántica.
Comprender la definición de equivalencia semántica y su relación con los valores de verdad.
Aplicar el teorema de deducción en su versión semántica para transformar problemas de consecuencia en problemas de validez.
Aplicar las propiedades útiles en el uso de las tablas de verdad para demostrar equivalencias semánticas.
Aplicar las leyes de absorción, distribución y DeMorgan en la simplificación de expresiones complejas.
Analizar la relación entre modelos y deducciones en el estudio de la lógica proposicional.

INDICE
ASIGNACIONES Y MODELOS
EL TEOREMA DE DEDUCCIÓN (VERSIÓN SEMÁNTICA)
USO DEL TEOREMA DE DEDUCCIÓN EN EL ESTUDIO DE LA CONSECUENCIA Y EQUIVALENCIA SEMÁNTICA
EQUIVALENCIA SEMÁNTICA Y PROPIEDADES
SÍNTESIS

El estudio de la Consecuencia y Equivalencia Semántica es la continuación natural de lo que hemos hecho cuando revisamos la semántica de la lógica proposicional. Ahora revisaremos la forma en que desde las asignaciones de valores de verdad se obtiene la noción de consecuencia semántica, el cómo desde esto emerge de forma natural una versión semántica del teorema de deducción. A partir de ésto se mostrarán ejemplos prácticos del uso de las tablas de verdad para obtener algunas propiedades útiles. Todo esto lo puedes ver tambien en el canal de youtube.

Asignaciones y modelos

Primero partamos con una definición que es crucial para los desarrollos que veremos en esta entrada, la de consecuencia semántica.

DEFINICIÓN: Una expresión

G

es consecuencia (semantica) de otra expresión

F

si para cada asignación

\mathcal{A}

se cumple que

$\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$

Esto lo representamos escribiendo $F\models G$ y se lee «la expresión $F$ modela a la expresión $G$ » o « $G$ es consecuencia (semántica) de $F$ .»

Con esta definición a la mano, debemos notar que el símbolo $\models$ tiene en realidad varias lecturas distintas según el contexto:

$\mathcal{A} \models F$ significa que $\mathcal{A}(F) = 1$ ; es decir, que « $\mathcal{A}$ modela a $F$ .»
$G \models F$ significa que si una asignación cualquiera modela a $G$ , entonces modela a $F$ y leemos esto como « $F$ es consecuencia de $G$ .»
$\models F$ significa que $F$ se sostiene bajo cualquier asignación; es decir, que $F$ es una tautología.

Así, a pesar de que el símbolo $\models$ puede tener muchas interpretaciones, el contexto no es ambiguo.

La noción de consecuencia (semántica) es cercana a la noción de «implicancia» que hemos revisado con anterioridad, en el sentido de que si se cumple que $F\models G$ , entonces $\models (F\rightarrow G)$ . De hecho, esto tiene mucha similitud con el teorema de deducción que vimos varias clases atrás.

El Teorema de Deducción (Versión Semántica)

[ver]

TEOREMA: Si

F

G

son expresiones cualesquiera, entonces se cumple

$F\models G \Leftrightarrow \models (F\rightarrow G)$

Demostración:

La demostración de este teorema se obtiene con facilidad observando las tablas de verdad

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Si nos concentramos en el significado de $F\models G$ , veremos que esto es equivalente a decir que $\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$ , que a su vez es lo mismo que decir que $\mathcal{A}\not\models F \vee \mathcal{A}\models G$ . Ahora, si notamos que además $\mathcal{A}\not\models F$ es exactamente lo mismo que $\mathcal{A}\models \neg F$ , entonces se tiene que $F\models G$ es quivalente a decir que $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ . Ahora, si hacemos una tabla de verdad para $F \rightarrow G$ y marcamos en verde la región en que se cumple que $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ , entonces veremos lo siguiente:

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

De aquí tenemos que, cuando $F\models G$ , siempre ocurre que $\models (F \rightarrow G)$ y viceversa, que no es otra cosa que el teorema de deducción y su recíproco en versión semántica.

Supongamos que queremos saber si una expresión $G$ es consecuencia de alguna otra expresión $F$ . Nos referiremos a esto como el problema de consecuencia. Utilizando el teorema anterior, este problema se puede transformar en un problema de validez, porque « $G$ es consecuencia de $F$ si y sólo si $(F\rightarrow G)$ es un teorema».

Uso del teorema de deducción en el estudio de la consecuencia y equivalencia semántica

A partir de las tablas de verdad se pueden inferir algunas propiedades que recuerdan a algunas vistas en el pasado.

EJEMPLO: Mostrar usando tablas de verdad que valen las siguiente propiedades

Eliminación de la Conjunción:

(F\wedge G)\models F

Introducción de la Disyunción:

F\models (F\vee G)

Contradicción:

(F\wedge\neg F)\models G

Solución: Utilizando el teorema de deducción que acabamos de revisar, podemos transformar el problema de consecuencia en un problema de validez.

Para resolver la Eliminación de la Conjunción, podemos realizar la siguiente tabla de verdad

$F$	$G$	$(F\wedge G)$	$((F\wedge G) \rightarrow F)$
$0$	$0$	$0$	$1$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

Con esto demostramos que $((F\wedge G)\rightarrow F)$ es una tautología y, por lo tanto, siguiendo el reciproco del teorema de deducción obtenemos que $(F\wedge G) \models F$ .

La Introducción de la Disyunción se resuelve de forma análoga armando una tabla de verdad adecuada

$F$	$G$	$(F\vee G)$	$(F\rightarrow(F\vee G))$
$0$	$0$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$1$	$1$

Aquí observamos que $(F\rightarrow (F\vee G))$ es una tautología y, por lo tanto, por el recíproco del teorema de deducción, se tiene que $F\models (F\vee G)$

Y finalmente, la propiedad de Contradicción se demuestra utilizando el mismo método

$F$	$\neg F$	$(F\wedge \neg F)$	$G$	$((F\wedge \neg F)\rightarrow G)$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$0$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$

Con esta tabla de verdad hemos demostrado que $((F\wedge \neg F)\rightarrow G)$ es una tautología y, por lo tanto, por el recíproco del teorema de deducción, se tiene que $(F\wedge \neg F)\models G$ .

Equivalencia Semántica y Propiedades

[ver]

DEFINICIÓN: Si ocurren ambos y al mismo tiempo,

F\models G

G\models F

, entonces se dice que

F

G

son semánticamente equivalentes entre si. Esto se representa escribiendo

F\equiv G

Como consecuencia de esta definición se tiene que dos expresiones son semánticamente equivalentes si y sólo si tienen los mismos valores de verdad

EJEMPLO: Se puede mostrar usando tablas de verdad que valen las equivalencias semánticas de simetría.

(F\downarrow G) \equiv (G\downarrow F)

(F\vee G) \equiv (G\vee F)

(F\wedge G) \equiv (G\wedge F)

(F\leftrightarrow G) \equiv (G\leftrightarrow F)

(F\underline{\vee} G) \equiv (G\underline{\vee} F)

EJEMPLO: Si

F

es una expresión cualquiera,

\top

una tautología y

\bot

una contradicción, entonces mediante tablas de verdad se pueden probar las siguientes equivalencias semánticas

(F\wedge \top) \equiv F

(F\vee \top) \equiv \top

(F\wedge \bot) \equiv \bot

(F\vee \bot) \equiv F

Estas equivalencias se conocen como leyes de absorción.

EJEMPLO: En la semántica de la lógica proposicional valen las equivalencias de distribución de la conjunción y la disyunción.

(F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H))

(F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H))

EJEMPLO: En la semántica de la lógica proposicional tambien valen las Leyes de DeMorgan.

\neg(F\wedge G) \equiv (\neg F \vee \neg G)

\neg(F\vee G) \equiv (\neg F \wedge \neg G)

EJERCICIO: Un buen ejercicio es probar mediante tablas de verdad que, en efecto, se cumplen las equivaencias semánticas de las Leyes de Absorsión, Distributividad y Las leyes de DeMorgan.

EJEMPLO: Demostrar utilizando equivalencias semánticas que ocurre la siguiente equivalencia:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))$ .

Solución: Podemos probar esta equivalencia usando tablas de verdad, pero si hacemos esto tendremos que lidiar con una expresión con 5 variables proposicionales, y esto implica hacer una tabla de verdad con

2^5 = 32

filas y sería ideal evitar ese escenario. Para lograrlo utilizaremos las equivalencias que ya hemos mostrado.

Primero notemos que $(E\vee \neg E)$ es una tautología. Denotemos ésta tautología por $\top$ . Enotnces utilizando las leyes de absorción tendremos que

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B))$

Usando las leyes de distribución obtenemos

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B))$

Finalmente, por simetría

$((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D))$

Por lo tanto, siguiendo estas equivalencias se tiene la equivalencia

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D))$

que es lo que se quería demostrar.

Síntesis

Si observamos el desarrollo de este último ejemplo veremos que, conforme aumenta el número de variables, la complejidad a la hora de estudiar los problemas de consecuencia y equivalencia semántica crece de forma exponencial si dependemos de las tablas de verdad. Sin embargo, hemos visto que del desarrollo de la idea de modelo emerge algo análogo a las técnicas de deducción que ya hemos estudiado con bastante detalle. Esta relación entre los modelos y las deducciones son las que veremos pronto, y la combinación de ambos será lo que nos ahorrará finalmente innumerables dolores de cabeza en el estudio de la lógica.

Vistas: 43

Consecuencia y equivalencia semántica