Álgebra de Boole: Fundamentos e Aplicações

Vista previa del material en texto

G.
 C
as
an
ov
a
EL ALGEBRA 
DE BOOLE
Dirigidá por Javier de Lorenzo
SERIE DE MATEMATICA
GODEUENT, Rogcr: Algebra.
JEREZ JUAN, Miguel: Tablas de /Unciones primitivas. Formulario de 
cálculo integral.
LORENZO, J. de: Iniciación a la teoría intuitiva de conjuntos 
M alliavin, Paul: Geometría diferencial intrínseca.
SÁNCHEZ CORDOVÉS, J.: Matemáticas aplicadas a radio y televisión 
(2.a edición aumentada).
STEWART, Frank M.: Introducción al Algebra lineal 
WARUSFEL, A.: Diccionario razonado de matemáticas.
WILLIAMSON, J. H.: Integración l.ebesgue.
EL ALGEBRA DE BOOLE
EL ALGEBRA 
DE BOOLE
EDITORIAL TECNOS
Los derechos para la versión castellana 
de la obra L'Algébre de Boole (3.a ed.), 
publicada por Presses Universitaires de Franee. París, 
en la colección «Que sais-je?»
© Presses Universitaires de 'France, 1967, 
son propiedad de Editorial Tecnos, S. A.
Traducción por 
DIONISIO GARCIA CONDE
© EDITORIAL TECNOS, S. A., 1975 
O'Donnell, 27. Madrid-9 
ISBN. 84-30905804 
Depósito legal: M 18.027-1975
INDICE
EL ALGEBRA DE BOOLE
Capítulo VII: Retículoi..........................................................
I. Definición, 55. - 2. Ejemplos, 55. - 3. Propiedades gene- 
oles de los retículos, 57. - 4. Semirretículos. Subretículos, 
58. - 5. Retículos distributivos, 60. - 6. Retículos complemen­
tarios, 60. - 7. Retículo de Boole, 6 1 .-8 . Otros retículos, 62. -
9. Aplicaciones, 63.
Capítulo VIH: Funciones de B o o l e ........................................
1. Términos minimales, 64. - 2. Forma canónica disyuntiva, 
65. - 3. Ejemplos de descomposición, 67. - 4. Términos max ima­
les, 68. - 5. Forma canónica conjuntiva, 69. -■ 6. Términos maxi- 
males y Términos minimales, 71.-7. Funciones características, 72.
Capítulo IX: Algebra binaria....................... — .......................
1. Variables de Boole, 74. - 2. Funciones de variables de Boole, 
74. - 3. Propiedades de las funciones lógicas elementales, 75. -
4. Suma disyuntiva, 76. - 5. Propiedades de la suma disyuntiva, 
77. - 6. Operación de Sheffer, 78. - 7. Formas canónicas, 79. -
8. Ejemplo de función lógica, 80. - 9. Aplicación a la lógica, 80. -
10. Aplicaciones a la teoría de grafos, 82.
Capítulo X: Algebra de los circuitos..........................................
1. Generalidades, 88. - 2. Esquemas lógicos, 89. - 3. Relé 
electromagnético, 89. - 4. Contactos en serie, 90. - 5. Contactos 
en paralelo, 91. - 6. Circuito de estructura dada, 92. - 7. Función 
de estructura de un circuito dado, 94. - 8. Circuito dual, 95. -
9. Dilema, 96. - 10. Diodos y transistores, 97.
Capítulo XI: Numeración binaria ....................... -.........
1. Numeración en la base B, 99. - 2. Cambio de base, 101. - 
3. Sistema octal, 103. - 4. Suma de dos números en el sistema 
binario, 105.
Capítulo XII: Calculadoras binarias...........................................
1. Sumadora, 108. - 2. Resta, 111.-3. Complemento de un 
número binario, 111.-4. Sumas algebraicas. Números negativos, 
113. - 5. Multiplicación. División, 114. - 6. Coma, 115. - 7. Sis­
tema decimaL Código binario, 116. - 8. Organización de una cal­
culadora, 116. - 9. Usos, 118.
INTRODUCCION
El fin esencial del matemático inglés George Boole (181S- 
1864) fundando el álgebra que lleva su nombre era el de someter 
el tazonamiento lógico a reglas convenientes de cálculo. En efec­
to, esta álgebra se ha revelado independiente de la naturaleza 
de las proposiciones con que trabaja aunque no aparece más 
que como un caso particular del álgebra de las partes de un 
conjunto, cuando se utilizan las operaciones unión, intersección 
y complementación.
El empleo de la función característica de un subconjunto 
introduce en el álgebra de G. Boole dos valores - 0 ó 1, verda­
dero o falso, abierto o cerrado - y se obtiene asi un método 
de estudio de las cadenas de contacto de circuitos eléctricos 
cuyas estructuras son la base de la construcción de las calcula­
doras automáticas y de los ordenadores.
Este importante desarrollo moderno del cálculo electrónico 
es una consecuencia imprevista de las posibilidades de un lengua­
je binario; explica y justifica el interés con que hoy se enseñan 
los elementos de la teoría de conjuntos. Este estudio no necesita 
ningún conocimiento matemático previo y puede así ser com­
prendido por todos los que deseen informarse de los métodos 
modernos de tratamiento de los más diversos problemas de la 
ciencia pura y aplicada, por máquinas cuya utilización, cada vez 
más corriente, modifica sin cesar el campo de las actividades 
económicas y sociales de la humanidad.
Capítulo I
CONJUNTOS
1. Generalidades. - La consideración simultánea de varios objetos 
cualquiera que sea su naturaleza constituye un conjunto. Cada uno de es­
tos objetos se denomina elemento del conjunto.
a) Un conjunto se designa generalmente por una letra mayúscula, 
por ejemplo E. Así, se escribirá:
E = {«, b, c. d)
para indicar que el conjunto E está formado por las letras a, b, c, d. 
Habremos definido un conjunto E cuando dado un objeto cualquiera a, 
se pueda decir si es o no un elemento de E, es decir si pertenece o no 
a E.
Si a pertenece a E, se escribirá a € E.
Si a no pertenece a E, se escribirá a $ E.
b) El conjunto de los enteros positivos escritos en el orden creciente:
1 2 3 ... n
se denomina de los números naturales y se designa por N .
Se designa por N el conjunto de los enteros positivos o nulos, es decir 
el conjunto anterior añadiéndole el número 0 (cero).
Se designa por Z el conjunto de los enteros negativos, positivos o
. . . - « ' . . . - 3 - 2 - 1 0 1 2 3 ...« ...
c) Definiremos más adelante relaciones entre los elementos de un 
conjunto; estas relaciones serán independientes de la naturaleza de los 
elementos y los razonamientos sobre ellas serán pues válidos para con­
juntos abstractos. Sin embargo, será a menudo cómodo seguir estos razo­
namientos sobre esquemas; los más utilizados son los conjuntos de pun­
tos de un plano interiores a círculos y son denominados diagrama de 
Euler-Venn.
12 EL ALGEBRA DE BOOLE
Estos esquemas deben ser considerados como una ayuda, a veces muy 
importante, pero nunca como un procedimiento de demostración.
2. Igualdad de dos conjuntos. - Dos conjuntos E y F son 
iguales si, y sólo si, todo elemento de uno es elemento del otro. 
Si E y F'son iguales se escribirá E = F.
Así, si E ={a, b , c ,d ) y F ={6, c, d, a} será E = F.
El orden en el que se escriban los elementos carece de impor­
tancia para que dos conjuntos sean iguales.
Si E y F no son iguales, se escribirá E # F.
3. Conjunto de un elemento y conjunto vacío. — La idea de 
conjunto hace intervenir varios elementos, pero es cómodo para 
dar mayor generalidad a ciertos resultados utilizar el conjunto 
formado por un solo elemento o el con/unto vacio que no posee 
ninguno.
a) El conjunto {a} cuyo único elemento es a no coincide 
sin embargo con su elemento a pues una tal identificación con­
duciría en algunos casos a una contradicción. En efecto, un 
conjunto con varios elementos puede ser él mismo elemento de 
otro conjunto. Sea, por ejemplo, E = {a, b], conjunto de dos 
elementos, y sea {E} el conjunto cuyo único elemento es E. 
Si fuese {E} = E, el conjunto {E} de un elemento sería igual 
al conjunto E de dos elementos, lo que es absurdo. Se escribirá
l a } * a ( 1)
b) Se llama conjunto vacío un conjunto que no tiene ningún 
elemento; se admite que no hay más que un conjunto vacío que 
se denota #.
Un conjunto cuyo único elemento es el conjunto vacío no 
es vacío ya que contiene un elemento. Es pues necesario escri­
bir:
14>}*<I>;
esta desigualdad no es más que un caso particular de la des­
igualdad ( 1), que así está justificada de nuevo.
CONJUNTOS 13
4. Inclusión. Subconjuntos. — a) Cuando todos los elementos 
de un conjunto E pertenecen a un conjunto F, se dice que E 
está incluido en F y se escribe E C F, el signo C indica la 
inclusión.
La figura 1 representa unconjunto E incluido en un con-
b) He aquí tres propiedades de la inclusión:
Si G es un conjunto, E C F y F C G implican E C G pues 
todo elemento de E pertenece a F y por tanto a G; por otra 
parte, es evidente E C E; finalmente, E C F y F C E implican 
E = F y, recíprocamente, si E = F, E está incluido en F y F 
está incluido en E.
c) Se dice que E es un subconjunto de F o una parte de F 
si, y sólo si, E está incluido en F.
Se admite que el conjunto vacío es subconjunto de cualquier 
conjunto, es decir que $ C E cualquiera que sea E.
El conjunto de partes de un conjunto E será designado por 
Sp (E). Cuando E tiene un número finito de elementos, jp (E) 
permite definir las funciones de Boole.
5. Conjunto de las partes de un conjunto finito. — a) For­
memos el conjunto tp(E) para conjuntos E que tengan sucesiva­
mente 1, 2, ...,n elementos.
Si E = {a} 9p(E) tiene y {a} como elementos.
Si E = {a, ¿} ip(E) tiene <p, {a}, {ó}, {a, ó} como elementos.
Si E tiene n elementos, 
mentos:
9p(E) tiene por ele-
14 EL ALGEBRA DE BOOLE
el conjunto vacío: 0 ,
los subconjuntos de E de un elemento: (ai), (a2j {a„ } ,
los subconjuntos de E de dos elementos: {ai, a2), (a i, ).
I los subconjuntos de E de p elementos: {a, ,a2, ...,a„}, ... , 
{‘n -p . i «ni sip€N
\e l propio conjunto E = {ai. a2. ...,an}. 
b) Vamos a probar que si E tiene n elementos, $)(E) tiene 
2" elementos. En efecto, si E tiene un elemento, $ (E) tiene 
2 = 2' elementos. Si E tiene n elementos, designamos por C{¡ 
el número de conjuntos diferentes de p elementos que se pueden 
formar con los n elementos de E. Resulta que (E), después 
del estudio precedente, tiene tantos elementos como
1 + Cj + - + Cg + -■ + CJ¡.
Ya es conocido, por la fórmula del binomio, que esta suma 
vale 2n, lo que demuestra la proposición, pero vamos a dar de 
este resultado una demostración por inducción. Admitamos para 
ello que 3P(E) tiene 2" ~ 1 elementos si E tiene n - 1 elementos. 
Supongamos ahora que E tiene n elementos denotados 
a i , a2, ...,a „ _ |, a. Un elemento de 9p(E) o bien contiene a, 
o bien no contiene a. Elementos que no contienen a hay, por 
hipótesis, 2"- 1 . Veamos cuántos elementos de ^3(E) contie­
nen a. Los conjuntos de p elementos que siendo elementos de 
?P(E) contienen a, contienen otros p - 1 elementos elegidos, 
de todas las formas posibles, entre a, , a2, ...,a„_ i ; su número 
es pues C j l ¡ .
Como p varía de 1 a n el número de elementos de Sp(E) que 
contienen a es:
1 +CA_, + ...,Cg + ... + C 3 l¡,
Por tanto, el número de elementos de 9P(E) es pues'
CONJUNTOS 15
Ahora bien, por hipótesis:
2n_l = 1 +CA_, + ... + c 3i ¡ .
Así pues $ (E ) tiene 2"_ 1 + 2n_l = 2 , 2" -1 = 2 " ele­
mentos.
Como este resultado es verdadero para n ='1 y para n si lo 
es para n — 1, está demostrado por inducción.
6. Complementario de un conjunto. — a) Si un conjunto E 
está incluido en un conjunto F, los elementos de F que no per­
tenecen a E forman un conjunto llamado complementario de E 
con respecto a F. Se dice que el conjunto F es el conjunto de 
referencia y en general, está definido para siempre en un pro­
blema dado. Se representa este complementario de E en F:
C f E ó F — E, o simplemente E 
cuando F ha sido fijado. Será esta última notación la que en 
general utilizaremos.
La parte rayada de la figura 2 representa el complementario 
de E respecto al conjunto de referencia F que lo expresamos 
por un rectángulo.
Figura 2
b) Este complementario de E en F admite ¿1 mismo, como 
subconjunto que es de F, un complementario en F que es evi­
dentemente E.
Escribiremos E = E.
Finalmente, el complementario del conjunto vacío 0 en F 
es el mismo F, mientras que el complementario de F en F es 
el conjunto vacío.
16 EL ALGEBRA DE BOOLE
7. Conjuntos infinitos. — Los conjuntos N y Z tienen un nú­
mero de elementos superior a cualquier entero positivo dado; se 
dice que son conjuntos infinitos.
Los conjuntos de puntos de un segmento, de una recta o de 
un plano, son también conjuntos infinitos. Naturalmente el pro­
blema está en decidir si todos estos conjuntos infinitos tienen 
el “mismo número” de elementos, claro que en un sentido que 
se debe precisar ya que la noción ordinaria de número cardinal, 
sólo permite contar los elementos de conjuntos finitos. En efec­
to, es necesario distinguir entre varios casos posibles y hay así 
varios “números infinitos” , pero no analizaremos esta cuestión 
puesto que sólo utilizaremos conjuntos finitos en las aplicaciones 
de la teoría de conjuntos al álgebra de Boole1.
Capítulo II
OPERACIONES ENTRE CONJUNTOS
La unión, intersección y complementación son las operacio­
nes más usuales entre conjuntos. Estas operaciones elementales 
nos sirven para la definición de las funciones de Boole cuya 
realización concreta con la ayuda de circuitos eléctricos con­
venientes permite la construcción de calculadoras automáticas 
modernas; pueden también ser aplicadas al estudio de la lógica 
de proposiciones.
1. Unión. - a) Sea I = {1 ,2 , .... «} con n número entero 
positivo cualquiera, y sea {E,}i e | una colección de n conjuntos; 
se Dama unión de los E; al conjunto E formado por todos los 
elementos que pertenecen a un E,- al menos. I se denomina 
conjunto de índices y al conjunto unión, que se lee unión de 
los E/,le denotamos por E = U E,-.
Si I = {1, 2 ) , el conjunto unión de Ei y E j se escri­
be E = Ei U E2 ó E = E jU E i pues el orden es indiferente.
Si I = {1, 2, 31 el conjunto unión de E ,, E2 y E j se 
denota E = E | U Ej U E j, siendo el orden también indiferente 
(Fig- 3).
b) Esta operación es a menudo llamada operación “O” pues 
la unión de dos conjuntos E! y Ej se obtiene formando el con­
junto de los elementos que pertenecen a E , ó a E j , pero es 
necesario señalar que a veces en el lenguaje corriente, la con­
junción O puede tener dos sentidos diferentes que sólo el con­
texto nos permite distinguir. Así, O es disyuntiva o excluyeme
cuando significa uno u otro pero no ambos, y es inclusiva cuan­
do significa uno, otro o ambos a la vez. Sólo nos conviene este 
último sentido cuando O define la unión de dos conjuntos;
18 EL ALGEBRA DE BOOLE
Figura 3
es por ello que la operación unión es llamada a veces operación 
Y I O. De todos modos, en teoría de conjuntos el sentido de 
la operación O no es, en absoluto, ambiguo.
2. Intersección, - a ) Llamamos intersección de los conjuntos 
E,- (/ = 1 ,2 ,..., n) al conjunto E formado por los elementos que 
pertenecen a todos losE¡.
Se denota esta intersección: E = fl E,- con 1= {1,2 ,...,n}y
se lee: intersección de los E¡. Si I = {1,2}, se escribe E = Ei n E2 
ó E = Ej n E | ya que el orden es indiferente (fig. 4). To­
do elemento de E pertenece simultáneamente a E | y a Ej y
Figura 4
todo elemento que pertenece a la vez a E , y a E2 pertenece 
a su intersección E.
OPERACIONES ENTRE CONJUNTOS 19
Si I = { 1, 2, 3} se escribe el conjunto intersección 
E = E | n Ej O E j, siendo indiferente el orden.
b) Esta operación es a menudo llamada operación Y, ape­
lativo que carece de ambigüedad.
Si dos conjuntos E | y Ej no tienen ningún elemento común, 
su intersección es el conjunto vacío y se escribe: E | O Ej = 0. 
Se dice en este caso, y únicamente en él, que los dos conjuntos 
son disjuntos.
Son evidentes las propiedades de la unión e intersección 
siguientes:
E, O E jC E |C E, U E j; E, n E jC Ea C E, U E , (2)
c) Veamos dos sencillos ejemplos de unión e intersección.
Si Ei es el conjunto de los triángulos isósceles de un plano, 
Ej el conjunto de los triángulos rectángulos de este plano, 
Ei U Ej es el conjunto de los triángulos del plano que son ya 
rectángulos, ya isósceles, o ambas cosas simultáneamente, mien­
tras que Ei n Ej es el conjunto de los triángulos del plano que 
son a la vez rectángulos o isósceles.
3. Complementación. - a) La operación de complementa- 
ción consiste en sustituir un conjunto A, contenido en otro E, 
por su complementario A en E: Es puesuna operación de paso 
a los complementarios.
Figura 5
El conjunto E es representado en la figura S por un rectán­
gulo. Son dos relaciones importantes:
A U A = E; A flA =<p (3)
b) He aquí tres sencillas propiedades:
1.° S = A (4)
como ya se ha dicho.
20 EL ALGEBRA DE BOOLE
2.° Dos conjuntos iguales tienen el mismo complementario 
(respecto a E).
A = B implica A = B y recíprocamente (S)
3.° Si A está contenido en B, B está contenido en A, escri-
A C B implica B C A (6)
Sea, en efecto, b un elemento cualquiera de B, por perte­
necer a B no pertenece a B. Como todo elemento de A lo es 
de B, b í A; por tanto pertenece a A, y está probado (6).
4. Fórmulas de De Morgan. — Permiten pasar de una unión 
a una intersección y viceversa.
a) El complementario de una unión es la intersección de los 
complementarios. Es preciso probar, para subconjuntos cuales­
quiera E/ de E:
T T e7= n i í (7)
<el ie l
Escribamos(7) en la forma F = G.
Si x £ F, no pertenece a ningún E,, pues de lo contrario 
pertenecería a su unión, y por ello a F; por consiguiente x 
pertenece al complementario de cualquier E/ y por ende a su 
intersección.
Recíprocamente, si x e G, pertenece a cualquier E,-; en 
consecuencia, no puede pertenecer a la unión y pertenece a F. 
(7) es verdadera.
Para dos conjuntos, (7) se escribe en la forma de uso co-
E, U E , = E , n Ej (8)
b) Por paso a los complementarios, obtenemos de (7) una 
nueva relación, siempre en E que incluye a todos los Ef, que es:
OPERACIONES ENTRE CONJUNTOS 21
y haciendo E¡ = F¡, se tiene:
U F¡ = "7 T f7 (9)
ie l /e l
ya que E/ = F¡, su enunciado es:
El complementario de una intersección es la unión de los 
complementarios.
Con dos conjuntos, obtenemos la relación (10) de uso muy 
corriente:
E, O E j = E , U E , (10)
Las fórmulas (7) y (9) son conocidas con el nombre de fór­
mulas de De Morgan, matemático y lógico inglés (1806-1871).
S. Propiedades de las operaciones. — Las operaciones prece­
dentes tienen numerosas propiedades tales como idempotencia, 
conmutatividad, asociatividad, distributividad.
Nosotros las estudiaremos después de haber dado sus defini­
ciones generales en los capítulos que siguen, de tal suerte que, 
en cierto modo, utilizaremos un vocabulario muy importante 
y que no es absolutamente necesario para una exposición del 
álgebra de Boole, pero este método de exposición presenta la 
ventaja de integrar esta álgebra en la corriente general del pen­
samiento matemático moderno.
Capítulo III
APLICACIONES 
FUNCIONES DE BOOLE. GRAFOS
La noción de aplicación cubre amplios dominios de la refle­
xión matemática; es susceptible de una definición que podemos 
calificar de “geométrica”, dando a esta palabra un sentido muy 
amplio.
1. Aplicación. — a) Esta definición necesita de la presencia 
de dos conjuntos E y F, llamados respectivamente con/unto de 
partida y conjunto de llegada y que no tienen necesariamente 
elementos de la misma naturaleza.
Una aplicación f nos hace corresponder a cualquier elemento 
a de E un elemento y un solo b de F.
Veamos varias notaciones utilizadas para f:
l.o a - í - > b es decir: a a le corresponde b por / ;
2 .° b = / (a) que se escribe también a -°—* f ia ) , es decir: 
a a le corresponde /( a ) por la aplicación f \
3.° E -^ —> F, es decir: a E le corresponde F p o r /.
b) Se dice que f e s una aplicación de E en F, o también que / 
está definida en E y toma valores en F, y b se llama imagen de a 
por f El conjunto de las imágenes por f de los elementos de E, 
se designa por / ( E).
c) Si E = F y si además a = /( a ) para todo a de E, se dice 
que / es la aplicación idéntica. Se la representa por i o por fg 1
APLICACIONES. FUNCIONES DE BOOLE. GRAFOS 23
aplica E sobre E. Si E y F son ambos vacíos, se dice que existe 
una aplicación vacia de E en F.
d ) En general si / es una aplicación de E en F, / ( E) no 
coincide con F.
Cuando F = /(E ) la aplicación / se llama suprayectiva o sobre; 
todo elemento de F es imagen de al menos un elemento de E 
(% 6).
sobre F (y no en como hasta ahora hemos dicho).
Si F =£ / (E), la aplicación / de E en F no es suprayectiva 
pero / es siempre una aplicación sobre de E en /(E ), por defi­
nición de f(E ).
2. Ecuación, - a) Si i es un elemento de / ( E), en general 
no es imagen de un único elemento de E. Sea x un elemento 
cualquiera de E cuya imagen por / es b; se verifica la igualdad: 
/(* ) = *> (11)
Una igualdad como la expresada en (11) donde f es una 
aplicación dada, b un elemento cualquiera del conjunto de lle­
gada F y x un elemento desconocido del conjunto de partida, 
es una ecuación.
Cualquier x que perteneciendo a E verifique (11), es una 
solución de la ecuación. Resolver la ecuación, es encontrar el 
conjunto de sus soluciones.
24 EL ALGEBRA DE BOOLE
A menudo este conjunto de soluciones se denota f~ '(b ) y 
se llama imagen reciproca de b por f. En este caso,/ - 1 debe 
ser considerado como una simple notación, cómoda aunque un 
poco abusiva, pero no como una aplicación ya que, en general, 
la ecuación (11) tiene más de una solución. Si ó £ / ( E) la 
ecuación ( l l ) no tiene soluciones; en este caso se llama im­
posible. Es de señalar que la incógnita x no es necesariamente
que puede ser un número, pero también un vector, una matriz, 
una aplicación, etc.
3. Inyección. Biyección. — Es particularmente importante el 
caso en que la ecuación f ( x ) = b tenga a lo sumo una solución.
a) Se dice que una aplicación / de E en F es inyectiva si 
dos elementos cualesquiera diferentes de E tienen siempre imá­
genes distintas en F (fig. 7).
Se escribe: f(a )¥ = f (a') si a ¥= a', para cualquier a y a ' dife­
rentes de E; o también, pues es equivalente:
/ ( a ) = /(a ’) si, y sólo si a = a '.
b) Una aplicación / de E en F es biyectiva si es simultánea­
mente inyectiva y sobre.
Si / es biyectiva, a cualquier a E E le corresponde un b y 
uno solo por ser / aplicación; cualquier b E F es imagen de 
al menos un elemento de E y a que / es sobre y es imagen de un 
único elemento a de E ya que f es inyectiva.
APLICACIONES. FUNCIONES DE BOOLE. GRAFOS 25
Si / es biyectiva existe pues otra aplicación/ - 1 de F en E, 
también biyectiva, y definida por la igualdad f~ '(b ) = a , que 
equivale a b =/(<r).
Esta aplicación / “ 1 se llama, cuando existe, aplicación re­
ciproca1. Es de señalar que cuando/es inyectiva, la aplicación/ 
de E sobre / (E) es una biyección; por tanto existe la aplicación 
recíproca / - l de / ( E) en E. Así si N es el conjunto de los 
enteros no negativos y N' el de los enteros pares o nulos, la 
aplicación definida por / ( n ) = 2n para todo n E N e s una in­
yección de N en N y una biyección de N sobre N’; la aplicación 
recíproca estará definida por f ~ ‘(2n) = n y aplica N‘ sobre N.
4. Compuesta de dos o más aplicaciones. - Dos aplicaciones 
/ i y / 3 son iguales y se escribe f x = / 2 si tienen el mismo con­
junto de partida E, de llegada F y cada elemento de E tiene la 
misma imagen por ambas.
a) Si f aplica E en F y si g aplica F en G, existe una apli­
cación de E en G denotada g » f y que se denomina compuesta 
de f y de g (o también producto de / por g).
Es de señalar que el orden en que / y g aparecen escritas 
en g ° / es en realidad el inverso a como actúan: prim ero /y 
después g.
Esta definición se géneraliza a un número finito de aplica­
ciones / i , / j , —,fn escribiéndose su compuesta.
/ „ % - . < > - • / i « /.•
Se verifica fácilmente siendo h aplicación de G en H que:
( h ° g ) ° f = h ° ( g o f ) ( 12)
y se dice que la ley de composición es asociativa; los paréntesis 
indican que, por ejemplo en el segundo miembro, se compone 
primero / con g y después el producto con h mientras que el 
primer miembro nos dice que componemos / con el producto 
de g por h. La figura 8 ilustra la asociatividad.
26 EL ALGEBRA DE BOOLE
b) Si g o / está definida, en general f ° g no tiene por qué 
estarlo,pero, si E = F = G, tan to /com o; son aplicaciones de E 
en F y / ° ; está definida: es una aplicación de E en E.
Figura 8
Si /» g = g o /■ lo que aun existiendo ambas no tiene por qué 
verificarse se dice que las dos aplicaciones son permutables (o 
conmutan).
Finalmente, s iE = F y s i ; = / , se escribe / ’ para designar 
el producto/ ° / y de un modo más general/" para/« /» ... ° / 
donde la aplicación / figura n veces (n € N* ).
c) Es inmediato comprobar que ; ° / es biyectiva si / , que 
es aplicación de E en F, y ; que aplica F en G, son biyectivas. 
Así, la compuesta de dos biyecciones es otra biyección y este 
resultado se extiende a un número cualquiera de biyecciones.
Finalmente, decimos que una biyección de E en E se llama 
sustitución y que una sustitución igual a su inversa ( / = / " 1 ó 
/ “ / = 'E) se llama involución. Si por ejemplo E = {1,2,..., n} 
o conjunto de los n primeros números enteros, y si ponemos 
n = / ( l ) , n — 1 = / ( 2), n - p + 1 = f(p ), ..., 1 = /(« ) , con p 
entero menor que n , / e s una sustitución; además, / ° / = íg 
pues / o f ( p ) = f (n - p + l) = /> y / es una involución.
Todo este vocabulario puede resultar embarazoso pero rápi­
damente nos apercibiremos de que su uso es por el contrario 
indispensable para clarificar las nociones matemáticas más di­
versas. Nos limitaremos aquí a dar algunos ejemplos que tengan 
relación con nuestro objetivo.
APLICACIONES. FUNCIONES DE BOOLE. GRAFOS 27
5. Ejemplos de aplicaciones. — a) Si E es el conjunto N * y F 
un conjunto cualquiera, una aplicación de E en F recibe el 
nombre de sucesión de elementos de F, y se escribe
 “n.
