El Teorema de Compacidad del Cálculo Proposicional (II)

TEOREMA DE COMPACIDAD.- Si un conjunto de fbfs $\Sigma$ es finitamente satisfacible, entonces es satisfacible.

Demostración.- Por el LEMA, existe un conjunto de fbfs $\Delta$ tal que $\Sigma \subseteq \Delta$ y $\Delta$ es finitamente satisfacible y completo.
Entonces $\forall \phi \in W, \phi \notin \Delta \iff N\phi \in \Delta$ pues, por ser $\Delta$ completo, si $\phi \notin \Delta$, entonces $N\phi \in \Delta$; y, por ser $\Delta$ finitamente satisfacible, si $N\phi \in \Delta$, entonces $\phi \notin \Delta$, porque en otro caso sería $\left\{N\phi ,\phi \right\}\subseteq \Delta$ satisfacible, lo que es falso.

Sea la valoración de verdad $v:S\to \left\{0,1\right\}$, dada por $\forall p\in S, v\left(p\right)=1 syss p\in \Delta$.

Por inducción sobre fbfs demostraremos que

(*) $\overline{v}\left(\phi \right)=1 syss \phi \in \Delta$

lo cual es equivalente a $\overline{v}\left(\phi \right)=0 syss \phi \notin \Delta$.

Para los símbolos aserción del lenguaje, se cumple (*), por definición de $v$ y ser $\overline{v}\left(p\right)=v\left(p\right), \forall p\in S$.

Si $\alpha \in \Delta$ cumple (*), entonces

$\overline{v}\left(N\alpha \right)=1 syss \overline{v}\left(\alpha \right)=0 syss \alpha \notin \Delta syss N\alpha \in \Delta$

También se tiene que

$\overline{v}\left(C\alpha \beta \right)=0 syss \overline{v}\left(\alpha \right)=1 y \overline{v}\left(\beta \right)=0 syss \alpha \in \Delta y \beta \notin \Delta syss \alpha \in \Delta y N\beta \in \Delta syss C\alpha \beta \notin \Delta$

pues, en caso contrario, si $C\alpha \beta \in \Delta$, se tendría que $\left\{\alpha ,N\beta ,C\alpha \beta \right\}\subseteq \Delta$, y de $\left\{\alpha ,C\alpha \beta \right\}╞\beta$ se verificaría que $\beta \in \Delta$, lo que es imposible pues $N\beta \in \Delta$ y $\Delta$ es finitamente satisfacible, no siéndolo $\left\{\beta ,N\beta \right\}\subseteq \Delta$.
Se ha probado, pues, que la valoración $v$ satisface a $\Delta$, luego también a $\Sigma \subseteq \Delta$. Q.E.D.

El Teorema de Compacidad del Cálculo Proposicional (I)

En el lenguaje de la Lógica Proposicional (en adelante, CP), si $S$ representa al conjunto de símbolos aserción (que a su vez representa al conjunto de proposiciones simples del lenguaje ordinario, del que es modelo el CP), y $W$ denota al conjunto de las fórmulas bien formadas (fbfs, en adelante) del lenguaje, por definición una valoración de verdad o semántica en $L$ es una aplicación $v:S\to \mathcal{V}$, donde $\mathcal{V}$ es un conjunto que se denomina de los valores de verdad de la valoración.
En Lógica Bivaluada, $\mathcal{V}=\left\{0,1\right\}$; pero en Lógica Multivaluada $\mathcal{V}$ suele ser un subconjunto del intervalo real $[0,1]$, el cual contiene a $\left\{0,1\right\}$.

Se demuestra que existe una extensión única, $\overline{v}:W\to \mathcal{V}$, de $v$ al conjunto $W$ de fórmulas bien formadas del lenguaje, la cual constituye algebraicamente un homomorfismo de (1,2)-álgebras libres:

(i) el (1,2)-álgebra libre generada por el conjunto de símbolos aserción mediante las operaciones constructoras (o conectivas): $C y N$, o $F_C,F_N$, respectivamente, donde

$F_N:W\to W, F_N\left(\alpha \right)=N\alpha$

y

$F_C:W\times W\to W, F_C\left(\alpha ,\beta \right)=C\alpha \beta$

resultando la estructura $\left(W,N,C\right)$ una (1,2)-álgebra libre, y

(ii) definiendo en $\mathcal{V}$ las operaciones internas $G_N$ (unaria) y $G_C$ (binaria), de tal forma que verifican, para cualesquiera fbfs $\alpha y \beta$:

$\overline{v}\left(N\alpha \right)=G_N\left(\overline{v}\left(\alpha \right)\right), \overline{v}\left(C\alpha \beta \right)=G_C\left(\overline{v}\left(\alpha \right),\overline{v}\left(\beta \right)\right)$

siendo $\left(\mathcal{V},G_N,G_C\right)$ también una (1,2)-álgebra libre y $\overline{v}:\left(W,N,C\right)\to \left(\mathcal{V},G_N,G_C\right)$ el homomorfismo entre (1,2)-álgebras antecitado.

