Apéndice K. Lógica binaria

§1  Sinopsis

El álgebra lógica fue desarrollada a principios del siglo XIX por el matemático George Boole para investigar las leyes fundamentales en que se basa el razonamiento humano. Este álgebra tiene una característica especial:  sus variables solo pueden adoptar dos valores, tradicionalmente denominados cierto y falso (es usual representarlos con 1 y 0 respectivamente), en estos casos, ambos dígitos pueden representar cualquier par de estados, con la condición de ser mutuamente excluyentes [1]. Por esto se dice que no maneja cantidades en el sentido del resto de las matemáticas, sino valores lógicos binarios y se la denomina Álgebra o lógica binaria (o Booleana).

Los circuitos eléctricos digitales, los circuitos con fluidos (hidráulicos y neumáticos), con luz (fibra óptica) y otros, se prestan muy bien a tratar este tipo de señales, porque es fácil construir circuitos que adopten tales valores, tensión no-tensión, conectado no-conectado, abierto-cerrado, encendido, apagado etc. La adaptación del álgebra de Boole a los computadores digitales fue presentada en 1938 por Claude Shannon de los Laboratorios Bell.

Hagamos hincapié que en estos casos, las cifras 0 y 1 no representan cantidades numéricas. Son símbolos de dos estados mutuamente excluyentes. El hecho de que en este tipo de sistemas (de variables lógicas binarias) se utilice un sistema de numeración binario (de base 2), es porque al tener este sistema de numeración solo dos dígitos 0 y 1, es posible establecer una relación biunívoca entre los valores numéricos y los estados lógicos. Esta relación se hace a veces tan íntima que la distinción tiende a desdibujarse, aunque el sistema de numeración de base dos (o cualquier otra base) y la lógica binaria (representada por su álgebra) sean conceptos totalmente distintos. También son conceptos distintos los dígitos 0/1 del sistema binario y los valores cierto/falso de las variables lógicas binarias.

Existe un álgebra lógica de mas de dos estados, la lógica difusa, donde las cosas no son blancas o negras, pueden existir grados intermedios; los estados no son mutuamente exclusivos.

§2  Operaciones lógicas

De forma análoga al álgebra tradicional, en el álgebra binaria se definen operadores y relaciones con los que se pueden construir funciones (relaciones), que se llaman "lógicas" o "booleanas". Por ejemplo:  s = a . b+b . c;  en forma implícita: s = f(a, b, c)

Donde  s , a, b, c  son variables lógicas. s es la variable dependiente (o función). a, b y c son las variables independientes. = es una relación,  + y . son operadores lógicos (no tienen ninguna relación con los peradores "suma" y "producto" que estamos acostumbrados a ver en aritmética).

Tabla-1 a b s 0 0 0 0 1 1 1 0 1 1 1 1

En el álgebra tradicional, para que una operación (otra manera de llamar a una función) entre dos variables esté perfectamente definida, es preciso definir el valor de la resultante (función) para todo el ámbito de existencia de las variables independientes. Del mismo modo, para definir un operador entre dos variables lógicas, es preciso definir el valor que adopta la variable dependiente para todas las posibles combinaciones de las independientes.

Puesto que en el álgebra de Boole las variables (independientes y función) solo pueden adoptar dos valores, aquí, la definición de un operador entre 2 variables a y b, exige definir el resultado (0 o 1) para las 4 (2²) combinaciones de valores posibles que a y b pueden presentar. Del mismo modo, para 3 variables hay que definir 2³ resultados, y en genera 2ⁿ para n variables. Estas definiciones pueden expresarse cómodamente en forma tabular.

Este tipo de representación se denomina Tabla de Verdad de la función. Consiste en una tabla con tantas columnas como variables (contando la dependiente o función), y tantas filas como resultados hay que definir (tantos como combinaciones pueden hacerse con las variables independientes) es decir, 2ⁿ, siendo n el número de variables independientes. En la Tabla-1 se ha representado lo que podría ser la definición (tabla de verdad) de una función de dos variables, y en la Tabla-2 la correspondiente a una función de tres variables.

