El álgebra de Boole - latecnicalf.com.ar

G. C

asan

ova

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 complementarios, 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 imales, 68. - 5. Forma canónica conjuntiva, 69. -■ 6. Términos maximales 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. Sistema decimaL Código binario, 116. - 8. Organización de una calculadora, 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 efecto, 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, verdadero 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 calculadoras automáticas y de los ordenadores.

Este importante desarrollo moderno del cálculo electrónico es una consecuencia imprevista de las posibilidades de un lenguaje 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 comprendido 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 estos 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 ... nse 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 conjuntos abstractos. Sin embargo, será a menudo cómodo seguir estos razonamientos sobre esquemas; los más utilizados son los conjuntos de puntos 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 conducirí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 escribir:

14>}*<I>;esta desigualdad no es más que un caso particular de la desigualdad ( 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 un conjunto 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) Formemos el conjunto tp(E) para conjuntos E que tengan sucesivamente 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-


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) contienen 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 " elementos.

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 pertenecen 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 problema 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 evidentemente 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.


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 problema 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 efecto, 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 operaciones 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 convenientes 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 escribe 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 conjunto de los elementos que pertenecen a E , ó a E j , pero es necesario señalar que a veces en el lenguaje corriente, la conjunción O puede tener dos sentidos diferentes que sólo el contexto nos permite distinguir. Así, O es disyuntiva o excluyeme

cuando significa uno u otro pero no ambos, y es inclusiva cuando significa uno, otro o ambos a la vez. Sólo nos conviene este último sentido cuando O define la unión de dos conjuntos;


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). Todo 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, apelativo 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, mientras 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 pues una operación de paso a los complementarios.

Figura 5

El conjunto E es representado en la figura S por un rectángulo. 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.


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 pertenecer 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 cualesquiera 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 precedentes tienen numerosas propiedades tales como idempotencia, conmutatividad, asociatividad, distributividad.

Nosotros las estudiaremos después de haber dado sus definiciones 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 pensamiento matemático moderno.

Capítulo III

APLICACIONES FUNCIONES DE BOOLE. GRAFOS

La noción de aplicación cubre amplios dominios de la reflexió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 definició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 llegada 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.


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 imposible. 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 ' diferentes 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áneamente 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.


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 reciproca1. 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 inyecció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 conjunto 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 aplicació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 aplicaciones / 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.


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ápidamente nos apercibiremos de que su uso es por el contrario indispensable para clarificar las nociones matemáticas más diversas. Nos limitaremos aquí a dar algunos ejemplos que tengan relación con nuestro objetivo.


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 aplicaciones 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.


La importancia de las funciones características reside en el hecho de que nos hacen de cómodo intermediario entre el álgebra de conjuntos y el álgebra de Boole.

7. Producto de conjuntos. Proyectores. — o) Se llama producto 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 producto 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 queE /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-


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 aplicació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 aplicació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 considerar aplicaciones tales que un elemento a del conjunto de partida E admita una o varias imágenes en el conjunto de llegada F. Tales apücadones son llamadas aplicaciones multiformes o mejor, para evitar cualquier confusión, correspondencias.


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 denotan 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 correspondencia 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 aplicaciones se extiende a las correspondencias.

El grafo G de una correspondencia T es el conjunto de los pares (a, b) donde a e E 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 elementos 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 caballo 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 precedente. 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.


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 extremo 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.


(3) Se demuestra que podemos colorear G ', y por tanto el mapa, con sólo cinco colores de forma que dos países con frontera 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 completo 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 dificultad 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


/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 caracterí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, cualquier aplicación de E 2 en E recibe el nombre de ley de composició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


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 sucesivamente 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 aplica 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 idempotentes. 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 elementos 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 inmediatamente 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 asociatividad, y la segunda relativa a una ley a la vez asociativa yconmutativa.


d ) S i una ley interna es asociativa, al componer n elementos podemos reemplazar p elementos consecutivos por su compuesto 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 consecutivos, 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 conveniente 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.


6. Elemento neutro. — a) Dada una ley interna en un conjunto 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 todo b, c e E.

El elemento a es regular si es regular a derecha y a izquierda, 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 composición internas denotadas • y i , la ley • se dice que es distributiva 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 intersección. Probemos:

FU (ieIE')=ieI(FUE,) (23)


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-


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 ley

la 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 evidentementebiyectiva. 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 definido un isomorfismo.

10. Estructuras. — Las leyes de composición interna permiten 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 necesita 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 espacio vectorial o como las diferentes estructuras de espacios topológicos.

El estudio de las estructuras ha tomado una importancia considerable en matemáticas modernas bajo la influencia de la escuela bourbakista. Aunque este estudio no puede pretender cubrir la totalidad de la actividad y reflexión matemáticas, ha provocado, por su misma generalidad, un enriquecimiento y un prolongamiento considerables de esta actividad y de esta reflexión.

1 Ver L algebre múdeme de M. QUEYSANNE y A. DELACHET (Colecció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 definen 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 referencia E al conjunto de los entes matemáticos actualmente definidos por los matemáticos. Un subconjunto E | se dice caracterizado 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 propiedades 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 implicació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 correspondientes 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 yE 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 utilizando 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 verifica.

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-


b) A verdadera; B verdadera; C falsa; D verdadera; E verda-

Se hubiera podido llegar a este resultado únicamente razonando, 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 “cualquiera que sea” y es utilizado para escribir que todos los elementos 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 pertenece 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 reemplazá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 subconjunto 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 parcialEn 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 enteros 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 relació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 siempre por a < b una relación de orden cualquiera sobre un conjunto y escribiremos a < b si a=t=b.

4. Cadenas. - a) Cuando la relación de orden sobre E es parcial, un subconjunto de E totalmente ordenado por esta relació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 subconjunto 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 divisores 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 cadenas1, 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 ordenada 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.


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 relació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 ejemplo, 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 superior 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 relacionados 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.


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 relacionarse por un camino al menos en G; se dice queG es fuertemente 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 antisimé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 admite circuitos, las relaciones Ay á? Am y Am 9t Ay son incompatibles.

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 parcialmente 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 particulares. 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 extremos 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 conjunto 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 conjunto 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.


b) El conjunto N ’ ordenado por a I b es un retículo. Es suficiente 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 divisor y del mínimo común múltiplo, los extremos de {a, ó}.

Se puede además demostrar que las operaciones A y V aidefinidas 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 comunes 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 vectorial 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 evidentemente 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 particularmente 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)


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 parcialmente 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 aplicando 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.


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ículo pues 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 vacío E es un retículo distributivo ya que las leyes A y V son respectivamente O y U, operaciones que sabemos son distributivas 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 intersecció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 tienen 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 importantes 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 relación de (38): r = O V x = r V O (conmutatividad). Finalmente, x < x y x < u implican x < u A x ; mientras que u A x < x de donde, uniendo ambas, tenemos la segunda relació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 á)


(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 demuestrala 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 menudo 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 definidos 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 irreducible 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 simplificar 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 conducido 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 programas 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 particulares 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 tomemos 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 forman, 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 minimales sin omisión ni repetición. En efecto, no hay repetición pues dos términos de T difieren o en el p¡ o en el último elemento; no hay omisión pues si m¡ es un término minimal de orden n, se obtiene, suprimiendo el último elemento, uno de orden n - 1 que figurará en T y a partir de él por el método de formación precedente, tiene necesariamente que figurar m¡ en T'. En T‘ hay pues 2" ~ 1 • 2 = 2" términos ya que a partir de u¡ sé forman 2 términos minimales distintos. La proposición está pues demostrada por recurrencia.

b) Dos términos minimales del mismo orden son dis/untos.Sean m¡ y m¡ dos términos minimales de orden n. No pue

den formarse eligiendo en todos los pares (A/, A/) el mismo elementó pues serían idénticos; es decir que uno de ellos contiene por ejemplo Ai y el otro A i, y su intersección por lo tanto está contenida en Ai n A'i que es 0, es decir que:

c) La unión de todos los términos minimales de orden n es el conjunto E.

Sea x un elemento cualquiera de E. Pertenecerá a Ai o a A i, a Aj o a A j , ... a A„ o a A„, es decir a uno de los términos minimales y por lo tanto a su unión. Escribiremos, para todon:

E * (U * |( con I = {1,2.......2"}

2. Forma canónica disyuntiva. — Demostremos el siguiente resultado:

Toda función f ( A , An) de n partes de un conjunto E,que no sea vacia, puede ponerse, de forma única, como unión de términos minimales de orden n. Se dice que la función /( A i, A j , .... An) está puesta en la forma canónica disyuntiva. Se llama argumentos de / a A i, A j,.... An.


а) Demostremos en primer lugar que si la descomposiciónexiste, es única. Supongamos, en efecto, que f(A ¡, Aj A„)=é0puede escribirse de dos formas diferentes como unión de términos minimales.

Um, = Um/ = /( A ,,A J ......A„) (44)

Estas dos formas diferirán al menos en un término minimal no vacío, por ejemplo m i, que figura, por ejemplo, en el primer miembro de (44) y no en el segundo. Todo elemento de rh¡ debe pues figurar en / ( A i , A j , .... A„) que es un subconjunto de E, por la primera forma de descomposición, pero por la segunda descomposición no figura en él ya que m/ n m , = 0 para todo / # 1. Por lo tanto debemos rechazar el supuesto, lo que prueba la proposición.

б) Cualquier parte A¡ de E puede ser puesta como unión de términos minimales de orden n, de argumentos A ,, A2, .... A,-. .... An-

Sea m¡ un téimino minimal cualquiera de orden n - 1 que tenga por argumentos A], A -. ..., A /_i, A /. , , A„, es decir las n - 1 partes A/ con /

Formemos U (m¡ O A,-). Es una unión de términos minimales

de orden n que se escribe por la distributividad.A/ n ( U m¡) = A; O E = Af,

ya que la unión de todos los términos minimales de orden dado (aquí n - 2) es E. De aquí el resultado.

c) Demostremos la existencia de una forma canónica disyuntiva para cualquier función de n partes A |, A2,..., A„.

Consideremos para ello una unión cualquiera p de términos minimales de orden n que escribimos:

p = U (<*/ n m¡) (45)

