Art & Design">
Logica de Primer Orden
Logica de Primer Orden
Logica de Primer Orden
, también llamada ë
o
ëë
, es un
sistema formal diseñado 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 sólo a variables de individuo, y con
predicados y funciones cuyos argumentos son sólo constantes o variables de individuo.
En la lógica de primer orden, los predicados son tratados como funciones. îna función 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 imágenes. Considérese por ejemplo la
siguiente función matemática: Esta función toma números como argumentos y devuelve más
números como valores. Si toma el número 1, devuelve el número 2, y si toma el 5, devuelve el 10.
En la lógica de primer orden, se propone tratar a los predicados como funciones que no sólo toman
números como argumentos, sino expresiones como «Marte», etc. De este modo, la oración «Marte es un
planeta» puede transcribirse, siguiendo la notación propia de las funciones: Planeta(Marte) O P(m)
En la matemática existen además funciones que toman varios argumentos. Por ejemplo: Esta
función, si toma los números 1 y 2, devuelve el número 3, y si toma el -5 y el -3, devuelve el -8. Siguiendo
esta idea, la lógica de primer orden trata a los predicados que expresan relaciones, como funciones que
toman dos o más argumentos. Por ejemplo, la oración «Caín mató a Abel» puede formalizarse así:
Mató(Caín,Abel) o M(c,a). Este procedimiento puede extenderse para tratar con predicados que expresan
relaciones entre muchas entidades. Por ejemplo, la oración «Ana está sentada entre Bruno y Carlos» puede
formalizarse: S(a,b,c)
îna constante de individuo es una expresión lingüística que refiere a una entidad. Por ejemplo «Marte»,
«Júpiter», «Caín» y «Abel» son constantes de individuo. También lo son las expresiones «1», «2», etc., que
refieren a números.
îna entidad no tiene que existir para que se pueda hablar acerca de ella, de modo que la lógica de primer
orden tampoco hace supuestos acerca de la existencia o no de las entidades a las que refieren sus
constantes de individuo.
Además de las constantes de individuo que hacen referencia a entidades determinadas, la lógica de primer
orden cuenta con otras expresiones, las variables, cuya referencia no está determinada. Su función es similar
a la de las expresiones del lenguaje natural como «él», «ella», «esto», «eso» y «aquello», cuyo referente varía
con el contexto. Las variables generalmente se representan con letras minúsculas cerca del final del alfabeto
latino, principalmente la x, y, z.
Del mismo modo, en la matemática, la x en la función f(x) = 2x no representa ningún número en particular,
sino que es algo así como un espacio vacío donde pueden insertarse distintos números. En conclusión,
podemos representar una expresión como «esto es antiguo» con la expresión:
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 expresión «esto es antiguo», del mismo modo que hasta que no se determine un número para la
x en la función f(x) = 2x, no será posible calcular ningún valor para la función.
Por supuesto, al igual que con las constantes de individuo, las variables sirven también para formalizar
relaciones. Por ejemplo, la oración «esto es más grande que aquello» se formaliza: G(x,y)
Y también pueden combinarse constantes de individuo con variables. Por ejemplo en la oración «ella está
sentada entre Bruno y Carlos»: S(x,b,c)
Considérese ahora la siguiente expresión matemática: . Esta expresión no es ni verdadera ni falsa, y
parece que no lo será hasta que no reemplacemos a la x por algún número cualquiera. Sin embargo, también
es posible dar un valor de verdad a la expresión si se le antepone un cuantificador. în cuantificador es una
expresión que afirma que una condición se cumple para un cierto número de individuos. En la lógica clásica,
los dos cuantificadores más estudiados son el cuantificador universal y el cuantificador existencial. El primero
afirma que una condición 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 expresión "para todo x" es un cuantificador
universal, que antepuesto a "x < 3", produce: Para todo x, x < 3. Esta es una expresión con valor de verdad
que resulta una expresión falsa, pues existen muchos números (muchos x) que son mayores que tres.
Anteponiendo en cambio la expresión "para al menos un x", un cuantificador existencial, se obtiene: para al
menos un x, x < 3. La cual resulta ser una expresión verdadera. Sin embargo, el valor de verdad de las dos
expresiones anteriores depende de qué números se esté hablando. En lógica, a aquello de lo que se está
hablando cuando se usa algún cuantificador, se lo llama el dominio de discurso.
A continuación se formalizan ambas oraciones, introduciendo la notación especial para los cuantificadores:
Para todo x, x es amigable.
Existe al menos un x, tal que x está mintiendo.
La lógica de primer orden incorpora además las conectivas de la lógica proposicional. Combinando las
conectivas con los predicados, constantes, variables y cuantificadores, es posible formalizar oraciones como
las siguientes:
Oración Formalización
Sócrates es sabio y prudente. ·á
Si Sócrates es sabio, entonces también es prudente. åá
üadie es sabio y además prudente. ¬ ( · á)
Todos los sabios son prudentes. ( å á)
Conectivas Lógicas:
Considérese el siguiente argumento clásico:
- Todos los hombres son mortales.
- Sócrates es un hombre.
- Por lo tanto, Sócrates es mortal.
La tarea de la lógica de primer orden consiste en determinar por qué los argumentos como éste resultan
válidos. Para eso, el primer paso es traducirlos a un lenguaje más preciso, que pueda ser analizado mediante
métodos formales.
Xa
în
ë o un
es un artificio matemático compuesto de símbolos que se
unen entre sí formando cadenas que a su vez pueden ser manipuladas según 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 señalar como válidas determinadas cadenas. Estas cadenas válidas se
denominan teoremas. Para obtener los teoremas se emplean las reglas de producción que convierten una
cadena en otra. Hay ciertos teoremas iniciales que no se obtienen de ninguna regla, éstos son los axiomas
que se suponen válidos por definición y se convierten en el germen de producción de teoremas.
-Completitud: El sistema formal es completo si cada proposición verdadera puede ser representada
mediante un teorema. Es incompleto si alguna verdad no puede expresarse.
- Decidibilidad: în 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 aritmética de los
números naturales. Los primitivos de este sistema son los términos "0" (cero), "número" y "sucesor", de los
cuales, por ser primitivos no se da definición alguna. Sin embargo, se entiende por "0" dicho número, el
término "número" designa a los números naturales 0, 1, 2, 3,... exclusivamente, y con "sucesor" de un número
natural se refiere al número natural inmediato siguiente de en el orden natural.
El último postulado entraña el principio de inducción matemática e ilustra claramente el alcance de una
"verdad" matemática por convención. Se construye la aritmética fundamental sobre esta base, definiendo los
diversos números naturales como el sucesor de cero ( 0' ), el sucesor del sucesor de cero( 0 ), y así hasta el
infinito.
Luego, se establece la definición de suma, que expresa que la adición de un número natural a otro dado
puede considerérsela como la suma repetida de 1; esta última operación es fácilmente expresable por medio
de la relación de sucesor:
+ 0 = ; (b) + k' = ( + k)¶
Pasando ahora a la multiplicación de los números naturales, se la puede definir por medio de la siguiente
definición por recurrencia, que expresa de manera rigurosa que el producto de dos números naturales
puede ser considerado como la suma de términos cada uno de los cuales es igual a , en otros términos:
(a) . 0 = 0; (b) . k' = . k +
El alfabeto L de la lógica de primer orden es un conjunto que contiene los siguientes tipos de símbolos:
ë
ë
: Son símbolos que corresponden a funciones (reciben
argumentos) que 'predican' algo acerca de referentes. Corresponden a afirmaciones. Ej: (x) abrevia 'x es
calvo', y es una función unaria (recibe sólo una entrada); (y, z) abrevia 'y le debe dinero a z' y es una función
binaria; (a,b,d) abrevia 'a y b se casaron en el lugar c' y es trinaria. En general, la relación R(X1, X2, ..., Xk)
es una relación k-aria. Aquí, D, R y H se llaman símbolos de relación y estos símbolos son los elementos de L,
no las funciones.
ë
: Son símbolos que corresponden a funciones que denotan cosas únicas, en
función de sus argumentos. üote que difieren de los predicados ya que no simbolizan fórmulas, sino
términos ('cosas'). Ej: (w) abrevia 'el padre de w' ; D(v) abrevia 'la edad de v'. üote que H(x) (el hijo de x)
no es función, ya que no precisa necesariamente un único objeto determinado, sino que es ambiguo.
ë: x, y, z, w, x1, x2, ...(principalmente). Se refieren a objetos indeterminados.
: a, b, c, a1, a2, a3, ... Se refieren a objetos determinados, particulares (p.ej., n denota a üicolás).
: (existe), (para todo).
ë
: (üo), (o), (y), (implica), (equivale/si y solo si).
ë
: = , , ( , ).
3. Si l y son fórmulas bien formadas de L, entonces (l), (l), (l) y (l) también lo son.
4. Sólo las expresiones que pueden ser generadas mediante las cláusulas 1 a 3 en un número finito de pasos
son fórmulas bien formadas de L.
îna regla de inferencia es una función que va de conjuntos de fórmulas a fórmulas. Al conjunto de fórmulas
que la función toma como argumento se lo llama premisas, mientras que a la fórmula que devuelve como
valor se la llama conclusión. En general se busca que las reglas de inferencia transmitan la verdad de las
premisas a la conclusión. Es decir, que sea imposible que las premisas sean verdaderas y la conclusión 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 podría ser:
Si está soleado, entonces es de día.
Está soleado.
Por lo tanto, es de día.
El cálculo de predicados puede ser axiomatizado de varias formas diferentes. üo existe estándar sobre los
axiomas y reglas de inferencia dadas, pero cualquier formalización produce los mismos teoremas de la lógica.
Los siguientes tres axiomas son heredados de la lógica proposicional y se incorporan a la lógica de primer
orden. Sean A, B y C fórmulas bien formadas de Q. Luego, los siguientes son axiomas lógicos:
Ax1:A å (B å A)
Ax2: (A å (B å C)) å ((A å B) å (A å C))
Ax3: (¬A å ¬B) å (B å A)
Los dos axiomas siguientes son característicos de la lógica de primer orden. Sean A y B fórmulas bien
formadas de Q con como máximo una variable libre, x. Sea t un término cerrado y A(x/t) el resultado de
reemplazar toda aparición de x en A por t. Luego, los siguientes son axiomas lógicos:
Ax4: x A å A(x/t)
Ax5: x (A å B) å (x A å 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 también: «Si todos son mortales, entonces el padre de Mateo es
mortal» El quinto axioma es análogo al axioma K de la lógica modal, y un caso particular del mismo podría
ser: «Si todos los humanos son mortales, entonces, si todos son humanos, todos son mortales.»
îna interpretación es un par <D,I>, donde D es un conjunto no vacío llamado el dominio de discurso e I es
una función llamada la función de interpretación 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 función 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 noción de para una interpretación (para las oraciones de Q):
1. P(t1,...,tn) es verdadera para la interpretación M si y sólo si la n-tupla formada por las interpretaciones de
t1,...,tn es un elemento de la interpretación de P.
2. ¬A es verdadera para la interpretación M si y sólo si A es falsa bajo esa interpretación.
3. (A · B) es verdadera para la interpretación M si y sólo si A es verdadera y B es verdadera bajo esa
interpretación.
4. (A B) es verdadera para la interpretación M si y sólo si A es verdadera o B es verdadera bajo esa
interpretación.
5. (A å B) es verdadera para la interpretación M si y sólo si A es falsa o B es verdadera bajo esa
interpretación.
6. (A B) es verdadera para la interpretación M si y sólo si A y B son ambas verdaderas o ambas falsas bajo
esa interpretación.
continuación
Para dar las definiciones de verdad para fórmulas con la forma x A o x A, primero son necesarias algunas
definiciones preliminares: Sea A(x/a) el resultado de reemplazar toda aparición de x en A por un nombre a
(que no haya sido utilizado en la fórmula). Además, si M e M' son interpretaciones y a un nombre, entonces
M' es una a-variante de M si y sólo si M' es idéntica a M o difiere sólo en el elemento del dominio que le
asigna al nombre a.
7. x A es verdadera para M si y sólo si A(x/a) es verdadera para toda a-variante de M.
8. x A es verdadera para M si y sólo si A(x/a) es verdadera para al menos una a-variante de M.
îna fórmula es ë bajo una interpretación si y sólo si no es verdadera bajo esa interpretación.