Se demuestra, así mismo, que $W$ (el conjunto de las fbfs del lenguaje) está libremente generado por el conjunto de símbolos aserción $S$, mediante las operaciones conectivas, y de forma análoga ocurre $\mathcal{V}$ y las operaciones unaria y binaria internas definidas sobre él.

El teorema de extensión de $v$ a $\overline{v}$ se demuestra, en su generalidad, para cualquier conjunto de valores $\mathcal{V}$, como el descrito.

DEFINICIÓN 1.- Se dice que una valoración de verdad, $v$, satisface a una fbf $\alpha$ cuando $\overline{v}\left(\alpha \right)=1$.

DEFINICIÓN 2.- Diremos que un conjunto de fbfs $\Sigma$ implica tautológicamente a una fbf $\alpha$, si cada valoración de verdad que satisface a todas las fbfs de $\Sigma$ satisface también a $\alpha$.
Escribiremos, entonces: $\Sigma ╞\alpha$. En caso contrario, se escribe: $\Sigma \cancel{╞}\alpha$.

Ejemplo: $\left\{\alpha ,C\alpha \beta \right\}╞\beta$.

Si $\Sigma =\varnothing , \varnothing ╞\alpha$ significa que $\alpha$ es verdadera en cualquier valoración, y se dice que $\alpha$ es una fbf tautológica o que es una tautología, escribiendo en ese caso: $╞\alpha$.

DEFINICIÓN 3.- Un conjunto $\Sigma$ de fbfs se dice satisfacible si existe una valoración de verdad $v$ que satisface a cada fbf de $\Sigma .$Se dice finitamente satisfacible si cualquier subconjunto finito de $\Sigma$es satisfacible.

DEFINICIÓN 4.- Un conjunto $\Delta$ de fbfs se dirá completo si para cualquier fbf $\alpha$, se tiene: $\alpha \in \Delta ó N\alpha \in \Delta$.

LEMA.- Si un conjunto $\Sigma$ de fbfs es finitamente satisfacible, entonces existe un conjunto $\Delta$ finitamente satisfacible y completo que contiene a $\Sigma$.

Demostración.- Sea $\Gamma$ un conjunto de fbfs tal que

$\Gamma =\left\{H|\Sigma \subseteq H y H es finitamente satisfacible\right\}$

Entonces $\Gamma \ne \varnothing , pues \Sigma \in \Gamma$. Además, $\left(\Gamma ,\subseteq \right)$ es un conjunto parcialmente ordenado.
Sea en él una cadena

$H_0\subseteq H_1\subseteq H_2\subseteq \cdots$

Entonces $\cup \left\{H_0,H_1,H_2,...\right\}$ es una cota superior de $\left\{H_0,H_1,H_2,...\right\}$, pues $\Sigma \subseteq \cup \left\{H_0,H_1,H_2,...\right\}$ y $\cup \left\{H_0,H_1,H_2,...\right\}$ es finitamente satisfacible, dado que cualquier subconjunto finito de $\cup \left\{H_0,H_1,H_2,...\right\}$ está contenido en algún $H_m,m\in \mathrm{\mathbb{N}}$.

Aplicando el Lema de Zorn, existe un elemento maximal $\Delta en \left(\Gamma ,\subseteq \right)$; es decir, un conjunto de fbfs $\Delta$ que satisface: $K\in \Gamma y \Delta \subseteq K implican K=\Delta$.

Como $\Delta \in \Gamma$, $\Sigma \subseteq \Delta$ y $\Delta$ es finitamente satisfacible.
Además, $\Delta$ es completo. En efecto. Dada $\alpha \in W$, si $\Delta \cup \left\{\alpha \right\}$ es finitamente satisfacible, entonces pertenece a $\Gamma$ y, por ser $\Delta$ maximal, $\alpha \in \Delta$.
Si $\Delta \cup \left\{\alpha \right\}$ no es finitamente satisfacible, entonces existe $J_1\subseteq \Delta$ tal que $J_1\cup \left\{\alpha \right\}$ no es satisfacible.
Consideremos a $\Delta \cup \left\{N\alpha \right\}$ y sea $J_2\subseteq \Delta \cup \left\{N\alpha \right\}$ un subconjunto finito cualquiera. Si $J_2\subseteq \Delta$, $J_2$ es satisfacible, y si $J_2⊈\Delta$, se tiene que $J_2=J_3\cup \left\{N\alpha \right\}$, donde $J_3\subseteq \Delta$.
El conjunto finito $J_1\cup J_3\subseteq \Delta$ es satisfacible, luego existe una valoración de verdad $v$ que satisface a $J_1 y J_3$. Entonces $\overline{v}\left(\alpha \right)=0$, pues $J_1\cup \left\{\alpha \right\}$ no es satisfacible, y por tanto $\overline{v}\left(N\alpha \right)=1$ y $v satisface a J_3\cup \left\{N\alpha \right\}=J_2$. En consecuencia, $\Delta \cup \left\{N\alpha \right\}$ es finitamente satisfacible y, como contiene a $\Sigma$, y $\Delta$ es maximal, se concluye que $N\alpha \in \Delta$. Q.E.D.