LogicaProposicional

Dpto de Informática. UVA
Lógica de proposiciones

Lógica de proposiciones
1 Introducción
Lenguaje lógico simbólico más sencillo.
Permite representar sentencias simples del lenguaje natural mediante formulas atómicas, cuya
composición representa sentencias más complejas:
p ≡ temperatura alta
q ≡ nivel bajo
r ≡ cerrar by-pass salida
((p ∧ q) ⊃ r) ≡ Si la temperatura está alta y el nivel es bajo,cerrar el by-pass de salida
Aporta:
• Lenguaje de representación simbólico
• Calculo de valores de verdad: la valor de verdad de una sentencia compuesta se obtiene a partir del
valor de verdad de las sentencias que la constituyen
• Deducción: métodos para inferir nuevas fórmulas

2 Lenguaje de la lógica proposicional
2.1 Sintaxis
Alfabeto proposicional: AP = SP ∪ CL ∪ SA
Símbolos Proposicionales,SP: p, q, r, ..., t (pueden variar; típicamente, alfabeto contable)
Conectores Lógicos, CL:
¬
∧
∨
⊃
↔

negación lógica
conjunción lógica
disyunción lógica
condición lógica
bi-condición lógica

no
y
o
implica
si y solo si

Símbolos Auxiliares, SA: ( )
SP, CL y SA han de ser disjuntos dos a dos.
Def. 2.1.1 Fórmula Atómica o Átomo.
Se denomina Fórmula Atómica a cualquier símbolo proposicional.
Def.2.1.2 Fórmula Bien Formada (FBF) .
Las FBF’s se definen inductivamente por:
1. Una formula Atómica es una FBF.
2. Si α es una FBF, (¬α) es una FBF.
3. Si α y β son FBF’s (α ∧ β), (α ∨ β), (α ⊃ β), (α ↔ β) son FBF’s .
4. El conjunto de FBF’s es el cierre transitivo del conjunto de fórmulas atómicas con las leyes 1), 2) y
3).
Conjunto de FBF’s: Lenguaje proposicional sobre AP: LAP (L si AP fijo).FBF’s:
no FBF’s:

(p ⊃ (q ∧ r))
(p ⊃ )

((p ∧ q) ∨ r)
(p ∧ ∨ r)

1
28/10/2004

Dpto de Informática. UVA
Lógica de proposiciones
El uso de paréntesis se puede reducir con los convenios:
asociatividad: de izquierda a derecha
prioridad (creciente): ↔, ⊃, ∧, ∨, ¬

2.2 Semántica
Def. 2.2.1 Interpretación.
Se denomina interpretación (sobre SP), I, a una función que asigna a cada fórmula atómica un valor deverdad.
I: SP ---> {T, F}
Def. 2.2.2 Evaluación de FBF’s
A partir de I, se define de forma única una función de evaluación de FBF’s, V: LAP ---> {T, F}, de la
siguiente forma:
1. Si p es un átomo, V(p)=I(p)
2. Si α es una FBF, V(¬α): T si V(α)= F; F si V(α)= T
3. Si α y β son FBF’s,
V(α ∧ β)= T si V(α)=V(β)=T; F en otro caso
V(α ∨ β)= F si V(α)=V(β)=F; T en otro caso
V(α ⊃ β)= F si V(α)=T y V(β)=F;T en otro caso
V(α ↔ β)= T si V(α)=V(β); T en otro caso
Se dice que α es cierta bajo I, o que I satisface α sii V(α)= T, donde V se define a partir de I según def.
2.2.2. En caso contrario, se dice que α es falsa bajo I

3 Modelo, Consistencia, Validez y Satisfacibilidad.
3.1 Modelo, Consistencia y Validez
Def 3.1.1 Modelo.
Una interpretación, I, es un modelo de una FBF, α, sii V(α)=T
Unainterpretación, I, es un modelo de un conjunto finito de FBF’s, Ω={α1, α2, ...
modelo de todo αi ∈ Ω.
α ≡ (p ∧ q)
Ω={p, q}

, αn} sii I es un

cualquier I con I(p)=I(q)=T es un modelo de α.
cualquier I con I(p)=I(q)=T es un modelo de Ω.

Def 3.1.2 Consistencia.
Una FBF, α, es consistente o satisfacible sii tiene un modelo.
Un conjunto finito de FBF’s, Ω, es consistente o satisfacible sii tiene un modelo.α ≡ ((p ∧ q) ⊃ r) es consistente, pues cualquier I con I(p)=I(q)=I(r)= F es un modelo para α

2
28/10/2004

Dpto de Informática. UVA
Lógica de proposiciones
Def 3.3 Inconsistencia.
Una FBF, α, es inconsistente o insatisfacible sii no es consistente.
Un conjunto finito de FBF’s, Ω, es consistente o satisfacible sii no es consistente.
β ≡ (p ∧ ¬p)
es inconsistente
γ ≡ ((p ⊃ q) ∧ (p ∧ ¬q)) esinconsistente

Def. 3.1.4 Validez.
Una FBF, α, es valida o tautológica sii α es cierta bajo todas las interpretaciones de SP.
α ≡ (p ∧ ¬p)
β ≡ (p ⊃ (p ∨ q))
γ ≡ (p ↔ (p ∨ q))

es una fórmula válida
es una fórmula válida
no es válida

Inconsistentes
Siempre F

Consistentes
T oF

Validas
Siempre T

Relación entre Fórmulas consistentes, inconsistentes y validas.

3.2 Satisfacibilidad
Def. 3.2.1...