Facultad de Ciencias Exactas, Ingenierı́a

y Agrimensura (FCEIA - UNR)

Tecnicatura Universitaria en Inteligencia Artificial
Lógica

Unidad 4: Algebra de Boole.

Definición:
Un álgebra booleana B consiste en un conjunto S que contiene elementos distintos 0 y 1, operadores
binarios + y · en S, y un operador unitario ′ en S que satisface las siguientes leyes:

a) Leyes asociativas:
(x + y) + z = x + (y + z), para todo x, y, z ∈ S
(x · y) · z = x · (y · z), para todo x, y, z ∈ S

b) Leyes conmutativas:
x + y = y + x, para todo x, y ∈ S
x · y = y · x, para todo x, y ∈ S

c) Leyes distributivas:
x · (y + z) = (x · y) + (x · z), para todo x, y, z ∈ S
x + (y · z) = (x + y) · (x + z), para todo x, y, z ∈ S

d) Leyes de identidad:
x + 0 = x, para todo x ∈ S
x · 1 = x, para todo x ∈ S

e) Leyes de complemento:
x + x′ = 1, para todo x ∈ S
x · x′ = 0, para todo x ∈ S

Si B es un álgebra booleana, se escribe B = (S, +, ·,′ , 0, 1).

Es adecuado hacer algunos comentarios respecto a la definición anterior. En primer lugar, 0 y 1 son
sólo nombres simbólicos y, en general, no tienen relación con los números 0 y 1. Este mismo comen-
tario se aplica a + y ·, que sólo denotan operadores binarios y, en general, no tienen relación con la
suma y multiplicación comunes.

Ejemplo:
Sea U un conjunto universal y sea S = P (U ) el conjunto potencia de U . Si se definen las siguientes
operaciones:

X +Y =X ∪Y,

X · Y = X ∩ Y,

2022 1/11
 X′ = X

en S, entonces (S, ∪, ∩, , ∅, U ) es un álgebra booleana.

El conjunto vacı́o ∅ asume el papel de 0 y el conjunto universal U hace el papel de 1. Si X, Y y Z
son subconjuntos de S, las propiedades 1. a la 5. de la definición de algebra booleana se convierten
en las siguientes propiedades de conjuntos:

1. (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z), para todo X, Y, Z ∈ P (U )

(X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z), para todo X, Y, Z ∈ P (U )
2. X ∪ Y = Y ∪ X, para todo X, Y ∈ P (U )
X ∩ Y = Y ∩ X, para todo X, Y ∈ P (U )
3. X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z), para todo X, Y, Z ∈ P (U )
X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z), para todo X, Y, Z ∈ P (U )
4. X ∪ ∅ = X, para todo X ∈ P (U )
X ∩ U = X, para todo X ∈ P (U )
5. X ∪ X = U, para todo X ∈ P (U )
X ∩ X = ∅, para todo X ∈ P (U )

Teorema
En un álgebra booleana, el elemento x′ de la definición es único. Especı́ficamente, si x + y = 1 y
x · y = 0, entonces y = x′ .
Demostración:
y = y · 1 (def. de algebra booleana, item d)
= y · (x + x′ ) (def. de algebra booleana, item e))
= y · x + y · x′ (def. de algebra booleana, item c))
= x · y + y · x′ (def. de algebra booleana, item b))
= 0 + y · x′ (información proporcionada)
= x · x′ + y · x′ (def. de algebra booleana, item e))
= x′ · x + x′ · y (def. de algebra booleana, item b))
= x′ · (x + y) (def. de algebra booleana, item c))
= x′ · 1 (información proporcionada)
= x′ (def. de algebra booleana, item d))

Definición
En un álgebra booleana, el elemento x′ recibe el nombre de complemento de x.

Sin duda el lector ha observado que las ecuaciones que incluyen elementos de un álgebra booleana
vienen en pares. Por ejemplo, las leyes de identidad en la definición de álgebra booleana (item d))
son:

x+0=x
x·1=x

2022 2/11
Se dice que estos pares son duales.

Definición
El dual de una afirmación que incluye expresiones booleanas se obtiene sustituyendo 0 por 1, 1 por
0, + por · y · por +.

Ejemplo:
El dual de (x + y)′ = x′ · y ′ es (x · y)′ = x′ + y ′ .

