L´ogica Proposicional y de Predicados

Introducci´on

La l´ogica, o al menos la matem´atica l´ogica, consiste en deducciones. Vamos a examinar las reglas

de deducci´on haciendo uso de precisi´on que caracteriza el enfoque matem´atico Al hacer esto, si

queremos que haya tenemos que hacer inequ´ıvoco nuestro lenguaje, y la manera matem´atica estandar

de lograr esto consiste en introducir un lenguaje simb´olico en el que los s´ımbolos tengan significados

y usos enunciados con toda presici´on.

El lenguaje , como instrumento de comunicaci´on del conocimiento humano, est´a constituido por

frases de tipo interrogativo, imperativas y declarativas. Estas ´ultimas constituyen el elemento b´asico

de la descripci´on del conocimiento.

El conocimiento puede producirse bien por constataciones de hechos o ideas, que tienen un reflejo

en frases de tipo declarativas, como por deducci´on, a partir de una serie de declaraciones, de otras

nuevas cuya afirmaci´on se sigue necesariamente de las declaraciones previas.

Todas las presentaciones de las formulas matem´aticas de la l´ogica m´as usual, tienen en com´un una

etapa previa de simbolizaci´on de las formas de lenguaje usual que puede hacerse a dos niveles seg´un

el grado de complejidad del an´alisis y son el Calculo Proposicional y el Calculo de Predicados.

Calculo Proposicional

es la representaci´on del lenguaje usual tomando como elemento b´asico de la formulaci´on una

representaci´on matem´atica de las frases declarativas simples (proposiciones).

Calculo de Predicados

es la representaci´on del lenguaje usual tomado como base de los componentes de algunos tipos

de proposici´on: t´erminos y predicados.

Para cada uno de los niveles de representaci´on matem´atica del lenguaje, la forma de presentar las

estructuras deductivas correctas tiene dos l´ıneas principales:

1. Definici´on axiom´atica de una serie de estructuras deductivas correctas, y de las reglas para

obtenci´on de nuevas estructuras deductivas correctas a partir de aquellas.

2. Definici´on de un conjunto de significados (normalmente: verdadero o falso) atribuible a las

proposiciones, y definici´on de las estrucuturas deductivas correctas en t´erminos de relaci´on

entre significados de los elementos de la deducci´on.

En la primera l´ınea est´an los modelos de teor´ıa de la demostraci´on y deducci´on natural, y en la

segunda l´ınea la teor´ıa interpretativa o de modelos.

Predicados y Cálculo de Predicados

El Cálculo Proposicional nos permitió razonar con fórmulas construídas con variables y

operadores booleanos, con lo cual nos fue posible expresar afirmaciones o frases que pueden

modelizarse utilizando expresiones de tipo booleano. El Cálculo de Predicados nos permitirá

ampliar el espectro, trabajando con fórmulas de diversos tipos además del booleano. La construcción

de fórmulas que veremos en este cálculo nos obliga a definir nuevas expresiones llamadas

predicados

pueden ser de diferentes tipos, es decir un predicado puede ser una función de tipo

. Un predicado es una aplicación de una función booleana cuyos argumentosZ → B

como la función

Los nombres de las funciones (

utilizamos la notación

expresión

Vemos que los argumentos de los predicados son en este caso, variables de tipo distinto de

par.i o Z × Z → B como la función igual(x, x − z + z) o menor(x, y + z).igual, menor) son llamados símbolos de predicados. Tambiénx < y para expresar el predicado menor(x, y). Por ejemplo, la siguientex < y ∧ x = z ⇒ q(x, z + x) contiene tres predicados, x < y, x = z y q(x, x + z).B

o también expresiones de éstos tipos. Los argumentos de un predicado son llamados

por ejemplo en la fórmula anterior los términos en los predicados son

Diremos que una fórmula del cálculo de predicados es una expresión booleana en la cual

alguna de las variables booleanas ha sido reemplazada por:

términos,x, y, z y z + x.

•

predicados.

•

Por ejemplo, la expresión

predicados.

El cálculo de predicados incluye los axiomas del cálculo proposicional y los axiomas correspondientes

a las expresiones cuantificadas

Las reglas de inferencia del cálculo de predicados son la Sustitución, Transitividad de la igualdad,

Leibniz y la extensión de esta regla para cuantificaciones que también vimos en el capítulo

anterior.

cuantificaciones existenciales o universales.x < y ∧ x = z ⇒ q(x, z + x) es una fórmula del cálculo de(∧ : R : P) y (∨ : R : P) que vimos en el capítulo 5.

6.2. El cuantificador universal

La conjunción

considerarse una operación válida para definir la expresión cuantificada

∧ es asociativa, conmutativa y tiene elemento neutro true. Por lo tanto puede

(

como ya vimos en el capítulo 5. El símbolo

universal

6.2. E

todo

anterior para el caso particular del cuantificador universal.

∧x : R : P) (6.1)∀, que se lee “para todo”, se conoce como cuantificadory la expresión anterior se denomina cuantificación universal y se lee “paraL CUANTIFICADOR UNIVERSAL 113x que satisfaga R se satisface P”. Vamos a repasar ahora los axiomas vistos en el capítulo

Rango vacío

(

∀ i : false : T.i) ≡ true

Rango unitario

Si i no es una variable libre en la expresión N, entonces

(

∀ i : i = N : T.i) ≡ T.N

Distributividad

Como el operador ∨ es distributivo a derecha e izquierda con respecto al operador

∧

, y true es absorbente para ∨, vale

(

∀ i : R.i : x ∨ T.i) ≡ x ∨ (∀ i : R.i : T.i) (6.2)

(

En este axioma la expresión

dependiendo del lado derecho o izquierdo) no puede contener a

Esta restricción asegura que el lado izquierdo y el derecho en el axioma referencian a las

mismas variables libres, de otro modo no se podría asegurar la equivalencia en general.

∀ i : R.i : T.i ∨ x) ≡ (∀ i : R.i : T.i) ∨ x (6.3)x que es trasladada fuera del alcance (o dentro del alcance,i como variable libre.

Partición de rango

es de la forma

Como el operador ∧ es idempotente, entonces cuando el rango de especificaciónR ∨ S vale

(

∀ i : R.i ∨ S.i : T.i) ≡ (∀ i : R.i : T.i) ∧ (∀ i : S.i : T.i)

Partición de rango generalizada

(

∀ i : (∃j : S.i.j : R.i.j) : T.i) ≡ (∀ i, j : S.i.j ∧ R.i.j : T.i)

Regla del término

(

∀ i : R.i : T.i ∧ G.i) ≡ (∀i : R.i : T.i) ∧ (∀i : R.i : G.i)

Regla del término constante

decir, la variable cuantificada

entonces

Si el término de la cuantificación es igual a una constante C, esi no aparece en C y el rango de especificación es no vacío,

(

∀ i : R : C) ≡ C

Regla de anidado

(

Regla de intercambio de variables dummy

Si V.j ∩ (FV.R ∪ FV.T) = ∅ entonces

(

∀ i : R : T) ≡ (∀ j : R[i := j] : T[i := j])

Regla de cambio de variable dummy

no aparezca en

Para toda función f biyectiva y para toda variable j queR ni en T, vale

(

∀ i : R.i : T.i) ≡ (∀ j : R.f.j : T.f.j)

A continuación presentaremos axiomas adicionales y teoremas para el cuantificador universal.

6.2.1. Traslación con el operador universal

El axioma que sigue nos permitirá trasladar el rango de especificación hacia el término de

cuantificación:

(6.1) Axioma.

Traslación

(

∀ i : R.i : T.i) ≡ (∀ i : : R.i ⇒ T.i)

Este axioma permite demostrar también los siguientes teoremas:

(6.2) Teorema.

Traslación

a)

(∀ x : R : P) ≡ (∀ x :: ￢R ∨ P)

b)

(∀ x : R : P) ≡ (∀ x :: R ∧ P ≡ R)

c)

(∀ x : R : P) ≡ (∀ x :: R ∨ P ≡ P)

(6.3) Teorema.

Traslación

a)

(∀ x : Q ∧ R : P) ≡ (∀ x : Q : R ⇒ P)

b)

(∀ x : Q ∧ R : P) ≡ (∀ x : Q : ￢R ∨ P)

c)

(∀ x : Q ∧ R : P) ≡ (∀ x : Q : R ∧ P ≡ R)

d)

(∀ x : Q ∧ R : P) ≡ (∀ x : Q : R ∨ P ≡ P)

Probaremos (6.3a))

(

=

∀ x : Q ∧ R : P)hTraslación 6.1i

(

=

∀ x :: Q ∧ R ⇒ P)hTeorema 3.64i

(

=

∀ x :: Q ⇒ (R ⇒ P))hTraslación 6.1i

(

∀ x : Q : R ⇒ P)

6.2. E

L CUANTIFICADOR UNIVERSAL 115

6.2.2. Distributividad con el cuantificador universal

Ya vimos en 6.2 cómo

∨ distribuye respecto de ∀

Suponiendo que

x no es una variable libre en P, vale

P

∨ (∀ x : R : Q) ≡ (∀ x : R : P ∨ Q)

El axioma 6.2 nos permite demostrar los siguientes teoremas:

(6.4) Teorema.

Suponiendo que x no es variable libre en P, se tiene que

(

∀ x : R : P) ≡ P ∨ (∀ x :: ￢R)

(6.5) Teorema.

libre en

Distributividad de ∧ respecto de ∀: Suponiendo que x no es una variableP, vale

￢

(∀ x :: ￢R) ⇒ ((∀ x : R : P ∧ Q) ≡ P ∧ (∀ x : R : Q))

(6.6) Teorema.

(

∀ x : R : true) ≡ true

(6.7) Teorema.

(

∀ x : R : P ≡ Q) ⇒ ((∀ x : R : P) ≡ (∀ x : R : Q))

Vamos a probar el teorema 6.5. Este teorema asegura que una conjunción puede trasladarse

fuera del alcance de la cuantificación si el rango

R no es siempre falso como lo indica el antecedente

￢

el consecuente:

(∀ x :: ￢R). La prueba se hará suponiendo el antecedente ￢(∀ x :: ￢R) y demostrando

(

=

∀ x : R : P ∧ Q)h(5.11) Distributividad de ∀ sobre ∧i

(

=

∀ x : R : P) ∧ (∀ x : R : Q)h(6.4) ya que x no es variable libre en Pi

(

=

P ∨ (∀ x :: ￢R)) ∧ (∀ x : R : Q)hSuposición de ￢(∀ x :: ￢R) o bien (∀ x :: ￢R) ≡ falsei

(

=

P ∨ false) ∧ (∀ x : R : Q)h(3.29) Elemento neutro de ∨i

P

∧ (∀ x : R : Q)∀ i, j : R.i ∧ S.i.j : Ti.j) ≡ (∀ i : R.i : (∀ j : S.i.j : T.i.j))