Fundamentos de Lógica y Computabilidad: Validez, Satisfacibilidad y Teorema de Rice

Conceptos Fundamentales de Lógica Proposicional

Validez y Satisfacibilidad de Fórmulas

Sabemos que la fórmula $ \sim F \lor G $ no es válida. Esto significa que la fórmula $ \sim F \lor G $ es falsa bajo alguna interpretación. Por lo tanto, existe alguna interpretación bajo la que la fórmula $ F $ es verdadera y la fórmula $ G $ es falsa.

Es seguro que $ F $ es satisfacible, ya que existe al menos una interpretación que la hace verdadera. Y también es seguro que $ G $ no es válida, puesto que existe una interpretación que la hace falsa.

Razonamiento Lógico y Consecuencia

Consideremos la relación de consecuencia lógica: $ F \to G \models H $. Si $ G $ es satisfacible, podemos asegurar que $ H $ es satisfacible.

Un razonamiento correcto nos exige que, siempre que las premisas sean verdaderas, la conclusión debe ser también verdadera. Como $ F $ es válida, entonces $ H $ debe ser verdadera, como mínimo, en todas las interpretaciones en las que $ G $ sea verdadera.

Definiciones Clave en Lógica

• Consistente: Un conjunto de fórmulas es consistente si todas son verdaderas bajo alguna interpretación $I$.
• Válida: Una fórmula es verdadera en todas las interpretaciones (Tautología).
• Satisfacible: Una fórmula es verdadera en alguna interpretación.
• Insatisfacible: Una fórmula es falsa en todas las interpretaciones (Contradicción).

Teoría de la Computabilidad: La Macro de Universalidad

Si queremos ejecutar el programa $P$ con un único parámetro de entrada $x$, deberemos utilizar la macro de universalidad $U$.

Para ello, se le pasa como primer parámetro la codificación de $P$ (generalmente almacenada en un registro, digamos $X2$) y como segundo parámetro la entrada $x$ (almacenada en $X1$). Además, queremos dejar el resultado de $f(x)$ en $X1$.

Por lo tanto, la solución utilizando la macro de universalidad es:

X1 := U(X2, X1);

Tablas de Verdad de Conectivas Lógicas

A continuación, se presentan las tablas de verdad para las principales conectivas binarias:

Conjunción ($P \land Q$)

Disyunción ($P \lor Q$)

Implicación ($P \to Q$)

Doble Implicación ($P \leftrightarrow Q$)

Ejemplo de Programa: Cálculo de Funciones Recursivas

A continuación, se presenta un programa $P$ que calcula la función $\varphi^{(2)}_P(x, y) = x \times (y + 1)$ utilizando registros y operaciones básicas (sucesor, predecesor, bucles):

X3 := X1;
X1 := 0;
while X3 $\neq$ X4 do
    begin
    X5 := X2;
    X1 := succ(X1);
    X3 := pred(X3);
    while X5 $\neq$ X4 do
        begin
        X1 := succ(X1);
        X5 := pred(X5);
        end
    end
end

Nota: Se asume que $X4$ contiene el valor 0.

Propiedades de las Funciones Computables: Totalidad

Afirmaciones Verdaderas sobre Totalidad

1. Puede ocurrir que la función $\varphi^{(1)}_P(x)$ sea total y que la función $\varphi^{(3)}_P(x, y, z)$ no sea total.
2. Si $\varphi^{(2)}_P(x_0, y_0) = \perp$ (indeterminado) para algún $x_0, y_0$, entonces $\varphi^{(3)}_P(x, y, z)$ no es total.

La razón es que si $\varphi^{(2)}_P(x_0, y_0) = \perp$, esto implica que el programa diverge para esa entrada. Dado que $\varphi^{(2)}_P(x_0, y_0) = \perp = \varphi^{(3)}_P(x_0, y_0, 0)$, si la función de aridad 2 diverge, la función de aridad 3 también diverge para esa entrada, y por lo tanto, no es total.

Ejemplo de Divergencia (Bucle Infinito)

begin 
    while X3 $\neq$ 0 do 
        begin 
        end 
end

El Teorema de Rice y la Irresolubilidad

El Teorema de Rice establece que cualquier propiedad no trivial de las funciones parciales computables es indecidible.

Requisitos para Aplicar el Teorema de Rice

1. Que la propiedad sea semántica:

   La propiedad debe depender únicamente de la función calculada por el programa, y no de la sintaxis o estructura interna del código. En este caso, la propiedad es obviamente semántica, ya que solo depende de los valores devueltos por el programa.

2. Que la propiedad no sea trivial:

   Para demostrar que la propiedad no es trivial, debemos diseñar un programa que cumpla la propiedad y otro programa que no la cumpla.

Demostración de Irresolubilidad

La irresolubilidad de la propiedad puede demostrarse mediante el Teorema de Rice considerando los siguientes ejemplos:

Programa que Cumple la Propiedad

begin
    X1 := 1;
end

Programa que NO Cumple la Propiedad

begin
end