Observe que en el primer caso, es preciso definir el resultado (0 o 1) para las 2² = 4 combinaciones que pueden presentarse. Como estos resultados podrían ser dos para cada combinación, se pueden definir 2⁴ = 16 funciones distintas para dos variables, lo que puede expresarse  2^{2^2} (la que se ha representado en la Tabla-1 es una de las 16 funciones posibles). Del mismo modo, como hemos visto en la Tabla-2, para definir una función de tres variables hay que definir 2³ = 8 resultados, pudiendo existir 2⁸ = 2^{2^3} = 256 funciones distintas.

Nota:  Por conveniencia de la notación, utilizamos aquí la expresión a^b como equivalente a: a^b.

Tabla-3 t v c p 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0

La lógica del asunto podría presentarse como sigue: n variables lógicas (a, b, c, d, Etc.) representan n situaciones (no tienen porque tener ninguna conexión entre si), cada una de las cuales puede tener dos estados mutuamente excluyentes. Una función entre n variables significa establecer una relación de forma que a cada combinación de las n situaciones (variables de entrada, o independientes) le corresponde uno de los dos valores posibles de una nueva variable (lógica) s, que denominamos salida (también puede ser llamada variable dependiente o función).

Nota: lo de "entrada" y "salida" viene de su utilización en circuitos electrónicos. Estas funciones pueden ser emuladas físicamente mediante circuitos electrónicos ("puertas" lógicas) con tantos hilos de "entrada" como variables independientes, y un hilo para la "salida". Aplicando señales (por ejemplo tensión/no tensión) en los hilos de entrada del circuito, el de salida adopta el valor definido por la tabla de verdad.

Podemos concretarlo en un caso:  Imaginemos que una variable t representa el estado del tiempo en lo que a lluvia se refiere, otra variable v representa el estado del viento;  una tercera c representa si sacaremos el coche. Podríamos establecer una cuarta variable p que representa si llevaremos o no paraguas, y decimos que p dependerá del valor de las restantes variables (técnicamente decimos que es función de t, v, y c), y se expresa:  p = f(t, v, c).

Recordemos que todas estas variables son binarias, solo pueden tener dos valores si/cierto (que representamos con 1) y no/falso (que representamos con 0). Nuestro criterio respecto a sacar el paraguas podría ser expresado por la tabla de verdad de la Tabla-3, que representaría sin ambigüedades el comportamiento que seguiremos al respecto.

§3  Relación de igualdad

Igualdad a b 0 0 1 1

Decimos que entre dos variables a, b hay una relación de igualdad cuando su tabla de verdad es la que se adjunta (es una identidad).

Notación:  a = b

Propiedades:

Reflexiva:  a = a 
Simétrica: a = b  b = a 
Transitiva:  a = b y b = c a = c

§4Operación Negación, NOT, Inversión

Es una operación unitaria (afecta a una sola variable), que aplicada a una variable la transforma en otra según la tabla de verdad que se adjunta.

Notación:   s  = not(a) = a

 * En realidad es una barra superior, aunque aquí, por necesidades tipográficas la representemos como un subrayado.

Teorema:  Dos negaciones sucesivas de una variable producen la variable primitiva. Esto puede expresarse algébricamente mediante la expresión:   NOT(a) = a.

 Nota:   esta afirmación, que parece "de cajón", y casi todos los teoremas y axiomas que se citen sobre álgebra binaria, tienen su demostración mediante el uso de la tabla de verdad, dado que el pequeño número de casos a revisar, permite verificarlos todos.

Ejemplo:  Sea a una variable que define el estado meteorológico de lluvia (1 = Cierto = llueve / 0 = falso = No llueve). Si en un caso es a = Llueve a = No llueve.

§5  Funciones lógicas

