7

2. Funciones booleanas en el ´algebra de Boole binaria

Consideramos a partir de ahora el ´algebra de Boole binaria B = f 0; 1 g y
denotamos mediante Bn el producto cartesiano de B por s´ı mismo n veces.

Bn = B £ B £ ¢ ¢ ¢ £ B = f(x1; x2; : : : ; xn) = xi 2 f0; 1g; i = 1; : : : ; n; g

Los elementos de Bn son n¡plas de elementos de B, es decir, sucesiones de
0’s y 1’s cuyo n´umero total es n.

Funci´on booleana en B = f 0; 1 g

Llamamos funci´on booleana definida en B = f 0; 1 g o funci´on de conmutaci´on
l´ogica a toda aplicaci´on

f : Bn ! B

de manera que f(x1; x2; : : : ; xn) pueda expresarse a partir de las operaciones
definidas en B efectuadas sobre las variables x1; x2; : : : ; xn.

Ejemplos

f : B2 ! B definida por f(x1; x2) = x1 + x2

g : B2 ! B definida por g(x1; x2) = x1 x2

Tablas de valores o tablas de verdad

Toda funci´on booleana en B = f 0; 1 g puede representarse mediante tablas
de valores o tablas de verdad. Las n primeras columnas permiten representar
los 2n elementos de Bn y la columna final indica el valor asignado por la
funci´on f a cada n¡pla (x1; x2; : : : ; xn).

Ejemplo

Tablas de verdad de algunas funciones binarias (de dos variables) definidas
en B = f 0; 1 g.

OR AND XOR NAND NOR

x1 x2 x1 + x2 x1 x2 x1 © x2 x1 j x2 x1 # x2

0 0 0 0 0 1 1
0 1 1 0 1 1 0
1 0 1 0 1 1 0
1 1 1 1 0 0 0
8

El ´algebra de Boole binaria de los interruptores

Un interruptor instalado en un circuito el´ectrico es un mecanismo que produce
dos respuestas: permite o impide el paso de la corriente el´ectrica.
Se puede pensar en el conjunto de respuestas de un interruptor como en los
elementos de un ´algebra de Boole binaria B = f 0; 1 g, asociando valor 1 a la
variable que denota el interruptor en caso de permitir el paso de la corriente
y valor 0 en caso de impedir el paso de la misma.

x toma valor 0 x toma valor 1
La suma de dos variables x, y asociadas a interruptores corresponde a la
instalaci´on de ambos interruptores en paralelo. El interruptor asociado a la
suma x + y ofrece respuesta 0 ´unicamente en el caso en que x, y ofrecen
respuesta 0.

x
y
x + y
x y x + y

0 0 0
0 1 1
1 0 1
1 1 1
9
Por su lado, el producto de dos variables x, y asociadas a interruptores
corresponde a la instalaci´on en serie. El interruptor asociado al producto x y

´unicamente ofrece respuesta 1 si x, y ofrecen respuesta 1.

x y x y
x y x y

0 0 0
0 1 0
1 0 0
1 1 1

N´umero de funciones booleanas en el ´algebra de Boole binaria

Para el ´algebra de Boole binaria
B = f 0; 1 g, el n´umero de funciones de n
variables
f : Bn ! B resulta ser igual al n´umero de variaciones con repetici´on
de 2 elementos tomados de 2
n en 2n.
El n´umero de elementos en el conjunto
Bn es 2n y para cada uno de estos
elementos una funci´on
f definida sobre B = f 0; 1 g puede tomar valor 0 o
valor 1. Entonces,

card
f f = f
: Bn ! Bg = RV2;2n = 2(2n)
Para
n = 2, el n´umero de funciones de conmutaci´on l´ogica de dos variables
es 2
4 = 16; para n = 3, el n´umero de funciones de tres variables es 28 = 256;
para
n = 4, el n´umero de funciones de cuatro variables es 216 = 65536.