La lgica de primer orden, tambin llamada lgica de predicados o
clculo de predicados, es un sistema formal diseado para estudiar la
inferencia en los lenguajes de primer orden. Los lenguajes de
primer orden son, a su vez, lenguajes formales con cuantificadores
que alcanzan slo a variables de individuo, y con predicados y
funciones cuyos argumentos son slo constantes o variables de
individuo. Los conceptos bsicos de la Lgica de Primer Orden son:
son: Predicados Constantes de Individuos Variables de Individuos
Cuantificadores Conectivas Argumentos
Un predicado es una expresin lingstica que puede conectarse con
una o varias otras expresiones para formar una oracin. Por ejemplo,
en la oracin Marte es un planeta, la expresin es un planeta es un
predicado que se conecta con la expresin Marte para formar una
oracin. Cuando un predicado se conecta con una expresin, se dice
que expresa una propiedad, y cuando se conecta con dos o ms
expresiones, se dice que expresa una relacin. En la lgica de primer
orden, los predicados son tratados como funciones. Una funcin es un
proceso que recibe un conjunto de cosas, las procesa, y devuelve
como resultado una nica cosa. A las cosas que entran a las
funciones se las llama argumentos, y a las cosas que salen, valores
o imgenes. Considrese por ejemplo la siguiente funcin matemtica:
f(x) = 2x Esta funcin toma nmeros como argumentos y devuelve ms
nmeros como valores. Si toma el nmero 1, devuelve el nmero 2, y si
toma el 5, devuelve el 10. En la lgica de primer orden, se propone
tratar a los predicados como funciones que no slo toman nmeros como
argumentos, sino expresiones como Marte, etc. De este modo, la
oracin Marte es un planeta puede transcribirse, siguiendo la
notacin propia de las funciones: Planeta(Marte) O P(m) En la
matemtica existen adems funciones que toman varios argumentos. Por
ejemplo: f(x,y) = x + y Esta funcin, si toma los nmeros 1 y 2,
devuelve el nmero 3, y si toma el -5 y el -3, devuelve el -8.
Siguiendo esta idea, la lgica de primer orden trata a los
predicados que expresan relaciones, como funciones que toman dos o
ms argumentos. Por ejemplo, la oracin Can mat a Abel puede
formalizarse as: Mat(Can,Abel) o M(c,a). Este procedimiento puede
extenderse para tratar con predicados que expresan relaciones entre
muchas entidades. Por ejemplo, la oracin Ana est sentada entre
Bruno y Carlos puede formalizarse: S(a,b,c)
Una constante de individuo es una expresin lingstica que refiere
a una entidad. Por ejemplo Marte, Jpiter, Can y Abel son constantes
de individuo. Tambin lo son las expresiones 1, 2, etc., que
refieren a nmeros. Una entidad no tiene que existir para que se
pueda hablar acerca de ella, de modo que la lgica de primer orden
tampoco hace supuestos acerca de la existencia o no de las
entidades a las que refieren sus constantes de individuo.
Adems de las constantes de individuo que hacen referencia a
entidades determinadas, la lgica de primer orden cuenta con otras
expresiones, las variables, cuya referencia no est determinada. Su
funcin es similar a la de las expresiones del lenguaje natural como
l, ella, esto, eso y aquello, cuyo referente vara con el contexto.
Las variables generalmente se representan con letras minsculas
cerca del final del alfabeto latino, principalmente la x, y, z. Del
mismo modo, en la matemtica, la x en la funcin f(x) = 2x no
representa ningn nmero en particular, sino que es algo as como un
espacio vaco donde pueden insertarse distintos nmeros. En
conclusin, podemos representar una expresin como esto es antiguo
con la expresin: Antiguo(x) o A(x). Es evidente, sin embargo, que
hasta que no se determine a qu refiere la x, no es posible asignar
un valor de verdad a la expresin esto es antiguo, del mismo modo
que hasta que no se determine un nmero para la x en la funcin f(x)
= 2x, no ser posible calcular ningn valor para la funcin. Por
supuesto, al igual que con las constantes de individuo, las
variables sirven tambin para formalizar relaciones. Por ejemplo, la
oracin esto es ms grande que aquello se formaliza: G(x,y) Y tambin
pueden combinarse constantes de individuo con variables. Por
ejemplo en la oracin ella est sentada entre Bruno y Carlos:
S(x,b,c)
Considrese ahora la siguiente expresin matemtica: x < 3. Esta
expresin no es ni verdadera ni falsa, y parece que no lo ser hasta
que no reemplacemos a la x por algn nmero cualquiera. Sin embargo,
tambin es posible dar un valor de verdad a la expresin si se le
antepone un cuantificador. Un cuantificador es una expresin que
afirma que una condicin se cumple para un cierto nmero de
individuos. En la lgica clsica, los dos cuantificadores ms
estudiados son el cuantificador universal y el cuantificador
existencial. El primero afirma que una condicin se cumple para
todos los individuos de los que se est hablando, y el segundo que
se cumple para al menos uno de los individuos. Por ejemplo, la
expresin "para todo x" es un cuantificador universal, que
antepuesto a "x < 3", produce: Para todo x, x < 3. Esta es
una expresin con valor de verdad que resulta una expresin falsa,
pues existen muchos nmeros (muchos x) que son mayores que tres.
Anteponiendo en cambio la expresin "para al menos un x", un
cuantificador existencial, se obtiene: para al menos un x, x <
3. La cual resulta ser una expresin verdadera. Sin embargo, el
valor de verdad de las dos expresiones anteriores depende de qu
nmeros se est hablando. En lgica, a aquello de lo que se est
hablando cuando se usa algn cuantificador, se lo llama el dominio
de discurso. Tmese por caso la afirmacin "todos son amigables".
Esta oracin puede traducirse as: Para todo x, x es amigable. Y una
oracin como "alguien est mintiendo" puede traducirse: Para al menos
un x, x esta mintiendo. Tambin es frecuente traducir esta ltima
oracin as: Existe al menos un x, tal que x est mintiendo. A
continuacin se formalizan ambas oraciones, introduciendo la notacin
especial para los cuantificadores: Para todo x, x es amigable. x
A(x) Existe al menos un x, tal que x est mintiendo. x M(x)
La lgica de primer orden incorpora adems las conectivas de la
lgica proposicional. Combinando las conectivas con los predicados,
constantes, variables y cuantificadores, es posible formalizar
oraciones como las siguientes: Oracin Scrates es sabio y prudente.
Si Scrates es sabio, entonces tambin es prudente. Nadie es sabio y
adems prudente. Todos los sabios son prudentes. Conectivas Lgicas:
Formalizacin Ss Ps Ss Ps x (Sx Px) x (Sx Px)
Considrese el siguiente argumento clsico: - Todos los hombres
son mortales. - Scrates es un hombre. - Por lo tanto, Scrates es
mortal. La tarea de la lgica de primer orden consiste en determinar
por qu los argumentos como ste resultan vlidos. Para eso, el primer
paso es traducirlos a un lenguaje ms preciso, que pueda ser
analizado mediante mtodos formales. Segn lo visto ms arriba, la
formalizacin de este argumento es la siguiente: x (Hx Mx) Hs Ms
Un sistema formal o un sistema axiomtico es un artificio
matemtico compuesto de smbolos que se unen entre s formando cadenas
que a su vez pueden ser manipuladas segn reglas para producir otras
cadenas. De esta manera, el sistema formal es capaz de representar
cierto aspecto de la realidad. El objetivo de un sistema formal es
sealar como vlidas determinadas cadenas. Estas cadenas vlidas se
denominan teoremas. Para obtener los teoremas se emplean las reglas
de produccin que convierten una cadena en otra. Hay ciertos
teoremas iniciales que no se obtienen de ninguna regla, stos son
los axiomas que se suponen vlidos por definicin y se convierten en
el germen de produccin de teoremas. Un sistema formal matemtico
consiste en lo siguiente: - Un conjunto finito de smbolos que
pueden ser usados para la construccin de frmulas, llamado el
alfabeto o vocabulario. - Una gramtica formal o mecanismo para la
construccin de frmulas bien formadas. Tambin debe proporcionarse un
algoritmo de decisin para conocer si una determinada frmula es bien
formada o no. - Un conjunto de axiomas que deben ser frmulas bien
formadas. - Un conjunto de reglas de inferencia. - Un conjunto de
teoremas. Este conjunto incluye todos los axiomas, ms todas las
frmulas bien formadas que pueden ser derivadas de los axiomas o de
otros teoremas por medio de las reglas de inferencia. La gramtica
no necesariamente garantiza la decidibilidad de si una frmula es
teorema o no.
Las propiedades de un Sistema Formal son: -Coherencia: El
sistema formal es coherente si cada teorema al ser interpretado no
corresponde a una decisin verdadera. -Completitud: El sistema
formal es completo si cada proposicin verdadera puede ser
representada mediante un teorema. Es incompleto si alguna verdad no
puede expresarse. - Decidibilidad: Un sistema formal es decidible
si existe un algoritmo que diga en tiempo finito si una cadena
cualquiera es un teorema o no lo es.
El sistema de Peano es un sistema de postulados a partir del
cual puede deducirse toda la aritmtica de los nmeros naturales. Los
primitivos de este sistema son los trminos "0" (cero), "nmero" y
"sucesor", de los cuales, por ser primitivos no se da definicin
alguna. Sin embargo, se entiende por "0" dicho nmero, el trmino
"nmero" designa a los nmeros naturales 0, 1, 2, 3,...
exclusivamente, y con "sucesor" de un nmero natural n se refiere al
nmero natural inmediato siguiente de n en el orden natural. El
Sistema de Peano contiene los 5 postulados que siguen: P1 0 es un
nmero. P2 El sucesor de un nmero es siempre un nmero. P3 Dos nmeros
nunca tienen el mismo sucesor. P4 0 no es el sucesor de nmero
alguno. P5 Si P es una propiedad tal que (a) cero tiene la
propiedad P, y (b) siempre que un nmero n tenga la propiedad P el
sucesor de n tambin tendr la propiedad P, entonces todos los nmeros
tendrn la propiedad P.
continuacin
El ltimo postulado entraa el principio de induccin matemtica e
ilustra claramente el alcance de una "verdad" matemtica por
convencin. Se construye la aritmtica fundamental sobre esta base,
definiendo los diversos nmeros naturales como el sucesor de cero (
0' ), el sucesor del sucesor de cero( 0 ), y as hasta el infinito.
Luego, se establece la definicin de suma, que expresa que la adicin
de un nmero natural a otro dado puede considerrsela como la suma
repetida de 1; esta ltima operacin es fcilmente expresable por
medio de la relacin de sucesor: (a) n + 0 = n; (b) n + k' = (n + k)
Pasando ahora a la multiplicacin de los nmeros naturales, se la
puede definir por medio de la siguiente definicin por recurrencia,
que expresa de manera rigurosa que el producto nk de dos nmeros
naturales puede ser considerado como la suma de k trminos cada uno
de los cuales es igual a n, en otros trminos: (a) n . 0 = 0; (b) n.
k' = n. k + n
El alfabeto L de la lgica de primer orden es un conjunto que
contiene los siguientes tipos de smbolos: Smbolos de predicados o
de relaciones n-arias: Son smbolos que corresponden a funciones
(reciben argumentos) que 'predican' algo acerca de referentes.
Corresponden a afirmaciones. Ej: C(x) abrevia 'x es calvo', y es
una funcin unaria (recibe slo una entrada); D(y, z) abrevia 'y le
debe dinero a z' y es una funcin binaria; H(a,b,d) abrevia 'a y b
se casaron en el lugar c' y es trinaria. En general, la relacin
R(X1, X2, ..., Xk) es una relacin k-aria. Aqu, D, R y H se llaman
smbolos de relacin y estos smbolos son los elementos de L, no las
funciones. Smbolos de Funcin n-aria: Son smbolos que corresponden a
funciones que denotan cosas nicas, en funcin de sus argumentos.
Note que difieren de los predicados ya que no simbolizan frmulas,
sino trminos ('cosas'). Ej: P(w) abrevia 'el padre de w' ; D(v)
abrevia 'la edad de v'. Note que H(x) (el hijo de x) no es funcin,
ya que no precisa necesariamente un nico objeto determinado, sino
que es ambiguo. Variables: x, y, z, w, x1, x2, ...(principalmente).
Se refieren a objetos indeterminados. Constantes: a, b, c, a1, a2,
a3, ... Se refieren a objetos determinados, particulares (p.ej., n
denota a Nicols). Cuantificadores: (existe), (para todo).
Conectivos lgicos: (No), (o), (y), (implica), (equivale/si y solo
si). Igualdad, comas y parntesis: = , , , ( , ). As, el conjunto A
definido arriba es de la forma: A = { R1, R2, ..., f1, f2, ..., x,
y, z, w, x1, x2, ..., a, b, c, a1, a2, ..., , ,,, ,,, =, (, )},
donde las R's son smbolos de relacin, y los f's son smbolos de
funcin. Al especificar un conjunto A, debe tambin especificarse la
aridad de cada relacin y de cada funcin.
Una vez definido el alfabeto, el siguiente paso es determinar qu
combinaciones de smbolos pertenecen al lenguaje del sistema. Esto
se logra mediante una gramtica formal. La misma consiste en un
conjunto de reglas que definen recursivamente las cadenas de
caracteres que pertenecen al lenguaje. A las cadenas de caracteres
construidas segn estas reglas se las llama frmulas bien formadas.
Las reglas del sistema L son: 1. Las variables proposicionales del
alfabeto de L son frmulas bien formadas. 2. Si * es una frmula bien
formada de L, entonces * tambin lo es. 3. Si * y = son frmulas bien
formadas de L, entonces (*=), (*=), (*p=) y (*m=) tambin lo son. 4.
Slo las expresiones que pueden ser generadas mediante las clusulas
1 a 3 en un nmero finito de pasos son frmulas bien formadas de
L.
Una regla de inferencia es una funcin que va de conjuntos de
frmulas a frmulas. Al conjunto de frmulas que la funcin toma como
argumento se lo llama premisas, mientras que a la frmula que
devuelve como valor se la llama conclusin. En general se busca que
las reglas de inferencia transmitan la verdad de las premisas a la
conclusin. Es decir, que sea imposible que las premisas sean
verdaderas y la conclusin falsa. En el caso de L, la nica regla de
inferencia es el modus ponens, el cual dice: Si A, entonces B A Por
lo tanto, B Por ejemplo, un razonamiento que sigue la forma del
modus ponens podra ser: Si est soleado, entonces es de da. Est
soleado. Por lo tanto, es de da. Otro ejemplo sera Si Javier tiene
rabia, es una nube. Javier tiene rabia. Por lo tanto, Javier es una
nube. Otra manera de presentar el modus ponens con el condicional
es:
Los axiomas lgicos son parte del clculo de predicados. Al
formalizar teoras de primer orden particulares (aritmtica de Peano)
se agregan axiomas no-lgicos especficos, es decir axiomas que no se
consideran verdades de la lgica pero s verdades de una teora
particular. Cuando el conjunto de axiomas es infinito, se requiere
de un algoritmo que pueda decidir para una frmula bien formada si
es un axioma o no. Ms an, debera existir un algoritmo que pueda
decidir si la aplicacin de una regla de inferencia es correcta o
no. El clculo de predicados puede ser axiomatizado de varias formas
diferentes. No existe estndar sobre los axiomas y reglas de
inferencia dadas, pero cualquier formalizacin produce los mismos
teoremas de la lgica. Los siguientes tres axiomas son heredados de
la lgica proposicional y se incorporan a la lgica de primer orden.
Sean A, B y C frmulas bien formadas de Q. Luego, los siguientes son
axiomas lgicos: Ax1:A (B A) Ax2: (A (B C)) ((A B) (A C)) Ax3: (A B)
(B A) Los dos axiomas siguientes son caractersticos de la lgica de
primer orden. Sean A y B frmulas bien formadas de Q con como mximo
una variable libre, x. Sea t un trmino cerrado y A(x/t) el
resultado de reemplazar toda aparicin de x en A por t. Luego, los
siguientes son axiomas lgicos: Ax4: x A A(x/t) Ax5: x (A B) ( xA x
B) Intuitivamente, el cuarto axioma dice que lo que vale para todos
vale para cualquiera. Por ejemplo: Si todos son mortales, entonces
Abel es mortal; o tambin: Si todos son mortales, entonces el padre
de Mateo es mortal El quinto axioma es anlogo al axioma K de la
lgica modal, y un caso particular del mismo podra ser: Si todos los
humanos son mortales, entonces, si todos son humanos, todos son
mortales.
Una interpretacin es un par , donde D es un conjunto no vaco
llamado el dominio de discurso e I es una funcin llamada la funcin
de interpretacin definida como sigue: - Si a es un nombre, entonces
I le asigna un elemento del dominio. - Si f es un functor de aridad
n, entonces I le asigna una funcin de n argumentos que toma
elementos del dominio y devuelve elementos del dominio. - Si P es
un predicado de aridad n, entonces I le asigna un conjunto de
n-tuplas construidas a partir del dominio. Luego es posible definir
la nocin de verdad para una interpretacin (para las oraciones de
Q): 1. P(t1,...,tn) es verdadera para la interpretacin M si y slo
si la n-tupla formada por las interpretaciones de t1,...,tn es un
elemento de la interpretacin de P. 2. A es verdadera para la
interpretacin M si y slo si A es falsa bajo esa interpretacin. 3.
(A B) es verdadera para la interpretacin M si y slo si A es
verdadera y B es verdadera bajo esa interpretacin. 4. (A B) es
verdadera para la interpretacin M si y slo si A es verdadera o B es
verdadera bajo esa interpretacin. 5. (A B) es verdadera para la
interpretacin M si y slo si A es falsa o B es verdadera bajo esa
interpretacin. 6. (A B) es verdadera para la interpretacin M si y
slo si A y B son ambas verdaderas o ambas falsas bajo esa
interpretacin.
Para dar las definiciones de verdad para frmulas con la forma x
A o x A, primero son necesarias algunas definiciones preliminares:
Sea A(x/a) el resultado de reemplazar toda aparicin de x en A por
un nombre a (que no haya sido utilizado en la frmula). Adems, si M
e M' son interpretaciones y a un nombre, entonces M' es una
a-variante de M si y slo si M' es idntica a M o difiere slo en el
elemento del dominio que le asigna al nombre a. 7. x A es verdadera
para M si y slo si A(x/a) es verdadera para toda a-variante de M.
8. x A es verdadera para M si y slo si A(x/a) es verdadera para al
menos una a-variante de M. Una frmula es falsa bajo una
interpretacin si y slo si no es verdadera bajo esa interpretacin. A
partir de esto pueden definirse varias otras nociones semnticas: -
Una frmula es una verdad lgica si y slo si es verdadera para toda
interpretacin. - Una frmula es una contradiccin si y slo si es
falsa para toda interpretacin. - Una frmula es consistente si y slo
si existe al menos una interpretacin que la haga verdadera. - Una
frmula A es una consecuencia semntica de un conjunto de frmulas si
y slo si no hay ninguna interpretacin que haga verdaderas a todas
las frmulas en y falsa a A. Cuando A es una consecuencia semntica
de en un lenguaje Q, se escribe: - Una frmula A es lgicamente vlida
si y slo si es una consecuencia semntica del conjunto vaco. Cuando
A es una frmula lgicamente vlida de un lenguaje Q, se escribe:
continuacin
El dominio de un modelo es el conjunto de objetos que contiene;
a estos objetos a veces se les denomina elementos del dominio.
