LogicaProposicional

Lógica Formal
Roberto Moriyón

Introducción
• El objetivo de la Lógica Formal o Lógica
Matemática es proporcionar un sistema formal
único en el que la producción de palabras a
partir de axiomas dé lugar a deducciones válidas
en contextos arbitrarios.
• Hay varios sistemas lógicos formales que son
capaces de formalizar cualquier razonamiento
válido.
• Un sistema lógico formal se puede ver comoun
sistema formal deductivo universal, en el mismo
sentido que las máquinas de Turing universales.

Esbozo histórico
• En el siglo IV aC, Aristóteles clasificó los
distintos tipos de razonamiento.
• En el siglo XVII, Arnold y Locke destacaron la
importancia de estudiar las ideas asociadas a
cada afirmación lógica (su interpretación).
• También en el siglo XVII, Descartes y Leibnitz
destacaron losaspectos algebraicos de la
manipulación formal de las fórmulas lógicas.

Esbozo histórico, II
• En el siglo XIX, Frege introdujo la utilización de
variables y cuantificadores para representar
fórmulas lógicas; Peano dio la primera
axiomatización de la aritmética, y Peirce
introdujo la lógica de segundo orden.
• A comienzos del siglo XX, Hilbert propuso un
programa para demostrar la consistencia delas
Matemáticas en base a una axiomatización de
ellas. Posteriormente, Gödel demostró que esto
era imposible.

Esbozo histórico, III
• A lo largo del siglo XX se han desarrollado
particularmente lógicas especiales (modal,
temporal, etc) y lógicas relacionadas con
la teoría de la computación (Cálculo  con
tipos, lenguajes de programación lógicos,
etc)

Lógica proposicional
• Sistema formaldeductivo que genera fórmulas
proposicionales basadas en afirmaciones
atómicas que pueden ser verdaderas o falsas.
• Alfabeto:
– Atomos: P, Q, R, P’, Q’, R’, P’’, …
– Operaciones lógicas: ^, v, , ~
– Separadores: (, ) [A veces es útil utilizar separadores
especiales y obligatorios, < y >, para desambiguar la
gramática]

• Ejemplos de fórmulas proposicionales: P v ~P,
~Q  (Q  P)

Operadoreslógicos
X

Y

X^Y

XvY

X Y

T

T

T

T

T

T

F

F

T

F

F

T

F

T

T

F

F

F

F

T

Operadores lógicos:
Significado de XY
• En principio, el significado de XY es “si X
es cierto, entonces Y también es cierto”.
• Por lo tanto su tabla de verdad será como
sigue:
X

Y

XY

T
T
F
F

T
F
T
F

T
T
?
?

Operadores lógicos:
Significado de XY, II
• Ejemplos con cuantificador universal:
– Para todos losnúmeros x, si x es impar, entonces
x+1 es par
x,(impar(x)  par(x+1))
– Para todos los números x, si x es impar, entonces
x+x es par
x,(impar(x)  par(x+x))
– Para todos los números x, si x es impar, entonces
x+1 es impar
x,(impar(x)  impar(x+x))

Operadores lógicos:
Significado de XY, III
p(x+1) p(x+x) i(x+x) i(x)p(x+1) i(x)p(x+x)

i(x)i(x+x)

X

i(x)

0

F

F

T

F

?

?

?

1

T

TT

F

T

T

F

2

F

F

T

F

?

?

?

3

T

T

T

F

T

T

F

4

F

F

T

F

?

?

?

5

T

T

T

F

T

T

F

Operadores lógicos:
Significado de XY, IV
• Para que los ejemplos anteriores tengan
contestaciones razonables hay que
interpretar que la implicación XY es
cierta si “Si X es cierto, entonces Y
también. Si X no es cierto, da lo mismo
que se verifique Y o no”.
• (X ^ Y) v ~X
• Estadefinición es consistente en general
con la definición de implicaciones en la
Lógica de Predicados.

Lógica proposicional:
Interpretaciones
• Una interpretación I de una fórmula F es una
asignación de un valor lógico PI (True o False) a
cada átomo P de F. La interpretación asigna un
valor lógico a la fórmula utilizando las tablas de
los distintos operadores.
• Una fórmula es cierta en unainterpretación si
le corresponde el valor True mediante ella.
• La tabla asociada a una fórmula tiene una
interpretación en cada fila.

Interpretaciones
en el mundo real
• Normalmente las fórmulas lógicas se
interpretan a un primer nivel haciendo
corresponder a cada símbolo proposicional una afirmación (por ejemplo, llueve o
los eliomartos rusitan). La interpretación
se completa mediante una imagen del...