LyA - Predicados11

LOGICA Y ALGORITMOS

Módulos

!Cardinalidad y conjuntos inductivos"Lógica: proposicional y de 1er orden!Formalismos de cálculo: FR y FL!Lenguajes y autómatas

LyA - Predicados12

Distintos Sistemas Lógicos:LOGICA PROPOSICIONAL

➨ LOGICA DE PREDICADOSLOGICAS NO-CLASICAS

– MULTIVALUADAS (Fuzzy Logic)– MODALES

OBJETIVO: ESTABLECER LA VALIDEZ DEDISTINTOS RAZONAMIENTOS -OBTENER CONCLUSIONES DE UN CONJUNTODE FORMULAS

LyA - Predicados13

Lógica de predicados

Introducción

LyA - Predicados14

Lógica de PredicadosLENGUAJE

– Sintaxis: fbfs del lenguaje, más rico quePROP

– Semántica: Cómo probar la veracidad delas fórmulas ??

RAZONAMIENTOS– Justificación sintáctica (pruebas formales)

LyA - Predicados15

Motivación

Todo natural es entero y 2 es un natural, luego 2 es un entero.

p, q |= |= |= |= r

p

r

q

No es un razonamiento válido?

LyA - Predicados16

#La corrección de este razonamientodepende de la relación entre los sujetos delas proposiciones.

∀ x (x ∈Ν→ x∈Ζ)2 ∈Ν

2∈Ζ

Todo natural es entero y 2 es un natural, luego 2 es un entero.

7

La corrección de este razonamiento depende de la relación entre los sujetos de las

proposiciones.

"Lógica proposicional NO es suficientementeexpresiva para captar esta relación

∀ x (Perro(x)→ Mamífero (x))Perro (Rex) Mamífero (Rex)

∀ x. P(x) P(Rex)

Todo perro es un mamífero y Rex es un perro, luego Rex es un mamífero..

LyA - Predicados18

Por qué lógica de predicadosLógica proposicional : bajo poder expresivoproposiciones usuales en matemática no son

expresables

« 2 es natural »

En proposicional:

p (una prop. atómica)

En predicados:

Sujeto: 2

Propiedad: Ser Natural

Natural(2)

LyA - Predicados19

La validez de ciertos razonamientos dependede la relación entre las proposiciones

" análisis « fino » de la estructura de las proposiciones

" el análisis de oraciones clásico no es el másadaptado para reflejar (o explicitar) la relación(o la estructura) entre las proposiciones quecomponen el razonamiento

LyA - Predicados110

Por ejemplo la oración Rex es un perro

puede analizarse de una de las siguientes maneras:Es (Rex, perro)Es-perro (Rex) Perro (Rex)Es-Rex (Perro)

Como Traducir ???

LyA - Predicados111

Otro ejemplo Mafalda detesta la sopapuede analizarse de una de las siguientes maneras:

Detesta(Malfalda, x)DetestaSopa (Mafalda)DetestadoPorMafalda(sopa)

" según la propiedad o relación que seidentifique, y según los individuos del universode quienes se hable.

LyA - Predicados112

Lógica de predicados

Informal

LyA - Predicados113

Lenguaje de lógica de predicados

• Símbolos para denotar objetos - sb. de constante (ej. Mafalda, Rex, 2) - sb. de variable (ej. x, y, z) - sb. de función (ej. Padre, +, *, etc que

permiten crear nuevos nombres de objetoscomo Padre(juan), (1+1), (2*1) )

• Símbolos de propiedades y de relaciones• Conectivos• Cuantificadores

LyA - Predicados114

Símbolos de relación

- símbolos unarios, binarios, etcEjemplos.

Símbolos de propiedad (unario) Par(x)Primo(x)

≥ es un símbolo de relación binariox ≥ 0 Mayor(x,0)

LyA - Predicados115

Símbolos de relación" Pedro es docente" Pedro tiene otro trabajoEjemplo: Docente y Otro-trabajo son

símbolos de propiedad (unarios)Docente(pedro) Otro-trabajo(pedro)

Ejemplos de mayor aridad:Tiene (pedro, otro-trabajo)Padre (pedro,juan)Vuelo (123,AA,BsAs,Madrid)

LyA - Predicados116

Por qué símbolos de función sitenemos símbolos de relación?

padre (juan) ∃ y Padre(y,juan) suma(x,y) ∃ s Suma(s,x,y)

• el factorial de un número es parPar(fact(x))∃ y Fact(x,y) → Par(y)

"los símbolos de función simplifican la notación