con 1 - {1,2 ,. . . . 2") y a¡ representando bien el conjunto vacío, bien el conjunto E del que los A/ son subconjuntos.

FUNCIONES DE BOOLE 67

Si a¡ = t/>, a¡ O m¡ = <t>, y m¡ no figura en la unión dada por la fórmula (45).

Si <*í = E, a, n m¡ = m¡, y m¡ figura en la unión. Designemos por F el conjunto de estas uniones p.

Como todo argumento de la función / puede ponerse, como se ha visto, en la forma (45), y como toda función de Boole se obtiene a partir de los A,- por un número finito de operaciones intersección, unión y complementaron; es suficiente probar que F es estable para cada una de estas operaciones para probar que una función de Boole cualquiera es unión de términos minimales. Sean p¡ y p2 dos elementos de F, es decir dos uniones de términos minimales, de la forma (45).

1.° La unión p, U p2 es evidentemente una unión de términos minimales, de la forma (45), ya que los términos minimales son disjuntos dos a dos.

2.° La intersección p, n p2 es la unión de los términos minimales comunes a pi y p2 ya que dos términos minimales distintos son disjuntos.

3.° Como p t U p¡ = E, se obtiene finalmente p, como unión de todos los términos minimales de orden n que no figu-

Así tenemos probada la estabilidad, y por lo tanto la existencia de la forma canónica disyuntiva está demostrada.

Como también se ha probado la unicidad, el teorema es válido pues en el caso general de una función / ( A i , ..., An) no vacía. Si / ( A i , ..., A„) fuese vacío, se debe tomar en (45) a¡ = <p para todo i y solamente podemos decir que el conjunto vacío es una unión bien definida de términos minimales.

3. Ejemplos de descomposición. — Indicaremos sobre un ejemplo cómo podremos efectuar prácticamente esta descomposición.

Sean A, B, C tres subconjuntos de E y la función

/(A , B, C) = A U (B D C ) U (A n B)El método teórico nos da también un método práctico para

EL ALGEBRA DE BOOLE

su búsqueda; es sin embargo preferible simplificar, en lo posible, la expresión dada de la función. Ahora bien,

A U(B n C) = A n (B UC) aplicando las fórmulas de de Morgan.

Utilizando luego la distributividad:A n ( B u c ) = ( A n B ) u ( S n c )

de donde tenemos: /(A , B, C) =(A O B )U (A n C).■ Es ya una unión de intersecciones, pero no una unión de

términos minimales.Para introducir aquí éstos, es necesario que aparezcan C,C

y B, B. Ahora bien:Á n B = ( Á n B n c ) u ( A n B n c )

pues cualquier elemento de A O B pertenece a C ó C y lo es por lo tanto de A n B n C ó de A n B f~i C y, en consecuencia.

Operamos de forma análoga en A n C y finalmente se ob-

/ ( A, B,C) = ( Á n B n c ) u ( A n B n c ) u ( A n B n c ) que sí es unión de términos minimales.

Veremos en el capítulo siguiente un método de puro cálculo para llegar al mismo resultado.

4. Términos maximales. — Existe una segunda forma canónica para una función de Boole, llamada forma canónica conjuntiva, y de cualquier forma, dual de la precedente.

Definimos, para llegar a ella, los términos maximales sustituyendo en (43) el signo O por el signo U. Si M, es un término maximal de orden n, se obtiene de este modo:

Mí = A, U A2 U A3 U ... U A„ _ , U A„ (46)

a) Hay 2n términos maximales de orden n.La demostración es evidentemente toda ella análoga a la he

cha para los términos minimales.


b) La unión de dos términos maximales del mismo orden es el conjunto E.

Como resulta de las fórmulas de De Morgan que el complementario en E de un término minimal es un término maximal del mismo orden, tendremos en consecuencia, que a toda propiedad de los términos minimales, corresponde una dual de los términos maximales que se obtiene por paso a los complementa-

Sean, por ejemplo. Mí y M/ dosjérminos maximales cualesquiera de orden n. Por lo tanto M,- y M/ son dos términos minimales y M¡ D M/ = $.

De aquí, por paso a los complementarios, tenemos la pro-

M/ U M/ = E.c) La intersección de todos los términos maximales de or

den n es el conjunto vacio.En efecto, f l M, = U M, = E.con I = {1,2.......2") ya que

/ e l _ r e íel conjunto de los M,- es el conjunto de los términos minimales cuya unión es el conjunto E_(pág. 65).

Por lo tanto fl^ M,- = E = tj>, de donde tenemos la propo-

5. Forma canónica conjuntiva. — a) Tomemos de nuevo la descomposición ya efectuada de una función no vacia en la forma canónica disyuntiva, es decir la fórmula (45):

/(A /) = | (a,- O mi),

con I = {1, 2 .......2") y /(A ,) representa / ( A , , A ,. .... A„).La función complementaria f (A,) se descompone de una

sola forma según:7 (A ,)= .U (5 ¡ n mi) (47)

ya que su descomposición debe contener los términos minimales que no figuran en el desarrollo de / , y sólo ellos.


Tomemos el complementario de (47). Se obtiene de forma

/(A/) = (a¡ U m¡)

Si o/ = 0, a¡ U m¡ = m¡ que figura por ello en la descompo-

Si a¡ - E, Bj U m¡ = E, elemento neutro de la intersección, y m¡ no figura eil la descomposición. En definitiva tendremos, poniendo:

m¡ = M,-la descomposición de f en la forma canónica conjuntiva, es decir en forma de intersección de términos maximales:

/ = . n f a U M ,) (48)

siendo la descomposición evidentemente única.b) Tomemos de nuevo la descomposición en términos mini

males de la función /(A , B, C) estudiada anteriormente: / ( A ,B ,C ) = ( A n B n c ) u ( A n B n c ) u ( A n I n c ) .

Para aplicar (48) se escriben los 5 términos minimales (23 — 3 = 5) que no figuran en la descomposición anterior. Sean éstos:A n l n c , A n B n c , a n b n c , A n B n c , A n B n c

y se forma por la intersección de sus complementarios, sea:/(A , B ,C )= (A U B U C )n (A U B U C )n (A U B U C )n

(A U B U C )n (Á U B U C ). Esta regla de formación de la forma canónica conjuntiva a

partir de la disyuntiva, resulta de forma inmediata de la comparación de las fórmulas (45) y (48).

Esta comparación nos muestra qué si (45) contiene p términos, es decir p términos minimales, la forma canónica conjuntiva (48) contiene 2" — p términos maximales, de tal suerte que el número total de términos minimales y de términos maximales en las dos descomposiciones de una misma forma es 2".


6. Términos maximales y términos minimales. — Justifiquemos ahora el nombre de término maximal y de término minimal.

a) Si m (A j) es un término minimai cualquiera de orden n donde los A¡ (i = 1, 2 ,..., n) son los argumentos, no existe ninguna función de Boole f (A¡) de estas n partes que sea diferente de m(A¡), no vacia y esté contenida en m (A j).

Supongamos, en efecto, que existe / (A ,) # é y distinta de m (A/), tal que/(A ,-) C m(A,-). Esta función/(A ,) puede, después del teorema general, descomponetse según una forma disyuntiva conteniendo al menos un término minimal no vacio m (A/) y se deberá tener:

m C \m = m'(Af), ya que m (A/) C /(A /) C m (A,). Ahora bien, la intersección de dos términos minimales diferentes es el conjunto vacio; por tanto la proposición está demostrada y por ella justificado el nombre de término minimal utilizado.

b) Igualmente, no existe ninguna función de Boole que contenga un término maximal, y sea diferente de este término maximal o de E. (El término maximal y la función están formados a partir de los mismos argumentos A;.)

Sea, en efecto, / (A ,) una función tal que /(A /) + M (A,) y / (A ,) * E tal que /(A /) O M (A,).

De esta inclusión se deduce:7 (A ,)C M (A/).

Ahora bien, M (Aj) es im término minimal y después del resultado anterior tenemos / = ó ó f =M de donde:

/(A j) = E o / ( Aj)=M(Aj), con lo que tenemos demostrada la proposición.

c) Aplicando las definiciones de unión y de intersección dadas en el primer capitulo para la unión e intersección de conjuntos, se numeran fácilmente las reglas de formación de la unión o de la intersección de dos funciones de Boole puestas en forma conjuntiva o disyuntiva.


7. Funciones características. - Recordemos la definición de función característica / (A; x) de una parte A de un conjunto E, dada en el capítulo III:

V x€A , / ( A ;x ) = l y V x£ A ,/(A ; x) = 0

a) Función característica de una intersección.Sean A y B subconjuntos de E. Se verifica:

/ (A n B; x) = /(A ; x ) ■ /(B ; x) (49)pues, V x£ AH B, / (A ;x )= /(B ;x ) = 1, mientras que, para todo x que no pertenezca a la intersección, o bien /(A ; x) = 1 y / ( B; x) = 0, o bien f ( A; x) = 0 y /(B ; x) = 1 o bien /(A ;x )= /(B ;x ) = 0.

b) Función característica de una unión.Introduciremos la operación suma lógica -también denomi

nada suma digital- que denotada + viene definida por la tabla:0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1

Esta suma + no debe ser confundida con la suma ordinaria; es por ello por lo que colocamos un punto sobre el signo +. Entonces se verifica:

/ (A U B; x) = /(A ; x) + /(B ; x) (50)Comprobemos que es cierto en tos cuatro casos posibles:1.° Si x e a y x € B: /(A ; x) = 1 ,/(B ; x) = 1 y

/(A U B X) = 1.2.° Si x e a y x « B : /(A ; x) = 1, / ( B; x) = 0 y

/(A U B X) = 1.3.° Si x ? A y x € B: /(A ; x) = 0, / ( B; x) = 1 y

/(A U B x) = 1.4.° Si X e A y x * B: /(A ; x) = 0, / ( B; x) = 0 y

/(A U B x) = 0.


Se puede también expresar /(A U B ;x) por medio de la suma y del producto ordinario pues es suficiente escribir:

/(A U B:x) = /(A ;x) + / ( B ;x ) - /(A ;x ) • / (B;x),

o también por (49):/ (A U B ;x )= /(A ;x ) + / ( B ;x ) - / ( A n B;x)

la comprobación en cada caso es inmediata.Se podría pues pensar, desde un punto de vista puramente

abstracto, que la suma lógica no es más que una notación cómoda que simplifica la escritura con el precio de nuevas reglas de cálculo. En efecto, es la suma lógica y no la ordinaria una operación fundamental en la teoría de circuitos eléctricos que además se introduce de forma natural.

