Download Lógica de Predicados 1

Lógica de Predicados 1!
rafael ramirez
[email protected]
55.316 (Tanger)
Porqué Lógica de Predicados!
   La logica proposicional maneja bien afirmaciones
compuestas de no, y, o, si…entonces
En situaciones con un conjunto finito (pequeño) de
elementos, esto es suficiente para hablar de existe,
todo, para todo.
Ejemplo: si tenemos 3 estudiantes A, B y C, tomando
p=“A juega tenis”, q=“B juega tenis”, r=“C tiene juega tenis”
la afirmacion “existe un estudiante que juega
tenis” se puede representar por p ∨ q ∨ r
2
Porqué Lógica de Predicados!
 En situaciones con conjuntos infinitos (o muy
grandes) requríamos formulas infinitas (o muy
grandes), p.e. “cada persona es hombre o mujer” se
traduciría como:
(p0∨q0)∧ (p1∨q1)∧ (p2∨p2)∧…
 Que pasa si queremos representar el argumento:
Todos los hombres son mortales,
Socrates es un hombre,
Por lo tanto, Socrates es mortal.
3
Lógica de Predicados!
    La logica de predicados (también llamada logica de primer
orden) es una extension de la lógica proposicional que usa
variables para los objetos.
Si usamos x para representar a algun humano, la afirmacion
“cada persona es hombre o mujer” se puede representar como
∀x(h(x)∨m(x)) donde h(x)= “x es hombre”, m(x)= “x es mujer”
Estas variables se pueden combinar con símbolos de función
para representar objetos nuevos y con símbolos de predicado
para describir ralaciones entre objetos.
Ejemplo: si s(x) representa “el padre de x”, y
m(x,y) representa “x es menor que y”, entonces
“toda persona es menor que su padre” se representa por
∀x m(x,s(x))
4
De LPred a Lenguaje Natural !
Traduce:
5
De Lenguaje Natural a LPred!
   Ejercicio 1 “no todas las aves pueden volar”
Ejercicio 2 “todos los hombres son mortales. Socrates es un
hombre. Por lo tanto Socrates es mortal.”
Ejercicio 3“Existe un hermano de Ana que le gusta a Blanca”
6
De Lenguaje Natural a LPred
 Ejercicio P4-#3a “no todas las aves pueden volar”
¬(∀x (B(x) → F(x)))
 Ejercicio P4-#3b “todos los hombres son mortales. Socrates es
un hombre. Por lo tanto Socrates es mortal.”
∀x (H(x) → M(x)) , H(s) |⎯ M(s)
 Ejercicio P4-#3c “Existe un hermano de Ana que le gusta a
Blanca”
∃x (H(x,a) ∧ L(x,b))
7
Lenguaje Natural y LogPred
La lógica de predicados es un lenguaje formal y preciso
El lenguaje natural (p.e. el Inglés) es un lenguage vago y
ambiguo.
Pasar de lógica a lenguaje natural es facil/simple pero
pasar de lenguaje natural a lógica es mas
problemático (puede ser que hay mas de una
fórmula por la ambiguedad del lenguage natural)
8
Consistencia y Completitud
Extenderemos ambos interpretación semántica
Natural
y deducción
a la lógica de predicados.
El resultado básico es un teorema de consistencia y completitud
si y solo si
Probado por Gödel (la prueba es mucho mas complicada)
Así que, una vez más, cualquiera de los dos métodos podría ser usado
9
Alfabeto de la logica de 1er orden!
      Símbolos de puntuación
“(“ “,” “)”
Variables
x, y, z, x1, x2, … , u, v
Constantes
a, b, c, a1, …
Símbolos de función
f, g, f1,…
Simbolos de predicado
p, q, r, s, t, p1,…
Conectivos
¬, ∧, ∨, → (igual que Log. Proposicional) + ∀, ∃
10
Términos y fórmulas atómicas!
TERMINOS
  Las variables y constantes son terminos
Si f es una función de n argumentos y t1,…,tn son términos,
entonces f(t1,…,tn) es un término.
FORMULAS ATOMICAS
 Si p es un predicado con n argumentos y t1,…,tn son terminos,
entonces p(t1,…,tn) es una fórmula atómica.
11
Fórmulas de Lógica de Predicados!
 FORMULAS DE PRIMER ORDEN
1. Una fórmula atómica p(t1,…,tn) es una fórmula
2. Si A y B son fórmulas entonces
A→B, ¬A, A∨B, A∧B, ∀xA, ∃xA
son fórmulas
3. Nada mas es una fórmula
12
Variables Libres y Acotadas!
    El alcance de un cuantificador es la fórmula a la cual
se aplica.
Una ocurrencia de una variable esta acotada si esta
dentro del alcance de un cuantificador ∀x
Si no lo esta entonces la variable esta libre
Una fórmula esta cerrada si no tiene ninguna
ocurrencia libre de variables
13
Variables Libres y Acotadas!
14
Interpretaciones!
Una interpretación I para una formula A es:
      Un dominio D (un conjunto no vacío)
Una relacion en el dominio D para cada símbolo de
predicado en A
Una funcione en el dominio D para vada símbolo de funcion
en A
Un elemento de D para cada constante en A
En caso de que la formula sea abierta, un elemento de D
para cada variable libre de A
Nota que en el caso proposicional solo hay variables (p,q,…) y
nuestro dominio D es el conjunto {T,F}
15
Modelos!
Sea A una formula cerrada
Definicion: A es verdad en I, o I es una modelo de A, si
v(A) = T bajo I. Notacion: I╞ A
Si A = ∀x p(a,x)
I1: D=N, p= ≤, a=1
I2: D=N, p= ≤, a=0
I3: D=Z, p= ≤, a=0
I1╞ A
No I2╞ A
No I3╞ A
16
Satisfacibilidad!
Definicion: Una formula A es satisfacible si para alguna
interpretación I, I╞ A
Definicion: Una formula A es válida (notación ╞ A) si para
toda interpretación I, I╞ A
∀x p(a,x) satisfacible y es falsifiable
Que tal ∀x p(x) → p(a) ?
Que tal ∃x p(x) → p(a) ?
17
Fórmulas válidas (1)!
18
Fórmulas válidas (2)!
19
Tableaux Semánticos!
20
Tableaux semánticos!
Ejercicio: Determinar con un tableau semántico si la
siguientes fórmulas son válidas o no
∀x ( p(x) ∨ q(x) ) → ( ∀x p(x) ∨ ∀x q(x) )
∀x A(x) → ¬∃x¬A(x)
21
Natural Deduction!
Reglas
La lógica de predicados extiende la lógica
proposicional así que todas las reglas de deducción
natural de la lógica proposicional se heredan.
Solo tenemos que añadir reglas para los cuantificadores
22
Natural Deduction!
23
Natural Deduction!
24
Natural Deduction!
25
Natural Deduction!
26
Natural Deduction!
27
Natural Deduction!
28