LyA - Predicados117

Conectivos: Enunciados compuestos

- Las sentencias simples del cálculo depredicado se pueden combinar usando losconectivos ya vistos (C= {¬ ∧∨ → ↔})

Ejemplos:Si alguien es docente entonces gana poco

Docente(x) → Gana-poco(x)La suma de dos naturales no es negativa

(Nat(x) /\ Nat(y)) → Positivo(suma(x, y))suma(x, y)>0

LyA - Predicados118

Enunciados compuestosx es natural par y es mayor o igual a cero. Par(x) /\ (x ≥ 0)

Par(x) /\ (Mayor(x,0)Pedro es el padre de Juan y Juan es el padre de

MaríaPadre(pedro,juan) /\ Padre(juan, maria)

Pedro es el padre de Juan y Pedro es el padre deMaría

Padre(pedro,juan) ∨ Padre(pedro,maria)

LyA - Predicados119

Enunciados compuestosLa suma de dos naturales es positiva

(Nat(x) /\ Nat(y)) → Positivo(suma(x, y))suma(x, y)>0

Juan escribe el programa y no funciona Escribe-prog(juan) /\ ¬ Funciona(programa)Escribe(juan, programa) /\ ¬ Funciona(programa)

LyA - Predicados120

Traducción• Puede ser mas complicado definir los

predicados…Si Juan escribe el programa y nofunciona, entonces o lo arregla por latarde o se lo da a un programador al diasiguiente.

(Escribe(juan, programa) /\ ¬¬¬¬ Funciona(programa)) →→→→

→→→→ (Arregla (juan, programa, tarde) ∨∨∨∨∨∨∨∨ Da(programador, programa, dia-siguiente))

LyA - Predicados121

CuantificadoresNecesitamos tratar con expresiones que

incluyan términos como todos o algunos:"todos (∀ x) CUANTIFICADOR UNIVERSAL

• Todo entero tiene un factor primo (∀ x) (E(x) → Fp(x))• Todo número es par o impar

(∀ x) (N(x) → P(x) ∨ I(x)) (∀ x) (N(x) → P(x) ∨ ¬ P(x))

LyA - Predicados122

Cuantificadores"algunos (∃ x) CUANTIFICADOR

EXISTENCIAL

• Agunos docentes tienen otro trabajo (∃ x) (D(x) ∧ O-t(x))• Existen números pares que son

cuadrados de otro número par (∃ x) (∃ y) (P(x) ∧ P(y) ∧ (x=y2)) (∃ x) (∃ y) (P(x) ∧ P(y) ∧ Igual(x, cuad(y))

LyA - Predicados123

Cuantificadores-En general, si A es un predicado (simple o

compuesto), son predicados:

(∀ x) A(x)“Todo objeto tiene la propiedad A”(∃ x) A(x)“Existe algún objeto con la propiedad A”

LyA - Predicados124

Relación Cuantificadores• No todas las aves vuelan ¬(∀ x) (A(x) →V(x))• Justificamos la expresión anterior pues

“existen aves que no vuelan” (∃ x) (A(x) ∧ ¬ V(x)) Aquí tenemos una equivalencia semantica

entre las dos expresiones que nos lleva auna equivalencia entre los cuantificadores:

¬(∀ x) P(x) equivale a (∃ x) ¬P(x) ¬(∀ x) ¬ P(x) equivale a (∃ x) P(x)

LyA - Predicados125

Relación Cuantificadores• Algunos números reales no son racionalesUsando el cuantificador existencial

(∃ x) (R(x) ∧ ¬ Q(x))

Usando el cuantificador universal ¬(∀ x)¬ (R(x) ∧ ¬ Q(x)) ¬(∀ x) (R(x) → Q(x))

LyA - Predicados126

Ejemplos de traducción• Si algunos trenes se retrasan entonces

todos se retrasan (∃ x) (T(x) ∧ R(x)) → (∀ x) (T(x) → R(x))

• Todo número es par o impar (∀ x) (N(x) → P(x) ∨ I(x)) (∀ x) (N(x) → P(x) ∨ ¬ P(x))

• Ningún número es a la vez par e impar ¬(∃x) (P(x) ∧ I(x))

LyA - Predicados127

Ejemplos de traducción• Todo número es negativo o tiene raíz

cuadrada. (∀ x) (Neg(x) ∨ (∃ y) (y*y) =x) (∀ x) ((x ≤ 0 ) ∨ (∃ y) Raiz(x,y))

• Todo número es par o impar (∀ x) (N(x) → P(x) ∨ I(x)) (∀ x) (N(x) → P(x) ∨ ¬ P(x))

LyA - Predicados128

• Si algunos trenes se retrasan entoncestodos se retrasan

y sólo hablamos de trenes(∃ x) R(x) → (∀ x) R(x)

• Todo número es par o impar y sólo hablamos de naturales

(∀ x) (P(x) ∨ I(x))

Universo de discurso

LyA - Predicados129

Universo de discurso# Si la naturaleza de los objetos de quienes

hablamos está sobreentendida (ej. hablamossiempre de trenes, de naturales, de reales,etc.) podemos obviar el símbolo de propiedadrespectivo

# cuando el universo de discurso separticiona en clases de objetos, y predicamossobre las subclases, utilizamos símbolos depropiedad para referenciar los objetos de lasubclase

LyA - Predicados130

Ejemplos de traducción• Ningún número es par e impar a la vez ¬(∃ x) (P(x) ∧ I(x)) ¬(∃ x) (P(x) ∧ ¬P(x))

• El sucesor del sucesor de un número par, espar.

• Existe un entero que es mayor que cualquierotro entero traducción???

(∀ x) ( P (x) → P(S(S (x)) )

LyA - Predicados131

#Qué es lo que determina los símbolos del alfabetoque necesitamos en nuestro lenguaje?

La realidad que queremos describir

noción de estructura

Antes de formalizar el lenguaje de lalógica de predicados...

LyA - Predicados132

Lógica de predicados

Definición de FORM ypropiedades

LyA - Predicados133

Sintaxis: Lógica de predicados

#Debemos definir un lenguaje formaldando el alfabeto y las reglas deconstrucción de las fórmulas bienformadas (conjunto FORM)#Según la realidad que quierarepresentar tendré distintos lenguajes(L1, L2...), que utilizarán distinto alfabeto(me interesa su estructura)

LyA - Predicados134

Un lenguaje formal:provee nombres abstractos para denotar losindividuos, funciones y relaciones de nuestrouniverso o estructura. De las funciones ypredicados nos interesa la aridad (i.e. si es unaria,binaria, etc). De las constantes interesa lacantidad.

Esta información esta dada por el alfabetoelegido (funciones y relaciones con su aridad,conjunto de ctes)

LyA - Predicados135

Def [alfabeto de un leng. de primer orden]Un alfabeto para un lenguaje de primer orden,

consiste de los siguientes símbolos:

- Símbolos de relación: A11,.., A2

1, A12

, … , Anm

- Símbolos de función: f11,..,f1

2,f22…, fi

j

- Símbolos de constantes: ci tal que i∈ I- Variables: x1, x2, x3,..- Conectivos : ¬ ∧∨ → ↔- Cuantificadores: ∀ ∃- Auxiliares : (, )

36

Dado el alfabeto < A1

1,… , Anm; f1

1,.., fij, ; c1,...ck;

otros elementos > para predicar sobre esa estructura usaremos en el

lenguaje n símbolos de relación, m símbolos defunción y k de constantes donde:

# Aridadm es la aridad del símbolo de relación An

m

j es la aridad del símbolo de función fij,

# Nota:cuando escribimos « alfabeto » daremos por entendidoque también están los símbolos independientes(variables, conectivos, cuantificadores, paréntesis ).

37

Para definir un Lenguaje L de primer orden,debemos definir la noción de término

Def [términos de un leng. de primer orden]El conjunto TERM de los términos de un

lenguaje de primer orden de alfabeto A1

1,… , Anm; f1

1,..,fij ;c1,...ck; se define

inductivamente por:ι) xi ∈ TERM (i ∈Ν)ιι) ci ∈ TERM (i∈Ι)ιιι) si t1 ∈ TERM, ... tn ∈ TERM

