Download logica de predicados

PONTIFICIA UNIVERSIDAD CATOLICA- ESTUDIOS GENERALES CIENCIAS
ESTRUCTURAS DISCRETAS
LOGICA DE PREDICADOS
Un predicado es una función definida en un dominio D, e imagen en L = {V,F}
p: D  L
Donde el dominio D  X1x X2 x ...x Xn, con Xi conjuntos no vacíos.
Si p es un predicado en D, y a D, entonces, p(a) es una proposición
Ejemplo:
Si D = Z x Z, y el predicado es:
p(x,y): x < y
Entonces p(2, 4) y p(9, 3) son proposiciones con:
p(2, 4)  V y p(9, 3)  F
Operaciones con Predicados
1)
(p)(x)  p(x)
2)
(p  q)(x)  p(x)  q(x)
3)
(p  q)(x)  p(x)  q(x)
4)
(p  q)(x)  p(x)  q(x)
5)
(p  q)(x)  p(x)  q(x)
6)
(p  q)(x)  p(x)  q(x)
Cuantificador Universal  (Para todo)
 x  D : p(x)
} Es una proposición que:
Será V si para cada valor de a D, p(a)  V
Será F si existe algún a D tal que, p(a)  F
Cuantificador Existencial  (Existe)
} Es una proposición que:
 x  D : p(x)
Será V si existe algún a D, p(a)  V
Será F si para cada a D,
p(a)  F
Leyes de Predicados
1)
(  x: p(x))
  x: ~ p(x)
2)
(  x: p(x))   x: ~ p(x)
 x: (p(x)  q(x))  (  x: p(x))  (  x: q(x))
3)
4)
 x: (p(x)  q(x))  (  x: p(x))  (  x: q(x))
 x: ( p(x)  q(x))
5)
(  x: p(x))  (  x: q(x))


6)
(  x: p(x))  (  x: q(x))
 x: ( p(x)  q(x))
Teorema de Particularización
Sea p: D  L un predicado, y a D, entonces:
p(a) es una consecuencia lógica de (  xD: p(x))
Teorema de Generalización
Sea p: D  L un predicado, y a D, entonces:
(  xD: p(x)) es una consecuencia lógica de p(a)
Variables ligadas y variables libres
Si p: D  L un predicado en n variables: (x1,x2, xn), entonces:
(  xkD: p(x))
y
(  xkD: p(x))
Son predicados en las (n-1) variables que no son xk.
Se dice entonces que la variable xk está ligada y las variables restantes son libres.
Elaborado por: Prof. Miguel Sierra
Semestre 2007-II