Ppr razones de simetría se introduce en esta teoría'el nombre de producto lógico para el producto ordinario, pero ambas operaciones son idénticas.

c) Función característica de una negación.La relación

/ ( A ; * ) = l - / ( A ; x ) (51)

es evidente, y / ( A;x) se expresa en la forma / (A;x).

Capítulo IX

A LGEBRA BIN A RIA

1. Variables de Boole. — Cuando los subconjuntos A¡ de E son las variables o argumentos de una función de Boole, se llaman variables de Boole a sus funciones características x , = /(A ,; x).

Estas variables no pueden tomar pues más que los valores 0 y 1 y, en consecuencia, se les llama a menudo variables binarias.

Si x¡ es una variable de Boole, 1 - x¡ es también una variable de Boole, que denotamos x¡. De aquí la relación de negación lógica que es válida para todo i :

X,= l - X , (52)

2. Funciones de variables de Boole.—Sea B = /(A j, A j , ..., A„) una función de Boole que escribiremos / ( A¡) = B. Los conjuntos B y / (Aj) al ser iguales, tienen la misma función característica. Sea y = /(B ; x ) la de B.

El conjunto /(A j) se deduce de los conjuntos Aj por las operaciones de unión, intersección y de negación. Su función característica y , se deduce pues de las x¡ por las operaciones lógicas (49), (50) y (51), es decir, por el producto, suma y negación lógicas. Resulta que y es una función de las Jtj, asociada a la función /(A j), que se llamará función lógica de / o función de las variables de Boole.

Se escribirá:y=< p(xI,x2 xn) o y = v (x j) (53)

con x¡ = f { A ¡ \x ) e _y=/(B;.x).

ALGEBRA BINARIA 75

3. Propiedaaes de las funciones lógicas elementales. - Lasfunciones lógicas elementales son el producto, la suma y la negación lógicas. Sus propiedades resultan directamente de las de la intersección, unión y complementarión de conjuntos.

Dados los conjuntos A, B, .... L, designaremos por a, b , ..., / las variables de Boole correspondientes y por a, b. ...,7 sus complementarias I - a, 1 b , ..., 1 - /.

1. Como la intersección y la unión son idempotentes, se puede escribir:

para cualquier variable de Boole a.

2.° Como la intersección y la unión son conmutativas y asociativas, también lo serán el producto y la suma lógica:

ab=ba\ a + b = b + a ab - b a ; a + í = f> + a .

Escribiremos pues los productos y las sumas lógicas de n variables sin paréntesis, y se utilizarán las notaciones:

2a / = a , + a2 + ... + a„,

si a i , a2. ...,a„ son n variables de Boole (obsérvese el punto sobre el signo 2 ).

3." Como la unión e intersección son recíprocamente distributivas, tenemos:

a 2 a , = 2aa, y a + IIa , = FI (o + a,) (54)

Desarrollemos (54) para /'S {1, 2,3}:

a (a , + a2 + a j) = aa, + aa2 + aa3; a + a ,a 2a3 = (a 4- a , ) (a + a 2) (a + a3).


4.° Las fórmulas de De Morgan nos permiten el paso a las variables complementarias a¡ :

¿ a ,= I l í , y lia,-= ¿ 5 , (55)

Desarrollemos(55)para /€ { 1 ,2 ,3 ):

a , + a2 + a3 =a , a , a3 y a, a2 a3 = a, + á2 +a3

Como aplicación podemos obtener el resultado siguiente:La suma lógica de n variables es nula si y sólo si lo son cada

una de ellas:¿ a , =0=»a, =Bj ... =a„ =J0..

Apliquemos (55): ¿a,- = 1 » 115/ = 1, es decir, a,- = 1 para

todo i y por consiguiente a¡ = 0 para todo i.Las reglas del producto son las del álgebra ordinaria, pero

las de la suma lógica difieren sensiblemente y así las reglas de cálculo para las fórmulas de este álgebra lógica no deben ser confundidas con las habituales del cálculo algebraico.

4. Suma disyuntiva. - La función lógica llamada suma disyuntiva' que representamos a © b juega un papel muy importante en el cálculo numérico binario utilizado en las calculadoras automáticas.

Sea / (A, B) = A ffi B el conjunto formado a partir de dos A y B por los elementos que pertenecen a uno de los conjuntos, pero no al otro (ftg. 12).

ALGEBRA BINARIA 77

Por tanto, ¡ ¡ j E A S B , pertenece a A y a B o bien a B y a A. Es decir x e A ó_x € B utilizando la O, en el sentido disyuntivo, y A © B = (A n B) U (B n Á).

Pasando a las funciones lógicas:

a © b = ab + b a

Examinemos todos los casos que se nos pueden presentar:

l . ° a = 6 = 0 = » ñ = 5 = l=»affif> = 0.2 ° a = 1, ft = 0 a =0 , b = \* » a ® b = l.3 ° a = 0, b = l =>á = l , b =0=»a©i> = l.4 ° afF& = l= » a = S = 0 '» f lf f ib = 0 .

De donde la tabla de la suma disyuntiva es:

0 © 0 = 0° ® 1=1 ÍCAti ® o = i l56>1 0 1=0

5. Propiedades de la suma disyuntiva. - 1P La suma disyuntiva es conmutativa y asociativa.

La conmutatividad resulta de la tabla anterior. Para la asociatividad será necesario probar que

(a ffib) © c =a © (6 ©c)

en todos los casos posibles.Si a = 0 la propiedad es inmediata. Si a = 1 y b = 0 , también

es evidente, pues 0 es el elemento neutro de la suma. Si a = b = 1 es necesario verificar c = 1 © (1 © c), lo que se hace fácilmente tomando c = 0 y c= 1.

i Por consiguiente podemos escribir en cualquier orden y sin paréntesis una suma disyuntiva de n variables:

2 ° La suma disyuntiva no es distributiva respecto al producto:

a © be 1= (a © ¿>) ■ (a © c).Basta comprobarlo para a = 1, 6 = 0 y c = 1.3.° El producto es distributivo respecto a la suma:

a(b © c)=ab ®ac

Es clara la igualdad si a = 1 y si a - 0 cualesquiera que sean b y c.

6. Operación de Sheffer. - Dados dos conjuntos A y B, esta operación queda definida por la función S(A, B):

S(A, B) = Á U B (57)

Su función lógica s es:s = a + b (58)

Es de señalar que:

S(A, A) = A U A = A (complementación)S (A, B) = A O B (intersección)S(A,B) = A U B (unión).

La operación S (A, B) de Sheffer permite así obtener todas las operaciones del álgebra de conjuntos.

Otra operación, la de Pcirce o negación de la suma lógica, definida por

P(A, B) = A U B = A n B posee, como fácilmente puede .comprobarse, las mismas propiedades.

Puede demostrarse que estas operaciones S y P son las únicas funciones de dos variables que nos permiten expresar todas las demás. Por otra parte este resultado no tiene más que un interés teórico puesto que actualmente no se saben realizar estas operaciones sin pasar por las operaciones elementales.


ALGEBRA BINARIA 79

7. Formas canónicas. - Toda función lógica •p está asociada a una función de Boole f que puede escribirse en la forma canónica disyuntiva:

f(A¡)= Ut(a,nm¡).

Designemos por ¡p¡ la función característica del término minimal m¡ y conservemos a¡ para designar la del conjunto a¡. Se

¥>(*/)=<*i¥>i + . - + <*p¥>p con p = 2", ya que hay 2" términos minimales, o sea:

lfi(xi) = Í a i ifi¡ (59)

Como existen 2" términos minimales y dos posibles elecciones para a/, hay 22 funciones lógicas asociadas a igual número de funciones de Boole. Este número crece muy rápida-

La expresión (59) es la forma canónica disyuntiva de una función lógica.

b) De forma análoga, la descomposición de cualquier función de Boole, como unión de términos minimales conduce a la forma conjuntiva, la más general de las funciones lógicas aso-

•fi = II (a,- + <P¡)

siendo <t>, la función característica del término maximal M, = m¡. Por tanto:

* / = * y * = n (<*, + */) (60)

Las fórmulas (59) y (60) no deben hacemos ilusiones. Recordemos que en (59) no figuran en definitiva más que los <p¡ correspondientes a a,- = 1, ya que o,- <p¡ = 0 si a¡ = 0, y que en (60) figuran sólo los íp¡ correspondientes a a,- = 0 ya que I + yy = I , cualquiera que sea ¡p¡, y que este factor 1 no modifica el producto.

EL ALGEBRA DF. BOOLE

8. Ejemplo de función lógica. - Tomemos de nuevo la fundón ya estudiada:

/(A , B, C) = A U (B D C ) U (A flB )Designemos por a, b, c, las funciones de Boole que son fun

dones características de los conjuntos A. B y C. Si <f es la función lógica asodada a / , se escribe:

•fi = a + b c + ab

Transformemos el segundo miembro según las reglas del álgebra lógica:

y como b • c = b + c resulta:

= a (ó + c) + ab =ab + a c + ab,

lo que corresponde efectivamente al primer resultado anteriormente obtenido. Para escribir ip en la forma disyuntiva es suficiente introducir c + c = 1 en el primer producto y b + b = 1 en el segundo. Se obtiene:

<p = ab(c + c ) + a c (b + 5 ) = ábe 4- abe + aT¡c (61)

Para escribir ip en forma conjuntiva se forma el producto de los complementarios de los términos minimales que no figuran en el segundo miembro de (61). Será:¡p = (a + b + c )(3 + b + c )(a + b + c) (a + b + c)

(a + b + c)

El álgebra lógica conduce así al resultado de forma metó-

9. Aplicación a la lógica. - Esta álgebra binaria se aplica al estudio de problemas de lógica análogos a los estudiados en el capítulo V.

ALGEBRA BINARIA

En efecto, una propiedad^ es verdadera para un elemento .* de un conjunto E si x pertenece a un subconjunto Ei de E. Se puede pues poner, si Jr, es una variable de Boole definida sobre E ,, x , = 1 si 9 es verdadera y x t = 0 si & es falsa, ya que x , = / ( E , ; x).

Recordemos el enunciado del problema que y a hemos estudiado.

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 reciprocamente.5.° A es verdadera.La “O " es siempre inclusiva y en teoría de conjuntos se

