1.1: El bit booleano

Como hemos visto, la información puede ser comunicada por secuencias de valores 0 y 1. Al usar solo 0 y 1, podemos tratar datos de muchos tipos diferentes de fuentes, y no preocuparnos por lo que significan los datos. Con ello estamos utilizando valores abstractos, no específicos. Este enfoque nos permite ignorar muchos detalles desordenados asociados con sistemas específicos de procesamiento y transmisión de información.

Los bits son simples, teniendo sólo dos valores posibles. Las matemáticas utilizadas para denotar y manipular bits simples no son difíciles. Se le conoce como álgebra booleana, según el matemático George Boole (1815—1864). De alguna manera el álgebra booleana es similar al álgebra de enteros o números reales que se enseña en la secundaria, pero de otras maneras es diferente.

El álgebra es una rama de las matemáticas que trata de variables que tienen ciertos valores posibles, y de funciones que, cuando se presentan con una o más variables, devuelven un resultado que nuevamente tiene ciertos valores posibles. En el caso del álgebra booleana, los valores posibles son 0 y 1.

Primero considere las funciones booleanas de una sola variable que devuelven un solo valor. Exactamente son cuatro de ellos. Uno, llamado la identidad, simplemente devuelve su argumento. Otro, llamado no (o negación, inversión o complemento) cambia 0 en 1 y viceversa. Los otros dos simplemente devuelven 0 o 1 independientemente del argumento. Aquí hay una tabla que muestra estas cuatro funciones:

Tabla 1.1: Funciones booleanas de una sola variable

\(x\)	\(f(x)\)
Argumento	IDENTIDAD	NO	CERO	UNO
0	0	1	0	1
1	1	0	0	1

Tenga en cuenta que el álgebra booleana es más simple que el álgebra que trata de números enteros o reales, cada uno de los cuales tiene infinitamente muchas funciones de una sola variable.

A continuación, considere las funciones booleanas con dos variables de entrada A y B y un valor de salida C. ¿Cuántas hay? Cada uno de los dos argumentos puede tomar cualquiera de los dos valores, por lo que hay cuatro patrones de entrada posibles (00, 01, 10 y 11). Piense en cada función booleana de dos variables como una cadena de valores booleanos 0 y 1 de longitud igual al número de posibles patrones de entrada, es decir, 4. Hay exactamente 16 (24) formas diferentes de componer tales cadenas, y por lo tanto exactamente 16 funciones booleanas diferentes de dos variables. De estos 16, dos simplemente ignoran la entrada, cuatro asignan la salida para que sea A o B o su complemento, y los otros diez dependen de ambos argumentos. Los más utilizados son\(AND\),\(OR\),\(XOR\) (exclusivos o),\(NAND\) (no y), y\(NOR\) (no o), mostrados en la Tabla 1.2. (De manera similar, debido a que hay 8 posibles patrones de entrada para funciones booleanas de tres entradas, existen\(2^8\) o 256 funciones booleanas diferentes de tres variables).

Tabla 1.2: Cinco de las 16 posibles funciones booleanas de dos variables

\(x\)	\(f(x)\)
Argumento	Y	NAND	O	NI	XOR
00	0	1	0	1	0
01	0	1	1	0	1
10	0	1	1	0	1
11	1	0	1	0	0

Es tentador pensar en los valores booleanos 0 y 1 como los enteros 0 y 1. Entonces\(AND\) correspondería a la multiplicación y\(OR\) a la suma, algo así como. Sin embargo, los resultados familiares del álgebra ordinaria simplemente no se mantienen para el álgebra booleana, por lo que tales analogías son peligrosas. Es importante distinguir los enteros 0 y 1 de los valores booleanos 0 y 1; no son los mismos.

Hay una notación estándar utilizada en álgebra booleana. (Esta notación a veces es confusa, pero otras notaciones que son menos confusas son incómodas en la práctica). La\(AND\) función se representa de la misma manera que la multiplicación, escribiendo dos valores booleanos uno al lado del otro o con un punto intermedio:\(A\, AND\, B\) se escribe\(AB\) o\(A•B\). La\(OR\) función se escribe usando el signo más:\(A\, +\, B\) significa\(A\, OR\, B\). La negación, o la\(NOT\) función, se denota con una barra sobre el símbolo o expresión, así\(NOT\, A\) es\(\overline{A}\). Finalmente, la función exclusive-or\(XOR\) está representada por un círculo con un signo más en su interior,\(A\, ⊕\, B\).

\ begin {ecuación}\ nonumber
\ begin {alineado}
&\ begin {array} {rl}
N O T &\ bar {A}\\
A N D & A\ cdot B\\
n A N D &\ overline {A\ cdot B}
\ end {array}\\
&\ begin {array} {cc}
O R & ; A+B\\
N O R &\ overline {A+B}\\
X O R & A + B\ end {array}
\ end {alineada}
\ end {ecuación}

