PDF de programación - Tema 7: Sintaxis y semántica de la lógica de primer orden - Lógica informática (2015–16)

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

Lógica informática (2015–16)

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

José A. Alonso Jiménez
Andrés Cordón Franco
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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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

PD 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