1 ° E C ( A n I ) n ( C U D ) .2.° A n (BU C)C D.3.° BC A.4.° C C D y D C C osea. C = D.Pasemos a las variables de Boole que son respectivamente

a, b, c, d, e para los conjuntos A, B, C, D, E caracterizando las propiedades.

Es suficiente señalar que A n B = A «*A C B para escribir las igualdades lógicas que correspondan a las cuatro condiciones precedentes, ya que A C B equivale a ab = a después de lo señalado.

1.° é a H c + d ) = e.2.n a { b + c ) d = a ( b + c ) .3.° a b = 5.4.° c = d.Se sabe que a = 1, por tanto a = 0 y por 1 e = 0, que im

plica e = 1; de 3.° se deduce b = 0, es decir b = 1.De 2.° obtenemos: (b + c ) d = b + c de donde cd=c que

siempre es cierto a la vista de 4 °

En definitiva A, B, E son verdaderas y C y D son incompatibles; es el mismo resultado ya obtenido anteriormente, pero este último método de resolución es más sistemático.

10. Aplicaciones a la teoría de grafos. - Podemos utilizar los resultados precedentes para completar las nociones sobre giafos que han sido expuestas en el capítulo III.

a) Funciones características.Recordemos que se definió sobre:

E = {A ,.A , ... An} el grafo completo simétrico R, que contiene todos los arcos A,• Ay; un grafo G, defmido sobre E, es un subconjunto de R cuyos elementos A/ Ay se designarán por x¡¡.

La función característica F(G; x¡¡), de G está definida por las condiciones:

F(C;x,/) = l si A¡ Ay e G ,F(G;x//) = 0 si A/Ay$G.

Si G y G' son dos grafos definidos sobre E y si G es el complementario de G en R, se obtienen sin dificultad las relaciones:

F(G U G'iXff) = F(G;x,y) + F(G'; x,y)F (G n G '; x¡¡) = F(G ;x¡j) • F(G’;x/y)F (G; x¡¡) + F (G; x¡¡) = 1,

el signo + de la última relación no lleva superpuesto ningún

b) Matrices de grafo.1.° Pongamos a/y = F (G; x¡¡).Los a/y no pudiendo tomar más que los valores 0 ó 1 son

variables de Boole en número de n2 y se pueden disponer, en consecuencia, en una tabla cuadrada o matriz que se denotará:

M(G) = (a,y)siendo i el índice que designa la línea y / la columna.


ALGEBRA BINARIA 83

A todo grafo G parte de R se le puede asociar una matriz de orden n cuyos términos son 0 ó 1; recíprocamente, a toda matriz de orden n cuyos términos son 0 ó 1, se puede asociar un grafo G parte de R.

Si G es simétrico a,y' = a¡¡ para cualquier i¡ y M(G) es una matriz simétrica1, es decir, igual a su traspuesta, lo que se es-

M(G) = 'M(G)Si G designa el grafo complementario de G en R, se obtiene:

M (5 ) = («$•),

cada término de M (G) se sustituye por su negación lógica dada según la relación (S2).

Si G es antisimétrico, se verifica claramente que:M(G) = 'M(G)

2.° Consideremos de nuevo el grafo estudiado en el capítulo III y definido por la correspondencia T dada sobre E = {A |, Aj, A3, A4} por las relaciones:

r (A ,) = A ,.A 2; r (A j) = A3,A 4: r(A 3) = A ,,A 4; r(A 4) = A |, A2, Aj.

Este grafo G contiene los arcos A i Aj, Aj As, Aj A4, Aj A[, A3 A4, A4 A ,, A4 A2, A4 A3 y el arco nulo Ai Ai y solamente a ellos. Por lo tanto su matriz asociada M (G) será:

matruiel (Colección “Que sais-je?" n.° 927), Prcsscs Universilaircs (edición castellana de editorial Eudoba), o también G. Casanova. Mathé- matiques spécioles, Uvr. I, París, Ed. E. Belin.

EL ALGEBRA DE BOOLE

3.° Resultan sin dificultad de las fórmulas (49) y (50) las matrices de la intersección y de la unión de dos grafos G y G', partes de R y de matrices M (G) = (ay); M (G') = (a}/).

Se obtiene de este modo:M (G n G') = (ay • ay) por (49)M (G U G ') = (ay + a'y) por (50),

de esta última relación puede también escribirse:M(GUG') = M(G) + M(G'),

por definición de la suma lógica de dos matrices de grafos.4.° La matriz asociada a R cuyos términos son todos iguales

a 1, la designaremos por J, siendo fijo el orden n.c) Producto lógico de matrices de grafo.1.° Se define un producto lógico de dos matrices de gra

fo M (G) y M (G ) como el producto habitual de dos matrices sustituyendo las sumas ordinarias por sumas lógicas de forma que si se designa por P = (py) el producto lógico de M (G) por M(G') se obtiene:

Pij - ¿ i ay, • a'i¡/, siendo k un índice de sumación que varia de 1 a n.

d) Las definiciones de la suma y producto lógicos se generalizan sin dificultad a un número cualquiera de matrices de grafos y se verifica la asociatividad y conmutatividad de la suma y la distributividad del producto respecto a la suma.

e) Formemos el cuadrado lógico de la matriz M (G). Su término general py será igual a 1 si y sólo si existe al menos un k tal que a,* = a*/ = 1 por la propiedad fundamental de la suma lógica, es decir si existen al menos dos arcos A¡ A* y Ak Aj que pertenecen a G lo que equivale a decir: si, y sólo si existe al menos un camino A,- A* A/ que pertenece a G. Así el cálculo del cuadrado lógico de la matriz M (G) permite determinar los puntos enlazados entre sí por un camino formado por dos arcos a lo sumo, y determinar estos arcos.

ALGEBRA BINARIA 85

Por recurrencia, se demuestra que el cálculo del producto lógico de p matrices de grafos que sean iguales a M (G) permite determinar los puntos enlazados entre sí por un camino formado por p arcos a lo sumo y determinar estos arcos. Escribiremos MP (G) para designar la matriz del producto. Este resultado nos va a conducir a un criterio muy simple de fuerte conexidad de un grafo.

/ ) Grafo fuertemente conexo.1.° Se dice que un grafo es fuertemente conexo si existe al

menos un camino que una dos puntos cualesquiera.El ejemplo siguiente muestra el interés de este concepto.Sea E un conjunto de personas A) ... An que constituyen una

asociación de la que ellas son miembros. Si la persona A, puede comunicar directamente con la persona A/ se dirá que el arco A,- Aj pertenece al grafo G de la organización que así queda definida. En general G será simétrico, es decir que si A/ puede comunicar directamente con A/, también recíprocamente Ay puede comunicar con A/, pero esta condición de simetría no se supone que se cumpla necesariamente. Si esta asociación quiere utilizar una red de comunicaciones bien organizadas es necesario que cada miembro A; de la asociación pueda comunicar con cualquier otro miembro de ella Ay, bien sea directamente o por intermedio de otros miembros de la asociación. Esto ocurrirá así si y sólo si G es fuertemente conexo.

2.° La matriz asociada a un grafo puede ser utilizada para obtener un criterio simple de fuerte conexidad.

En efecto, como hay n puntos Ay, un camino admite como máximo n - 1 arcos de tal forma que si, y solamente si, G es fuertemente conexo, la matriz M" (G) es igual a la matriz J. Es pues suficiente calcular M" 1 (G) para poder decidir si el grafo es total. Consideremos, por ejemplo, la matriz M (G) del grafo G ya estudiado. Su cuadrado lógico M! (G) será igual a:

EL ALGEBRA DE BOOLE

y su cubo lógico M3(G) es igual a J, por lo tanto el grafo es total.

g) Caminos hamiltonianos.1 -° Se dice que un camino es hamilloniano si contiene una

vez y una sola cada vértice del grafo.Demostremos con motivo de estos caminos el teorema de

Rédei:S i un grafo G es completo, existe en G al menos un camino

hamilloniano.Supongamos que el teorema es falso y sea p < n el máximo

número de vértices que pertenecen a un camino X de G. Como G contiene al menos un arco, p existe y es mayor o igual que 2.

Siempre es posible, basta un cambio de notaciones, suponerque los p vértices de X son los vértices A i , A j Ap del grafo.Escribimos:

X = A» A2 ... Ap .Veamos que, dado un vértice A4 que no pertenezca a X,exis

te un camino X'que contiene a A , y a losp vértices Ai, Aj ...Ap , es decir que existe un entero k tal que

X = A, ...A* A q A * ,, ... Ap ; si k = 0, A será el primer vértice de X’ y si k = p, Aq será el último.

Utilicemos la matriz M (G) asociada a G recordando que a¡¡ = 1 si, y sólo si. A,- A¡ € G.

Como el grafo es completo, la suma lógica a¡¡ + a¡¡ es igual a 1 para cualquier ij. Por consiguiente:

Si aq i = l, \ q A | 6 G y X’ existe.Si aql = 0 , entonces alq = 1 y si a , , = 1, A, A , A2 € G,

y X' existe.Si aq t = 0, entonces a2q = 1 y si aq i = 1, A2 A? A3 6 G

y X' existe; así sucesivamente de forma que, o bien tenemos probada la existencia de X, o bien se obtiene aqp = 0 y por lo tanto apq = 1. En este caso, Ap A , e G y X' existe y tiene Aq como último vértice.

ALGEBRA BINARIA 87

Así existe un camino A' que contiene p + I vértices de G en contra de la hipótesis: el teorema de Rédei está probado.

2.° Apliquemos este resultado a un problema de búsqueda operacional.

Sean n equipos que disputan un torneo enfrentándose dos a dos de todas las formas posibles. Se dice que A¡ A /6G si el equipo A,- precede al equipo A/ lo que ocurre si, y sólo si, el equipo A/ ha superado al equipo A/ o si ha empatado con él.

El grafo G es evidentemente completo y después del teorema de Rédei existe al menos un camino hamiltoniano, es decir, que se pueden colocar todos los equipos, cualesquiera que sean los resultados del torneo, en. una sucesión al menos, tal que cada equipo preceda al siguiente.

h) De una forma general, el álgebra de Boole tiene numerosas aplicaciones1. Vamos a ver cómo se utiliza para estudiar algunos circuitos eléctricos, en particular las cadenas de contacto, antes de dar indicaciones sobre los principios de funcionamiento de calculadoras numéricas.

Capítulo X

ALGEBRA DE LOS CIRCUITOS