Tabla 1.3: Símbolos lógicos booleanos

Existen otras anotaciones posibles para el álgebra booleana. El que se usa aquí es el más común. A veces\(AND\)\(OR\),, y\(NOT\) están representados en la forma\(AND(A, B)\),\(OR(A, B)\), y\(NOT(A)\). A veces se usa notación infija donde\(A\, ∧\, B\) denota\(A\, ·\, B\)\(A\, +\, B\),\(A\, ∨\, B\) denota y\(∼A\) denota\(A\). El álgebra booleana también es útil en la lógica matemática, donde la notación\(A\, ∧\, B\)\(A\, ∨\, B\) para\(A\, ·\, B\)\(A\, +\, B\),\(¬A\) para y para\(A\) se usa comúnmente.

Varias propiedades generales de las funciones booleanas son útiles. Estos se pueden probar simplemente demostrando que se mantienen para todos los valores de entrada posibles. Por ejemplo, se dice que una función es reversible si, conociendo la salida, se puede determinar la entrada. Dos de las cuatro funciones de una sola variable son reversibles en este sentido (y de hecho son autoinversas). Claramente ninguna de las funciones de dos (o más) entradas puede ser por sí mismas reversible, ya que hay más variables de entrada que variables de salida. Sin embargo, algunas combinaciones de dos o más de tales funciones pueden ser reversibles si la combinación resultante tiene el nombre número de salidas como entradas; por ejemplo, se demuestra fácilmente que la función exclusiva o\(A\, ⊕\, B\) es reversible cuando se aumenta por la función que devuelve el primer argumento, es decir, decir, más precisamente, la función de dos variables que tiene dos salidas, una\(A\, ⊕\, B\) y la otra\(A\), es reversible.

Para funciones de dos variables, hay muchas propiedades a considerar. Por ejemplo, una función de dos variables\(A\) y\(B\) se dice que es conmutativa si su valor no cambia cuando\(A\) y\(B\) se intercambian, es decir, si\(f(A, B)\) =\(f(B, A)\). Así la función\(AND\) es conmutativa porque\(A\, ·\, B\) =\(B\, ·\, A\). Algunas de las otras 15 funciones también son conmutativas. Algunas otras propiedades de las funciones booleanas se ilustran en las identidades en la Tabla 1.4.

\ begin {array} {rrrr}\ nonumber
\ text {Idempotent:} & A\ cdot A=A &\ text {Absorción:} & A\ cdot (A+B) =A\\
& A+A=A & A+ (A\ cdot B) =A\\
\ text {Complementario:} & A\ cdot\ overline {A} =0 &\ texto {Asociativo:}:} & A\ cdot (B\ cdot C) = (A\ cdot B)\ cdot C\\
& A+\ overline {A} =1 & & A+ (B+C) =( A+B) +C\\
& A\ oplus A =0 & A\ oplus (B\ oplus C) =( A\ oplus B)\ oplus C\\
& A\ oplus\ overline {A} =1 y\
\ text {Mínimo:} & A\ cdot 1=A &\ text { Teorema sin nombre:} & A\ cdot (\ overline {A} +B) =A\ cdot B\\
& A\ cdot 0=0 & & A+ (\ overline {A}\ cdot B) =A+B\
\ texto {Máximo:} & A+0 =A &\ text {De Morgan:} &\ overline {A}\ cdot\ overline {B} =\ sobrelínea {A+B}\\
& A+1=1 & &\ overline {A} +\ overline {B} =\ overline {A\ cdot B}\\
\ text {Conmutativo:} & A\ cdot B=B\ cdot A &\ text {Distributivo:} & A\ cdot (B+C) =( A\ cdot B) + (A\ cdot C)\\
& A+B=B+A & A+ (B\ cdot C) =( A+B)\ cdot (A+C)\\
& A\ oplus B=B\ oplus A\\
&\ overline {A\ cdot B} =\ overline {B\ cdot A}\\
&\ overline {A+B} =\ overline {B+A}\ end {array}

Cuadro 1.4: Propiedades del Álgebra Booleana. Estas fórmulas son válidas para todos los valores de\(A\),\(B\), y\(C\).

El bit booleano tiene la propiedad de que se puede copiar (y también de que se puede descartar). En álgebra booleana la copia se realiza asignando un nombre al bit y luego usando ese nombre más de una vez. Debido a esta propiedad el bit booleano no es un buen modelo para sistemas cuántico-mecánicos. A continuación se describe un modelo diferente, el bit cuántico.