Teorema:
El dual de un teorema de álgebras booleanas también es un teorema.
Demostración:
Suponga que T es un teorema de álgebras booleanas. Entonces existe una prueba P de T que invo-
lucra sólo las definiciones de un álgebra booleana. Sea P ′ la secuencia de afirmaciones obtenidas al
sustituir cada enunciado en P por su dual. Entonces P ′ es una prueba del dual de T .

Circuitos Combinatorios
En una computadora digital sólo hay dos posibilidades, que se escriben como 0 y 1, para el obje-
to indivisible más pequeño. En última instancia, todos los programas y datos se pueden reducir a
combinaciones de bits. A través de los años se ha usado una variedad de dispositivos en las compu-
tadoras digitales para almacenar bits. Los circuitos electrónicos permiten que estos dispositivos de
almacenamiento se comuniquen entre sı́. Un bit en una parte del circuito es trasmitido a otra parte
del circuito como un voltaje. Entonces se necesitan dos niveles de voltaje; por ejemplo, un voltaje
alto puede comunicar un 1 y un voltaje bajo, un 0.
En esta sección analizaremos los circuitos combinatorios. La salida de un circuito combinatorio se
define de manera única para cada combinación de entradas. Un circuito de este tipo carece de
memoria; las entradas anteriores y el estado del sistema no afectan su salida.
Los circuitos combinatorios se pueden construir usando dispositivos de estado sólido, llamados com-
puertas, que son capaces de cambiar los niveles de voltaje (bits). Se comenzará por analizar las
compuertas AND (y), OR (o) y NOT (no).

Definición:
Una compuerta AND recibe entradas x1 y x2 , donde x1 y x2 son bits, y produce una salida denotada
por x1 ∧ x2 , donde

1 si x1 = 1 y x2 = 1
x1 ∧ x2 =
0 de otra manera

Una compuerta AND se dibuja como se indica en la figura 1

Definición:
Una compuerta OR recibe entradas x1 y x2 , donde x1 y x2 son bits, y produce una salida denotada

2022 3/11
 Figura 1: Compuerta AND

por x1 ∨ x2 , donde

1 si x1 = 1 o x2 = 1
x1 ∨ x2 =
0 de otra manera

Una compuerta OR se dibuja como se indica en la figura 2

Figura 2: Compuerta OR

Definición:
Una compuerta NOT (o inversor) recibe una entrada x, donde x es un bit, y produce una salida
denotada por x, donde

1 si x = 0
x=
0 si x = 1

Una compuerta NOT se dibuja como se indica en la figura 3

Figura 3: Compuerta NOT

La tabla lógica de un circuito combinatorio lista todas las entradas posibles junto con las salidas
producidas.
A continuación aparecen las tablas lógicas para los circuitos AND, OR y NOT básicos (Tablas 1, 4
y 3).

x1 x2 x1 ∧ x2
1 1 1
1 0 0
0 1 0
0 0 0
Cuadro 1: Tabla lógica del AND

Se observa que realizar la operación AND (OR) es lo mismo que tomar el mı́nimo (máximo) de dos
bits x1 y x2 .

2022 4/11
 x1 x2 x1 ∨ x2
1 1 1
1 0 1
0 1 1
0 0 0
Cuadro 2: Tabla lógica del OR

x x
1 0
0 1
Cuadro 3: Tabla lógica del NOT

Ejemplo: El circuito de la Figura 4 es un ejemplo de un circuito combinatorio, ya que la salida y se

define de manera única para cada combinación de entradas x1 , x2 y x3 .
La tabla lógica para este circuito combinatorio es la siguiente:

x1 x2 x3 y
1 1 1 0
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1
Cuadro 4: Tabla lógica del Circuito Combinatorio

Observe que se listan todas las combinaciones posibles de los valores de las entradas x1 , x2 y x3 . Para
un conjunto determinado de entradas, el valor de la salida y se calcula rastreando el flujo a través del
circuito. Por ejemplo, la cuarta lı́nea de la tabla da el valor de la salida y para los valores de entrada

x1 = 1, x2 = 0, x3 = 0

Si x1 = 1 y x2 = 0, la salida de la compuerta AND es 0 (vea la Figura 5). Como x3 = 0, las entradas

a la compuerta OR son ambas 0. Por lo tanto, la salida de la compuerta OR es 0. Como la entrada
a la compuerta NOT es 0, se produce una salida y = 1.

Figura 4: Un circuito combinatorio