1. Generalidades. - a) Sean x e y los extremos de entrada y salida de un dipolo entre los que existe un contacto A que puede estar abierto o cenado.

Si el contacto está abierto (fig. 13) -se dice también en reposo— la comente no pasa. La función de estructura del circuito tomará en este caso el valor 0.

Si el contacto está cerrado (fig. 14) -se dice también trabajando- la corriente pasa. La función de estructura del circuito tomará en este caso el valor 1.

Si se asocia al contacto A la variable de Boole ir y si se designa por /(A ) la función de Boole o función de estructura del circuito, se pondrá por definición de /(A):

a = 1 significa que el contacto está cerrado, a = 0 que está abierto. Naturalmente podemos hacer el convenio inverso: a = 1 si el contacto está abierto, y a = 0 si cerrado. Se dice en este caso que se trabaja en lógica negativa. Utilizaremos constantemente los convenios de la lógica positiva como hemos hecho al comienzo de este parágrafo.

b) Podemos ya enunciar el problema general que vamos a abordar: Teniendo un dipolo de extremos x e y entre los que

Figura 13 Figura 14

/(A ) = e (62)

ALGEBRA DE LOS CIRCUITOS 89

se encuentran un número finito cualquiera de contactos, A, B , C ... L , representados por las variables de Boole a, b ... 1, encontrar una función lógica de estas variables, llamada función de estructura, que valga 1 si la corriente pasa de x a y y 0

Precisemos dertos puntos.Representaremos por letras diferentes a, b , c ... I variables

independientes, es decir, que representan contactos cuya apertura y cierre sea independiente para unos y otros.

Por el contrario, si dos contactos, A y H, por ejemplo, se abren o cierran al tiempo, es decir si el cierre y la apertura de A implica el derre y la apertura de H, tomaremos a = h según nuestro convenio.

Si el derre de A implica la apertura de H y viceversa, escribiremos h = a siguiendo nuestro convenio.

2. Esquemas lógicos. - La realización práctica de los diferentes contactos se halla evidentemente sentada. En genera] no entraremos en detalles tecnológicos, pero sí indicaremos esquemas lógicos o logigramas adoptados de forma más o menos con- vendonal para representar las partes elementales que materializan estos contactos, pues nuestro fin esencial es hacer comprender la posibilidad de realizar efectivamente los circuitos de los que estudiamos la función lógica, pero no reprodudr, de forma más o menos aproximada, los sumadores de una máquina de calcular automática. Es por esto por lo que nos figuraremos siempre relés electromagnéticos, muy cómodos desde nuestro punto de vista, pero hoy abandonados en la construcción de calculadoras, pues su tiempo de respuesta a una excitación eléctrica es muy largo; el uso de semiconductores tales como diodos y transistores tiene muchas ventajas prácticas en este campo.

3. Relé electromagnético. — a) Se compone de una laminilla AL móvil alrededor de A (fig. 15) y de dos contactos fijos R y T llamados contactos de reposo y de trabajo así como una bobina 0 ‘ .


Cuando la corriente pasa en p la laminilla AL es atraída por la bobina y su extremo L hace contacto con T; el dipolo xy queda entonces cerrado y su función de estructura / (A) toma el valor 1.

Cuando la corriente eléctrica cesa de recorrer la bobina p un resorte r fijo en 0 sitúa AL en contacto con R; el dipolo xy está entonces abierto y su función de estructura /(A ) toma el

Así /(A ) = a donde a es una variable de Boole y hemos realizado de forma práctica esta función lógica /(A ).

b) Se realiza la forma lógica /(A ) = a tomando la salida del dipolo xy sobre R (flg. 16), pues cuando la corriente pase por p, el dipolo está abierto ya que /(A ) = á = 0 y cuando no pase /(A ) = a = 1. Así la variable de Boole a es igual a 1 si la corriente pasa por la bobina p y a O si no pasa.

4. Contactos en serie. — a) Sean tres contactos A, B, C sobre el dipolo xy cuyos contactos de trabajo están en serie (fig. 17), es decir tales que el cierre de los tres contactos y sólo él asegura


el paso de corriente en el dipolo xy. La función de estructura del dipolo que nosotros designamos por P es:

siendo a ,b ,c las tres variables de los contactos.Si (punteado de. la fig. 17) ponemos en serie dos contactos

trabajo y el contacto reposo de C R", la función del dipolo xy ', designada por P ', es:

f ( f ’)=abc.

En general, si n contactos trabajo se montan en serie para n contactos A], A2 ... A„ con p contactos reposo B ,, B2 ... Bp la función estructura del dipolo P es:

f(p )= a ,a 1 ... a„ b¡ b2 ... bp .Así queda realizado en forma práctica el producto lógico de

variables de Boole u operación Y.b) Sean 0, 0' y 0" ¡as bobinas de los contactos A, B y C.

Si montamos 0 y 0' en serie (punteado de la fig. 17), se pone a = b ya que las variables de Boole a y ó son siempre iguales. Si se_monta 0 y & en serie estando la salida y ' en R", se pone a - c, estas dos variables a y c son siempre iguales. Todo esto realizado según los convenios anteriores.

S. Contactos en paralelo. - Dados tres contactos A, B, C cuyos contactos trabajo están todos en paralelo, la función de estructura / ( P) del dipolo xy (fig. 18) valdrá 1 si, y sólo si, uno


de los contactos está cerrado. En consecuencia, dadas las propiedades de la suma lógica, se escribirá: /(P ) =a + b + c.

Si se ponen en paralelo dos contactos trabajo T ' y f y uno reposo R (punteado sobre la fig. 18) la función del nuevo dipolo será:

/(P ') = S + b + c

De forma general, si ponemos en paralelo n contactos trabajo A i, Aj ... A„ y p contactos reposo B |, Bj ... Bp , la función de estructura del dipolo P es:

/ ( P) = ¿ a , 4- t b ,

donde los S indican sumas lógicas.Asi queda realizada de forma práctica la suma lógica de va

riables de Boole, u operación 0.Podemos ahora resolver los dos problemas siguientes:1.° Montar un circuito cuya función de estructura sea co-

2.° Determinar la función de estructura de una red de cadenas de contacto.

6. Circuito de estructura dada. - Toda función de estructura se descompone como se ha visto en unión de términos minimales o como intersección de términos maximales; la realización de un circuito cuya función de estructura sea una función de Boole cualquiera, está asegurada.

a) Estando representado un término minimal por contactos en serie, basta situar en paralelo todas estas series de contactos para obtener un circuito que responda a la pregunta, es decir que tenga una función de estructura idéntica a la función dada supuesta descompuesta en términos minimales, lo que es siempre posible.

b) Igualmente, representando un término maximal por un conjunto de contactos en paralelo, es suficiente montar en serie todos estos conjuntos para obtener un circuito cuya función


de estructura coincida con la dada, suponiéndola descompuesta en términos maximales cosa que siempre es posible. Asi dada una función se pueden construir varios circuitos de los que sea su función de estructura; es interesante construir un circuito tan simple como sea posible y para eso comenzar por simplificar la función.

c) Consideremos, por ejemplo, la función ya estudiada

¡fi = a + be + ab 1,° Podemos escribirla en la forma:

<p = abe + abe + a b c de aquí el circuito de la Gg. 19 representando esquemáticamente cada contacto por su función de estructura:

* i b 5 y

3 b cFigura 19

2.° Pero ip puede también expresarse como un producto de

<f = (a + b + c)(a +i> + c )(fl + b + c )(a + b + c )(a + b 4- c)

de donde nos resulta el circuito de la ñg. 20.

u b i b b b y


El primer circuito tiene 9 contactos y el segundo 15 para la misma función de estructura. Ahora bien, hemos visto que

y puede por tanto ser representada por un circuito que sólo tenga cuatro contactos:

Es importante en las aplicaciones reducir el número de contactos, no importa cuánto, para disminuir el calentamiento del circuito; de aquí el interés del álgebra de Boole.

7. Función de estructura de un circuito dado. - Utilizaremos el método de los itinerarios para encontrar la función de estructura de un circuito dado como el de la fig. 22:

Consiste en unir los polos x e y por todos los caminos en serie posibles y formar el producto de los contactos encontrados al recorrer cada uno de estos caminos. Se obtiene la función

<p = ab +

*,yFigura 22


de estructura del dipolo xy formando la suma lógica de todos estos productos. En efecto, sabemos por las propiedades de la suma lógica que será nula si, y sólo si, todos estos productos lo son, es decir si la corriente que entre por el extremo x no encuentra ningún camino cerrado para llegar a y.

Se obtiene así, para la función de estructura / (P) buscada: / ( P) =abc + abe b + abe ab + cá b + cb + ccc

pues hay seis caminos posibles.Pero bb =aa = cc = 0, luego:

f(P)=abc + cáb + cb = bc(a + a ) + cb Ahora bien, a + a = 1, por lo tanto:

/(P)=*c + cft=c(í.+b)=c.Así / ( P) = c y todo el circuito se comporta como un único

contacto c; los contactos a, b, a y b pueden ser suprimidos a no ser que modifiquemos el comportamiento del dipolo.

8. Circuito dual. - Por las fórmulas de De Morgan se obtiene la negación de una función de Boole transformando las sumas lógicas en productos y recíprocamente, a la vez que sus variables son sustituidas por sus negaciones.

Si a partir de un circuito dado, se construye el obtenido al cambiar cada contacto por su negación y montando en paralelo los circuitos en serie y recíprocamente, se dice que se ha construido el circuito dual del primero. Su función de estructura, si / es la del primer circuito, será f . Es de señalar que el dual del dual es evidentemente el circuito primitivo. Así sobre la fig. 22 se ha designado en punteado el dual x 'y del dipolo xy.

Hallemos su función de estructura g por el método de los itinerarios, reemplazando las variables de la fig. 22 por sus negaciones:g = a c +b c 4- acba + acbb -i- beba + bebb +ccc +

„ , , c ba+cbbDe donde:

96 FL ALGEBRA DE BOOLE

Ahora bien:

a + ba = a ■ ba = e (a + b) = ab = b + a Por tanto:

g = c (á + b + b ) = c ( i + l ) = c ,

es el resultado esperado / .