entonces fin (t1,.. tn) ∈ TERM

LyA - Predicados138

Términos de un leng. de primer orden

El conjunto TERM de los términos de unlenguaje de primer orden se utilizan pararepresentar los objetos del dominio

# Constantes# Variables# Funciones aplicadas a términos (objetos) que me dan objetos del dominio

39

Ejemplos de términosSea el lenguaje de alfabeto A1

2, f21 f12 c1, c2.

x1 ∈ TERM ? c2 ∈ TERM ?Si (por i) Si (por ii)

f21(x1) ∈ TERM ?Si pues por i) x1 ∈ TERM y f21 es unario

f21(x1,c2) ∈ TERM ? No pues f21 es unario y no puede aplicarse a dos términosf12(f21(x1),c2) ∈ TERM ? A1

2(c2, c2) ∈ TERM ?Si pues … (completar) No pues … (completar)

40

Def [FORM] f.b.f.El conjunto FORM de las fórmulas de un lenguaje deprimer orden L de alfabeto A1

1,… , Anm; f11,..,fij ;c1,...ck

se define inductivamente por:

ι)Si t1∈ TERM, ...tm∈ TERM entonces Anm (t1,...,tri)∈ FORM

Fórmulas atómicasii) Si α ∈ FORM y β ∈ FORM entonces

