PDF de programación - Tema 1: Sintaxis y Semántica de la Lógica Proposicional

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Tema 1:

Sintaxis y Semántica de la Lógica

Proposicional

Dpto. Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

Lógica Informática

(Tecnologías Informáticas)

Curso 2015–16

Contenido

Introducción

Sintaxis

Fórmulas
Inducción sobre fórmulas

Semántica

Funciones de verdad
Valoraciones
Consecuencia Lógica y satisfactibilidad

Problemas de decisión

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Problema básico

Dados un conjunto de afirmaciones (hechos, hipótesis,...), BC,
y una afirmación A, decidir si A ha de ser necesariamente cierta,
suponiendo que todos las afirmaciones de BC lo son.

La Lógica proporciona formulaciones precisas de este
problema y diferentes soluciones.
Algunos aspectos esenciales de este problema son:

1. El lenguaje para expresar (representar) los afirmaciones.

2. La definición precisa de la noción de “afirmación cierta”.

3. Reglas y procedimientos efectivos para garantizar la
corrección de las deducciones (cálculos deductivos,
algoritmos de deducción).

Empezaremos estudiando estas cuestiones en el caso más
simple: la Lógica Proposicional.

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Lógica proposicional

Características generales de la Lógica proposicional:

Es una lógica cuyas expresiones representan

afirmaciones que pueden considerarse verdaderas o
falsas.

La expresiones de la lógica (fórmulas) se construyen a
partir de las expresiones básicas mediante composición,
usando para ello operadores básicos (conectivas).

Las conectivas se corresponden con formas sencillas de
construir afirmaciones complejas en el lenguaje natural
partiendo de otras mas sencillas:

Conjunción: “. . . tal . . . y. . . cual. . . ”
Disyunción: “. . . tal . . . o. . . cual . . . ”
Implicación “Si . . . tal . . . entonces. . . cual . . . ”
Negación: “No es cierto que tal . . . ”

Sólo permite analizar las formas de razonamiento

ligadas a este tipo de construcciones.

Símbolos del lenguaje

El lenguaje de la lógica proposicional consta de:

1. Un conjunto numerable, VP, de variables

proposicionales: p0, p1, . . . , p, q, r , . . .

2. Las conectivas lógicas:

De aridad 1: ¬ (negación).
De aridad 2: ∨ (disyunción), ∧ (conjunción),

→ (condicional) y ↔ (bicondicional).

3. Símbolos auxiliares: “(” y “)”.

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Fórmulas

El conjunto de las fórmulas proposicionales es el menor
conjunto de expresiones PROP tal que:

VP ⊆ PROP ,
Si F ∈ PROP entonces ¬F ∈ PROP
F , G ∈ PROP entonces

(F ∨ G ), (F ∧ G ), (F → G ), (F ↔ G ) ∈ PROP.

La sintaxis del lenguaje pretende evitar la ambig¨uedad en la
interpretación de las fórmulas. Esa es la función de los
símbolos auxiliares.

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Árboles de formación

Asociamos a cada fórmula un árbol de formación

(esencialmente único) que describe el modo en que se
construye la fórmula a partir de otras más sencillas.

Ejemplo:

¬(¬(p ∨ q) → (¬r ∧ s))
(¬(p ∨ q) → (¬r ∧ s))
HHH

(¬r ∧ s)
¬(p ∨ q)
HH¬r
(p ∨ q)
 HH
p
q

s

r

Las fórmulas que aparecen en el árbol de formación de

una fórmula F se denominan subfórmulas de F .

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Reducción de paréntesis

Para facilitar la lectura de las fórmulas adoptaremos los
siguientes convenios de notación:

1. Omitiremos los paréntesis externos.

2. Daremos a las conectivas una precedencia de asociación.
De mayor a menor, están ordenadas por: ¬,∧,∨,→,↔.
Ejemplo: F ∧ G → ¬F ∨ G es ((F ∧ G ) → (¬F ∨ G )).
3. Cuando una conectiva se usa repetidamente, se asocia

por la derecha: F ∨ G ∨ H es (F ∨ (G ∨ H)).

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Principio de Inducción sobre fórmulas

Gracias a la definición de PROP si deseamos probar que
toda fórmula proposicional satisface cierta propiedad Ψ,
podemos probarlo por inducción sobre fórmulas.
Para ello probamos:
1. Caso base: Si F ∈ Var , entonces F tiene la propiedad