2022 5/11
 Figura 5: Circuito de la Figura 4 cuando x1 = 1 y x2 = x3 = 0

Un circuito combinatorio con una salida, como el de la Figura 4, se representa mediante una expresión
que usa los sı́mbolos ∧, ∨ y ¬. Se sigue el flujo del circuito simbólicamente. Primero se aplica AND
a x1 y x2 (Figura 6), lo que produce la salida x1 ∧ x2 . Esta salida después se une por OR con x3 para
producir la salida (x1 ∧ x2 ) ∨ x3 . Después se aplica NOT a esta salida. Entonces la salida y puede ser

Figura 6: Representación de un circuito combinatorio mediante una expresión booleana.

Definición
Las expresiones booleanas en los sı́mbolos x1 , · · · , xn se definen de manera recursiva como sigue.

0, 1, x1 , · · · , xn

son expresiones booleanas. Si X1 y X2 son expresiones booleanas, entonces

a) (X1 )

b) X1

c) (X1 ∨ X2 )

d) (X1 ∧ X2 )

son expresiones booleanas.

Si X es una expresión booleana en los sı́mbolos x1 , · · · , xn , algunas veces se escribe

X = X(x1 , · · · , xn )

Cualquiera de los sı́mbolos x o x se llama literal.

Por el item a) de la definición de expresión booleana, x1 y x2 son expresiones booleanas. Por el item
d), x1 ∧x2 es una expresión booleana. Por a), (x1∧x2) es una expresión booleana. x3 es una expresión
booleana también es una expresión booleana. Como (x1 ∧ x2 ) y x3 son expresiones booleanas, por
c), también lo es (x1 ∧ x2 ) ∨ x3 . Por último, se aplica b) para concluir que

(x1 ∧ x2 ) ∨ x3

2022 6/11
 x1 x2 x1 ⊕ x2
1 1 0
1 0 1
0 1 1
0 0 0
Cuadro 5: OR-exclusivo

es una expresión booleana.

Si X = X(x1 , · · · , xn ) es una expresión booleana y se asignan valores a1 , · · · , an en {0, 1} a x1 , · · · , xn
para calcular el valor de X. Este valor se denota por X(a1 , · · · , an ) o X(xi = ai).

Funciones booleanas y simplificación de circuitos

Un circuito permite realizar una tarea especı́fica. Si se quiere construir un circuito combinatorio, el
problema puede darse en términos de entradas y salidas. Por ejemplo, suponga que se desea construir
un circuito combinatorio para calcular el OR-exclusivo de x1 y x2. Se puede establecer el problema
haciendo una lista de las entradas y salidas que define el ORexclusivo. Esto equivale a elaborar la
tabla lógica deseada.

Definición
El OR-exclusivo de x1 y x2 escrito x1 ⊕ x2 se define en la Tabla 5.
Una tabla lógica, con una salida, es una función. El dominio es el conjunto de entradas y el recorrido
o imagen es el conjunto de salidas. Para la función OR-exclusivo dada en la tabla 5, el dominio es el
conjunto

{(1, 1), (1, 0), (0, 1), (0, 0)}

y el rango

Z2 = {0, 1}

Si se pudiera desarrollar una fórmula para la función OR-exclusivo de la forma

x1 ⊕ x2 = X(x1 , x2 )

donde X es un expresión booleana, se podrı́a resolver el problema de la construcción del circuito

combinatorio. Se podrı́a simplemente construir el circuito correspondiente a X.

Definición
Las funciones que se pueden representar por expresiones booleanas se llaman funciones booleanas.
Sea X(x1 , . . . , xn ) un expresión booleana. Una función f de la forma

f (x1 , . . . , xn ) = X(x1 , . . . , xn )

2022 7/11
 x1 x2 x3 f (x1 , x2 , x3 )
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 0

Cuadro 6: Tabla lógica correspondiente a la expresión booleana x1 ∧ (x2 ∨ x3 )

x1 x2 x3 f (x1 , x2 , x3 )
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 0
Cuadro 7:

se llama función booleana.

Definición
Si f : Z2n → Z2 , entonces el complemento de una función booleana f , que se denota f , es la función
booleana definida sobre Z2n como

f (x1 , . . . , xn ) = f (x1 , . . . , xn )

Ejemplo:
La función f : Z23 → Z2 definida por

f (x1 , x2 , x3 ) = x1 ∧ (x2 ∨ x3 )

es una función booleana. Las entradas y salidas se dan en la tabla 6.

