AlgebraBooleana CircuitosLogicos

Álgebra Booleana y Circuitos
Lógicos

UCR – ECCI
CI-1204 Matemáticas Discretas
Prof. M.Sc. Kryscia Daviana Ramírez Benavides

Álgebra Booleana
Tanto los conjuntos como las proposiciones tienen
propiedades similares. Estas propiedades se usan para definir
una estructura matemática llamada álbebra de Boole o
álgebra booleana, en honor de George Boole (1813-1864).
Esta álgebra se utiliza en doscasos concretos:
Compuertas lógicas.
Circuitos de interruptores.

UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

2

Álgebra Booleana (cont.)
Sea B un conjunto en el cual se han definido dos operaciones
binarias, + y *, y una operación unitaria, denotada ’; sean 0 y 1
dos elementos diferentes de B. Entonces a la sextupla
〈 B,+,*, ' ,0,1〉
se le llama álgebra de Boole si secumplen los axiomas de la
tabla para elementos a, b y c cualesquiera en el conjunto B:
Leyes conmutativas.
Leyes distributivas.
Leyes de identidad.
Leyes de complemento.

UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

3

Álgebra Booleana (cont.)
Aspectos importantes del álgebra:
Al elemento 0 se le llama el elemento cero.
Al elemento 1 se le llama elemento unidad.
Ala operación unitaria a’ se le llama complemento de a.
A los resultados de las operaciones binarias + y * se les llama,
respectivamente, suma y producto.

Aparte de los axiomas, en la tabla se muestran otras
propiedades que tiene el álgebra de Boole, que se pueden
obtener mediante los axiomas.

UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

4

UCR-ECCI CI-1204Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

5

Álgebra Booleana (cont.)
Ejemplos:
Sea B el conjunto de dos elementos, {0,1}, con operaciones + y *
definidas:

+ 1 0
1 1 1

* 1 0
1 1 0

0 1 0

0 0 0

Los complementos se defines por 1’ = 0 y 0’ = 1.
El ejemplo anterior se puede extender para sucesiones de n bits, sea
Bn.

UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y CircuitosLógicas

6

Álgebra Booleana (cont.)
Ejemplos:
Sea ζ una colección de conjuntos cerrados bajo uniones,
intersecciones y complementos. Se tiene como elemento cero al
conjunto vacío ∅ y como elemento unidad al conjunto universal U.

〈ζ ,∪,∩, ¬, ∅,U 〉

Sea Π el conjunto de proposiciones, que tiene como operaciones ∨ y
∧, con la negación ∼ como complemento. Se tiene como elemento
cero una contradicción fy como elemento unidad una tautología t.

〈 Π,∨,∧, ≈, f , t 〉

UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

7

Álgebra Booleana (cont.)
Ejemplos:
Sea D70 = {1,2,5,7,10,14,35,70}, los divisores de 70. Se tienen las
operaciones de mínimo común múltiplo de a y b como la suma,
máximo común divisor de a y b como el producto, y 70 dividido
entre a el complemento de a. Setiene como elemento cero al 1 y
como elemento unidad al 70.

〈 D70 , MCM (a, b), MCD (a, b), 70 a ,1,70〉

UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

8

Dualidad
El dual de cualquier enunciado en un álgebra de Boole B es el
enunciado obtenido al intercambiar las operaciones + y *, e
intercambiar los correspondientes elementos identidad 0 y 1,
en el enunciadooriginal.
Ejemplo: (1 + a) * (b + 0) = b ⇒ el dual es: (0 * a) + (b * 1) = b

Principio de Dualidad: El dual de cualquier teorema en un
álgebra de Boole es también un teorema.
En otras palabras, si cualquier enunciado es una consecuencia de los
axiomas de un álgebra de Boole, entonces el dual también es una
consecuencia de estos axiomas; ya que el enunciado dual se puede
probar usando el dual de cadapaso en la demostración del enunciado
original.
UCR-ECCI CI-1204 Matemáticas Discretas
Álgebra Boolena y Circuitos Lógicas

9

Orden y Álgebra de Boole
Una relación p es un conjunto S se llama un orden parcial en
S si cumple las tres propiedades siguientes:
a p a, ∀a ∈ S.
Si a p b y b p a, entonces a = b.
Si a p b y b p c, entonces a p c.

Un conjunto S junto con un orden parcial se llama...