9. Dilema. - El circuito en dilema realiza la suma disyuntiva a ffi b de dos variables de Boole a y b;Juega pues un papel esencial en la suma de dos números escritos en el sistema binario. Se compone (observar el logigrama de la fig. 23)jie los contactos a y b montados en serie y de los contactos a y b montados también en serie. Finalmente los pares, a, b y a, b se sitúan en paralelo.

Este circuito puede realizarse con dos relés interconectados como indica la fig. 24, uniéndose los extremos R y T’, por un lado y R' y T por otro.


Si por la bobina 0 pasa corriente, se pone a = 1, y a = 0 si no. Análogamente, si por 0' pasa comente ponemos b = 1 y si no pasa 6 = 0 .

A la vista de la fig. 24 tenemos los resultados siguientes:1.° a =b = 0, a © b = 0 , pues el circuito se interrumpe por T'.2.° a = l , ó = 0 , a © 6 = l , pues el circuito ATR'B está

cerrado.3.° a = 0, 6 = 1, a © b = 1, pues el circuito ART'B está

cerrado.4.° a = b = 1, a © b = 0, pues el circuito queda interrum

pido en R'.

10. Diodos y transistores. — a) En la práctica los relés electromagnéticos son sustituidos ventajosamente por los diodos.

Estos, esquematizados por una flecha (fig. 25), tienen la propiedad fundamental de no permitir el paso de corriente más que en el sentido indicado por la flecha.

Sobre la fíg. 25 el diodo es de paso si el potencial en A es superior al potencial en B y queda bloqueado si el potencial en A es inferior al potencial en B. Un diodo funciona, pues, como un contacto cerrado (diodo de paso) o abierto (diodo bloqueado) y, desde el punto de vista lógico, equivale a un relé electromagnético.

Los diodos permiten disminuir el volumen de los circuitos y las potencias consumidas. Tienen además una larga duración en su uso, pero, muy sensibles al calor, precisan instalaciones de refrigeración apropiadas.

b) De descubrimiento relativamente reciente, los transistores pueden funcionar lógicamente como diodos y presentan numerosas ventajas de utilización como son: vida larga, volumen reducido y poder amplificador, pues débiles variaciones de la

EL ALGEBRA DE BOOLE

corriente de entrada provocan importantes variaciones de la de

El lector encontrará en las obras especializadas detalles acerca de la realización práctica de los diferentes circuitos lógicos por diodos y transistores.

Capítulo XI

NUMERACION BINARIA

Un número escrito en el sistema de numeración binario utiliza sólo las cifras 0 y 1; podrá pues ser representado por uri circuito eléctrico conveniente, es decir por un conjunto de contactos cada uno de ellos en un estado bien determinado. Este número podrá luego ser tratado por una calculadora, es decir sometido a una sucesión de cálculos, si poseemos circuitos que permitan efectuar con los números las operaciones aritméticas fundamentales: suma, resta, multiplicación y división. Es pues necesario estudiar las reglas de estas operaciones en el sistema de numeración binario. Además, como los datos numéricos vienen dados en el sistema decimal y los resultados se deben expresar también en este sistema para poder ser utilizados, es necesario estudiar la conversión de un número del sistema binario al decimal y recíprocamente del decimal al binario; se comprueba entonces que el sistema octal, es decir de base 8, es un intermediario cómodo para efectuar prácticamente estas dos conversiones. Es pues interesante estudiar en primer lugar los sistemas de numeración en una base cualquiera B.

1. Numeración en la base B. — Dado un número decimal positivo x, se escribirá: X=X, +Xj

designando por x , su parte entera, es decir el mayor entero inferior a x , y por x 2 su parte fraccionaria, necesariamente comprendida entre 0 y 1 o igual a 0 si x es entero.


a) Se dice que x está escrito en la base B si x , y x 2 son de la forma:

*1 =oin.iB '1 + onBn_ 1 + ... +<*3Bj + <*2B + a, x2 = P ,B -' + & B ~ J + ... + 0p B- ' ’ (63)

siendo los a¡ y los P¡ enteros positivos o nulos y necesariamente inferiores a B. Se conviene en escribir:

* = < * ,., o„ . . .a ¡ a , ,p , ...0P suprimiendo las potencias del entero B ya fijo de una vez por todas y utilizando una coma para separar la parte entera. Es pues necesario disponer de B signos o cifras para escribir los a,- y los P¡. El sistema se llama decimal si B = 10 y las diez cifras empleadas, como ya se sabe, son:

0, 1, 2, 3 , 4 , 5, 6 , 7 , 8, 9.Supondremos en lo que sigue B < 10 de forma que las B

cifras utilizadas serán, por convenio, las B primeras de la sucesión precedente.

b ) Formemos el producto x • B para k entero positivo: x = B* = a„ . , B" rk + ... + a, B* + p, B*- 1 + ... + pk +

+ Pk . , B - ‘ + ... + pp B -p*k.Es suficiente pues desplazar la coma k lugares hacia la dere

cha para multiplicar x por B*; puede ser preciso añadir ceros

Si, por ejemplo, B = 2 las cifras del sistema, que se llama binario, son 0 y 1.

Si y = 101100,1101, 23 y = 101100110,1 y 2* y = 101100110100.

c) Formemos el productox • B“ * = (*„.,Bn_ * + ... + a*.,+o:*B -1 +... + ppB~p~*.

Es suficiente desplazar la coma k lugares hada la izquierda, añadiendo incluso ceros si es necesario, para dividir x por

2~3y = 101, 1001101 y 2_‘ .v = 0,101100i l 01.

NUMERACION BINARIA 101

2. Cambio de base.— a) Estudiemos para un número dado en el sistema decimal su expresión en un sistema de base B inferior a 10.

1.° Parte entera.Sea x t = o„», B" + ... + a 2B + a¡ supuesto escrito en el

el sistema de base B. Pongamos:f B"_ I + a„ B" ~ 2 + ... + a 2.

Entonces x , se escribe: x , = q, B + ot| y c o m o O < a j< B , q i y a i son el cociente y el resto de la división de x , por B, en no importa qué base.

Si se divide pues x¡ por B en el sistema decimal se obtiene, en este sistema el resto a ¡ ; pero, después del convenio hecho al comienzo, a i es también la cifra de las unidades de x t escrita en la base B ya que B es inferior a 10 y que, por consiguiente, los B primeros números, incluido el cero, del sistema de base B se escriben como los B primeros números del sistema decimal.

Igualmente, a2 es el resto de la división de q , por B en el sistema decimal, y asi sucesivamente.

Sea pues * i = 243, por ejemplo en el sistema decimal, para escribirle en el sistema binario (B = 2) se disponen cómodamente, como indica la fig. 26, las divisiones por 2.

1 243 1 121 1 60 I 30 | 15 1 7 | 3 1 1 I

1 <!> 1 (1) || (0) I (0) | <1> 1 O) | <1) | O ) |Figura 26

La flecha indica el orden en el que se deben tomar los restos 0 ó 1 para escribir luego de izquierda a derecha: x , =11110011.

2.° Parte fraccionaria.Sea x2 =/5| B“ 1 + 02B~ 2 + ... +PpB~p . De aquí se deduce:

B x j= 0 , + 02 B_ 1 + ... + PpB-P*'.Ahora bien:

02B~ 1 + ... + 0p B~p* ' <S(B - 1)(B_ 1 + B- 2 + ... + B_p * ') ,

ya que 02, ...0P < B - 1.


Por lo tanto:02B- 1 + ... +fipB~p*' < 1 - B_p*' < 1,

es decir 0 < Bx¡ - fi¡ < 1; resulta de estas desigualdades que 0i es la parte entera de Bx2 y que se obtiene multiplicando la parte decimal de x por B.

Sea x 3 = 02B- ' + ... + 0p B_p * ' la parte decimal de Bx2 operando del mismo modo 02 es la parte entera de Bx3, y así sucesivamente. De aquí que si x 2 = 0,287 en el sistema decimal, multiplicando sucesivamente por 2:

0,287 10,57410,148 I 0,296 I 0,592 I 0,184 I 0,36810,736 I 0,472

<«> I <i> I (o) | (o) | ( i) | (o) | (o) | a> |

Figura 27

Paramos esta sucesión de operaciones que pueden continuarse indefinidamente y escribimos:

jc, = 0,01001001...La flecha indica el orden de escritura, de izquierda a derecha

después de la coma, de las cifras obtenidas. Si x = 243,287 en el sistema decimal, x = 11110011, 01001001... en el binario.

b) La conversión al sistema decimal de un número escrito en el binario, se hace sin dificultad volviendo a la definición (63) y calculando en el sistema decimal.

Si, por ejemplo,x = 100110,0101, se obtiene:

* = l - 2 5 + 0 * 24 + 0 - 23 + l - 2 J + l - 2 + 0 ‘ l ++ 0 - 2 -1 + 1 -2 - 2 + 0 - 2 “ 3 + 1 -2~* =

= 32 + 4 + 2 + 1 + — = 3 8 + — = 38,3125.4 16 16

Un número fraccionario en el sistema binario es siempre igual a un número decimal en el sistema decimal, pues las fracciones de denominador 7P son todas decimales.


c) Veamos la expresión en el sistema binario de los enteros inferiores o iguales a 10:

1 | 2 | 3 | 4 | S | 6 | 7 | 8 | 9 | 1 0

1 110 11 1 11 0 011 0 111 1 0 11 1 1 |iooojiooi|ioio

Figura 28

En el binario un entero de n cifras es a lo sumo igual a 2" - 1, pues el mayor entero de n cifras se escribe poniendo en(63) los a¡ iguales a 1, y es:

11...1 = 1 + 2 + ... + 2n~ ‘ = 2 " — 1 = N.Ahora bien, en el sistema decimal, N tiene un número de

cifras dado por la parte entera de su logaritmo decimal. Sea p este número de cifras. De la desigualdad p < log (2” — 1) se deduce:

p < n log 2 o sea, más o menos, 0,3 • n es el número p.

Así con 10 cifras en el sistema binario no podremos poner muchos números de más de tres cifras (03 x 10 = 3) en el sistema decimal.En efecto: 210 = 1024 y N = 1.023.

3. Sistema octal. — Se llama sistema octal al sistema de base 8. Permite simplifícar notablemente las operaciones anteriores de conversión por dos razones:

1.° El sistema octal está relacionado de forma muy simple con el binario.

2.° Las conversiones decimal-octal u octal-decimal son más rápidas que las conversiones decimal-binario o binario-decimal.

