Download - Teoría de predicados
-
Tema 4: Lgica de Predicados
-
Motivacin
Todos los hombres son mortalesScrates es un hombreLuego Scrates es mortal
Propiedades
Juan ensea a PedroAlgunos hombres ensean a PedroTodos los hombres ensean a alguien
Relaciones
-
Motivacin
Limitacin de la lgica proposicional: su unidad mnima es la proposicin, que tiene informacin propia y se contempla como un todo.
Ej: para decir que todos los humanos son mortales habra que decir
Pepe es humano Pepe es mortalJuan es humano Juan es mortal
(y as sucesivamente)
-
MotivacinEjemplo: La lgica de predicados (Gottob Frege, 1879) nos permite dar una descripcin de la realidad ms detallada.
-
Motivacin
En lgica de predicados se simbolizan los componentes de una proposicin (no se trata como un todo)
La idea es simbolizar: Qu se afirma (predicado) De quien o quienes (sujetos o trminos)Ej: Pepe es humano Pepe es el sujeto es humano el predicado
El predicado es atribuible a varios sujetos
-
Simbolizacin Trminos o sujetos pueden ser:
Constantes, representados por a, b, c.. representan objetos concretos. Las constantes son individuos o elementos distinguidos del universo del discurso, que es la coleccin de objetos sobre los cuales queremos razonar.
Variables, representados por x, y, z sirven para representar objetos, cuyo dominio hay que especicar.
Predicados: se utiliza la notacin funcional P(p1,,pn), donde pi representa el lugar i en el predicado a ocupar por una variable o constante (procedimiento)
A cada lugar se le asigna un sujeto o trmino, que puede ser constante o variable
-
Simbolizacin Es posible asignar a un lugar un conjunto de trminos dentro del
dominio (todos los alumnos estn entre M y R, algunos alumnos estn entre M y R)
Para simbolizar esta diferencia se usan los cuantificadores. Asignar a una plaza todos los elementos del dominio:
(cuantificador universal ) xHumano(x) Ej: para cualquier x, x es humano,
Asignar a una plaza un subconjunto del dominio
(cuantificador existencial ) xRojo(x) Ej: hay/existen uno (o ms) x que son de color rojo
Las variables afectadas por cuantificadores se definen como ligadas
En el caso de no estar afectadas por cuantificadores se definen como libres
-
Simbolizacin La asignacin de valores a las plazas puede hacerse de varias formas
Sustitucin de trminos: Juan se sienta en clase entre Manuela y JosP(a,b,c) equivalente a Sentar(Juan,Manuela,Jose)
Sustitucin variable genrica: un alumno cualquiera se sienta en clase entre Manuela y Jos
P(x,b,c) equivalente a Sentar(x,Manuela,Jose) Sustitucin variable incgnita: un alumno se sienta en clase entre
Manuela y JosP(x,b,c) equivalente a Sentar(x,Manuela,Jose)
Cuantificacin universal: todos los alumnos se sientan en clase entre Manuela y Jos
xP(x,b,c) equivalente a xSentar(x,Manuela,Jose) Cuantificacin existencial: algunos alumnos se sientan en clase entre
Manuela y JosxP(x,b,c) equivalente a xSentar(x,Manuela,Jose)
-
Simbolizacin
En la frmula x((P(x) ^ Q(x)) v (P(x) ^ Q(x)))
la variable x aparece ligada en las dos componentes de la disyuncin, ya que el cuanticador existencial la afecta en los dos casos.
En la frmula (x(P(x) ^ Q(x)) v (P(x) ^ Q(x)))
La variable x esta ligada en el primer parntesis y libre en el segundo, y el cuantificador existencial solo afecta a la primera parte de la disyuncin.
-
Simbolizacin A la hora de aplicar la lgica de predicados es fundamental establecer
el dominio de definicin En funcin de ste, se pueden asignar frmulas distintas a las mismas
frases del lenguaje naturalEj: todas las guilas vuelan alto
Dominio de definicin: las guilas V(x) x vuela alto
xV(x) Dominio de definicin: las aves
A(x) x es guila V(x) x vuela alto
x(A(x) V(x))
-
Construccin de frmulas: alfabeto Smbolos para los trminos
Variables: x, y, z, t Constantes: a, b, c,
Smbolos para los predicados: (P,Q,R,): todo predicado tiene un nmero de argumentos. El nmero n es la aridad del predicado.
1. Predicados constantes, n = 0: representan proposiciones atmicas. Para representar las proposiciones atmicas se suelen usar los smbolos p, q, r, s, t
2. Predicados mondicos, n = 1: representan propiedades de objetos.3. Predicados polidicos, n > 1: representan relaciones entre objetos.
Smbolos para las conectivas: (~, , , y parntesis)* Smbolos de cuantificacin:
Universal Existencial
*(tambin se considera vlida la coimplicacin )
-
Construccin de frmulas: alfabeto
Los siguientes son ejemplos de predicados:
P(x): la raz cuadrada de x es irracional (predicado mondico),
P(x, y): x es el hermano de y (predicado binario), P(a, b, c): a preere b a c (predicado ternario).
-
Construccin de frmulas: alfabeto
Ejemplos: siendo E(Pedro): Pedro es un estudiante, aplicando la
negacin se obtiene
~(E(Pedro)) : Pedro no es un estudiante.
De forma similar, si P(x) : x es un nmero primo, ~(P(x)) : x no es un nmero primo.
-
Construccin de frmulas: alfabeto Ejemplos:
1) La frase Scrates es un filsofo, sin embargo no es un deportista F(x): x es un filsofo D(x): x es un deportistaSe escribe como (F(s) ~(D(s)))
2) La frase Scrates es un filsofo o Scrates es un deportista se escribe como (F(s) v D(s)):
3) La frase La luna es de papel si y slo si Carlos lee muchos Libros
P(x): x es de papel L(x): x lee muchos librosSe escribe como (P(luna) L(Carlos));
-
Construccin de frmulas: alfabeto Ejemplos:
La frase Todo nmero primo y mayor que 2 es impar P(x) : x es primo, Q(x) : x es mayor que 2 R(x) : x es impar.
se formaliza: (x((P(x) Q(x)) R(x))); La frase Todo hombre es mortal y hay hombres que no son
filsofos: P(x) : x es un hombre, Q(x) : x es mortal R(x) : x es filsofo.
se formaliza: ((x(P(x) Q(x))) (x(P(x) (~(R(x)))));
-
Construccin de frmulas: sintaxis Una frmula en el clculo de predicados es una sucesin
de smbolos del alfabeto que verifica las siguientes reglas de formacin: Toda proposicin (del clculo proposicional) es una frmula
Si p es un predicado de n lugares, p(t1,,tn) entonces es una frmula siendo ti smbolos de trminos (objetos/sujetos)
Si A es una frmula(hechos relativos a objetos o trminos) con xivariable libre, tambin son frmulas
xiA(x1,,xi,xn) xiA(x1,,xi,xn)
Si A y B son frmulas, tambin lo son ~A, ~B, AB, AB, AB Toda frmula del clculo proposicional es sintcticamente correcta en el
clculo de predicados
-
Construccin de frmulas: sintaxis
Estn bien construidas?
yP(x,a) Q(z) P(x, y) Q(z) x(P(x) yR(y,z))
-
Construccin de frmulas: sintaxis Colocacin de parntesis
En cuanto a las conectivas, las reglas son iguales a las utilizadas en el clculo de proposiciones
Los cuantificadores slo afectan a las variables libres inmediatamente siguientes. Para cambiar esto es necesario incluir parntesis
xP(x) Q(x) frente a x(P(x) Q(x)) Cuando hay varios cuantificadores seguidos, el proceso de
cuantificacin se realiza en el orden de mayor a menorproximidad a la frmula
El cambio de orden de un cuantificador puede alterar el significado de la frase:
xyF(x,y) frente a yxF(x,y)
-
Construccin de frmulas: sintaxis Generalizacin del concepto de trmino
Los trminos, adems de constantes y variables, pueden ser tambin funciones (f:DnD, siendo D el dominio de referenciao dominio del trmino)
Son una ayuda para la expresin de relaciones. No presentan propiedades entre los argumentos interpretables como V o F
Se utiliza la notacin f, g, h y letras griegas En estos casos, el concepto de trmino se puede definir de forma
recursiva de la siguiente manera: Son trminos las variables y constantes
Si es una funcin, son trminos las expresiones (t1, t2,..,tn)siendo ti trminos y n el nmero de variables de la funcin (x1, a1, [x2, a2,(x3)])
-
Construccin de frmulas: sintaxis
Generalizacin del concepto de trmino Ejemplos de trminos: x, a, f(x), g(x, y), g(x, f(x))
donde x es una variable, a es una constante, f es una funcin mondica
y g es una funcin binaria. Los primeros dos trminos de la lista son atmicos y
los restantes son compuestos.
-
Construccin de frmulas: sintaxis El uso de funciones permite simplificar la estructura de las
frmulas. Ej: ningn producto de dos nmeros naturales es primo
Dominio: nmeros naturales Predicados:
R(x,y,z): z es el producto de x e y P(w): w es primo x y z(R(x,y,z) ~P(z))
Si se considera la funcin (x,y)=x*y, la frase se puede escribir de la forma
x y ~P((x,y)) Deben ser funciones que tomen valores en el dominio.
Funciones que se aplican sobre un conjunto de trminos para dar otro trmino
-
CP de orden superior Clculo de predicados:
Primer orden: los cuantificadores se aplican exclusivamente a las variables
P(x,y) x=y x y P(x,y)
Orden superior: los cuantificadores se aplican a funciones o predicados
Ej: existe al menos una funcin tal que (a)=bP((a),b)
Ej: algunas relaciones entre pares de alumnos de la clase son simtricas
P xy(P(x,y)P(y,x))
-
Ejemplos
Frases simples:
Todos son de color azul
Juan es rubio
Juan es amigo de todos
Algunos son amigos de Juan
Todos son amigos
x Color(x,azul) o x Azul(x)
Rubio(Juan)
xAmigo(Juan,x)xAmigo(x,Juan)xyAmigo(x,y)
-
Ejemplos
Frases compuestas:
Algunos republicanos son ricos
Todos los republicanos son ricos
x(P(x) Rep(x) Rico(x))x(Rep(x) Rico(x))
Existen algunas personas en las que se da simultneamente la condicin de ser republicanos y ricos
No existe nadie que sea republicano y no sea rico Para cualquier x del dominio, si x es republicano, entonces x es rico
~x(Rep(x) ~Rico(x))x(Rep(x) Rico(x))
-
Ejemplos En toda pareja de vecinos existe algn envidioso
Todos los que son vecinos se odian entre s
Todos los estudiantes de informtica son amigos de los aficionados a la lgica
Cualquiera que sean x e y, si x e y son vecinos, entonces, o x o y o ambos, son envidiosos
Para cualquier x e y del dominio, si x e y son vecinos, se odian mutuamente
Cualquiera que sean x e y, si x es un estudiante de informtica, e y es aficionado a la lgica, entonces x es amigo de y
xy(Vec(x,y) Env(x) v Env(y))
xy(Vec(x,y) (Env(x,y) Env(y,x)))
xy((EstInf(x) AficLog(y)) Amigo(x,y))
-
Ejemplos Algunos estudiantes de informtica tienen amigos
aficionados a la lgica
Algunos estudiantes de informtica slo son amigos de los aficionados a la lgica.
Existen algunos elementos de x e y en los que se dan simultneamente las circunstancias de x ser estudiante de informtica, y aficionado a la lgica y x ser amigo de y
Existe algn x del dominio que es estudiante de informtica y slo es amigo de los aficionados a la lgica
xy((EstInf(x) AficLog(y)) Amigo(x,y))
x(EstInf(x) y(Amigo(x,y) AficLog(y)))
-
Ejemplos Algunos franceses son amigos de cualquier espaol
En el dominio de referencia existen individuos x en los que se da simultneamente la condicin de ser francs y la de ser amigo de cualquier y que sea espaol
Solo los futbolistas admiran a los futbolistas Cualquiera que sean x e y, si x admira a y e y es
futbolista, entonces x es futbolista Todos los futbolistas admiran solo a los futbolistas
Para cualquier x del dominio de referencia, si x es futbolista entonces, cualquiera que sea y, si x admira a y, entonces y es futbolista
x(F(x) y(E(y) Amigo(x,y)))
xy(Amigo(x,y) F(y) F(x))
x(F(x) (Amigo(x,y) F(y)))
-
Ejemplos Slo los tontos se dejan engaar por los vendedores
ambulantes
Para todo x e y del dominio de referencia, si x se deja engaar por y e y es vendedor ambulante, entonces x es tonto
xy (E(x,y) Vend(y) T(x))
-
Ejemplos
Frases con constantes
Antonio se deja engaar por Juan
Algunos abogados y obreros admiran a Lpez
Todos los que ayudan a Juan trabajan en casa de Manolo
E(juan,antonio)
xy (AB(x) OB(y) A(y,lopez) A(x,lopez))
x (A(x,juan)T(x,manolo))
-
Ejemplos
Varios
Algunas plantas no tienen flores
Cualquier edificio es habitable
Algunas personas son insoportables
Existen personas que no comen carne
x(P(x) ~F(x))x(E(x) H(x))x(P(x) I(x))x(P(x) ~C(x))
-
Notas prcticas Generalmente los cuantificadores existenciales van con
conjuncin y los universales con implicacin.
Esto puede no ser as dependiendo de que la frase sea hipottica.
Depende del dominio. El cuantificador va con cuando la relacin P(x)Q(x) no tiene que cumplirse siempre
Ej: hay algn artculo que si se cayese al suelo, se romperax(Caerse(x) Romperse(x))