definida para todo n €= N*.
b) Designamos por x una aplicación de N ' en F; se escribirá:
x= {u l ,u 1 u¡.....
o más abreviadamente x = (u„) y se llamará a u¡ proyección 
de índice i ó coordenada de índice i de x; así u i será la primera 
proyección de x, u2 la segunda proyección y así sucesivamente. 
Se escribirá u¡ = pr¡ (a:).
Dos sucesiones x = (u,-) y x' = (uj) son iguales si las aplica­
ciones x y x ' son iguales, en cuyo caso u, = u'¡ para todo i£N *, 
y viceversa.
c) En análisis, cuando los conjuntos E y F son por ejemplo 
ambos el conjunto de los números reales, la aplicación f se 
denomina función f y se escribe y = /(x ) , x será un número 
real del conjunto de partida e y un número real del conjunto de 
llegada; se dice que x es la variable y que/es una función real de 
una variable real. Así pues la palabra función sustituye muy a 
menudo a la de aplicación.
6. Función característica de un conjunto. — La noción de 
función característica es esencial en álgebra de Boole. Sea E 
un conjunto cualquiera y F = {0, 1} conjunto con únicamente 
dos elementos.
Toda aplicación de E en F se llama función característica f 
Precisemos la definición de / de la forma siguiente: llamamos A 
al conjunto f ~ ' ( 1), es decir, como ya se ha visto, el conjunto 
délos elementos de E cuya imagen en Fes 1; el conjunto/- '(0) 
es pues A. De aquí resulta:
La función característica deI conjunto A , subconjunto de E, 
que se denota por / a o /(A ;x ) , está definida así:
/ ( A ;x) = / a (x)= 1 para todo x que pertenece a A:
/ ( A;x) = /A (x) = 0 para todo x que pertenece a Á, comple­
mentario de A en E.
28 EL ALGEBRA DE BOOLE
La importancia de las funciones características reside en el 
hecho de que nos hacen de cómodo intermediario entre el álge­
bra de conjuntos y el álgebra de Boole.
7. Producto de conjuntos. Proyectores. — o) Se llama pro­
ducto de n conjuntos E ,,E 2, ..., E„ y se denota E , x E2 X ... x 
x E„ al conjunto de todas las sucesiones (a( , a , ,..., a„) donde 
a, e E „ f l, e E , , . . . ,a „ e E„. SiE, = E2 = ... = E„ =E. el pro­
ducto se denota E".
6) Si n = 1 las sucesiones no tienen más que un elemento 
y el conjunto de las sucesiones se identificará por definición 
con el conjunto de los elementos de forma tal que escribiremos 
E1 = E.
Si n = 2 las sucesiones se llaman pares.
El par (<Zi, a ,) es generalmente diferente del par (a2, a ,) 
ya que, en general, a, # a ¡ , incluso si E | = E2.
Si E, *■ E2, no se debe identificar E, x E2 con E , x E ,.
Si E | = E2 = E, el conjunto de pares (at , a2) es el conjun­
to EJ y llamamos diagonal de E5 al conjunto de los pares(a,a).
Si n = 3, las sucesiones ( a i, a2, a 3) reciben el nombre de
c) Es fácil comprobar que si existen conjuntos F, tales que
E /C Fj para todo i — 1,2, ...,n,
E ,x E ,x ... X E ,C F ,X F ,X ... x F„.
Finalmente, un producto de conjuntos es vacio si, y sólo si, 
uno de los conjuntos deI producto es vacio.
La condición es suficiente, pues si, por ejemplo, Ei = 4>, 
no podremos formar ninguna sucesión (a2, a2, ...,a„) pues a,
Es también necesaria, pues si ningún Ej es vacio se puede 
formar al menos una sucesión (ai, a ],...,a„) y el producto
d) Se llama proyector de E, x Ea sobre E( la aplicación 
de Ei x Ej en Et que a cualquier par (a¡, a2) le hace corres-
APLICACIONES. FUNCIONES DE BOOLE. GRAFOS 29
Análogamente se define el proyector de E, x E2 sobre E2 
que hace corresponder a cualquier par ( a , , a2) de E, X E2 el 
elemento a2 de E2.
Estas definiciones se generalizan sin dificultad a una aplica­
ción de E | X Ej x ... x E„ en E,- que hace corresponder a la 
sucesión (a j, n2,..., a¡ an) su i-ésima proyección a,'.
8. Fundones de Boole1. — Sea E un conjunto finito, es 
dedr que tiene un número finito de elementos, y sea 1P(E) 
el conjunto partes de E que sabemos es no vacío.
Se llama función de Boole de n partes a cualquier aplicación 
de "(£') en %i(E) que se defina con la ayuda de un número 
finito de uniones, intersecciones o de complementaciones.
Sean, por ejemplo, A i, A2 y A3 subconjuntos de E;la terna 
(A i, A2, A2) es un elemento de ^)3 (E) ya que este conjunto 
está formado, como ya se vio, por estas ternas. Supongamos 
que (A,, A2, A3) tiene por imagenenuna aplicación/ de $ 3(E) 
sobre ^J(E) el subconjunto de E: (A, U A2) n A j. La aplica­
ción f es una fundón de'Boole de tres partes y se escribe:
/(A , , A j, Aj) = (Á, U A j)n Aj .
Señalaremos que para formar /( A i, A2, A j) se debe efec­
tuar la unión de A i, complementario en E de A ,, con A2, 
y después tomar la intersecdón de esta unión con A3.
9. Grafos. Correspondencias. - a) Si f e s una aplicación de E 
en F, el conjunto de pares (a, /(a)) , obtenido cuando a toma 
valores en E, es un subconjunto de E X F llamado grafo de la 
aplicación f
Por ejemplo, si E = F la diagonal de E2 es el grafo de la 
aplicación idéntica / ( a ) = a.
b) En el estudio de numerosos problemas es necesario con­
siderar aplicaciones tales que un elemento a del conjunto de 
partida E admita una o varias imágenes en el conjunto de lle­
gada F. Tales apücadones son llamadas aplicaciones multiformes 
o mejor, para evitar cualquier confusión, correspondencias.
30 EL ALGEBRA DE BOOLE
No consideraremos más que correspondencias de E en E 
siendo E un conjunto finito. Se designará una correspondencia 
por la letra P.
c) He aquí un ejemplo de correspondencia utilizada en teoría 
de juegos.
Si E64 es el conjunto de las 64 posiciones posibles de una 
pieza de ajedrez sobre un tablero, de forma más usual se deno­
tan por a ,, ...,a8, b , , ha estas posiciones. Sea por ejemplo 
Cs la de un caballo que pertenece al jugador que le toca mover, 
las nuevas posiciones posibles de este caballo son a4,a6, ó3, ó , ,
d ],d 1,e , y et y estas posiciones forman un conjunto P (Cs): 
El reglamento del juego define así sobre E64 una corresponden­
cia r.
Si la pieza considerada es el rey situado en una posición a, 
es necesario restringir T(a) a las posiciones en las que el rey 
no está en posición de jaque y, en este caso, si r(a ) =#.el rey 
está ahogado, es decir en posición de mate.
d) La noción de grafo definida anteriormente para las apli­
caciones se extiende a las correspondencias.
El grafo G de una correspondencia T es el conjunto de los 
pares (a, b) donde a eE y b € T(a) si P(a) designa el conjunto 
de las imágenes del elemento a en la correspondencia P.
Nos limitamos, como ya se dijo, a los conjuntos E de n ele­
mentos que representaremos siempre por n puntos de un plano 
denotados A ,, A2,.... A /,.... An.
El conjunto de los puntos de E imágenes de A,- por T, será 
designado por r(A ,) y el conjunto de los puntos de E que 
tienen A; por imagen por r _ 1(A,).
l.° Una correspondencia está definida si se conocen todos 
los T(A/). Sea, por ejemplo:
E = {A,,A2,A 3,A 4}
y las condiciones:
r (A ,) = {A,, A j); r (A ,)= { A j,A 4); 
r(A3) = {A,,A4}; r(A 4)= { A ,,A j,A 3}.
APLICACIONES. FUNCIONES DE BOOLE. CRAFOS 31
Obtenemos para los T '(A,-):
r - ‘(A,) = {A1.A 3.A4); r - ' ( A 2) = {A1.A4}; 
r _ l (A3) = {Aj.A4}; r - ‘(A«) = {AI ,A 3}.
2.° A cada correspondencia T así definida se. le asocia un 
grafo G, es decir el conjunto de los pares (A,-, A/) donde A,€ E 
y Ay S T(A,). Esta representación de una correspondencia es 
completada en teoría de grafos por numerosas definiciones de 
las que nosotros daremos las más simples.
10. Definiciones de la teoría de grafos. - a) A todo par 
(A(, A/) se asocia el vector A,- Ay en la representación puntual 
del conjunto E y se llama este vector arco de G. Los A,- son los 
puntos o vértices del grafo; A/ es el extremo inicia] u origen 
y A/ el extremo final o simplemente extremo del arco A/ A/. 
Si i = / , A,- A¡ se llama arco nulo A,-. El conjunto de los arcos 
determina el grafo G y éste la correspondencia 1'.
b) Un grafo es simétrico si la existencia de un arco A,- A/, 
implica la del arco Ay A¡ , para todo arco A¡ Ay del grafo.
En la representación de un grafo simétrico se suprimen, para 
simplificar, las dos flechas de los vectores A¡ Ay y Ay Ai, y se 
dirá que el segmento A¡ Ay pertenece al grafo.
El grafo del caballo anteriormente definido sobre E44 es 
evidentemente simétrico después de la regla para mover el ca­
ballo sobre el tablero. Un grafo G es antisimétrico si uno y uno 
sólo de los arcos A,- Ay y Ay A¡ pertenecen a G para todo par 
(A,' Ay) del grafo G.
c) Sea T la correspondencia definida en el parágrafo prece­
dente. Dispongamos los puntos Ai, Aj, A3, A4 en los vértices 
de un cuadrado y dibujemos los vectores A¡ Ay pertenecientes 
al grafo G de I\
En torno al punto A| trazamos un círculo para señalar que 
el par (Ai, Ai), o arco nulo A i, pertenece a G.
32 EL ALGEBRA DE BOOLE
El grafo G no es simétrico ya que A! Á2 6 G y A¡ A, 9 G. 
Tampoco es antisimétrico ya que A3 A4 y A4 A3 pertenecen 
a G asi como A] A4 también y A4 A j. Se ha utilizado sin 
embargo, para simplificar, el convenio de representar los grafos 
simétricos por medio de los segmentos A3 A4 y A2 A4.
d ) Se llama camino a una sucesión de arcos lal que el extre­
mo de cada arco coincide con el origen del siguiente cuando
Un camino se llama circuito cuando está cerrado, es decir, 
cuando el vértice inicial coincide con el final.
Así, en la figura 9, Ai A2 A3 que unen Ai a A3 pasando
por A2 es un camino mientras que A¡ A¡ A3 A4 A, es un circui-
e) He aquí algunas definiciones más particulares.
1.° Se dice que un grafo simétrico es p-cromático o de nú­
mero cromático p (p , entero positivo) si, con sólo p colores 
diferentes, podemos colorear todos los vértices de forma que 
los dos extremos de un mismo arco no tengan el mismo color.
Sea, por ejemplo, un mapa de n países representando cada 
uno por un punto del conjunto E = {A j, A2,..., A„}. Se forma 
un grafo simétrico G con todos los pares (A,-, Aj) de países 
que tienen frontera común.
2 ° Este grafo G' posee las dos propiedades siguientes:
a ) Se pueden situar todos los vértices de t í sobre un plano 
de forma que dos cualesquiera de sus arcos no se corten; se dice 
que G' es un grafo plano.
APLICACIONES. FUNCIONES DE BOOLE. GRAFOS 33
(3) Se demuestra que podemos colorear G ', y por tanto el 
mapa, con sólo cinco colores de forma que dos países con fron­
tera común tengan siempre colores diferentes. Se comprueba 
experimcntalmente que bastan cuatro colores para hacerlo pero 
no ha sido posible, hasta el presente, demostrar este resultado.
11. Grafos completos. — 1.° Se dice que un grafo es com­
pleto si, y sólo si, al menos uno de los arcos A, A/ ó Ay A, 
pertenecen a G para cualquier i, j = 1 ,2 , n. Así el grafo G 
de la figura 9 es, como fácilmente puede comprobarse, completo.
2 ° Grafo completo simétrico.
Designaremos por R y llamaremos referencia!, al grafo com­
pleto simétrico formado por el conjunto: E = {Ai,A2 A„}.
Este grafo R contiene, a la vista de la definición, todos los 
arcos A,- A¡ ya que, por ser completo, debe contener uno al 
menos entre A jA /y á /A , para todo / , / y, como es simétrico, 
contiene a ambos.
Este grafo R es el asociado a la correspondencia T tal que 
r(A /) = E para todo i, que contiene evidentemente todos los 
pares (A,, A/).
3.° Un grafo cualquiera G definido sobre E no contiene, 
en general, más que algunos arcos A¡ A¡ ; es pues una parte de R 
(o grafo parcial de R).
El conjunto de los grafos G sobre E es el conjunto jp(R); 
se puede pues definir la unión y la intersección de dos grafos 
definidos sobre E así como el complementario de un grafo. 
La teoría de grafos está así en estrecha relación con el álgebra 
de Boole.
12. Función característica de un grafo. - Se aplica sin difi­
cultad la ya conocida definición de función característica de 
un conjunto.
Los elementos de R son los arcos A; A/ ; cualquier aplicación
34 EL ALGEBRA DE BOOLE
/d e R en el conjunto {0, 1} es una función característica que 
define el grafo G por las condiciones:
/ - '( 1 ) = G; / - ‘<0) = G, 
siendo G el complementario de G en R.
Llamamos x¡¡ al elemento A,- A¡ de R. La función caracte­
rística F(G;x//) está definida por:
F(G ;x„)= l si AjA/ €G 
F(G;Jtj,) = 0 si A /AyfG.
Completaremos estas nociones sobre grafos y sus funciones 
características en el capítulo IX, cuando hayamos introducido 
las variables de Boole.
Capítulo IV
ESTRUCTURAS DE CONJUNTOS
Algunas aplicaciones particulares nos permiten estructurar un 
conjunto. Aplicaremos las definiciones y resultados que siguen 
a los elementos del conjunto Sp(E), conjunto de las partes de 
un conjunto E no vacío y que en álgebra de Boole suponemos 
finito.
1. Ley de composición interna. - Dado un conjunto E, cual­
quier aplicación de E 2 en E recibe el nombre de ley de compo­
sición interna de E.
Esta ley hace pues corresponder a cualquier par ordenado 
(a, b) de elementos -distintos o no— de E, un elemento c y 
uno solo de E. Escribiremos:
(el signo « designa la ley de composición).
Se dice que c es el compuesto de a y de b.
a) En N* la suma y el producto habituales son leyes de com­
posición interna pero, sin embargo, la resta y la división no 
lo son, ya que la diferencia o cociente de dos enteros positivos 
no tiene por qué ser otro entero positivo.
b ) En ^P(E), conjunto de partes de un conjunto E, la unión 
y la intersección son leyes de composición interna.
2. Iteración de una ley interna. - Una ley de composición 
interna en un conjunto E puede ser iterada, es decir repetida
36 EL ALGEBRA DE BOOLE
a partir del resultado obtenido, ya que éste es un elemento de E 
por ser la ley interna. Asi, escribiremos:
para indicar que se compone a, con e3, después este resultado 
con a-i, a continuación el nuevo resultado con a4 y asi sucesiva­
mente respetando el orden de escritura de los a¡ de izquierda a 
derecha, el último resultado p será un elemento de E.
Si a, = a3 = ... = a„, se escribirá p =a", siendo n el número 
de elementos iguales a a.
3. Estabilidad. - Si en E tenemos una ley de composición 
interna, y si E' es un subconjunto de E tal que esta ley apli­
ca E'2 sobre E', se dice que E' es una parte de E estable para 
esta ley. Sea, por ejemplo, Z con la ley suma habitual. Esta 
ley aplica igualmente N2 sobre N ya que la suma de dos enteros 
positivos es un entero positivo; N es pues una parte estable 
de Z para esta ley.Igualmente para la ley de multiplicación 
en Z, N es una parte estable, pues el producto de dos enteros 
positivos es siempre otro entero positivo, en cambio no lo seria 
el conjunto de los enteros negativos ya que el producto de dos 
enteros negativos es un entero positivo.
4. Idempotencia. - a) Una ley interna es idempotente si, y 
sólo si:
a * a = a para todo a e E.
Si la ley * es idempotente, a" = a para todo a e E.
Supongamos, en efecto, que a" - 1 = a y compongamos con a 
los dos miembros de esta igualdad: a" - 1 » a = a * a = a, como 
a" ~ 1 * a = a" tenemos que a" = a y la proposición la hemos 
demostrado por recurrencia.
b) La intersección y la unión son dos leyes internas idem- 
potentes. En efecto, si A es un conjunto
A n A = A y A U A = A (13)
cualquiera que sea A.
ESTRUCTURAS DE CONJUNTOS 37
5. Asociatividad y conmutatividad. - a) Una ley interna es 
asociativa si para todo a, b, c, elementos de E, se verifica:
( a * 6) . c = a . ( f . . c ) (14)
y a este resultado común se le representa por a • b * c.
La unión e intersección son leyes internas asociativas-, es su­
ficiente recurrir a sus definiciones para observar que:
(A U B )U C = AU (B UC ) (15)
( A n B ) n c = A n ( B n c ) (16)
suprimiremos los paréntesis para escribir este resultado.
¿>) Hay que señalar que la asociatividad sólo es verificada 
por la unión por un lado, y por la intersección por otro, pero
(A U B )n C * A U (B n C ) (17)
En efecto, tomemos A = B. En el primer miembro de (17)
(A U A )n C = A flC . 
mientras que el segundo se convierte en:
A U (A O C) = A 
ya que A n C está contenido en A. En general A * A n C, y 
está justificada la proposición.
c) Una ley interna es conmutativa si para todo par de ele­
mentos a, b de E:
a * b = b * a (18)
En este caso se dice que a y b permutan o conmutan.
Las leyes unión e intersección son conmutativas; resulta in­
mediatamente de sus definiciones ya que:
A UB = B UA (19)
A fl B = B n A (20)
Veamos dos propiedades generales, la primera relativa a la aso­
ciatividad, y la segunda relativa a una ley a la vez asociativa y
conmutativa.
38 EL ALGEBRA DE BOOLE
d ) S i una ley interna es asociativa, al componer n elementos 
podemos reemplazar p elementos consecutivos por su compues­
to sin que el resultado se modifique.
Sea P = a, » ... * aq • ... • a, • ... » a„ con p , q , n e N*. 
q < r < n y sea p = r - q + 1.
Pongamos:
Supongámoslo demostrado para p - 1 elementos consecuti­
vos, es decir supongamos que b * aq * ... * ar_ ,= b * c .
Como b * aq • ... • a ,= (b * c) * a„ se obtiene por (14): 
b * aq . ... « a, =(¿ * c) . ar =b • (c *ar) = b * d, 
y la ley está demostrada por recurrencia.
En consecuencia, podemos escribir las siguientes fórmulas 
de inmediata comprensión:
am * o" =am*n; (J ” f = 0m'B.
é) Si una ley interna es asociativa y conmutativa, no cambia 
el compuesto de n elementos si cambiamos arbitrariamente su 
orden.
Sea P = a¡ • a2 • ...» «/_ i * a¡ * ... • a„.
Pongamos P'=a¡ • a2 » ... •<>/_].
Tenemos:
(p • « i - 1) * a¡ - p ’* (aí- 1 * a ,)= p '* (a / «a, - , ) 
ya que la ley es asociativa y conmutativa.
De esto deducimos:
p" . (a¡ • a¡. , ) <= (p • a/) * a/_ , 
al ser la ley asociativa.
Podemos pues permutar dos elementos consecutivos y por 
lo tanto poner como primer elemento mediante un número con­
veniente de permutaciones, uno arbitrariamente elegido; después 
en segundo lugar otro elemento cualquiera y asi sucesivamente, 
es decir efectuar las operaciones en un orden cualquiera.
ESTRUCTURAS DE CONJUNTOS 39
6. Elemento neutro. — a) Dada una ley interna en un con­
junto E un elemento e de E se dice que es el elemento neutro 
de la ley si para todo elemento a de E,
a . e = e . a = a (21)
lo que contradice la hipótesis; por tanto es único.
b) El conjunto vacío es elemento neutro para la unión 
conjuntos:
<t¡ U A = A, cualquiera que sea A.
El conjunto E, no vacío, es elemento neutro para el ci 
junto ^3 (E) con la intersección pues
E n A = A cualquiera que sea A subconjunto de E.
7. Elementos regulares. - a) Un elemento a de E se dice 
regular a la izquierda si a * b — a * c implica b = c, para todo 
ó , c e E y regular ala derecha si ft » a = c « a implica b=c para to­
do b, c e E.
El elemento a es regular si es regular a derecha y a izquier­
da, para la ley de composición interna definida sobre E.
b) Así sobre N todos los elementos son regulares para la 
. adición pues a + b = a + c implica b = c, para todo a, b, c e N.
En el conjunto 9p(E) de parte de un conjunto no vacío E, 
un elemento no es, en general, regular.
Sin embargo, el conjunto vacio es regular para la unión:
$ U B = 4> U C implica B = C, ya que 0 U B = B y 0 U C =C.
El conjunto E es regular para la intersección:
E n B = E n C implica B = C, ya que 
EO B = B y E O C = C.
EL ALGEBRA DE BOOLE
8. Distributividad. - a) Si existen sobre E dos leyes de com­
posición internas denotadas • y i , la ley • se dice que es dis­
tributiva a la izquierda con respecto a la ley 1 si, y sólo si: 
a • (b 1 c) = (a • b) 1 (a • a), 
cualesquiera que sean a, b, c € E.
Es distributiva a la derecha con respecto a i si, y sólo si:
(ó 1 c) * a = (ó • a) i (c • a), 
cualesquiera que sean a, b, c € E.
Finalmente diremos que • es distributiva con respecto a 1 
si es distributiva a izquierda y a derecha.
b) Cuando la ley es distributiva, se pueden aplicar las reglas 
del álgebra elemental relativas a la supresión de los paréntesis 
si la ley es asociativa. Por ejemplo:
( a , ia 2) . (6 , 10, 103) = (a, . 6 , ) l ( a , . ó , ) l
1 (a, . ¿>3) 1 (a, . b, )1 (a, . 6, ) i (a, . b3).
c) La operación intersección es distributiva con respecto a la
p n ( |ü í j - ü 1( r n W (22)
siendo F y los Ej conjuntos cualesquiera e I un conjunto de
Para demostrar (22), llamemos G al primer conjunto y H al 
segundo.
Si x 6 G, pertenece a F y al menos a un E,-. por ello a la 
intersección de F y de este E,, y por tanto a H.
Si x E H, pertenece a F n E, para un i al menos; pertenece 
pues a F y a este Ej y por tanto a G.
Así tenemos la igualdad G = H que nos prueba (22).
d)La operación unión es distributiva con respecto a la inter­
sección. Probemos:
FU (ieIE')=ieI(FUE,) (23)
ESTRUCTURAS DE CONJUNTOS 41
Tomemos complementarios con respecto a un conjunto E 
que contenga a F y a todos los E¡. Se obtiene, aplicando las 
fórmulas de De Morgan:
Ahora bien estos dos conjuntos son iguales por (22), lo que 
nos prueba (23).
e) Aplicaremos a menudo los resultados precedentes para 
tres conjuntos A, B, C, lo que se escribe:
9. Homomorfismo. Isomorfismo. - Es interesante considerar 
la imagen de una ley interna sobre E por una aplicación f.
a) De una forma precisa, si f aplica E sobre F, conjuntos 
éstos provistos respectivamente de leyes de composición interna 
• y J, se dice que f es un homomorfismo si, y sólo si, la imagen 
de a • b por / es la compuesta de las imágenes /(a ) y fif i) por 
la ley 1, es decir:
/ ( a * ó) = /(a) 1 f(b ), para cualesquiera a ,b e E.
Se comprueba sin esfuerzo que el compuesto de dos homo- 
morfismos, en el sentido de la composición de aplicaciones, 
es un homomorfismo.
Si E = F se dice que el homomorfismo es un endomorfismo. 
ó) Si /e s biyectiva, el homomorfismo se llama isomorfismo, 
y el endomorfismo automorfismo.
Demostremos que si / es un isomorfismo, / “ 1 es también 
un isomorfismo. Sean a, b e E; de a '= /(a), b' = f(b), se deduce 
a = f~ 1 (a'), b = f~ ‘ (b'). Ahora bien por hipótesis.
F n ( U E, | „ U ( P n l , ,
A n (B u c) = (A n b) u (A n C) (24)
(25)A u (B n c ) = (A u B) n (A u c)
/( a » i ) =/(a ) 1/ ( 6), por lo que:
a , b = r ‘ («' 1 b') = f~ 1 («’) * / " 1 (*’),
que nos demuestra que f 1 es un isomorfismo al ser / 1 biyec-
42 EL ALGEBRA DE BOOLE
c) Demos un sencillo ejemplo de isomorfismo.
Sea E = N* y la ley la adición usual denotada por +.
Sea F el conjunto de los elementos 2" con n G N* y la leyla multiplicación que, como se sabe, es tal que 2" • 2"1 = 2" 
para todos n, r i 6 N*.
La aplicación f definida por n * 2" es evidentemente
biyectiva. Además a la suma n + n en E le corresponde en F 
el producto 2" • 2" y como 2" • 2" =2n*’i tenemos bien defi­
nido un isomorfismo.
10. Estructuras. — Las leyes de composición interna permi­
ten clasificar ciertas estructuras de conjuntos, tales como las 
estructuras de grupo, de anillo, de cuerpo o de retículo.
La estructura de grupo no necesita más que una ley interna 
provista de ciertas propiedades. La estructura de retículo nece­
sita la existencia de dos leyes internas particulares así como la 
existencia de una relación de orden parcial sobre el conjunto.
Las estructuras de anillo y de cuerpo precisan la existencia 
de dos leyes internas, que para un cuerpo deben ser ambas de 
grupo1. Existen otras estructuras de conjuntos como la de es­
pacio vectorial o como las diferentes estructuras de espacios 
topológicos.
El estudio de las estructuras ha tomado una importancia con­
siderable en matemáticas modernas bajo la influencia de la es­
cuela bourbakista. Aunque este estudio no puede pretender cubrir 
la totalidad de la actividad y reflexión matemáticas, ha provoca­
do, por su misma generalidad, un enriquecimiento y un prolon­
gamiento considerables de esta actividad y de esta reflexión.
1 Ver L algebre múdeme de M. QUEYSANNE y A. DELACHET (Co­
lección "Que sais-je?" n.o 661), Presses Universilaires de Eranee. (Edición 
en castellano de Editorial Vcrgara.)
Capítulo V
ALGEBRA LOGICA
Se dice que un conjunto posee una estructura algebraica si 
está provisto de una sola operación. Se dice que se ha definido 
un álgebra si el conjunto posee al menos dos operaciones.
Las operaciones unión, intersección y complementación defi­
nen para el conjunto de las partes de un referencial un álgebra 
llamada álgebra de Boole que toma el nombre de álgebra de las 
proposiciones o álgebra lógica cuando se aplica al estudio de las 
funciones lógicas.
1. Implicación, — a) Tomamos como conjunto de referen­
cia E al conjunto de los entes matemáticos actualmente defi­
nidos por los matemáticos. Un subconjunto E | se dice carac­
terizado por una propiedad 0 si todo elemento de E , verifica 
0 y todo elemento de E que verifica 0 pertenece a E(, de 
tal forma que, si a € E, 0 es verdadera_para a si a G E, y 
0 es falsa para a si a $. E | , es decir si a € Ei -
Se construye así una lógica con dos valores, verdadero y 
falso, o lógica del tercio excluido.
ó) Dados dos conjuntos Ei y E2 caracterizados por las pro­
piedades 9 y 3 , se dirá que 0 implica 3. y se escribirá
0 = 3 (26)
si E ,C E , (27)
condición necesaria y suficiente para que todo elemento que 
posee la propiedad 0 posea también la propiedad 3 .
La proposición (26) se denomina teorema, 0 recibe el nom­
EL ALGEBRA DE BOOLE
bre de hipótesis y 3 el de conclusión; el signo =» es el signo 
de implicación.
La proposición 3 =» & es llamada implicación recíproca; 
se escribe también 9 «= 3 y el signo «■ es el signo de la impli­
cación recíproca, el teorema es llamado teorema reciproco y 
la inclusión (27) es reemplazada por la inclusión E] C E |.
Cuando se verifican las dos proposiciones, directa y recíproca,
& o 3
los conjuntos Ei y Ej son iguales y las propiedades & y 3 
lógicamente equivalentes.
Así, A U B = A ~ B C A;
e igualmente: A C B » B C A .
c) Los elementos de E | poseen por definición la propiedad 
negación de 9 ; se le denomina propiedad negación de & o 
propiedad no-^ que se denota & .
Es por esto que a menudo se llama a la operación de com- 
plementación negación o también operación NO. _ _
Como (27) equivale a E2 C Et 3 equivale a 3 &
(28). Este teorema (28) no es más que la forma negativa del 
teorema (26), forma negativa que a veces es más interesante 
que la directa.
d ) La implicación & » 3 (29) es la implicación contraria 
o teorejna contrario de la implicación directa (26). Supone pues 
Ei C E j ó Ej C E |, y equivale pues a 3 ■» i? , es decir a la 
implicación recíproca o teorema recíproco.
2. Lógica de las proposiciones. — Veamos sobre un ejemplo 
cómo se puede estudiar la compatibilidad y veracidad de varias 
proposiciones.
Sean A, B, C, D, E cinco proposiciones. Se sabe que:
1 ° Si E es falsa, A y B son falsas y C ó D son verdaderas.
2.° Si A es verdadera y si B ó C son falsas, D es verdadera.
3.° Si B es falsa, A es falsa.
4.° Si C es verdadera, D es falsa y recíprocamente.
5.° A es verdadera.
ALGEBRA LOGICA 45
La “o” de las frases precedentes es en todas ellas inclusiva. 
Designemos por las mismas letras A, B, C, D, E los conjuntos 
cuyos elementos poseen respectivamente las propiedades A, B, 
C, D, E, pues no dará lugar a confusiones.
Las proposiciones precedentes serán compatibles si existe 
al menos un elemento para el cual las cinco afirmaciones corres­
pondientes se verifiquen.
Utilicemos la inclusión para traducir las implicaciones dadas. 
Obtenemos:
_ 1.° E C (A n B) n (C U D), de donde tenemos E C A n B y
E c c u d .
2.° A n (B U C) C D, o lo que es lo mismo por la distribu-
( A n ! ) u ( A n c ) C D .
3.° B C A, que_implica AC B. _
4.° C C D y D C C es decir C =D ó C = D.
De 1,° se deduce:
A n B C E .e s decir A U B C E y por lo tainto:
A C E y B C E (30)
además: C U D C E o lo que es lo mismo C n D C E y utili­
zando 4.°: C n C C E o bien $ C E , que es cierto.
D e2 ° deducimos: _
A n B C D y A O C C D; pero como por 3.° A OB = 0 ya 
que B n B = 0 , tenemos que A n B = 0 C D que se verifica. 
Finalmente C = D implica A f lC C D que en efecto se veri­
fica.
Para terminar nos faltan las condiciones:
A C BC E y C = D
que en efecto son compatibles.
La veracidad de A implica pues las de B y de E, y las pro­
piedades C y D son incompatibles.
El sistema lógico estudiado admite pues dos soluciones:
a) A verdadera; B verdadera; C verdadera; D falsa; E verda-
46 EL ALGEBRA DE BOOLE
b) A verdadera; B verdadera; C falsa; D verdadera; E verda-
Se hubiera podido llegar a este resultado únicamente razo­
nando, pero la búsqueda precedente tiene carácter sistemático 
y nos conduce a él con mayor seguridad; el álgebra binaria de 
Boole, como veremos en el capítulo IX, permitirá encontrar los 
resultados precedentes utilizando únicamente cálculo.
3. Cuantificadores. - Se introducen a menudo dos convenios 
de escritura con la ayuda de los cuantificadores.
a) El cuantificador universal V se lee “para todo" o “cual­
quiera que sea” y es utilizado para escribir que todos los ele­
mentos de un conjunto poseen una cierta propiedad. Así A C B
Va.ae A=»a€B,
que significa que el conjunto A está incluido en el conjunto B, 
si y sólo si, todo elemento de A pertenece a B.
b) El cuantificador existencia13 se lee “existe al menos uno” 
y es utilizado para indicar que un elemento al menos de un 
conjunto posee una cierta propiedad. Así:
3 a tal que a G A =* a $ B, 
significa que existe al menos un elemento de A que no perte­
nece a B y por tanto A no está incluido en B. Esta proposición 
es la negación de la precedente y ha sido obtenida permutando 
los cuantificadores e invirtiendo la conclusión, es decir reem­
plazándola por su negación.
Esta regla es válida en general y útil para negar una afirma-
C apítulo VI 
R E L A C IO N E S D E O RD EN
RELACIONES DE ORDEN
3. Relaciones de orden. - a) Una relación en Ese dice que es 
de orden total si es reflexiva, antisimétrica y transitiva.
Sea por ejemplo en N la relación a < b si a precede a b en la 
sucesión natural:
0 1 2 ... n ...
Es una relación de orden total en N.
En efecto, para todo a e N, a < a ya que a = a (reflexi- 
vidad).
Para todo par (a, b), las desigualdades a < b y b < a im­
plican a = b, y es la propiedad de antisimetría.
Finalmente, a < b y b < c implican a < c (transitividad).
De forma general, si a ^ ó, se puede escribir la relación de 
orden en la forma a < ó; se dice que el orden es estricto.b ) Es interesante examinar en qué casos el orden no es total; 
se necesita evidentemente, y basta, que exista un par (a, b) 
para el cual la relación 31 no sea una relación de orden.
Entonces se dirá que el orden es parcial si existe un sub- 
conjunto de E, distinto de él, que esté ordenado por 91.
Se puede decir que el orden es parcial si existe como mínimo 
un par (a, b) ordenado por 91 y otro par al menos (c, d ) no 
ordenado por 91.
c) Veamos dos ejemplos importantes:
1,° La relación de inclusión en ^P(ff) es una relación de 
orden parcial
En efecto:
A CA (reflexividad):
A CB y B C A => A = B (antisimetría)
A CB y B C C ■» A C C (transitividad) 
pero las relaciones A C A y A C A son ambas falsas.
El orden no es pues total pues el par (A, A) no puede ser 
ordenado por inclusión y es parcial ya que un par (A, B) puede 
ser ordenado (por ejemplo A = ¡t> y B cualquiera de ?P(E)).
2.° La relación "a divide a b” para el conjunto de los en­
teros positivos es una relación de orden parcial.
En efecto: a divide a a (reflexividad);
a divide a b y b divide a a implican a = b (antisimetría), 
pues b = k a y a = k'b con k, fc'e N* de donde b = kk'b, es decir 
kk'= 1 y por tanto k = k ' - l .
Finalmente, a divide a b y b divide a c implican a divide a c, 
pues b - k a y c = k'b implican c = kk'a.
Así 2 divide a 4 y el par (2 ,4 ) está ordenado por esta rela­
ción; por el contrario el par (8, 13), por ejemplo, no lo está, 
pues ni 8 divide a 13 ni 13 divide a 8.
Se expresa a menudo a 1 ¿> a la relación “a divide a b” y a <¡> b 
la relación contraria “a no divide a ó".
Señalemos que la relación a | b no define ningún orden, ni 
siquiera parcial, en el conjunto de los números primos mayores 
que 1 pues ningún par puede ser ordenado. Denotaremos siem­
pre por a < b una relación de orden cualquiera sobre un con­
junto y escribiremos a < b si a=t=b.
4. Cadenas. - a) Cuando la relación de orden sobre E es par­
cial, un subconjunto de E totalmente ordenado por esta rela­
ción se dice forma una cadena.
Así, en N* ordenado por la relación a I b, los subconjuntos 
1, 3, 9, 18, 54 (H,)
1, 2, 6, 12, 36 (H,)
SO EL ALGEBRA DE BOOLE
son dos cadenas.
b) Una cadena se dice maximat en E para la relación 3 t si 
no existe ninguna otra cadena H', distinta de H, de la que ésta 
sea un subconjunto.
Resulta inmediato de esta definición que cualquier subconjun­
to H" de H, distinto de H, no puede ser una cadena maximal, 
lo sea o no H.
Podemos formalizar la definición anterior, lo que nos permite
RELACIONES DE ORDEN 51
enunciar cómodamente la condición de cadena no maximal, 
permutando en ella los cuantificadores e invirtiendo la conclu-
H maximal: V xeH , 3j>6 H, tal que x Qy e y 0x.
H no maximah 3x 6 H, tal que V_y e H, x \y ó y |x ; el 
complementario H de H está tomado en E.
Así, si E es el conjunto de los enteros menores o iguales a 
54, las cadenas anteriores (H ¡) y (H2 ) son maximales en E.
1° Veamos que la cadena (H ,) 1, 3, 9 , 18, S4 es maximal. 
En efecto, supongamos que no sea maximal: cualquier entero 
menor que 54, no puede ser múltiplo de 54; ahora bien los di­
visores de 54 son 1, 2, 3, 6 , 9, 18. 27 y 54. O bien están en la 
cadena como 1, 3 ,9 , 18, o bien no están en ella como 2 ,6 y 27. 
Pero 6 0 9 y 9 0 6, igualmente 27 0 18 y 18 0 27,2 0 3 y 3 0 2: 
la cadena es pues maximal.
Veamos que lacadena (H2) 1, 2, 6 , 12, 36 es maximal. 
Ningún entero de H2 puede ser múltiplo de 36; en cuanto a los 
divisores de 36, o están en la cadena como 1, 2, 6, 12 y 36 ó 
no lo están como 3, 4 , 9, 18. Pero, 3 0 2 y 2 0 3 ,4 0 6 y 6 0 4 , 
2 0 9 y 9 0 2, 18 0 12 y 12 0 18;la cadena es pues maximal.
2.” Por el contrario, y siempre en E, las cadenas
1, 9, 18, 54,
1, 2, 12, 36, 
por ejemplo, no son maximales, ya que son subconjuntos de 
(Hi) o de (H2). Igualmente, en el conjunto E ',de los enteros 
positivos menores o iguales a 108, las cadenas (H, ) y (H2) no 
son maximales pues 108 es divisible por todos sus elementos.
3.° En el conjunto infinito N ' ninguna cadena finita orde­
nada por la relación a | b puede ser maximal pues N* contiene 
necesariamente múltiplos comunes a todos los elementos de la 
cadena (por ejemplo los múltiplos de su producto).
Sin embargo una cadena infinita puede ser maximal en N*. 
Sea por ejemplo la cadena p" , donde n e N y p es un número 
primo fijo. Cualquier elemento de su complementario en N* es de 
la forma kpm con k , m G N, k & 1 y no divisible por p\ 
como kpm no se puede dividir por pm" ni es divisible por él, 
la cadena es maximal.
52 EL ALGEBRA DE BOOLE
Por el contrario, si consideramos la cadena anterior sin, por 
ejemplo, p 1, no es maximal como subconjunto que es de una 
cadena y distinta de ella.
Antes de aplicar esta noción de orden parcial a los retículos 
daremos todavía algunas definiciones.
5. Mayorante. Minorante. - Sea E C F. Los conjuntos E y F 
suponemos están parcial o totalmente ordenados por una rela­
ción < totalmente general.
a) Se llama intervalo cenado 1 y se denota I = [a, ó] con 
a, b e F, al conjunto de los x 6 E tales que a < x < b.
Si a = b, I = [a], conjunto de un elemento.
Se llama intervalo abierto O y se escribe O = ]a, ó[ con 
a, b € F al conjunto de los x e E tal que a < x < b .
Si a = b, O = Ja, a[ = 0.
b) Se llama mayorante de E a un elemento M de F, si existe, 
tal que x < M, para todo x 6 E.
Se llama minorante de E un elemento m de F, si existe, 
tal que x > m , para todo x € E.
c) Sea F = N y E = {2, 3, 7, 8, 9, 11}; se supone N orde­
nado siguiendo el orden de la sucesión natural de los enteros, 
es decir que damos al signo < el significado habitual (orden de 
menor a mayor).
1.° En N, si a = 2 y si b = 5, I = [a, ¿>] comprende los 
enteros, 2, 3, 4 y 5 mientras que O = ]2, 5[ sólo comprende los 
enteros 3 y 4.
2.° M = 11 es un mayorante de E pero M' = 12, por ejem­
plo, es también un mayorante de E.
m = 2 es un minorante de E, pero m = 1 ó m" = 0 son 
también minorantes de E.
6. Cotas1. — a) Se llama cota superior B de E, y se escribe 
B = sup E al menor, si existe, de los mayorantes de E.
RELACIONES DE ORDEN 53
Se llama cota inferior B’ de E, y se escribe B‘ = inf E, al 
mayor, si existe, de los minorantes de E.
Si B existe, es único pues si B( ¥= B fuese también cota supe­
rior se podría escribir B| < B por ser B mayorante y B| ser 
el menor de los mayorantes; igualmente podríamos escribir 
B < B, en contradicción con Bt < B; por tanto B, = B.
Se demostraría igualmente que si B' existe, es único.
b) Consideremos de nuevo el conjunto E del parágrafo pre­
cedente.
B = 11 pues es el menor de los mayorantes.
B = 2 pues es el mayor de los minorantes.
c) El mayorante, o el minorante de un conjunto no perte­
necen necesariamente al conjunto.
Sea, por ejemplo, el conjunto E de los racionales compren­
didos entre 1 y 2 , excluyendo los extremos 1 y 2: E = ]1, 2[ 
ordenado de menor a mayor.
El entero 2 es un mayorante y es el extremo superior; en 
efecto, pues si un racional x es menor que 2, no puede ser
mayorante ya que el racional - - +- ^ está estrictamente com­
prendido entre x y 2:
pues como x < 2 , 2 x < x + 2 < 4 .
Así pues 2 = sup E í E.
7. Preorden sobre un grafo. - Veamos en qué condiciones 
se puede asociar a un grafo una relación de orden.
a) Diremos que dos vértices \ ¡ y Am del grafo G están re­
lacionados por la relación St si, y sólo si, existe un camino en 
el grafo G de origen A,- y extremo Am. Escribiremos:
A, St Am en G.
l.° La relación d i es reflexiva ya que A,- está relacionado 
consigo mismo por el arco nulo.
54 EL ALGEBRA DE BOOLE
2.° La relación 9t es transitiva en G.
En efecto, A, 91 Am y Am 91 Aj ^ A,- 91 Ay pues el camino 
A,-... Am que relaciona A,- con Am y el camino Am ... Ay que 
relaciona Am con Ay nos originan el camino A,-... Am ... Ay que 
relaciona Aj con Ay.
A esta relación i%, que existe sobre cualquier grafo G, ya 
que en G existe al menos un arco, se le llama relación de pre-El preorden es total si dos vértices cualesquiera pueden rela­
cionarse por un camino al menos en G; se dice queG es fuerte­
mente conexo o también que G es un grafo total.
b) La relación 9 t sólo será de orden en G si además es anti­
simétrica, es decir, si Aj 91 Ay y Ay 91 Aj implican que Ay y Ay 
coinciden.
Ello es asi si, y sólo si G no admite circuitos', en particular, 
G no debe admitir ningún segmento.
La condición es necesaria pues si Ay... Aj es un circuito, 
existe al menos un A„ tal que Ay 9 t Am y Am 91 Ay, lo que 
implica, supuesto 91 ya antisimétrica, que Ay y Am coinciden, 
lo que contradice la hipótesis.
Es evidente que la condición es suficiente pues si G no ad­
mite circuitos, las relaciones Ay á? Am y Am 9t Ay son incom­
patibles.
El orden en G será pues total si, y sólo si, G es fuertemente 
conexo y no admite circuitos.
c) Así, sobre el grafo de la figura 9, existe un preorden, 
ya que Ai A2 A3 A4, por ejemplo, es un circuito, y el preorden 
es total pues el grafo es, claramente, fuertemente conexo.
Por el contrario se puede extraer del grafo de la figura 11 
un subgrafo tal que
l-*2 -»4 -* 8 -* 2 4 -» 4 8 
y es de orden total para la relación de divisibilidad.
Capítulo VII
RETICULOS
I. Definición. — Se llama retículo a un con/unto T parcial­
mente ordenado, tal que dos elementos cualesquiera a y b de T 
tienen una cota superior y una cota inferior en T.
Existen pues en T dos leyes de composición interna parti­
culares. Se utilizan las notaciones siguientes: sup {a, ó) = a V ó; 
inf {a,b) = a A b.
Damos la definición formalizada de un retículo escribiendo 
totalmente el que a A 6 y a V ó son respectivamente los extre­
mos inferior y superior de a y de b:
1.° a A K í j a A J < J ; ¥ z e T , x < a y x < 6 implican 
x < a A b (si no a A b no sería inf (a, b}).
2.° a V J > a ; a V í > J ; V r € T , j : > a y í > J implican 
x > a V b (si no a V b no sería súp {a,*}).
Aplicaremos esta definición generalizada al estudio de las 
propiedades fundamentales de los retículos.
2. Ejemplos. - a) El conjunto $(£") délas partes de un con­
junto no vacio E ordenado por inclusión, es un retículo.
Basta poner si A y B son dos subconjuntos de E: A V B = 
= A U B ;A A B = A flB ; pues A A B debe ser el mayor con­
junto contenido en A yen B; es, pues, su intersección.
Igualmente, A V B debe ser el menor conjunto que contiene 
a A y B< es, pues, su unión.
Por otro lado A U B y A O B son subconjuntos de E; se 
satisfacen todas las condiciones de la definición.
56 EL ALGEBRA DE BOOLE
b) El conjunto N ’ ordenado por a I b es un retículo. Es su­
ficiente poner si a y b son dos elementos de N*:
aA b = mcd(a,ó); a V b = mcm (a,6); 
tenemos así, a la vista de la definición del máximo común divi­
sor y del mínimo común múltiplo, los extremos de {a, ó}.
Se puede además demostrar que las operaciones A y V ai
definidas n< is que las operaciones de intersección y de
En efecto, descompongamos los enteros 
p = t f be
siendo a ,b , ...,/, 
Pongamos:
= a'“' b '^ ... 
factores primos.
Sean P = {a ,, a2 ... /x} y Q = {a'|, a'2 ... I¿ ) los conjuntos 
así obtenidos. Formemos P D Q y P U Q y tengamos en cuenta 
las relaciones (31); se obtienen en P n Q todos los factores co­
munes con sus menores exponentes, es decir el m.c.d. y en P U Q, 
todos los factores, comunes o no, con sus mayores exponentos,
c) La noción de retículo es muy general y se encuentra en 
los lugares más diversos de las matemáticas; así un espacio vec­
torial de dimensión n, ordenado según los índices, es un retículo; 
el conjunto de las funciones numéricas definidas sobre un 
segmento de la recta numérica es un retículo, pero limitaremos 
nuestro estudio a los ejemplos de retículos que interesen a 
nuestro fin.
d ) Si un conjunto está totalmente ordenado, es evidente­
mente un retículo pues, siendo a y b elementos cualesquiera, 
al ser la relación a < b de orden total nos permite poner siempre 
a A b = inf {a, ó] = a y a V b = sup {a, b] = b y las cotas per­
RETICULOS 57
tenecen al conjunto. Por tanto la noción de retículo es particu­
larmente interesante para conjuntos parcialmente ordenados con 
los cuales ella permite precisar las estructuras.
3. Propiedades generales de los retículos. - Enunciaremos y 
demostraremos aquí las propiedades fundamentales.
a) Las leyes internas son idempotentes.
1.° En a A b < a sustituimos ¿> por a y tenemos: a A a < a ; 
en * < a A b sustituimos x y b por a y tenemos: a < a A a. 
Concluyendo: a = a A a (idempotencia de la ley A ).
2.° En a V b > a sustituimos ó por a y nos queda: a V a > a; 
en x > a V b sustituimos x y b por a de donde: a > a V a. 
En conclusión: a = a V a (idempotencia de V).
b) Las leyes internas son conmutativas.
! ,° Por la definición tenemos s A K i y a A K a . d e 
donde a A b < b A a.
igualmente, fc A a < a y 6 A a < ó implican 6 A a < a A ó.
Por lo tanto:
a A b = ¿> A a (conmutatividad de la Ley A).
2.° Se demuestra del mismo modo sirviéndose nada mis que 
de la segunda parte de la definición formalizada:
a V í> = b V a (conmutatividad de la Ley V).
c) Las leyes internas son asociativas.
1.° Sean a ,b ,c tres elementos cualesquiera de T.
D e (a A 6) A e < c y d e ( a A f t ) A c < a A ó < ó ,s e deduce: 
( a A ó ) A c < ó A c (32)
Pero (aA ft) Ac < a A ¿ < a y con (32),
( a A J ) A c < a A(ÓAc) (33)
Igualmente,
a A ( J A c ) < j A c < i y a A ( iA c ) < a , de donde:
a A ( J A c ) < a A j (34)
58 EL ALGEBRA DE BOOLE
y, a A (6 A c) < b A c < c, de donde con (34), 
a A(b A c )< (a A b) A c.
Uniendo finalmente este resultado con (33), se obtiene:
(a A b) A c = a A (b A c) (asoáatividad de la ley A).
2.° Se demuestra análogamente la asodatividad de la ley V.
d) Las Leyes internas verifican una propiedad de absorción.
1 ° Para la Ley A esta propiedad se expresa:
a A (a V b) =<r (35)
Para demostrarla, vemos primero que a A (a V b) < a des­
pués de la primera propiedad de la definición (a V b juega aquí 
en la definición el papel de b). Vemos también que de a < a y 
de a < a V b se deduce a < a A (a V b).
Por tanto uniendo estos dos hechos tenemos el resultado (35).
2.° Se demostraría de igual modo la propiedad de absorción 
de la ley V que es:
a V (a Ab) =a (36)
4. Semirretículos. Subretículos. - a) Un conjunto parcial­
mente ordenado E en el que a V b existe para cualquier pareja 
{a,b} de elementos de E, se llama supsemirreticulo.
Si por el contrario, en E existe siempre a A b para toda 
pareja {a, b} de elementos de E, se dice que E es un infsemi- 
rreticulo.
Finalmente si T ' C T y si T' es un retículo para la misma 
relación de orden que T, se dice que T' es un subretículo de T 
si T es también un retículo.
Veremos ejemplos de estas diferentes estructuras con la ayuda 
de la relación a I b.
b) Escribimos sobre la primera línea de la figura 10 el nú­
mero 1, sobre la segunda los números primos en orden creciente,
RETICULOS 59
sobre la tercera los enteros productos de dos números primos, 
sobre la cuarta los enteros productos de tres números primos, 
siempre en orden creciente, y así sucesivamente. Se obtiene la
f e :
16 21 36 40 54 . . .
Se forman así cadenas. De la tabla (fig. 10) se extrae, por 
ejemplo, el siguiente grafo:
1.° Se comprueba que los conjuntos {1, 2, 4, 8 , 24, 48), 
{1 ,2,6, 12,24,48} y {1 ,2,4, 12,24,48} son retículos apli­
cando la definición.
2.° Un conjunto como {1, 2 ,4 , 8 , 24} es un retículo, por 
lo tanto subretículo del primer conjunto.
3.° El conjunto D = {2, 6, 8 , 12,24} es un supsemirretícu- 
lo, pues a V b G D para todo (a, i ) € D * D, pero 8 A 12 = 
= 4 ? D .
4.“ Por el contrario, I = {2, 4 , 6 , 8} es un infsemirretículo 
pues a A b GI para todo (a, b) € I x 1, pero 4 V 6 = 12 í I.
60 EL ALGEBRA DE BOOLE
5 ° Finalmente E = {4 ,6, 8 ,12} está parcialmente ordenado 
ya que 4 18, 4 112, 6 112, pero 6 4> 8 y 8 0 6; éste no es ni un 
retículo, ni un supsemirretículo ni tampoco un infsemirretículopues 6 V 8 = 2 4 < É E y 4 A 6 = 2 < ? E .
5. Retículos distributivos. - a ) Si las operaciones V y A son 
ambas distributivas una con respecto a la otra, el retículo se 
llama distributivo.
Es necesario pues, y también suficiente, si a, b, y c son 
tres elementos cualesquiera de T.que:
a A (ó V c) = (a A f>) V (a A c) 
j V ( i A c ) = (a V J ) A ( a V c )
b) El conjunto 5J5(E) de las partes de un conjunto no va­
cío E es un retículo distributivo ya que las leyes A y V son 
respectivamente O y U, operaciones que sabemos son distribu­
tivas una respecto de la otra.
Igualmente el conjunto N* provisto de la ley de divisibilidad 
es distributivo después de la anterior observación en la que se 
comparaban las operaciones A y V (m.c.d. y m.cjn.) a la inter­
sección y unión de conjuntos.
6. Retículos complementados. - a) Si un retículo T admite 
una cota superior que pertenece a T, ésta recibe el nombre de 
elemento universal de T y se representa por u.
Si un retículo T admite una cota inferior que pertenece a T, 
ésta recibe el nombre de elemento nulo de T y se representa 
por 0 .
Se dice que en un retículo T que tiene elemento nulo y 
universal, un elemento a tiene complemento si existe al menos 
un elemento a tal que
a A a = 0 y a V a = u (37)
Se dice que T es complementado si todos los elementos tie­
nen complemento.
b) Sea, por ejemplo, el conjunto $ (E ) de las partes de un 
conjunto no vacío E. El elemento 0 es el conjunto vacío ya
RETICULOS 61
que 0 C A para todo A subconjunto de E; el elemento u es 
el conjunto E, siendo la relación de orden la inclusión.
Además el complementario A de A verifica las relaciones (37) 
ya que A n A = 0 y A U A = E, siendo en este caso las leyes 
A y V la intersección y la unión.
Por tanto todos los elementos de E tienen complemento 
y ip (E) es complementado.
7. Retículo de Boole. — a) Se llama retículo de Boole a un 
retículo distributivo y complementado.
El retículo iP(E) de las partes de un conjunto no vacío E es, 
como se ha visto, distributivo y complementado y por ello un 
retículo de Boole. Vamos a demostrar las propiedades más im­
portantes de los retículos de Boole a partir de su definición. 
Estas propiedades se verifican en el ejemplo que acabamos de dar.
b ) Sea T un retículo de Boole arbitrario.
1 -° Los elementos nulo y universal verifican las relaciones
0 V x = x y «A x = x (38)
siendo x un elemento cualquiera de T.
En efecto, después de la definición general de retículo, 
x < x V 0 para todo » £ T ; por otra parte, r > r y r > 0 
implican x > x V 0. Uniendo ambas obtenemos la primera re­
lación de (38): r = O V x = r V O (conmutatividad). Final­
mente, x < x y x < u implican x < u A x ; mientras que 
u A x < x de donde, uniendo ambas, tenemos la segunda rela­
ción de (38).
2.° Cada elemento de T tiene sólo un complemento.
Ya que T es un retículo de Boole, cada elemento a de T 
tiene al menos un complemento. Supongamos que admitiese 
dos a y a . Se sabe que:
a A a = 0, a V a = « 
a A a' = 0, aV a ' = u
Utilicemos a = 0 V a . Se puede escribir:
a = (a A a') V a =(a V a) A (a 'V á)
62 EL ALGEBRA DE BOOLE
(distributividad) o también:
a = u A (a 'V a )= a 'V a ; 
de donde a < a (39)
Igualmente,
a = 0 V a = (a A a ) v a' = (a Va') A (a Va’) 
a' = u A (a V a ') = a V a ', de donde a <, a' (40)
Uniendo (39) y (40), se obtiene á = a', lo que demuestra
la unicidad.
3.° Para dos elementos cualesquiera a y b de T se verifican 
las relaciones:
a~AÍ = ? V 6 (41)
a V b = a A b (42)
En efecto:
(a Afc) A (J V 6 ) = (aA i, A fl )v ( flA6 A ft) = 0 V 0 = 0 
y
(a A¿>) V (a V ó ) = (a V a V 6) A (¿ V a V b) = u A u = u.
Por tanto a V 5 es el complemento de a A 6, y como este 
complemento es único se obtiene la relación (41).
Igualmente:
(a V fc) A (¡¡ A 5) = (a A a A 6) v (6 A a A ó) = 0 V 0 = 0 
(a V ó) V (a A 5 ) = (a V ó V a ) A (a V6 V ó ) = u A u = u. 
Por lo tanto a A ó es el complemento de a V b y, como este 
complemento es único, se obtiene la relación (42).
8. Otros retículos. - Otros retículos particulares son a menu­
do estudiados. Nosotros citaremos sólo dos nuevos modelos:
a) Los retículos modulares para los cuales a V (p A c) = 
= (a V ¿>) A c siempre que a < c y para cualquier a, ó,c.
RETICULOS 63
b) Los retículos libres que son engendrados por n elementos 
distintos o generadores, y contienen todos los elementos defi­
nidos a partir de estos elementos con las operaciones A y V.
Así para n = 2 el retículo libre debe contener los elementos 
a y b así como a A b y a V b y e s fácil verificar que este 
retículo de 4 elementos es libre.
En general, el número de elementos del retículo crece muy 
rápidamente con n y a menudo es muy conveniente imponer 
condiciones suplementarias para limitarle.
c) Añadamos aún que en un retículo se llama elemento irre­
ducible cualquier elemento, distinto del nulo y del universal, 
que no pueda deducirse de otros dos elementos por una de las 
operaciones A (irreducibilidad con respecto a la intersección) 
o V (irreducibilidad con respecto a la unión).
9. Aplicaciones. — Los retículos son utilizados para simpli­
ficar la transmisión y ejecución de programas operacionales.
Se puede estudiar así el conjunto de las señales diferentes, 
largas o cortas, que se pueden engendrar por los topes fijos 
sobre un árbol móvil. Como la construcción del árbol con topes 
es delicada, y el número de contactos y botones de selección 
puede aumentar fácilmente, es interesante simplificar al máximo 
el número de señales fundamentales de forma que obtengamos, 
combinándolas con ayuda de las operaciones Y y O, el mayor 
número posible de señales utilizables; uno es de esta forma con­
ducido a estudiar un retículo o un semirretículo engendrado 
por la realización concreta de estas operaciones por puesta en 
serie o en paralelo.
De una forma análoga se puede estudiar el conjunto de los 
programas de alumbrado de una lámpara con ayuda de los pro­
gramas fundamentales cuando se disponen estos programas en 
serie o en paralelo. El estudio del retículo distributivo de estas 
diferentes operaciones permite buscar la solución óptima del 
problema, es decir la solución más completa para un mínimo 
número de programas fundamentales.
Capítulo VIII
FUNCIONES DE BOOLE
Hemos definido en el capítulo III las funciones de Boole 
de n partes de un conjunto E; también se dice: función de n 
clases. Uno se propone escribir estas funciones bajo dos formas 
canónicas esenciales que introducen cómodamente las funciones 
de variables de Boole; utilizaremos para este fin dos tipos par­
ticulares de funciones de Boole: los términos minimales y los 
términos maximales.
1. Términos minimales. - Designemos por A ,, A ¡, A„ las 
n partes de E, por A, (i = 1,.... n) sus complementarios y to­
memos el conjunto de pares (At , A i) ,... (An, A„).
Se llama término minimal la parte de E que es intersección 
común de los_n elementos de! conjunto formado eligiendo en 
los pares (A¡, A j) precedentes un término y sólo uno.
Será, por ejemplo, un término minimal m¡:
m, = A, n a , n A j ... n An- , n A„ (43) 
El orden en que escribimos los A,- o los A/ es evidentemente 
indiferente ya que la intersección es conmutativa y asociativa. 
Se dice que m¡ es un término minimal de orden n igual al 
número de los A¡. Veamos algunas propiedades esenciales de 
los términos minimales.
a) Hay 2" términos minimales de orden n.
Para n = 1, hay evidentemente dos términos minimales posi­
bles A i y A¡. Supongamos que hubiera 2"~ 1 términos minimales 
de orden n - i y dispongámoslos sin omisión ni repetición en
FUNCIONES DE BOOLE
una tabla T. Si p¡ es un término minimal de esta tabla se for­
man, a partir de él, dos términos minimales de orden n ínter 
secándole bien con A„, bien con A„; son pues H A , y 
fij O A/|. Tenemos asi en una tabla T‘ todos los términos mi­
nimales sin omisión ni repetición. En efecto, no hay repetición 
pues dos términos de