Hemos adelantado que la definición de un operador entre 2 variables a y b, exige definir el resultado (0 o 1) para las 4 combinaciones de valores posibles que pueden presentar a y b (mostradas en la Tabla-1 ), y que pueden existir 16 de estas funciones. Para 3 variables hay que definir 2³ = 8 resultados, y pueden existir  2³ de estas funciones. En general, para definir una función entre n variables hay que definir 2ⁿ valores, y pueden ser definidas 2^{n^2} funciones distintas. Así pues, el arsenal de funciones distintas en función del número de variables implicadas es el siguiente:

Tabla-4 Valores de a 0 1 Función f0(a) 0 0 f(a) = 0 f1(a) 0 1 f(a) = a (identidad) f2(a) 1 0 f(a) = a (inverso) f3(a) 1 1 f(a) = 1

• Para una variable: 2¹ combinaciones,  2^{1^2} funciones.

  Este caso es el representado en la Tabla-4. En ella vemos que aparte de las dos seudo funciones (f₀ y f₃),  f₁ es una identidad (transforma la variable en si misma). Queda f₂ como auténtica función (la inversión ya estudiada anteriormente).

  Nota:  Esta tabla de verdad debe leerse de la siguiente forma:  la función f0 aplicada sobre a produce un resultado 0 con cualquier valor (0 o 1) que tenga a. Por su parte f1 aplicada sobre a produce un resultado 0 o 1 según el valor (0 o 1) que tenga a (en realidad no modifica el valor de a). La función f2 aplicada sobre a produce un resultado que es el inverso de a. Finalmente, f3 aplicada sobre a produce siempre un 1, independientemente del valor (0 o 1) de a.

• Para 2 variables:  hay 2² combinaciones 2^{2^2} =16 funciones, que se han representado en la Tabla-5  (incluyen las 4 posibilidades correspondientes a 1 variable).

• Para 3 variables:  2³ = 8 combinaciones. Las posibilidades de asignar 0/1 a estas combinación es 2^{3^2} = 256.

• Para n variables:  2ⁿ combinaciones. Las posibilidades de asignar 0/1 a estas combinación es 2^{n^2}.

A continuación definimos las 16 operaciones posibles entre "dos" variables lógicas (denominadas conectivas). Vemos que están incluidas algunas que no lo son realmente (resultados que no dependen de los valores de las variables independientes), y que están también las de una sola variable. En la Tabla-5 se han señalado estas 16 posibilidades.

Vemos que las funciones marcadas con 1^©, f₀ y f₁₅, no son realmente funciones, valen 0 y 1 (falso y cierto) respectivamente, con independencia de los valores a y b. Las marcadas con 2^© son las de una variable ya comentadas.

Es digno de destacarse que estas 16 funciones no son independientes entre sí. Pueden expresarse en función de tres de ellas: AND, OR y NOT. A continuación se comentan las mas interesantes, las tablas de verdad de cada operación las dejamos referidas a esta tabla.

§5.1  F₇  La operación Suma, inclusive-OR, Reunión, Unión (tiene todos estos nombres), se define mediante la tabla de verdad adjunta.

Inclusive OR a b s 0 0 0 0 1 1 1 0 1 1 1 1

En lenguaje coloquial diríamos que la salida o resultante es cierta si lo es alguna de las variables (entradas).

Notación:

s = a + b

s = a OR b

La notación utilizada puede ser cualquiera de las señaladas. Recuerde: el operador + no tiene nada que ver con la suma tradicional (aritmética).

Propiedades:

Conmutativa:  s = a + b = b + a
Asociativa:     s = a+(b+c) = (a+b)+c = a+b+c

Producto a b s 0 0 0 0 1 0 1 0 0 1 1 1 §5.2  F1  Operación Producto, AND, Intersección:  La salida es cierta si son simultáneamente ciertas las dos entradas. Notación: s = a . b  =  ab s = a AND b s = a Y b Propiedades: Conmutativa:  s = ab = ba Asociativa:  s = (ab)c = a(bc) = abc

§5.3  F₈  Operación Not-Or, NOR:  La salida es cierta si ninguna de las entradas lo es.

Notación:  s = a ↓ b = a+b

Propiedades:

Conmutativa:  s = a ↓ b = b ↓ a