a) Sea el entero x, escrito en el sistema binario: x , = an . , 2" + ... + 23 (a, • 21 + cts ■ 2 + a , ) +

+ (a ,-2 1 + o 1- 2 + a 1).Los números entre paréntesis son inferiores a 8: representan

pues las cifras de x , escrito en el sistema de base 8.

104 L'L ALGEBRA DE BOOLE

* ,2 3 = (0,-2J +/52-2 + fe) + P ,2 - ' + ...Se obtiene en el paréntesis la primera cifra después de la coma de x 3 en el sistema octal y por ello representa la expresión binaria. De aquí la regla:

Para escribir en el sistema octal un número dado en el binario, se separan las cifras de la expresión en el binario en grupos de tres a partir de la coma, hacia la izquierda y hacia la derecha, y se escribe cada uno de estos grupos en el sistema octaL

Sea por ejemplo,en el binario: x = 1 1 10 0 1 1, 0 10 0 10 10 0en el octal: *= 1 6 3, 2 2 4

c) En el decimal, x

r = l* 8 2 + 6*8 + 3 +

es decir, x= 115,289065.Recíprocamente, convirtamos 115,289065 al sistema o

operando como ya se dijo:0,2890625

(S) | <«> | O) |

10,3125 | 0.5 |

1 1 - T l

Se obtiene x = 163224.Evidentemente, no es cosa de abandonar el uso corriente del

sistema de numeración decimal pero el empleo del sistema octal


aportará simplificaciones estimables en la construcción de calculadoras que, trabajando a menudo en el sistema binario, están obligadas a transformar los números del sistema decimal al binario para someterlas al cálculo, y después convertir los resultados obtenidos de nuevo al sistema decimal.

4. Suma de dos números en el sistema binario. - a) La coma la podemos dejar a un lado ya que se sitúa simplemente en la suma en la misma posición.

Utilizaremos las notaciones siguientes para efectuar la suma a -I- ó de dos números binarios positivos.

Figura 30b2, b¡ son las cifras de a y de b.

i las cifras de la suma a + b. Las subíndices se sitúan en la misma

¡a, R| son las cantidades que nos de las dos cifras que tienen los Rp es la cantidad que nos lléva

la columna p, ap y bp. y se encuentra situada, como indica la fig. 30, en la columna p + 1.

Pondremos finalmente:

Los a„ ... a2, a, y los I Los S „ ., , S„ ...S¡, S,

letras a, b, ó S de los mis columna de la fig. 30.

Los R„, R„_ i ... R„_ i llevamos al efectuar la si mismos subíndices que R;

0 + 0= 0 0 + 1= 1 1 + 0 = 1 1 + 1 = 10


Comparando esta tabla con la tabla (56) de la suma disyuntiva © comprobamos que esta suma disyuntiva nos da la cifra Si y que la cantidad que nos llevamos es igual al producto a¡-b ,. De aquí que:

Si = í | =fl| © ¿>i; R i = r i = a |- 6 | .Pasemos a la segunda columna.1.° Si Ri = O la tabla de la suma es evidentemente la tabla

(64) sin modificaciones.2 ° Si Ri = 1 se construye la tabla:

1 + 0 + 0 = 11 + 0 + 1 = 10 m1 + 1 + 0 = 1 01 + 1 + 1 = 11

De ella deducimos:S2 = R, © íj (66)

relación que es cierta si R | = 0; es suficiente comprobarla si Ri = 1, cosa que se hace sin dificultad volviendo de nuevo a la tabla (56) que da la suma disyuntiva y comparándola con (65).

Además resulta de (64) y (65) que la cifra que nos llevamos Rj es a lo sumo igual a 1, como R i, y las tablas (64) y(65) serán válidas para cualquier columna de índice superior a 1.

De forma inmediata se deduce la fórmula general:

Sp = R p- i ® *p (67)El problema de la suma de dos números en el sistema binario

está completamente resuelto si sabemos determinar las cifras que nos llevamos R2 ... Rp ... R„. Ahora bien, Rp valdrá 1 si, y sólo si, dos de los tres números Rp - ¡, ap y bp son iguales a 1 lo que se expresa después de las propiedades de la suma lógica:

Rp = apbp + Rp ,ap + Rp. , b p (68)

ya que Rp = 0 implica a la vez ap bp = 0 , Rp . iflp = 0 y


Rp_ i bp = 0 , es decir, ap = bp = 0 ó Rp_ , = ap = 0 6 Rp_ i = bp = 0. Pero (68) puede también escribirse:

R p=rp + R p-i(ap + bp) y reemplazando en este último resultado ap + bp por la suma disyuntiva sp =ap @ bp , tenemos:

Rp = rp + Rp-isp (69)pues, en efecto, sp no difiere de ap + bp mis que para ap ~ bp = 1, pero, en este caso, Rp toma el valor 1 cuando se le aplica (68) o (69).

Se encuentra aquí en un caso particular el resultado general anteriormente demostrado y según el cual una misma función de variables de Boole puede ponerse de diversas formas, lógicamente equivalentes, de tal suerte que puede materializarse con la ayuda de circuitos eléctricos de apariencia muy diversa. Este hecho no debe perderse de vista cuando se estudian las aplicaciones del álgebra de Boole pues aclara algunas cuestiones.

Se podrá, por tanto, construir una sumadora de números en sistema binario utilizando las fórmulas (67) y (68) o también la (67) y (69); de este modo son posibles varios logigramas.

c) La resta de dos números en sistema binario, su suma algebraica, su producto o su división se efectuarán en principio por las calculadoras binarias a partir de la adición.

Capítulo XII

CALCULADORAS BINARIAS

Veremos estas calculadoras desde un punto de vista puramente conceptual y sin interesamos por los problemas tecnológicos que presenta su construcción; para ello recomendamos ver obras especializadas1.

1. Sumadora. - Es el elemento base de una calculadora binaria pues nos da la suma de dos números binarios. Se descompone en dos semisumadoras, cada una con varias partes:

a) Organo elemental. - Llamaremos órgano elemental a una semisumadora, es decir a un circuito eléctrico cuyo conjunto de contactos, realizados en la actualidad con ayuda de diodos y transistores, nos proporciona la suma disyuntiva sp y el producto rp cuando se conoce ap y bp .

Figura 31

El logigrama de un órgano elemental Mp es el de la fig. 31. Para realizarle, es suficiente en principio añadir a un circuito

de dilema que da sp, un circuito Y que da el producto rp.

1 Ver por ejemplo: P. NASLIN, Principes des calculatrices numéri- quesautomatiques, París, Dunod.

CALCULADORAS BINARIAS 109

Teóricamente, es suficiente situar las dos bobinas & y & del circuito dilema de la fig. 24, sobre dos contactos trabajo, unidos entre sí, de un circuito Y según el esquema 32.

Figura 32

Si apbp = 0 ,a p + bp = ap ® bp = sp .Si ap = bp = 1, sp = 0 y rp = 1 lo que (fig. 32) es el resultado

esperado.b) Totalizador. - Se llama totalizador al conjunto de órganos

elementales que permiten realizar la suma de dos o más números dados en el sistema binario. Puede concebirse su esquema según el dispositivo de la fig. 33.

1,° Cuando las tensiones correspondientes a las cifras binarias a ,, a2 ... se aplican a los órganos Mi, Mj .... el número ... a2, a, se dice inscrito en el registro M ,, M¡ ...

Si también se le aplican a Mi. M2 ... las tensiones correspondientes a 6 | , ó] ... la suma S| se registra en M'i mientras que i j y r¡ accionan un órgano m2 de tal suerte que S2 = s2 © R i queda anotado en M2; la cifra que nos llevamos s2 R| se suma lógicamente a r2 para formar R2 que con s , , suministrado por M3, acciona el órgano elemental m3 y así sucesivamente: la suma a + b queda inscrita en consecuencia en los registros M'l Mj M j...


Si se aplican los números binarios Ci, Cj, c3 ... a los órganos M’i Mi M'3 ... se obtiene de forma idéntica la suma a + b + c donde c =... c3 c j c , .

2 ° En el esquema anterior, cuando las tensiones dejan de ser aplicadas, el sistema vuelve a su estado inicial. Ahora bien, es indispensable conservar los resultados totales o parciales de los cálculos; se les anota por eso en los registros de memoria y las flechas m . Ma ... de la fig. 33 indican esta posibilidad. Un contacto que queda bloqueado cuando la comente se interrumpe, puede servir de célula de memoria, es decir de órgano elemental de memoria.

Se puede utilizar como célula de memoria una báscula de transistores y diodos que puede quedar bloqueada en dos estados estables y diferentes; el registro de memoria comprenderá tantas básculas como cifras binarias hay que registrar para formar los números binarios que se introducen en la suma.

Actualmente se utiliza sobre todo para la constitución de estos registros de memoria el magnetismo permanente de los cuerpos ferromagnéticos que persiste después del paso de la

* = (70)siendo x , su parte entera, y x¡ la fraccionaría.

a) Complemento de un número entero binario. — Como


0 < * i < 2" , la diferencia 2" — Jti está también comprendida entre 0 y 2; se le llama complemento del entero binario x , . Demostremos la regla:

Para formar el complemento de un entero dado en el sistema binario, se sustituyen las cifras por sus negaciones y se les

En efecto, six¡ =a„2n~ 1 + ... + a 2 - 2 + a , ,

hacemos: j>i =<^,2n_I + ... + a 2- 2 + S i .Ahora bien, a, + a¡ = 1 para todo i = 1,2 ... n, por lo tanto: + y ¡ = 2"-1 + ... + 2 + 1 = 2" — 1, es decir que:

2" — x t — y¡ + 1 de aquí la regla.Si por ejemplo, n = 6 y x¡ = 1010,

1010 = 001010 = 110101 + 1 TOlcr = 110110,

la barra que está sobre las cifras indica el complemento.b) Complemento de un número fraccionario. - La parte frac

cionaria x 2 de x está comprendida entre 0 y 1. La cifra de la izquierda de la coma es pues un 0. Se escribe: x 2 = 0 ,0 , f¡2 ... ¡¡p .

Se llama complemento de x 2 al número binario 2 — x 2.Sea * j = 0 - 2° + 0 , 2_ l + ... + Pp 2~p

y J-2 = l - 2 \ + 0 , •2- l + ... + 0p -2 - P.Se obtiene:

x j + y 1 = ¡ + 2 ~ ‘ + ... + 2- p = 2 — 2~p ,de donde:

