PDF de programación - Tema 1: Sintaxis y semántica de la lógica proposicional - Lógica matemática y fundamentos (2016–17)

Tema 1: Sintaxis y semántica de la lógica proposicional - Lógica matemática y fundamentos (2016–17)gráfica de visualizaciones

Publicado el 6 de Agosto del 2017
1.263 visualizaciones desde el 6 de Agosto del 2017
238,3 KB
34 paginas
Creado hace 7a (06/02/2017)
LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Lógica matemática y fundamentos (2016–17)
Tema 1: Sintaxis y semántica de la lógica proposicional

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 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Tema 1: Sintaxis y semántica de la lógica proposicional

1. Introducción

2. Sintaxis de la lógica proposicional

3. Semántica proposicional

2 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Introducción

Tema 1: Sintaxis y semántica de la lógica proposicional

1. Introducción

Panorama de la lógica
Ejemplos de argumentos y formalizaciones

2. Sintaxis de la lógica proposicional

3. Semántica proposicional

3 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Introducción

Panorama de la lógica

Lógica

Objetivos de la lógica:

La formalización del lenguaje natural.
Los métodos de razonamiento.

Sistemas lógicos:

Lógica proposicional.
Lógica de primer orden.
Lógicas de orden superior.
Lógicas modales.
Lógicas descriptivas.

Aplicaciones de la lógica en computación:

Programación lógica.
Verificación y síntesis automática de programas.
Representación del conocimiento y razonamiento.
Modelización y razonamiento sobre sistemas.

Lógica informática = Representación del conocimiento +

Razonamiento

4 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Introducción

Ejemplos de argumentos y formalizaciones

Argumentos y formalización

Ejemplos de argumentos:

Ejemplo 1: Si el tren llega a las 7 y no hay taxis en la estación,

entonces Juan llegará tarde a la reunión. Juan no ha llegado tarde
a la reunión. El tren llegó a las 7. Por tanto, habían taxis en la
estación.

Ejemplo 2: Si hay corriente y la lámpara no está fundida, entonces
está encendida. La lámpara no está encendida. Hay corriente. Por
tanto, la lámpara está fundida.

Formalización:

Simbolización:

Simb.

p
q
r

Ejemplo 1
el tren llega a las 7
hay taxis en la estación
Juan llega tarde a la reunión

Ejemplo 2
hay corriente
la lámpara está fundida
la lámpara está encendida

Si p y no q, entonces r. No r. p. Por tanto, q.
p ∧ ¬q → r , ¬r , p |= q.

.

5 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

Tema 1: Sintaxis y semántica de la lógica proposicional

1. Introducción

2. Sintaxis de la lógica proposicional

El lenguaje de la lógica proposicional
Recursión e inducción sobre fórmulas
Árboles de análisis (o de formación)
Eliminación de paréntesis
Subfórmulas

3. Semántica proposicional

6 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

El lenguaje de la lógica proposicional

El lenguaje de la lógica proposicional

Alfabeto proposicional:

variables proposicionales: p0, p1, . . . ; p, q, r.
conectivas lógicas:

monaria: ¬ (negación),
binarias: ∧ (conjunción),

→ (condicional), ↔ (bicondicional).

∨ (disyunción),

símbolos auxiliares: “(“ y “)”.

Fórmulas proposicionales:

Definición:

Las variables proposicionales son fórmulas (fórmulas atómicas).
Si F y G son fórmulas, entonces también lo son

¬F, (F ∧ G), (F ∨ G), (F → G) y (F ↔ G)

Ejemplos:

Fórmulas: p,
No fórmulas: (p),

(p ∨ ¬q), ¬(p ∨ p),

p ∨ ¬q,

(p ∨ ∧q)

((p → q) ∨ (q → p))

7 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

El lenguaje de la lógica proposicional

Fórmulas proposicionales (BNF)

Notaciones:

p, q, r , . . . representarán variables proposicionales.
F , G, H, . . . representarán fórmulas.
VP representa el conjunto de los variables proposicionales.
Prop representa el conjunto de las fórmulas.
∗ representa una conectiva binaria.

Forma de Backus Naur (BNF) de las fórmula proposicionales:

F ::= p | ¬G | (F ∧ G) | (F ∨ G) | (F → G) | (F ↔ G).

8 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

Recursión e inducción sobre fórmulas

Definiciones por recursión sobre fórmulas

Número de paréntesis de una fórmula:

Def: El número de paréntesis de una fórmula F se define

recursivamente por:

si F es atómica;
si F es ¬G;
si F es (G ∗ H)

9 / 34

0,

np(F) =

Ejemplos:

np(G),
2 + np(G) + np(H),

np(p) = 0
np(q) = 0
np(¬q) = 0
np((¬q ∨ p)) = 2
np((p → (¬q ∨ p))) = 4

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

Recursión e inducción sobre fórmulas

Demostración por inducción sobre fórmulas

Principio de inducción sobre fórmulas: Sea P una propiedad sobre

las fórmulas que verifica las siguientes condiciones:
Todas las fórmulas atómicas tienen la propiedad P.
Si F y G tienen la propiedad P, entonces ¬F, (F ∧ G), (F ∨ G),

(F → G) y (F ↔ G), tienen la propiedad P.

Entonces todas las fórmulas proposicionales tienen la propiedad
P.
par de paréntesis.

Propiedad: Todas las fórmulas proposicionales tienen un número

Demostración por inducción sobre las fórmulas.

