PROGRAMACIÓN LÓGICA

1

PROGRAMACIÓN LÓGICA

LÓGICA PROPOSICIONAL

Juan Juárez Fuentes

2

SintaxisSentencias proposicionales

Sentencias simples

Las sentencias simples expresan hechos simples del mundo.

Sentencias compuestas

Las sentencias compuestas expresan relaciones logicas entre las sentencias simples que las componen.

3

SintaxisSentencias simples

En la lógica proposicional, las sentencias simples toman la forma de simbolos atomicos, llamados proposiciones contstantes

Por convencion, las proposiciones constantes son escritas como un string de letras, digitos, el caracter especial “_”.

Ejemplos:

Nombres validos Nombres invalidosraining 324567 r32aining raining-or-snowingrAiNiNgraining_or_snowing

4

SintaxisComposición de las sentencias (1)

Negaciones: (¬p)Al argumento de una negación es llamados: objetivo.

Conjunciones: (p Λ q)Los argumentos de una conjunción son llamados: conyuntos.

Disyunciones: (p v q)Los argumentos de un disyunción son llamados: disyuntos.

5

SintaxisComposición de las sentencias (2)

Implicaciones: (p → q)

El argumento izquierdo de una implicación es el antecedente.

El argumento derecho es el concecuente.

Equivalencias / Bicondicionales: (p ↔ q)

6

SintaxisAnidación

Los componentes de las sentencias pueden ser anidados uno dentro de otro componente de la sentencia.

((p Λ q) Λ r)

((p v q) v r)

(((p Λ q) Λ r) → ((p v q) v r))

7

SintaxisParéntesis

Los paréntesis pueden ser algunas veces inecesarios. (((p Λ q) v r) → ((p v q) Λ r))

A veces se puede hacer de forma mas sencilla. (p Λ q) becomes p Λ q

Pero no ponerlo puede llevar a ambigüedades. ((p Λ q) v r) se convierte en p Λ q v r(p Λ (q v r)) se convierte en p Λ q v r

8

SintaxisPrecedencia

Los parentesis pueden ser omitidos cuando la estructura de una expresión puede ser determinada por la precedencia.

¬Λ

v→ ↔

9

SintaxisUtilizando la precedencia

Un operando rodeado por dos operadores se asocia con el operador de mas alta precedencia.

Si es rodeado por operadores de igual precedencia, el operando se asocia con el operador de la derecha.

p Λ q v r ((p Λ q) v r) p v q Λ r (p v(q Λ r)) p → q → r (p →(q → r)) p ↔ q ←r (p ↔(q → r)) ¬p Λ q ((¬p) Λ q)

10

SintaxisLenguages proposicionales

Un vocabulario proposicional es un conjunto/secuencia proposiciones constantes.

Dado un vocabulario proposicional, una sentencia proposicional es:

1. Una proposicion constante individual, o2. Una sentencia formada por sentencias simples.

Un lenguaje proposicional es el conjunto de todas las sentencias proposicionales que pueden ser formadas de un vocabulario proposicional.

11

SemánticaAsignación

Una asignación proposicional es una asociacion entre las proposiciones constantes en un lenguaje proposicional y los valores verdadero o falso.

Por simplicidad se utiliza el 1 como sinónimo para verdadero y 0 como sinónimo para falso.

p 1 p = 1q 0 q = 0r 1 r = 1

12

SemánticaAsignación en sentencias

Una asignación en sentencias es una asociacion entre sentencias arbitrarias en un lenguaje proposicional y los valores 0 y 1.

p = 1 (p v q) = 1q = 0 (q v ¬r) = 0r = 1 ((p v q) Λ ¬(q v ¬r)) = 1

13

SemánticaNegación

Negación:

Por ejemplo si el valor de verdad de p es 0, entonces el valor de verdad ¬p es 1.

Por ejemplo, si el valor de verdad de (p Λ q) es 1, entonces el valor de verdad de ¬(p Λ q) es 0.

0110

¬pP

14

SemánticaConjunción

Conjunción:

111

001

010

000

p Λ qqp

15

SemánticaDisyunción

Disyunción:

Este tipo de disyuncion es llamada or inclusivo, la cual dice que una disyunción es verdadera si y solo si al menos uno de sus disyuntos es verdadero.

En contraste con el or exclusivo, que dice que una disyuncion exclusiva es verdadera si y solo si un numero par de sus diyuntos es verdadero.

111

101

110

000

p v qqp

16

SemánticaImplicación

Implicación:

La semantica de la implicación es llamada implicación material.

Una implicación es verdadera si el antecedente es falso, haya o no haya una conexión con el consecuente.

Si George Washington esta vivo, yo soy billonario.

111

001

110

100

p → qqp

17

SemánticaEquivalencia

Equivalencia:

111

001

010

100

p ↔ qqp

18

SemánticaProcedimiento de evaluación

Se inicia con una asignación proposicional y una sentencia.

1. Se remplazan las constantes en la proposicion por sus valores de verdad.

2. Se usa el operador semántico para simplificar los componentes de las sentencias con valores de verdad como argumentos.

