ensayo

1)

Variable libre y ligada

La expresión a la cual el cuantificador se aplica es el dominio del cuantificador; y una ocurrencia de una variable individual x está ligada  si aparece como  o  o dentro del dominio de un o . Cualquier otro tipo de ocurrencia de una variable es una ocurrencia libre.

    Inductiva conjunto de VL(A) conjunto de variables libres de A.

1. Si A es atómica VL(A):= conjunto de todas las variables que aparecen en un A. 

2. Si A es ¬B entonces VL(A):= VL(B) 

3. Si A es (B*C) donde * es cualquier conectivo binario, entonces VL(A):= VL(B) U VL(C) 

4. Si A es B o B entonces VL(A):= VL(B) - {x}

    Si  es una proposición; sino es una forma proposicional.

Ejemplo. 1)

2) Equivalencias lógicas

Dos formas proposicionales P y Q se dicen lógicamente equivalentes, y se escribe P ≡ Q, si sus tablas de verdad coinciden.

Ejemplos:

1. Las dos sentencias siguientes son lógicamente equivalentes:

Si Lisa está en Francia, entonces ella está en Europa (en símbolos, {\displaystyle f\rightarrow e} {\displaystyle f\rightarrow e}).

Si Lisa no está en Europa, entonces ella no está en Francia (en símbolos, {\displaystyle \neg e\rightarrow \neg f} {\displaystyle \neg e\rightarrow \neg f}).

Sintácticamente, (1) y (2) son derivables cada una de la otra a través de la regla de contraposición y doble negación. Semánticamente, (1) y  (2) son verdaderas en exactamente los mismos modelos (interpretaciones, valuaciones); a saber, aquellos en que Lisa está en Francia es falso o bien Lisa está en Europa es verdadero.

2. El programa está bien escrito y bien documentado.

El programa está bien documentado y bien escrito.

~ (p ∨ q) ≡~ p∧ ~ q

3.

3) Forma rectificada

F esta en forma rectificada si ninguna variable aparece libre y ligada y cada cuantificador se refiere a una variable diferente.
Ejemplo:

4)

En lógica de primer orden, una fórmula bien formada tiene forma normal prenexa si está escrita encabezada por una cadena de cuantificadores existenciales o universales, seguidos por una fórmula sin cuantificadores lógicos, designada como «matriz».

Toda fórmula es equivalente en lógica clásica a una fórmula en forma normal prenexa. Por ejemplo, si ${\displaystyle \phi (y)}$, ${\displaystyle \psi (z)}$, y ${\displaystyle \rho (x)}$ son fórmulas sin cuantificar con las variables libres mostradas, luego

${\displaystyle \forall x\exists y\forall z(\phi (y)\lor (\psi (z)\rightarrow \rho (x)))}$

está en forma normal prenexa, con la matriz ${\displaystyle \phi (y)\lor (\psi (z)\rightarrow \rho (x))}$, mientras que

${\displaystyle \forall x((\exists y\phi (y))\lor ((\exists z\psi (z))\rightarrow \rho (x)))}$

es lógicamente equivalente pero no en forma prenexa.

El término «prenexa» viene del latín praenexus, pasado participio de praenectere, que significa «atado» o «atado en el frente».¹

Cuando una fórmula en forma normal prenexa sólo posee cuantificadores universales, se dice que está en forma normal de Skolem. Toda fórmula en forma normal prenexa es lógicamente equivalente a una en forma normal de Skolem, y la manera de llegar de una a otra se denomina skolemización.

Ejemplos:

Supóngase que ${\displaystyle \phi }$, ${\displaystyle \psi }$, y ${\displaystyle \rho }$ son fórmulas sin cuantificar y no comparten variable libre alguna. Considerese la fórmula

${\displaystyle (\phi \lor \exists x\psi )\rightarrow \forall z\rho }$.

Aplicando recursivamente las reglas empezando por las subfórmulas internas, la siguiente secuencia de fórmulas lógicamente equivalentes pueden obtenerse:

${\displaystyle (\exists x(\phi \lor \psi ))\rightarrow \forall z\rho }$,

${\displaystyle \forall x((\phi \lor \psi )\rightarrow \forall z\rho )}$,

${\displaystyle \forall x(\forall z((\phi \lor \psi )\rightarrow \rho )))}$,

${\displaystyle \forall x\forall z((\phi \lor \psi )\rightarrow \rho )}$.

Esta no es la única forma prenexa equivalente a la fórmula original. Por ejemplo, abordando el consecuente antes que el anecedente en el ejemplo, la forma prenexa

${\displaystyle \forall z\forall x((\phi \lor \psi )\rightarrow \rho )}$

Puede ser obtenida:

${\displaystyle \forall z((\phi \lor \exists x\psi )\rightarrow \rho )}$

${\displaystyle \forall z((\exists x(\phi \lor \psi ))\rightarrow \rho )}$,

${\displaystyle \forall z(\forall x((\phi \lor \psi )\rightarrow \rho ))}$,

${\displaystyle \forall z\forall x((\phi \lor \psi )\rightarrow \rho )}$