Base: F atómica =⇒ np(F) = 0 es par.
Paso: Supongamos que np(F) y np(G) es par (hipótesis de

inducción). Entonces,

np(¬F) = np(F) es par y
np((F ∗ G)) = 2 + np(F) + np(G) es par,

para cualquier conectiva binaria ?.

10 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

Árboles de análisis (o de formación)

Árboles de análisis (o de formación)


(p → (¬q ∨ p))

p

(¬q ∨ p)

p



p

¬q

q

p

¬

q

11 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

Eliminación de paréntesis

Criterios de reducción de paréntesis

Pueden eliminarse los paréntesis externos.
F ∧ G es una abreviatura de (F ∧ G).

Precedencia de asociación de conectivas: ¬,∧,∨,→,↔.

F ∧ G → ¬F ∨ G es una abreviatura de

((F ∧ G) → (¬F ∨ G)).

Cuando una conectiva se usa repetidamente, se asocia por la

derecha.

F ∨ G ∨ H
abrevia
F ∧ G ∧ H → ¬F ∨ G abrevia

(F ∨ (G ∨ H))
((F ∧ (G ∧ H)) → (¬F ∨ G))

12 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Sintaxis de la lógica proposicional

Subfórmulas

Subfórmulas

Def: El conjunto Subf(F) de las subfórmulas de una fórmula F se

define recursivamente por:



Subf(F) =

{F},
{F} ∪ Subf(G),
{F} ∪ Subf(G) ∪ Subf(H),

si F es atómica;
si F es ¬G;
si F es G ∗ H

Ejemplos:

Subf(p) = {p}
Subf(q) = {q}
Subf(¬q) = {¬q, q}
Subf(¬q ∨ p) = {¬q ∨ p,¬q, q, p}
Subf(p → ¬q ∨ p) = {p → ¬q ∨ p, p,¬q ∨ p,¬q, q}

13 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Semántica proposicional

Tema 1: Sintaxis y semántica de la lógica proposicional

1. Introducción

2. Sintaxis de la lógica proposicional

3. Semántica proposicional

Valores y funciones de verdad
Interpretaciones
Modelos, satisfacibilidad y validez
Algoritmos para satisfacibilidad y validez
Selección de tautologías
Equivalencia lógica
Modelos de conjuntos de fórmulas
Consistencia y consecuencia lógica
Argumentaciones y problemas lógicos

14 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Semántica proposicional

Valores y funciones de verdad

Valores y funciones de verdad

Valores de verdad (B): 1: verdadero y 0: falso.
Funciones de verdad:

H¬ : {0, 1} → {0, 1} t.q. H¬(i) =

0,
H∧ : {0, 1}2 → {0, 1} t.q. H∧(i, j) =

si i = 0;
si i = 1.

(1,
(1,
(0,
(0,
(1,

1,

0,

si i = j = 1;
en otro caso.
si i = j = 0;
en otro caso.
si i = 1, j = 0;
en otro caso.
si i = j;
en otro caso.

15 / 34

1,

0,

H∨ : {0, 1}2 → {0, 1} t.q. H∨(i, j) =

H→ : {0, 1}2 → {0, 1} t.q. H→(i, j) =

H↔ : {0, 1}2 → {0, 1} t.q. H↔(i, j) =

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Semántica proposicional

Interpretaciones

Interpretaciones de fórmulas

i ¬i
1
0
1
0

Funciones de verdad mediante tablas de verdad:
i → j
1
0
1
1

i ∨ j
1
1
1
0

i ∧ j
1
0
0
0

i
1
1
0
0

j
1
0
1
0

i ↔ j
1
0
0
1

Interpretación:

Def.: Una interpretación es una aplicación I : VP → B.
Prop: Para cada interpretación I existe una única aplicación

I0 : Prop → B tal que:

I0(F) =

H¬(I0(G)),
H∗(I0(G), I0(H)),

si F es atómica;
si F = ¬G;
si F = G ∗ H

Se dice que I0(F) es el valor de verdad de F respecto de I.

I(F),

16 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Semántica proposicional

Interpretaciones

Interpretaciones de fórmulas

Ejemplo: Sea F = (p ∨ q) ∧ (¬q ∨ r)

valor de F en una interpretación I1 tal que

I1(p) = I1(r) = 1, I1(q) = 0

(p ∨ q) ∧ (¬q ∨ r)
(1 ∨ 0) ∧ (¬0 ∨ 1)
∨ 1)
1

1
1

∧ (1

1

valor de F en una interpretación I2 tal que

I2(r) = 1, I2(p) = I2(q) = 0

(p ∨ q) ∧ (¬q ∨ r)
0
1

10 1

0

0

0

Prop.: Sea F una fórmula y I1, I2 dos interpretaciones. Si

I1(p) = I2(p) para todos las variables proposicionales de F,
entonces I0

1(F) = I0

Notación: Se escribe I(F) en lugar de I0(F).

2(F).

17 / 34

LMF Tema 1: Sintaxis y semántica de la lógica proposicional

Semántica proposicional

Modelos, satisfacibilidad y validez

Modelos y satisfacibilidad

Modelo de una fórmula

Def.: I es modelo de F si I(F) = 1.
Notación: I |= F.
Ejemplo (continuación del anterior):

– si I1(p) = I1(r) = 1, I1(q) = 0, entonces I1 |= (p ∨
  • Links de descarga
http://lwp-l.com/pdf6136

Comentarios de: Tema 1: Sintaxis y semántica de la lógica proposicional - Lógica matemática y fundamentos (2016–17) (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad