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 ∨
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