No asociativa: a ↓ (b ↓ c) ≠ (a ↓ b) ↓ c ≠ a+b+c

§5.4  F₁₄  Operación Not-And, NAND:   La salida es cierta siempre que no sean simultáneamente ciertas las dos entradas.

Notación:  s = a b = ab ≠ a.b

Propiedades

Conmutativa:  s = a b = b a

No asociativa: a (b c) ≠ (a b) c ≠ abc

a a = a = aa

§5.5  F₆  Operación Exclusive-OR, EOR:   La salida es cierta cuando solo una de las entradas es cierta.

Notación:  s = a ⊕ b

Propiedades:

Conmutativa:  s = a ⊕ b = b ⊕ a

Asociativa:  a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c = a ⊕ b ⊕ c

§5.6  F₉  Operación Exclusive-Not-OR, ENOR:   Esta función es la negación de la anterior. Se llama también Equivalencia, porque según puede verse en su tabla de verdad, mantiene en la salida un 1 lógico solo cuando a = b.

Notación:  s = a⊕b

§5.7  F₁₁/F₁₃  Función Implicación.

s = a ⊃ b a b s 0 0 1 0 1 1 1 0 0 1 1 1 s = b ⊃ a a b s 0 0 1 0 1 0 1 0 1 1 1 1

Notación:

s = a ⊃ b   Debe leerse: a implica b

s = b ⊃ a   Debe leerse: b implica a

Si una variable s está definida respecto a otras dos mediante una expresión de implicación de este tipo: s = a ⊃ b, debe entenderse que a implica a b en el sentido siguiente: Supongamos que la variable lógica a representa si un ser vivo pertenece a la raza humana, y que la variable b representa si un ser vivo es de sangre caliente (1) o fría (0). La variable s, definida mediante la ecuación s = a ⊃ b representa la condición que podría enunciarse mas o menos así:  "Si es ser humano su sangre debe ser de caliente necesariamente". La variable s representa esta implicación, indicándonos en cada caso si puede ser cierta o no cada una de las combinaciones de valores a y b, en el supuesto de que la implicación sea consistente. Veamos las posibilidades en este ejemplo analizando la tabla de verdad:

a no es humano (a=0), b no es de sangre caliente (b=0)  Podría ser cierto? Si (s = 1)

a no es humano (a=0), b si es de sangre caliente (b=1)  Podría ser cierto? Si (s = 1)

a si es humano (a=1), b no es de sangre caliente (b=0)  Podría ser cierto? No (s = 0)

a si es humano (a=1),  b si es de sangre caliente (b=1)  Podría ser cierto? Si (s = 1)

§5.8  F₂/F₄  Funciones de negación de implicación,  NOT implicación.

Observamos que estas funciones son la negación de las anteriores.

Notación:

F₂:  s = a ⊃ b   Debe leerse: a NOT implica b

F₄:  s = b ⊃ a   Debe leerse: b NOT implica a

Las tablas de verdad pueden construirse a partir de las anteriores (§5.7), cambiando los ceros por unos y viceversa (negando los valores correspondientes) en la columna s.

  Inicio.

---

[1]  Esto significa sencillamente que en un momento dado, una variable binaria puede adoptar un valor u otro (no ambos a la vez). En las lógicas de más de dos estados la variable podría optar entre más de dos valores. Por ejemplo, en la lógica ternaria podría ser "cierto", "falso" y "desconocido" (no definido, etc). Existe un tipo de lógica de más de dos estados, la lógica difusa, en la que las variables pueden adoptar múltiples valores, intermedios entre dos posiciones extremas. Estos valores intermedios representan estados no excluyentes. Por ejemplo, entre "cierto" y "falso" cabrían todo tipo de situaciones intermedias:  "casi completamente cierto", "medianamente cierto", etc. En estos casos, la variable tiene, en mayor o menor proporción, una componente de los valores extremos. En cierto sentido podríamos decir que la lógica binaria es absolutamente maniquea, mientras que la difusa se acercaría más al mundo real.