logica

TEMA

4

La L´gica Cl´sica de
o
a
Predicados de Primer Orden

4.1.

Lenguajes de Primer Orden

Alfabeto
Los elementos comunes de los alfabetos de los lenguajes de primer orden
son:
1. Las conectivas de la l´gica proposicional: ¬, →, ∧, ∨, ↔.
o
2. Las constantes l´gicas: ⊤, ⊥.
o
3. Los s´
ımbolos de cuantificaci´n: ∀, ∃.
o
4. Los s´
ımbolos de puntuaci´n: “(”, “)” y “,”
o5. Un conjunto infinito numerable, V , de variables. (como s´
ımbolos, utilizaremos las ultimas letras del alfabeto x, y, z,. . . , posiblemente subin´
dizadas).
A todos estos s´
ımbolos hay que a˜adir los elementos de la signatura del lenn
guaje, C, F , P , y que viene determinada por la aplicaci´n o el dominio en
o
el que queramos trabajar. Los tres conjuntos que describimos a continuaci´no
y el conjunto de variables V , deben ser disjuntos dos a dos, es decir, no puede
haber elementos comunes entre ellos.
6. C denota al conjunto de s´
ımbolos de constante, puede ser vac´ finito
ıo,
o infinito numerable. Utilizaremos las primeras letras del alfabeto, a, b,
c,. . . , con o sin sub´
ındices.
7. F denota al conjunto de s´
ımbolos de funci´n, puede ser vac´ finito o ino
ıo,finito numerable. Este conjunto tiene asociado una funci´n rF : F → N∗ ,
o

I. T. en Inform´tica de Sistemas. L´gica computacional
a
o

1

2

L´gica Computacional
o

que asigna a cada s´
ımbolo de funci´n un n´mero llamado aridad. Utilio
u
zaremos las letras del alfabeto, f , g, h,. . . , con o sin sub´
ındices.
8. P denota al conjunto de s´
ımbolos de predicado, puede ser finitoo infinito numerable, pero no vac´ Este conjunto tiene asociado una funci´n
ıo.
o
∗ , que asigna a cada s´
rP : P → N
ımbolo de predicado un n´mero llamado
u
aridad. Utilizaremos letras may´sculas, P , Q, R,. . . , con o sin sub´
u
ındices. Los s´
ımbolos de predicado de aridad 1 se denominan propiedades y
el resto se denominan gen´ricamente relaciones.
e
´
Definicion 4.1 Dados cuatroconjuntos C, F , P y V disjuntos do a dos y
en las condiciones descritas anteriormente, el alfabeto del lenguaje de primer
orden con signatura C, F , P , que denotamos L1 (C, F , P ), es:
C ∪ F ∪ P ∪ V ∪ {⊥, ⊤, ∧, ∨, ¬, →, ↔, ∀, ∃, ‘(′ , ‘)′ , ‘,′ }
T´rminos
e
En la l´gica de primer orden, las afirmaciones m´s simples no se represeno
a
tan por s´
ımbolos, sino que se entra en suestructura distinguiendo “de qui´n”
e
o qui´nes queremos establecer una propiedad o relaci´n y las “propiedades” y
e
o
“relaciones”. Para representar a los individuos de ese universo de discurso, utilizamos las variables, las constantes y las funciones, pero los objetos sint´cticos
a
que van a representar a estos individuos son los t´rminos.
e
El conjunto de t´rminos se define recursivamente apartir del alfabeto,
e
pero “no” ser´n f´rmulas del lenguaje. Como hemos dicho, se utilizar´n en su
a o
a
definici´n y representar´n a elementos concretos o arbitrarios del universo de
o
a
discurso.
´
Definicion 4.2 Dada la signatura C, F , P , denotaremos por T (C, F ) al
conjunto de los t´rminos, que se define recursivamente como sigue:
e
1. Los elementos de V y C son t´rminos,
e
2. Sif es un s´mbolo de funci´n de aridad n (es decir, rF (f ) = n) y
ı
o
t1 , . . . , tn son t´rminos, entonces f (t1 , . . . , tn ) es un t´rmino;
e
e
Los t´rminos en los que no intervienen variables se denominan t´rminos b´sie
e
a
cos y el conjunto formado por ellos se denota T B(C, F ).
Gram´tica de L1 (C, F , P )
a
Ya podemos definir el conjunto de f´rmulas del lenguaje de primer orden.o
Como vemos, en este caso, el punto de mayor complejidad es la definici´n de
o

E.T.S.I.Inform´tica
a

Tema 4: La L´gica Cl´sica de Predicados de Primer Orden.
o
a

las f´rmulas at´micas, en la que intervienen los t´rminos que hemos definido
o
o
e
anteriormente.
´
Definicion 4.3 El conjunto de f´rmulas (bien formadas) del lenguaje L1 (C, F , P )
o
se define recursivamente...