3. Se repite el proceso hasta producir un valor para la sentencia como un todo.

19

SemánticaEjemplo de evaluación

Interpretación i:

pi = 1qi = 0ri = 1

Componentes de la sentencia

(p v q) Λ (¬q v r)

20

SemánticaEjemplo con circuitos lógicos

Interpretación i:pi = 1qi = 1ri = 1

(r Λ ((p Λ ¬q) v (¬p v q))) v (p Λ q) (1 Λ ((1 Λ ¬1) v (¬1 v 1))) v (1 Λ 1)(1 Λ ((1 Λ 0) v (0 v 1))) v (1 Λ 1)

(1 Λ (0 v 0)) v 1(1 Λ 0) v 1

0 v 11

21

SemánticaSatisfacción y falsificación

Una asignación satisface una sentencia si y sólo si se asigna el valor de 1 a la sentencia.

Una asignación falsifica una sentencia si y sólo si se asigna el valor de 0 a la sentencia.

Una asignación satisface un conjunto de sentencias, si y sólo si se satisface cada elmento en el conjunto.

Una asignación falsifica un conjunto de sentencias si y sólo si falsifica al menos un elemento en el conjunto.

22

SatisfacciónEvaluación contra satisfacción

Evaluación:

pi = 1 (p v q)i = 1qi = 0 (¬q)i = 1

Satisfacción:

(p v q)i = 1 pi = 1(¬q)i = 1 qi = 0

23

SatisfacciónEjemplo

pi = ?qi = ?ri = ?

((r Λ ((p Λ ¬q) v (¬p v q))) v (p Λ q))i = 1

24

SatisfacciónTablas de verdad

Una tabla de verdad es una tabla con todas las posibles asignaciones para las proposiciones constantes en un lenguaje.

La cual contiene:

Una columna por constante.

Un renglón por asignación.

Para un lenguaje con n constantes hay 2n

asignaciones.

25

SatisfacciónTablas de verdad (2)

Ejemplo:

111011101001110010100000rqp

26

SemánticaProcedimiento de satisfacción

Método para encontrar las asignaciones proposicionales que satisfacen un conjunto dado de sentencias.

1. Formar una tabla de verdad para las constantes proposicionales y sumar columnas para cada sentencia en el conjunto.

2. Evaluar cada sentencia para cada uno de los renglones de la tabla de verdad.

3. Cualquier renglo que satisface todas las sentencias en el conjunto es una solución a el problema.

27

SemánticaProblema de satisfacción

Encontrar una asignación que satisface el siguiente conjunto de sentencias.

{q → r, p → q Λ r, ¬r}

28

SemánticaProblema de satisfacción (inicio) (2)

11110000p

11001100q

10101010r q → r ¬rp → q Λ r

{q → r, p → q Λ r, ¬r}

29

SemánticaProblema de satisfacción (3)

11110000p

11001100q

10101010r

10111011

q → r ¬rp → q Λ r

{q → r, p → q Λ r, ¬r}

30

SemánticaProblema de satisfacción (4)

11110000p

11001100q

10101010r

10111011

q → r ¬r

10001111

p → q Λ r

{q → r, p → q Λ r, ¬r}

31

SemánticaProblema de satisfacción (5)

11110000p

11001100q

10101010r

10111011

q → r

01010101¬r

10001111

p → q Λ r

{q → r, p → q Λ r, ¬r}

32

Propiedades de las sentenciasPropiedades de las sentencias

Valida

Una sentencia es valida si y sólo si cadainterpretación la satisface.

Contingente

Una sentencia es contingente si y sólo si algunainterpretacion la satisface y alguna interpretacion la falsifica.

Insatisfacible

Una sentencia es insatisfaccible si y sólo si no hay interpretacion que la satisfaga.

33

Propiedades de las sentenciasPropiedades de las sentencias (2)

Una sentencia es satisfaccible si y sólo si es valida o contingente.

Una sentencia es refutable si y sólo si es contingente o insatisfaccible.

34

Propiedades de las sentenciasEjemplo de validez (1)

11110000p

11001100q

10101010r p → q (p → q) v (q → r)q → r

35

Propiedades de las sentenciasEjemplo de validez (2)

11110000p

11001100q

10101010r

11001111

p → q (p → q) v (q → r)q → r

36

Propiedades de las sentenciasEjemplo de validez (3)

11110000p

11001100q

10101010r

11001111

p → q (p → q) v (q → r)

10111011

q → r

37

Propiedades de las sentenciasEjemplo de validez (4)

11110000p

11001100q

10101010r

11001111

p → q

11111111

(p → q) v (q → r)

10111011

q → r

38

Propiedades de las sentenciasMás validez

Doble negación:p ↔ ¬ ¬p

Leyes de DeMorgan:¬(p Λ q) ↔ (¬p v ¬q) ¬(p v q) ↔ (¬p Λ ¬q)

Implicación (introducción):p → (q → p)

Implicación (distribución):(p → (q → r)) → ((p → q) → (p → r))

39

Implicación lógicaImplicación lógica