En el siguiente ejemplo se muestra cómo una función f : Z2n → Z2 puede interpretarse como una
función booleana.

Ejemplo:
Demuestre que la función f dada por la Tabla 7 es una función booleana.
Considere el primer renglón de la tabla y la combinación

2022 8/11
 x1 ∧ x2 ∧ x 3

Observe que si x1 = x2 = x3 = 1, como se indica en el primer renglón de la tabla, entonces la

expresión x1 ∧ x2 ∧ x3 es 1. Los valores de xi dados por cualquier otro renglón de la tabla dan un
valor de 0 a la expresión anterior. De manera similar, para el cuarto renglón de la tabla se puede
construir la combinación

x1 ∧ x2 ∧ x 3

La expresión x1 ∧ x2 ∧ x3 tiene el valor 1 para los valores de xi dados por el cuarto renglón de la
tabla, mientras que los valores de xi dados por cualquier otro renglón de la tabla dan el valor 0.
El procedimiento es claro. Se considera un renglón R de la tabla cuya salida es 1. Después se forma
la combinación x1 ∧ x2 ∧ x3 y se coloca una barra sobre cada xi cuyo valor sea 0 en el renglón R. La
combinación formada es 1 si y sólo si las xi tienen los valores dados en el renglón R. Entonces, para
el renglón 6, se obtiene la combinación

x1 ∧ x2 ∧ x 3

Después, se aplica OR a los términos para obtener la expresión booleana

(x1 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x2 ∧ x3 )

Se asegura que f (x1 , x2 , x3 ) y (x1 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x2 ∧ x3 ) son iguales. Por lo tanto,

f (x1 , x2 , x3 ) = (x1 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x2 ∧ x3 ) ∨ (x1 ∧ x2 ∧ x3 )

Después de una definición más, se mostrará que el método del ejemplo anterior se puede usar para
representar cualquier f : Z2n → Z2 .

Definición
Un mintérmino en los sı́mbolos x1 , . . . , xn es una expresión booleana de la forma

y1 ∧ y2 ∧ . . . ∧ yn ,

donde cada yi es ya sea xi o xi .

Teorema:
Si f : Z2n → Z2 , entonces f es una función booleana. Si f no es idénticamente cero, sea A1 , . . . , Ak
los elementos Aj de Z2n para los cuales f (Ai ) = 1. Para cada Ai = (a1 , . . . , an ), sea

mi = y1 ∧ · · · ∧ yn ,

donde

2022 9/11
 
xj si aj = 1
yj =
xj si aj = 0

entonces

f (x1 , . . . , xn ) = m1 ∨ m2 ∨ . . . ∨ mk

Demostración:
Si f (x1 , . . . , xn ) = 0 para todo xi , entonces f es una función booleana, ya que 0 es una expresión
booleana.
Suponga que f no es idénticamente cero. Sea mi (a1 , . . . , an ) el valor obtenido de mi al sustituir cada
xj por aj . Se deduce de la definición de mi que

1 si A = Ai
mi (A) =
0 si A ̸= Ai

Sea A ∈ Z2n . Si A = Ai para alguna i ∈ {1, . . . , k}, entonces f (A) = 1, mi (A) = 1 y

m1 (A) ∨ . . . ∨ mk (A) = 1

Por otro lado, si A ̸= Ai para cualquier i ∈ {1, . . . , k}, entonces f (A) = 0, mi (A) = 0 para i = 1, . . . , k
y

m1 (A) ∨ . . . ∨ mk (A) = 0

Por lo tanto, f (x1 , . . . , xn ) = m1 ∨ m2 ∨ . . . ∨ mk se cumple.

Definición
La representación f (x1 , . . . , xn ) = m1 ∨ m2 ∨ . . . ∨ mk de una función booleana f : Z2n → Z2 se llama
forma disyuntiva normal de la función f.

El Teorema anterior tiene un dual. En este caso la función f se expresa como

f (x1 , . . . , xn ) = M1 ∧ M2 ∧ . . . ∧ Mk

Cada Mi es de la forma

y1 ∨ . . . ∨ yn
,

2022 10/11
donde yj es ya sea xj o xj . Un término de la forma y1 ∨. . .∨yn se llama maxtérmino y la representación
de f (x1 , . . . , xn ) = M1 ∧ M2 ∧ . . . ∧ Mk se llama forma conjuntiva normal.

2022 11/11