PDF de programación - Tema 7: Sintaxis y semántica de la lógica de primer orden - Lógica matemática y fundamentos (2014–15)

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Lógica matemática y fundamentos (2014–15)
Tema 7: Sintaxis y semántica de la lógica de primer orden

José A. Alonso Jiménez
María J. Hidalgo Doblado

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

1 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Tema 7: Sintaxis y semántica de la lógica de primer orden

1. Representación del conocimiento en lógica de primer orden

2. Sintaxis de la lógica de primer orden

3. Semántica de la lógica de primer orden

2 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Tema 7: Sintaxis y semántica de la lógica de primer orden

1. Representación del conocimiento en lógica de primer orden

Representación de conocimiento geográfico
Representación del mundo de los bloques
Representación de conocimiento astronómico

2. Sintaxis de la lógica de primer orden

3. Semántica de la lógica de primer orden

3 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación de conocimiento geográfico

Limitación expresiva de la lógica proposicional

Ejemplo 1: Si Sevilla es vecina de Cádiz, entonces Cádiz es vecina
de Sevilla. Sevilla es vecina de Cádiz. Por tanto, Cádiz es vecina
de Sevilla

Representación en lógica proposicional:

{SvC → CvS,

SvC} |= CvS

Ejemplo 2: Si una ciudad es vecina de otra, entonces la segunda

es vecina de la primera. Sevilla es vecina de Cádiz. Por tanto,
Cádiz es vecina de Sevilla

Representación en lógica proposicional: Imposible
Representación en lógica de primer orden:
{∀x ∀y [vecina(x , y ) → vecina(y , x )],
|= vecina(Cadiz, Sevilla)

vecina(Sevilla, Cadiz)}

4 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación de conocimiento geográfico

Limitación expresiva de la lógica proposicional

Ejemplo 1: Si Sevilla es vecina de Cádiz, entonces Cádiz es vecina
de Sevilla. Sevilla es vecina de Cádiz. Por tanto, Cádiz es vecina
de Sevilla

Representación en lógica proposicional:

{SvC → CvS,

SvC} |= CvS

Ejemplo 2: Si una ciudad es vecina de otra, entonces la segunda

es vecina de la primera. Sevilla es vecina de Cádiz. Por tanto,
Cádiz es vecina de Sevilla

Representación en lógica proposicional: Imposible
Representación en lógica de primer orden:
{∀x ∀y [vecina(x , y ) → vecina(y , x )],
|= vecina(Cadiz, Sevilla)

vecina(Sevilla, Cadiz)}

4 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación de conocimiento geográfico

Limitación expresiva de la lógica proposicional

Ejemplo 1: Si Sevilla es vecina de Cádiz, entonces Cádiz es vecina
de Sevilla. Sevilla es vecina de Cádiz. Por tanto, Cádiz es vecina
de Sevilla

Representación en lógica proposicional:

{SvC → CvS,

SvC} |= CvS

Ejemplo 2: Si una ciudad es vecina de otra, entonces la segunda

es vecina de la primera. Sevilla es vecina de Cádiz. Por tanto,
Cádiz es vecina de Sevilla

Representación en lógica proposicional: Imposible
Representación en lógica de primer orden:
{∀x ∀y [vecina(x , y ) → vecina(y , x )],
|= vecina(Cadiz, Sevilla)

vecina(Sevilla, Cadiz)}

4 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación de conocimiento geográfico

Limitación expresiva de la lógica proposicional

Ejemplo 1: Si Sevilla es vecina de Cádiz, entonces Cádiz es vecina
de Sevilla. Sevilla es vecina de Cádiz. Por tanto, Cádiz es vecina
de Sevilla

Representación en lógica proposicional:

{SvC → CvS,

SvC} |= CvS

Ejemplo 2: Si una ciudad es vecina de otra, entonces la segunda

es vecina de la primera. Sevilla es vecina de Cádiz. Por tanto,
Cádiz es vecina de Sevilla

Representación en lógica proposicional: Imposible
Representación en lógica de primer orden:
{∀x ∀y [vecina(x , y ) → vecina(y , x )],
|= vecina(Cadiz, Sevilla)

vecina(Sevilla, Cadiz)}

4 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

sobre(x , y ) se verifica si el bloque x está colocado sobre el bloque

sobre_mesa(x ) se verifica si el bloque x está sobre la mesa

Situación del ejemplo:

Simbolización:

y

sobre(a, b), sobre(b, c), sobre_mesa(c), sobre(d, e), sobre_mesa(e)

5 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

Definiciones:

bajo(x , y ) se verifica si el bloque x está debajo del bloque y

∀x ∀y [bajo(x , y ) ↔ sobre(y , x )]

encima(x , y ) se verifica si el bloque x está encima del bloque y

pudiendo haber otros bloques entre ellos

∀x ∀y [ encima(x , y ) ↔

sobre(x , y ) ∨ ∃z [sobre(x , z) ∧ encima(z, y )]]
libre(x ) se verifica si el bloque x no tiene bloques encima