Ψ.

2. Paso de inducción:

2.1 Si F ∈ PROP tiene la propiedad Ψ, entonces ¬F tiene
2.2 Si F , G ∈ PROP tienen la propiedad Ψ, entonces

la propiedad Ψ.
(F ∨ G ), (F ∧ G ), (F → G ) y (F ↔ G ) también tienen
la propiedad Ψ.

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Funciones de verdad

Los elementos del conjunto {0, 1} se llaman valores de
verdad. Se dice que 0 es el valor falso y el 1 es el valor
verdadero.

El significado de una conectiva se determina mediante

su función de verdad:

Para la negación su función de verdad es la función

H¬(i) =

si i = 0;
si i = 1.

0,

y para las demás conectivas:

1,
0,
1,
0,
1,

0,

1,

1,

0,

H∨(i, j) =

H∧(i, j) =

H→(i, j) =

H↔(i, j) =

si i = j = 0;
en otro caso.

si i = j = 1;
en otro caso.

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

si i = j;
en otro caso.

Valoraciones

Las variables proposicionales se interpretan mediante

una valoración de verdad (o interpretación), es decir,
una aplicación

v : VP → {0, 1}

Podemos extender cada valoración, v , al conjunto de

todas las fórmulas de manera que para cada fórmula F
se verifique:

v (¬F ) = H¬(v (F )).
v ((F ∨ G )) = H∨(v (F ), v (G )).
v ((F ∧ G )) = H∧(v (F ), v (G )).
v ((F → G )) = H→(v (F ), v (G )).
v ((F ↔ G )) = H↔(v (F ), v (G )).

Fijada v , estas ecuaciones permiten asignar de manera
única un valor v (F ) a cada fórmula. Se dice que v (F )
es el valor de verdad de F respecto de v .

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Valor de verdad (I)
Veamos el cálculo de v (¬(¬(p ∨ q) ∨ (¬r ∨ s)) en el árbol de
formación.

¬(¬(p ∨ q) ∨ (¬r ∨ s))

(0)

¬(p ∨ q) ∨ (¬r ∨ s)

(1)

HHHH


¬(p ∨ q)

(¬r ∨ s)

(0)
(p ∨ q)
(1)

 HHH
q
p
(1)
(1)

(1)
 HH
¬r
s
(0)
(1)

r
(0)

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Valor de verdad (II)

El valor v (F ) está bien definido gracias al siguiente
resultado:
Teorema. Para cada valoración de verdad, v , existe una
única aplicación V : PROP → {0, 1} tal que



V (A) =

v (A)
H¬(V (B))
H∨(V (B), V (C ))
H∧(V (B), V (C ))
H→(V (B), V (C ))
H↔(V (B), V (C ))

si A ∈ VP
si A es ¬B
si A es (B ∨ C )
si A es (B ∧ C )
si A es (B → C )
si A es (B ↔ C )

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Lógica

Proposicional

Introducción

Sintaxis
Fórmulas
Inducción sobre
fórmulas

Semántica
Funciones de verdad
Valoraciones
Consecuencia Lógica
y satisfactibilidad

Problemas de
decisión

Tablas de verdad

Dada una valoración v , el valor de verdad de una fórmula F
respecto de v está determinado por los valores de verdad de
las subfórmulas de F .

Ejemplo: si v (p) = v (q) = 0 y v (r ) = 1, entonces

v (¬((p → q) ∨ r )) = H¬(H∨(v (p → q), v (r ))) =

= H¬(H∨(H→(v (p), v (q)), 1)) = 0

Fijada v podemos presentar el cálculo de F mediante una
tabla:

p q r
0 0 1

p → q (p → q) ∨ r ¬((p → q) ∨ r )

1

1

0

Una tabla de verdad para F es una tabla similar que
contiene una fila por cada valoración que asigne valores
distintos a las variables proposicionales que aparecen en F .

Validez y satisfactibilidad (I)

Decimos que una fórmula F es válida en v , o que v es

un modelo de F , si v (F ) = 1.

Notación: v |= F .
Una valoración v es modelo de un conjunto de fórmulas

U, v |= U, si v es modelo de toda fórmula de U.

Una fórmula F es una tautología (o válida) si es válida

para toda valoración (notación |= F ).

Una fórmula F es satisfactible (o consistente) si existe
una valoración que es modelo de F . En caso contrario
diremos que es insatisfactible (o inconsistente).

Aná