− (α € β) ∈ FORM donde € ∈{→, ↔, ∧,∨}− (¬ α) ∈ FORM

ιιι) Si α ∈ FORM entonces− ((∀ xi) α) ∈ FORM

- ((∃ xi) α) ∈ FORM

LyA - Predicados141

Ejemplos de fórmulasSea L el lenguaje definido por el alfabeto

A11, A1

2; f11 , f12, c1, c2.

A11(x1) ∈ FORM ?

SI pues x1 ∈ TERMA1

2(f11(x1), c1) ∈ FORM ?SI pues A1

2 es binario, f11 (x1) ∈ TERM y c1 ∈ TERM

A11(f12 (x1, c1)) ∈ FORM ?SI pues …completar!

((∀ x1) (A11(f12 (x1, c1)) → A1

1(f12 (x1, c1)) ) ∈ FORM ?SI pues …. completar !

42

Ejemplos de fórmulas

((∀ x1) A12(f11 (x1), c1)) → ((∃ x2) A1

1(x1)) ∈ FORM ? SI pues … completar!

(∃ x2) f11(x1) ∈ FORM ?

f11(x1) ∈ FORM ?NO pues según el alfabeto f11 esun sb. de función y no de predicado

⇒⇒⇒⇒ No confundir sb. de predicado y sb. de función !

f11(x1) ∈ TERM y A11(x1) ∈ FORM

NO

LyA - Predicados143

Ejemplos (cont)A1

3(x1, x2, x3) ∈ FORM ? NO pues A1

3 no es un símbolo del alfabetodado

A11(x1, c1) ∈ FORM ?

NO pues A11 es un sb. de predicado unario y

se está utilizando como binario

LyA - Predicados144

Def [fórmula atómica]Se llaman fórmulas atómicas, a aquellas fórmulas

FORM que se obtienen con las cláusulas base(o sea que son de la forma A1

k (t1,...,tk))

Lema [ppio. de inducción para TERM]Sea P una propiedad sobre TERM. Si se cumple:

ι) P (xi ) para todo i ∈Ν.ιι) P (ci) para todo i∈Ι.ιιι) si P(t1),... P (tk) entonces P (fik (t1,..tk))

Entonces para todo t∈ TERM se cumple P(t)

LyA - Predicados145

Lema [ppio. de inducción para FORM]Sea P una propiedad sobre FORM. Si se cumple:

ι) P (α ) para todo α atómico.ιι) si P(α ) y P (β ) entonces P(α € β)

ιιι) si P(α ) entonces P(¬ α) ιν) si P(α ) entonces P((∀ xi) α) para todo i ∈Ν .

ν) si P(α ) entonces P((∃ xi) α) para todo i ∈Ν.Entonces para todo α∈ FORM se cumple P(t)

LyA - Predicados146

Reglas de parentizaciónPara simplificar la escritura de las fórmulas,

omitimos ciertos paréntesis:• Las reglas de precedencia de conectivos son las

mismas que para PROP.• Reglas para cuantificadores:

el (∀ x) y el (∃ x) tienen igual precedencia que el ¬¬¬¬....

• Atención: No confundir las siguientes fórmulas (∀ x)(α→β) y (∀ x)α →β (∃ x)(α→β) y (∃ x)α →β

47

Alcance de cuantificadoresDef [radio de acción o alcance] En la fórmula (∀ x)α [(∃ x)α ] radio de acción del (∀ x)

[(∃ x)] es la fórmula α. También se la llama alcance.Una ocurrencia de xi en αααα es ligada si se encuentra

bajo alcance de un cuantificador (∀ xi) o si es lavariable de un (∀ xi). Si la ocurrencia no es ligada sedice que es una ocurrencia libre.

Una variable xi es ligada en αααα si tiene algunaocurrencia ligada.

Una variable xi es libre en αααα si tiene alguna ocurrencialibre en α.

LyA - Predicados148

Ejemplo de alcance de cuantificadores

