Álgebras para la lógica implicativa con conjunción

Vol. XVIII, No 2, Diciembre (2010)
Matem´
aticas: 31–50

Matem´
aticas:
Ense˜
nanza Universitaria
c Escuela Regional de Matem´
aticas
Universidad del Valle - Colombia

´
Algebras
para la l´
ogica implicativa con conjunci´
on
Mauricio Castillo

Arnold Oostra

Universidad del Tolima

Universidad del Tolima

Recibido Oct. 08, 2009

Aceptado Sep. 10, 2010

Abstract
Weexplain different presentations of the algebraic structures that match the {→, ∧}-fragment
of intuitionistic propositional logic.
Keywords: Propositional logic, deductive system, algebraic semantics, Hilbert algebra, semilattice.
MSC(2000): 03B20, 03G25, 06A12
Resumen
Se elaboran diferentes presentaciones de las estructuras algebraicas que corresponden al segmento {→, ∧} del c´
alculoproposicional intuicionista.

Palabras y frases claves: L´
ogica proposicional, sistema deductivo, sem´
antica algebraica,
a
´lgebra de Hilbert, semirret´ıculo.

1

Introducci´
on

La idea de emplear m´etodos algebraicos para los razonamientos l´
ogicos se remonta, por lo menos, a Leibniz pero se cristaliz´
o por primera vez en el siglo XIX
con los trabajos de Boole. Con el tiempo lapropuesta de este u
´ltimo dio lugar
a las estructuras conocidas hoy como ´
algebras booleanas, cuyo ejemplo t´ıpico es
el ret´ıculo de subconjuntos de un conjunto. En la pr´
actica matem´
atica salta a la
vista cierta correspondencia entre el comportamiento de los subconjuntos, o en
general de los elementos de las ´
algebras booleanas, y las leyes l´
ogicas.
En realidad, estacorrespondencia sugerida se puede precisar y constituye la
piedra angular de la l´
ogica proposicional, una de las teor´ıas matem´
aticas que
m´
as presentaciones distintas posee. Por un lado, llamado a veces sintaxis, la l´
ogica proposicional es un sistema formal que permite realizar deducciones a partir de
premisas. Una posible presentaci´on de este aspecto de la l´
ogica, asociada al nombre deHilbert, se logra mediante ciertos axiomas y una regla de inferencia (v´ease
por ejemplo [6]); otra est´
a dada por las reglas de deducci´
on natural propuestas
por Gentzen; hay m´
as presentaciones. Por otro lado est´
a la llamada sem´
antica, en
la cual la l´
ogica proposicional toma el aspecto de un c´
alculo que tambi´en puede
hacerse de manera algebraica. La presentaci´
on sem´
anticam´
as sencilla consiste en
las llamadas tablas de verdad, que en principio permiten decidir si determinada
f´
ormula es “siempre verdadera”; otra sem´
antica, del todo algebraica, consiste en
leer las f´
ormulas en ´
algebras booleanas y considerar cu´
ando la lectura coincide
con el elemento m´
aximo del ´
algebra. En realidad, esto generaliza las tablas de

32

M. Castillo y A.Oostra

verdad pues ellas constituyen la lectura de la l´
ogica proposicional en el ´
algebra
booleana con dos elementos.
El teorema fundamental de la l´
ogica proposicional establece que las diferentes presentaciones, sint´
acticas y sem´
anticas, son equivalentes. En particular, las
tautolog´ıas calculadas por tablas de verdad corresponden con exactitud a las
f´
ormulas que sepueden deducir de manera formal sin premisas. La utilidad de
esta equivalencia es grand´ısima. Por ejemplo, la sem´
antica provee un criterio sencillo para determinar si determinada f´
ormula no se puede deducir, y en particular
permite probar con facilidad la consistencia del sistema deductivo. Por otra parte,
aunque en principio el c´
alculo de una tabla de verdad parece el camino m´
assencillo, este deja de serlo cuando el n´
umero n de las letras proposicionales aumenta
pues la tabla tendr´
a 2n renglones. En tal caso es preferible buscar alg´
un camino
deductivo.
A lo largo del siglo XX la l´
ogica matem´
atica fue estudiando sistemas deductivos alternativos, en algunos de los cuales ya no son v´
alidos todos los principios
adoptados desde la antig¨
uedad: la ley del...