2 - X j = y 2 + 2 p .

Llamamos peso de una cifra al exponente de la potencia de 2 que multiplica a esta cifra en el desarrollo binario del número (63); se obtiene para la formación del complemento de x 2 la misma regla que para la formación del de x , :

Sustituir cada cifra de x2 por su negación y añadir al resultado una unidad del peso más débil.


Sea por ejemplo, x¡ = 0,01101. Se obtiene, indicando la barra siempre el complemento:

0,01101 = 1,10010 + 0,00001 = 1,10011.

4. Sumas algebraicas. Números negativos. — Para efectuar las sumas algebraicas es necesario introducir los números negativos. Se utiliza para eso el convenio del código de los complementos, que sustituye el número negativo - x por su complemento.

a) Efectuemos y - x con y = y¡ + y t y x = x¡ + x 2 según (70). Formamos, ya que x, es un entero:

y como Xj es fraccionario:

y 2 + 10,0 . . .0 -X j

La máquina, en efecto, no registra más que n cifras, como 2" está formado por un 1 seguido de n ceros, su presencia en la suma no influye sobre el resultado obtenido por la máquina.

Igualmente, 10,0... 0 está formado por un 1 seguido de n ceros; el 1 no es registrado por la máquina, ésta nos da elresultado útil.

1 ° Los enteros negativos de - 2"~ 1 a - 1 se sustituyen pues por los enteros de 2 " " 1 a 2 " - l , los d e0 a 2" ~ ' - 1 representan los enteros positivos.

2 ° Los números fraccionarios comprendidos entre - 1 y _ 2- (« - i) son también representados por los números del 1 al 2 — 2~(n~ , los números entre 0 y 1 - 2~*n_ representan los números fraccionarios positivos inferiores a 1. Así los números fraccionarios positivos y menores que 1 tienen un 0 a la izquierda de la coma y los fraccionarios negativos tienen un 1 a la izquierda de la coma, por lo que la cifra a la izquierda de la coma nos indica el signo.

b) Vamos a efectuar, por ejemplo:

1101,001-1110,101.


1 ° Formamos 1101 - 1110 dando el complemento a 2*. es decir utilizando 5 cifras:

1101 + 7110 = 1101 + 10001 + 11101 + TÍTO = 1101 + 10010 = 11111 = 2 * - 1.

Esta suma es un número negativo según los convenios hechos para los complementos. Su valor absoluto se obtiene siempre, después del convenio hecho, formando su complementario que claramente se ve que es 1. Por lo tanto:

1101 - 1110 = - 1

2.° Hallemos del mismo modo 0,001 - 0,101. Sea:

0,001 + (M 0l = 0,001 + 1,010 + 0,001,

de donde:

0,001 + OJOÍ = 0,010 + 1,010 =1,100.

Es por tanto un número negativo. Su valor absoluto se obtiene, después del convenio hecho, formando su complementario

U = 0,0 + 0,1 =0,1.

Por lo tanto:

0,001 -0 ,101 = - 0 ,1

y finalmente:

1101,001 - 1110,101 = - 1,1.

5. Multiplicación. División. - a ) La teoría de la multiplicación binaria es muy simple.

Si A es el multiplicando y B el multiplicador, se obtiene el producto efectuando una serie de sumas.

Sea por ejemplo, A = 11010 y B = 1011.


11010 X 1011

11010 11010

11010 100011110

Los productos parciales son iguales a A o a 0 según que la dfra del multiplicador tomada sea 1 ó 0. Es suficiente pues sumarles números obtenidos por desplazamientos sucesivos del multiplicando A. En cuanto al signo del producto, se obtiene por un circuito de dilema; a los números positivos les asignamos un 0 y a los negativos un 1. El signo del producto es la suma disyuntiva que así se obtiene.

b) Se han inventado, para dividir en el sistema binario, diversos algoritmos de los que el de A. D. Booth es el más conocido. Teóricamente la operación es posible pues consiste en una sucesión de restos y multiplicaciones por 2 .

6. Coma. — Cuando se opera dejando la coma en su lugar en los datos y resultados parciales, se dice que se trabqa a coma fija. Ahora bien, a menudo es cómodo escribir todos los números en el interior de un cuadro de tamafio determinado y para eso se los multiplica o divide por una potencia de 2- Se escribe así el número a en la forma:

a = a '-2* ,donde llamamos mantisa a a’ y exponente a k; una representación de este modo se denomina coma flotante.

Se toma a menudo para a' un número de valor absoluto inferior a 1 y de tal suerte que el cero a la izquierda de la coma indica, como ya se dijo, un número positivo y el 1 uno negativo.

Este procedimiento es especialmente ventajoso en la formación del producto, pues, la suma disyuntiva de las dos cifras de la izquierda de la coma nos da el signo; además, si cada uno de


los números tiene p cifras a la derecha de la coma, el producto tiene 2 • p y podemos eliminar automáticamente las p cifras de menor peso, y sólo ellas.

A veces es necesario efectuar en el transcurso del cálculo cambios de escala para mantener esta representación de los resultados.

7. Sistema decimal. Código binario. — Otros sistemas de numeración más complejos son también utilizados en las calculadoras como forma de evitar, al comienzo, la transcripción de los datos dados en el sistema decimal al binario y al terminar, del binario al decimal.

Señalemos, sin entrar en detalles fuera de lugar, el uso del sistema llamado decimal, código binario, que permite operar en el sistema decimal pero escribiendo las cifras en el binario. Pensando de nuevo en la fig. 30, se ve que a lo sumo son necesarias cuatro dfras binarias para representar todas las del sistema decimal, algunos números binarios de 4 cifras quedan por otra parte sin emplear.

Se trata de este modo de combinar las ventajas particulares de ambos sistemas.

8. Organización de una calculadora. — Hagamos un esbozo a grandes trazos del funcionamiento de una calculadora o de un ordenador1.

a) Programa. - La ejecución por una máquina de una operación elemental de cálculo se ordena por una instrucción-, el conjunto de las instrucciones que la máquina puede interpretar y ejecutar constituye su código y cada instrucción se señala por un número binario que da su clasificación en el código. La lista de instrucciones necesarias para la ejecución de un cálculo se establece con la ayuda de los números del código. Esta lista, establecida por el programador, es un programa.

1 Ver Le langage électronique por J. y J. POYEN (Colección “Que sais-je?" n.° 900). París, Presscs Universitarios de France.


b) Memoria. - Los datos numéricos de interés para los cálculos a realizar se reúnen en la memoria. Está formada por un gran número de registros comprendiendo tantos órganos elementales como cifras hay en los números tratados por la máquina.

La memoria conserva también las instrucciones del programa, codificado como hemos dicho; registra además los resultados parciales y definitivos del cálculo.

Una instrucción sólo estará completa cuando indique no sólo la operación a efectuar sino también el lugar en la memoria de los datos numéricos del cálculo. Estas condiciones las establece el programador con la ayuda de una sucesión de números del sistema decimal que luego serán escritos en el binario por los órganos de entrada de la máquina.

c) Funcionamiento general. — Las instrucciones extraídas de la memoria, son registradas primeramente en una memoria especial de aparatos de pedido o memoria de instrucción, después interpretadas para formar las señales del pedido que, aplicadas al operador de cálculo y a la memoria, pondrán en marcha las diferentes operaciones cuyos resultados se pondrán en la memoria antes de ser descodificados por los órganos de salida para hacerlos ya comprensibles a quien les utiliza.

d) Información. - El encadenamiento de estas frases sucesivas será sincronizado por un generador de ritmo o reloj que emite impulsos sucesivos caracterizados por la existencia de dos niveles de tensión eléctrica; en lógica positiva, el más elevado corresponde a la cifra 1 y el menos elevado a la cifra 0 ; en lógica negativa, la situación es la inversa.

Una cifra, 0 ó 1, cuando se transmite de esta forma, constituye una unidad de información. Una palabra corresponde a una información de p unidades, es decir a la transmisión de un número de p cifras.

La duración del paso de una unidad de información se llama ciclo binario y la de una palabra ciclo menor. La máquina está “en serie” si las p unidades de una palabra se suceden en el tiempo en la misma vía de transmisión; está “en paralelo” si las p unidades de la palabra se transmiten al mismo tiempo por p vías diferentes.


9. Usos. - Las calculadoras automáticas pueden utilizarse para usos extremadamente variados debido a la flexibilidad de sus principios de organización.

Aparte de las operaciones ya mencionadas, pueden utilizarse para multiplicar matrices, calcular la inversa de una matriz dada, y por tanto para la resolución de sistemas de ecuaciones lineales, búsqueda de valores propios y vectores propios de matrices, resolución de ecuaciones algebraicas y, en general, para numerosos problemas de análisis matemático.

Actualmente su empleo en la gestión de empresas, administraciones o servicios hospitalarios1 no ha hecho sino comenzar, el uso de discos y de hojas magnéticas facilitan la puesta en la memoria de la información por cientos de millones de unidades. En principio, todo proceso complejo que se desarrolle según las reglas de la lógica puede ser programado en una máquina electrónica automática-, el álgebra de G. Boole permite su estudio por medio de las operaciones lógicas fundamentales y la rapidez de funcionamiento de las máquinas aseguran un rendimiento muy elevado.

BIBLIO GR A FIA

•^ ¡^ g ss ts ífía tu s s rs isbli». 1, Perú, S- B#n.(Col. “Que sais,»?”. t»° 74S),“rasaasr.'

D% ^ * ! - T S , T K S . ' ^r a s E S T S' S S Í J t i S S .

■ ^ s L j t t s s r i í u s í a K I “ ‘- “ ■• — •R ™ ; t , ¿ i ; í ( i í 2 f f i S ™ S 5 <Co1' "Q” “* 1" ’ ' " °

t L fin esencial del matemático inglés George Boole (1815-1864), fundando el álgebra que

lleva su nombre, era el de someter el razonamiento lógico a reglas convenientes de cálculo. Algebra que se ha revelado independiente de la naturaleza de las proposiciones con que trabaja a la vez que aparece 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, verdadero 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 calculadoras automáticas y de los ordenadores.

El importante desarrollo moderno del cálculo electrónico es una consecuencia imprevista de las posibilidades de un lenguaje 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 conocimiento matemático previo y puede ser comprendido 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.

Documents

El álgebra de Boole - latecnicalf.com.ar