(∀ x) A11(x) → (∀ y) A1

2(x,y)

(∀ y)(∀ x) (A11(x) → A1

2(x,y))

(∀ x) A11(x) → (∀ y) A1

2(x,y)

(∀ y) (∀ x) A1(x) → A2(x,y)

LyA - Predicados149

Ocurrencias libres y ligadas((∀ x1) A1

1(x1)) → (∀ x2) A12(x1,x2)

(∀ x1) A11(c1)

Ocurrencia libreOcurrencias ligadas

Ocurrencia ligada

LyA - Predicados150

EjemploSea α la fórmula ((∀ x) A1(x)) → (∀ y) A2(x,y)

x tiene 2 ocurrencias ligadas en α entonces x es ligada en α

x tiene 1 ocurrencias libre en α entonces x es libre en α

Obs: - una ocurrencia de variable en una fórmula es o bien libre o bien ligada - una variable puede ser libre y ligada en una fórmula

LyA - Predicados151

Def 2.3.6 [conj. de variables libres de un término]Definimos FV :TERM → Pot(Var) recursiva enTERM.

FV(xi) = { xi } si xi ∈ Var FV(ci) = ∅ FV(f1k

(t1,…,tk)) = FV(t1) ∪ …, ∪ FV(tk).

Def 2.3.7 [conj. de variables libres de un fórmula]Definimos FV :FORM → Pot(Var) recursiva enTERM.

FV(A1r(t1,…,tr)) = FV(t1) ∪ …, ∪ FV(tr)

F(α � β) = FV(α) ∪ FV(β)) FV(¬¬¬¬ α ) = FV(α) FV((∀ xi )α ) = F((∃∃∃∃ xi )α ) = FV(α) - { xi }

LyA - Predicados152

Ejercicio: Definir recursivamente la función que calculael conjunto de variables ligadas de una fórmula (BV)

Def 2.3.8 [términos y fórmulas cerradas]Un término t es cerrado si FV(t) = ∅ .Una fórmula α es cerrada si FV(α) = ∅ .

Notación: TERMc denota {t ∈∈∈∈ TERM | t es cerrado} SENT denota {αααα ∈∈∈∈ FORM | αααα es cerrada }

53

Ejemplo 1: el lenguaje L*, aritmética de los ΝΝΝΝ

Queremos definir un lenguaje que sea apropiado pararepresentar predicados referentes a la aritmética de los Ν

Alfabeto:símbolos de predicado A1

2 rep =símbolos de función: f1

1, f12,f2

2 rep. S,+, *símbolos de constante: c1 rep 0variables, conectivas, cuantificadores, puntuación

Luego expresiones como ∀∀∀∀ x1 ∃∃∃∃ x2 / x1+x2 = x1 x2Se traducen al lenguaje L*

(∀∀∀∀ x1)(∃∃∃∃ x2) A12 (f1

2 (x1 x2),f22 (x1,x2 ))

x1+x2 = 0 se traduce ????

LyA - Predicados154

Ejemplo 1: el lenguaje de la aritmética

Mas expresiones para traducirSon algunas propiedades de estructurasdenominadas de Peano

∀ x (x*0 = 0)∀ xy (x*S(y)) = (x*y) + x

∀ x (0 ≠ S(x)) ∀ xy (S(x)=S(y) → x=y) ∀ x (x+0 = x) ∀ xy (x+S(y) = S(x+y))

(∀∀∀∀ x1 ) ¬¬¬¬A12 (c1,f1

1 (x1)) ... Traducir !!!

LyA - Predicados155

Ejemplo 2: LG el lenguaje de Grupos

Alfabeto:símbolos de predicado A1

2 rep =símbolos de función: f1

1, f12 rep. -1, *

símbolos de constante: c1 rep e (identidad)variables, conectivas, cuantificadores, puntuación

Luego expresiones como ∀∀∀∀ x1 :x1* x1 -1 = e

Se traducen al lenguaje LG

(∀∀∀∀ x1 ) A12 (f1

2 (x1 ,f11(x1), c1)

La expresión ∀∀∀∀ x1x2x3 (x1 *x2) * x3 = x1 *(x2* x3 )se traduce???

LyA - Predicados156

Ejemplo 2: el lenguaje de los Grupos

Una grupo es un modelo (verifica) las siguientesfórmulas:

∀ xyz (x.y).z = x.(y.z)∀ x (x.e = x ∧ e.x = x)∀ x (x.x-1 = e ∧ x-1.x = e)

Traducirlas al lenguaje formal LG