PDF de programación - Logica Proposicional

Lógica proposicional

Ivan Olmos Pineda

Introducción
- Originalmente, la lógica trataba con argumentos en el

lenguaje natural

- ¿es el siguiente argumento válido?

- Todos los hombres son mortales
Todos los hombres son mortales
- Sócrates es hombre
- Por lo tanto, Sócrates es mortal

- En el lenguaje natural, se presentan una infinidad de

argumentos, en los cuales tenemos que determinar la
veracidad o falsedad de enunciados complejos

Lógica Proposicional
- Ejemplos de otros argumentos

- Algunas personas son políticas
- Sócrates es una persona
- Por lo tanto, Sócrates es político

- Creo que todos los hombres son mortales
- Creo que Sócrates es hombre
- Por lo tanto, creo que Sócrates es mortal

- Estos argumentos son válidos?

Lógica Proposicional
- También se pueden presentar cuestionamientos

interesantes como los siguientes:
- Sea A = {1, 2, 3}

- A ˛ A?
- A ˝ A?
- A A?
- A A?

- Sea X = {{1,2,3},{4,5}}

- X ˛ X?
- A ˛ X?

¿Porqué se necesita la lógica?
- Con la lógica, se busca formalizar la representación de
diferentes argumentos, no importando el origen de los
mismos
- Sintaxis precisa
- Semántica bien definida

- Se busca aplicar a

- Matemáticas: definición de objetos matemáticos, definición de

teorías matemáticas, técnicas de demostración

- Aplicarlo para formalizar diversos aspectos en el área de

computación

Aplicaciones de la lógica en la computación

- Lenguajes de programación: como se estructura la lógica

de un programa

- Bases de datos: lenguajes de consulta
- Inteligencia artificial: técnicas para el razonamiento,

deducción de conocimiento

- Análisis y diseño de algoritmos: análisis de complejidad de

los problemas

SU IMPACTO EN LA COMUTACIÓN ES MUY FUERTE!

Lenguaje de la Lógica Proposicional
- La lógica proposicional pretende estudiar las frases

declarativas simples (enunciados o proposiciones)
- Estos elementos son los utilizados como base para la

transmisión de conocimiento humano

Una proposición se define como un enunciado que puede
- Una proposición se define como un enunciado que puede
ser calificado como verdadero o falso y que no puede
descomponerse en otras frases verdaderas o falsas

- ¿Ejemplos de lo que serían proposiciones? ¿ejemplo de lo

que no serían proposiciones?

Lenguaje de la Lógica Proposicional
- Para relacionar las proposiciones, se utilizan diferentes

conectivos

Lenguaje de la Lógica Proposicional

Alfabeto de la Lógica Proposicional
- La siguiente tabla describe todo el alfabeto utilizado en la

lógica proposicional

Sintaxis de la Lógica Proposicional

1.

2.

3.

4.
4.

1.

1.

2.

3.

Las constantes V (verdadero) y F (falso) pertenecen a LP
Las letras de proposición p, q, r, … pertenecen a LP
Si “a” y “b” pertenecen a LP, entonces:

a, b, (a b), (a b), (a  b), (a «

b) pertenecen a LP

Se establece la jerarquía de operadores:
Se establece la jerarquía de operadores:

,
, «



fi
Ejercicios 1
- Formalizar las siguientes expresiones:

a) q si p
b) p pero q
c) como mínimo p
d) p no obstante q
e) q necesario para p
e) q necesario para p
f) q suficiente para p
g) p a pesar de q
h) No p a menos que q
i) p sólo si q
j) p sin embargo q
k) p suficiente para q
l) p siempre que q
m) p a no ser que q

Ejercicios 2
- Formalizar los siguientes razonamientos

- Si el resultado obtenido es superior al previsto en 5 unidades,
será debido a no haber realizado el proceso a la temperatura
adecuada o la existencia de errores en los cálculos finales

- El análisis realizado, innecesario si nos dejamos llevar por la

precipitación, se torna necesario si nos paramos a reflexionar
sobre el mensaje que se pretende transmitir

Soluciones Ejercicios 1

Solución Ejercicios 2

Semántica de la Lógica Proposicional
- Una interpretación de una fórmula F en lógica

proposicional es una asignación de valores {V, F} a cada
una de las letras proposicionales de F. El valor de una
proposición “p” bajo una interpretación I se denota como
VI(p)

- A partir de las interpretaciones, combinada con los conectivos

lógicos, se formulan valores de verdad para fórmulas de
diferente complejidad

Semántica de la Lógica Proposicional
- Sea la fórmula F y una interpretación I, el valor F bajo I es:

Semántica de la Lógica Proposicional

Ejemplos
- Determine el valor de las siguientes fórmulas bajo las

interpretaciones siguientes
- VI(p) = V, VI(q)= V, VI(r)=F

- ((p q)  r) «
q
(p  q) «
- (p  q) «
q
- ( p q)  p q  (r  p q)

p q

p
p


Comentarios
- Una interpretación I es un MODELO para una fórmula F

si VI(F) = V

- Existe una clasificación de las fórmulas proposicionales

- Válida o tautología: todas las interpretaciones son un modelo
Válida o tautología: todas las interpretaciones son un modelo
(para toda interpretación I, tal que VI(F) = V), denotado por |= F
(para toda interpretación I, tal que V (F) = V), denotado por

- Satisfactible: alguna interpretación es un modelo (existe una

interpretación I, tal que VI(F) = V)

- Insatisfacible: ó contradicción ninguna interpretación es un

modelo (no existe una interpretación I, tal que VI(F) = V)

Tautologías
- Listado de algunas tautologías conocidas

Modelos
- Notación: Vi |= F (Vi es un modelo de F)

- Por ejemplo, considere F = (p q)

r)
- v1(p) = v1(r) = V, v1(q) = F, entonces v1 |= (p q)
(p q)
- v2(r) = V, v2(p) = v2(q) = F, entonces v2 |„
(p q)
v2(r) = V, v2(p) = v2(q) = F, entonces v2 |„

( q

( q
( q
( q

r)
r)
r)

Modelos
- Sea S = {S1, …, Sn} un conjunto de fórmulas
- Modelo de un conjunto de fórmulas

- P.E. Sea S = {p q, q

r, q  r}, citar algún modelo para

S

Equivalencia Lógica

Equivalencia Lógica
- Se dice que A y B son equivalentes lógicamente
B), si para toda

(denotado como A ” B ó A
interpretación I, se cumple que VI(A) = VI(B)

- Existen algunas equivalencias ya conocidas dentro de la

lógica proposicional
lógica proposicional

Equivalencias lógicas

Consecuencia Lógica
- Sea C un conjunto de fórmulas {P1, …, Pn} y sea Q una

fórmula. Se dice que Q es consecuencia lógica del
conjunto C de premisas (se denota C ⇒ Q) si toda
interpretación que es un modelo de C es también un
modelo de Q
- V (P ) = V (P ) = … = V (P ) = V, entonces V (Q) = V
- VI(P1) = VI(P2) = … = VI(Pn) = V, entonces VI(Q) = V
- Q es consecuencia lógica de unas premisas es equivalente a

pensar que Q toma valor V en cualquier mundo en el que las
premisas tomen valor V

- {P1, …, Pn} ⇒ Q se denomina razonamiento, donde {P1,

…, Pn} se denominan premisas y Q la conclusión