Equivalencia Logica Y Sustitucion

3.1.4 Equivalencia Lógica y Sustitución

Dadas dos fórmulas cerradas

, , si () = () para todas las interpretaciones I, entonces, , es lógicamente equivalente a .

Sea A una fórmula cerrada y U un conjunto de fórmulas cerradas. Si para todas las interpretaciones I,

() = T siempre que

() = T para todo U, entonces A es una consecuencia lógica de U.

U |= A

A

B Si |= A B

U |= A

Si |= ( ^ … ^ ) A

Los dos cuantificadores son duales y uno puede ser definido en términos del otro.

x A(x) x A(x) x A(x) x A(x).

Los cuantificadores universales se distribuyen sobre conjunciones, y los cuantificadores existenciales se distribuyen sobre disyunciones, pero solo mantiene o contiene una dirección para los cuantificadores universales sobre disyunción y cuantificadores existenciales sobre conjunción:

(

x A(x) v x B(x)) x (A(x) v B(x))

x (A(x) ^ B(x)) (x A(x) ^ x B(x))

Si una subfórmula no contiene variables libres entonces los cuantificadores en esa variable pueden ser pasados libremente a travéz de subfórmula, por ejemplo:

x A(x) v B x (A(x) v B).

Pasando cuantificadores a travéz de implicaciones no es simple. La fórmula en la tabla puede ser derivada de fórmulas para disyunción y conjunción reemplazando las implicaciones por su equivalente disyunción y observando la alternación de cuantificadores como la negación se pasa a travéz de ellos.

Ejemplo:

x (A(x) B(x)) x( A(x) v B(x)) x A(x) v x B(x) x A(x) x B(x) x A(x) x B(x).

<=	Regresar Tema 3.1.3 Interpretacion de Predicados

=>	Siguiente Tema: 3.1.5 Tableaux Semantico para Logica de Primer Orden

Regresar al TEMARIO: Matematicas Para Maestria