Un conjunto de premisas ∆ implican logicamente una conclusión φ (se escribe ∆ |= φ) si y sólo so cada interpretación que satisface las premisas también satisface la conclusión.

{p} |= (p v q) {p} |# (p Λ q) {p, q} |= (p Λ q)

40

Implicación lógicaImplicación lógica ≠ a equivalencia lógica

{p} |= (p v q) {p v q} |# p

Analogía en aritmética: desigualdades más que ecuaciones.

41

Implicación lógicaMétodo de las tablas de verdad

Es un método para computar si un conjunto de premisas implican lógicamente una conclusión.

1. Formar una tabla de verdad para las proposiciones constantes y sumar una columna para las premisas y una columna para la conclusión.

2. Evaluar las premisas para cada renglón en la tabla.

42

Implicación lógicaMétodo de las tablas de verdad (2)

3. Evaluar la conclusión de cada renglón en la tabla.

4. Si cada renglón que satisface las premisas, también satisface la conclusión, entonces las premisas implican lógicamente la conclusión.

43

Implicación lógicaEjemplo

¿p implica lógicamente a (p v q)?

1111

1101

1010

0000

(p v q)pqp

44

Implicación lógicaEjemplo (2)

¿p implica lógicamente a (p Λ q)?

1111

0101

0010

0000

(p v q)pqp

45

Implicación lógicaEjemplo (2)

¿{p,q} implica lógicamente a (p Λ q)?

1

1

0

0

p

1111

0001

0110

0000

(p Λ q)qqp

46

Implicación lógicaEjemplo (3)

Problema: {(p → q), (m → p v q), m} |= q?

11110000m

11110000m

11001100p

10101010q

10111011

p → q

10101010q

11101111

m → p v q

47

Implicación lógicaImplicación lógica y Satisfacibilidad

Teorema de insatisfacibilidad: ∆ |= φ si y sólo si ∆ U {¬φ} es insatisfacible.

Prueba: suponga que ∆ |= φ. Si una signación satisface ∆, entonces también debe satisfacer a φ. Pero entonces prodría no satisfacer a ¬φ. Por consiguiente, ∆ U {¬ φ} es insatisfacible.

Suponga que ∆ U {¬ φ} es insatisfacible, entonces cada asignación que satisface a ∆ debe fallar al satisfacer ¬φ, por ejemplo: Si debe satisfacer φ. Por consiguiente, ∆ |= φ.

48

Implicación lógicaImplicación lógica y Satisfacibilidad (2)

Resultado: podemos determinar la implicación lógica mediante la determinación de insatisfacibilidad.

49

EjemploEl juego

Las personas de la ciudad A siempre dicen la verdad, y las personas de la ciudad B siempre mienten. Desafortunadamente, mirando una persona no se puede saber si es de la ciudad A o la ciudad B.

Si tu llegas a una bifurcación en el camino y quieres ir al estadio de fútbol tomando un camino. Sin embargo, no sabes que camino tomar. Hay una persona parada ahí.

¿Que pregunta simple puedes hacerle que te ayude a decidir que camino tomar?

50

EjemploIdea básica

11011000

respuestapreguntaCiudadano de ACamino de la izquierda

51

EjemploIdea básica (2)

111101010000

respuestapreguntaCiudadano de ACamino de la izquierda

52

EjemploIdea básica (3)

11111010010000

respuestapreguntaCiudadano de ACamino de la izquierda

53

EjemploIdea básica (4)

1111100100100100

respuestapreguntaCiudadano de ACamino de la izquierda

54

EjemploIdea básica (5)

Pregunta: Es el caso de que tomando el camino de la izquierda sea la forma de llegar al estadio si y sólo si tu eres de la ciudad A?

¿(Camino de la izquierda ↔ Ciudadano de A)?

55

BibliografíaNOTAS DE: Genesereth, Michael and Kao, Eric. Introductionto logic. Morgan \& Claypool Publishers. 2013.

David Barker-Plummer, Jon Barwise, and John Etchemendy. CSLI Publications, Stanford, CA, USA, 2nd edition.

Armin Biere, Marijn J. H. Heule, Hans van Maaren, and TobyWalsh, editors. Handbook of Satisfiability, volume 185 ofFrontiers in Artificial Intelligence and Applications. IOS Press, Lansdale, PA, USA, February 2009.

Hans K. Buning and T. Letterman. Propositional Logic: Deduction and Algorithms. Cambridge University Press, NewYork, NY, USA, 1999.

56

Bibliografía (2)Chin-Liang Chang and Richard C. Lee. Symbolic Logic andMechanicalTheorem Proving (Computer Science Classics). Academic Press, Salt Lake City, UT, USA, May 1973.

Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, Salt Lake City, UT, USA, 2nd edition, 2001.

Timothy Hinrichs and Michael Genesereth. Herbrand logic. Technical Report LG-2006-02, Stanford University, Stanford, CA, USA, 2006. http://logic.stanford.edu/reports/LG-2006-02.pdf.

John Alan Robinson and Andrei Voronkov, editors. Handbook of Automated Reasoning (in 2 volumes). MIT Press, Cambridge, MA, USA, 2001.