∀x [libre(x ) ↔ ¬∃y sobre(y , x )]

pila(x , y , z) se verifica si el bloque x está sobre el y, el y sobre el

z y el z sobre la mesa

∀x ∀y ∀z [ pila(x , y , z) ↔

sobre(x , y ) ∧ sobre(y , z) ∧ sobre_mesa(z)]

Propiedades:

Si z, y , z es una pila entonces y no está libre

∀x ∀y ∀z [pila(x , y , z) → ¬ libre(y )]

6 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

Definiciones:

bajo(x , y ) se verifica si el bloque x está debajo del bloque y

∀x ∀y [bajo(x , y ) ↔ sobre(y , x )]

encima(x , y ) se verifica si el bloque x está encima del bloque y

pudiendo haber otros bloques entre ellos

∀x ∀y [ encima(x , y ) ↔

sobre(x , y ) ∨ ∃z [sobre(x , z) ∧ encima(z, y )]]
libre(x ) se verifica si el bloque x no tiene bloques encima

∀x [libre(x ) ↔ ¬∃y sobre(y , x )]

pila(x , y , z) se verifica si el bloque x está sobre el y, el y sobre el

z y el z sobre la mesa

∀x ∀y ∀z [ pila(x , y , z) ↔

sobre(x , y ) ∧ sobre(y , z) ∧ sobre_mesa(z)]

Propiedades:

Si z, y , z es una pila entonces y no está libre

∀x ∀y ∀z [pila(x , y , z) → ¬ libre(y )]

6 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

Definiciones:

bajo(x , y ) se verifica si el bloque x está debajo del bloque y

∀x ∀y [bajo(x , y ) ↔ sobre(y , x )]

encima(x , y ) se verifica si el bloque x está encima del bloque y

pudiendo haber otros bloques entre ellos

∀x ∀y [ encima(x , y ) ↔

sobre(x , y ) ∨ ∃z [sobre(x , z) ∧ encima(z, y )]]
libre(x ) se verifica si el bloque x no tiene bloques encima

∀x [libre(x ) ↔ ¬∃y sobre(y , x )]

pila(x , y , z) se verifica si el bloque x está sobre el y, el y sobre el

z y el z sobre la mesa

∀x ∀y ∀z [ pila(x , y , z) ↔

sobre(x , y ) ∧ sobre(y , z) ∧ sobre_mesa(z)]

Propiedades:

Si z, y , z es una pila entonces y no está libre

∀x ∀y ∀z [pila(x , y , z) → ¬ libre(y )]

6 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

Definiciones:

bajo(x , y ) se verifica si el bloque x está debajo del bloque y

∀x ∀y [bajo(x , y ) ↔ sobre(y , x )]

encima(x , y ) se verifica si el bloque x está encima del bloque y

pudiendo haber otros bloques entre ellos

∀x ∀y [ encima(x , y ) ↔

sobre(x , y ) ∨ ∃z [sobre(x , z) ∧ encima(z, y )]]
libre(x ) se verifica si el bloque x no tiene bloques encima

∀x [libre(x ) ↔ ¬∃y sobre(y , x )]

pila(x , y , z) se verifica si el bloque x está sobre el y, el y sobre el

z y el z sobre la mesa

∀x ∀y ∀z [ pila(x , y , z) ↔

sobre(x , y ) ∧ sobre(y , z) ∧ sobre_mesa(z)]

Propiedades:

Si z, y , z es una pila entonces y no está libre

∀x ∀y ∀z [pila(x , y , z) → ¬ libre(y )]

6 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

Definiciones:

bajo(x , y ) se verifica si el bloque x está debajo del bloque y

∀x ∀y [bajo(x , y ) ↔ sobre(y , x )]

encima(x , y ) se verifica si el bloque x está encima del bloque y

pudiendo haber otros bloques entre ellos

∀x ∀y [ encima(x , y ) ↔

sobre(x , y ) ∨ ∃z [sobre(x , z) ∧ encima(z, y )]]
libre(x ) se verifica si el bloque x no tiene bloques encima

∀x [libre(x ) ↔ ¬∃y sobre(y , x )]

pila(x , y , z) se verifica si el bloque x está sobre el y, el y sobre el

z y el z sobre la mesa

∀x ∀y ∀z [ pila(x , y , z) ↔

sobre(x , y ) ∧ sobre(y , z) ∧ sobre_mesa(z)]

Propiedades:

Si z, y , z es una pila entonces y no está libre

∀x ∀y ∀z [pila(x , y , z) → ¬ libre(y )]

6 / 45

LMF Tema 7: Sintaxis y semántica de la lógica de primer orden

Representación del conocimiento en lógica de primer orden

Representación del mundo de los bloques

Representación del mundo de los bloques

Definiciones:

bajo(x , y ) se verifica si el bloque x está debajo del bloque y

∀x ∀y [bajo(x , y ) ↔ sobre(y , x )]

encima(x , y )