Álgebra booleana

Unidad 2. Algebra Booleana y representación de funciones lógicas Unidad 2. Algebra Booleana y representación de funciones lógicas

SISTEMAS DIGITALES COMBINACIONALES

FCE – BUAP 
M.C. Héctor Santiago Ramírez

Algebra Booleana
Constituye la base matemática para el diseño de sistemas digitales. g Desarrollado por primera vez por George Boole como un enfoque matemático del razonamientohumano. Le siguieron DeMorgan y Huntington con trabajos similares. Claude E. Shannon demostró en 1938 la posibilidad de emplear el álgebra booleana para predecir el comportamiento de circuitos eléctricos de conmutación a base de relevadores → Algebra de conmutación. Algebra de conmutación = Algebra booleana (binaria) (binaria).
FCE – BUAP 
M.C. Héctor Santiago Ramírez

2.1 Axiomas (postulados)del álgebra booleana
Postulado 1: Definición.
• El álgebra Booleana es un sistema algebraico cerrado que contiene un conjunto de dos elementos: B={0, 1}; • y un conjunto K de dos operadores: K={· ,+} K { , } • Los operadores también suelen representarse como: K {AND, K={AND OR} • La clausura implica que si • entonces
FCE – BUAP 
M.C. Héctor Santiago Ramírez

a, b ∈ B

a ⋅b ∈ B y a + b ∈ BAxiomas… Axiomas
Postulado 2: Identidad.
• Existen los elementos únicos 0 y 1 en B tal que para cada a en B se tienen:

(a) a + 0 = a
• Sean: a, b ∈ B • Entonces:

(b) a ⋅1 = a

Postulado 3: Conmutatividad Conmutatividad.

(a) a + b = b + a
FCE – BUAP 

(b) a ⋅ b = b ⋅ a
M.C. Héctor Santiago Ramírez

Axiomas… Axiomas
Postulado 4: Asociatividad.
• Sean a, b ∈ B • Entonces:(a) a + (b + c) = (a + b) + c
Postulado 5: Distributividad.
• S Sean a, b ∈ B • Entonces:

(b) a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c

(a) a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c) (b) a + (b ⋅ c) = (a + b) ⋅ (a + c)
FCE – BUAP 
M.C. Héctor Santiago Ramírez

Axiomas… Axiomas
Postulado 6: Complementariedad.
• Para toda a en B existe un único elemento llamado complemento de a y denotado como:

a' o a
• talque:

(a) a + a = 1
• Además Además,

(b) a ⋅ a = 0

a'∈ B
M.C. Héctor Santiago Ramírez

FCE – BUAP 

2.2 2 2 Teoremas
Cometarios:
• Los teoremas nos servirán para la simplificación algebraica de expresiones booleanas. • La demostración de los teoremas se puede realizar a partir de los axiomas o a partir de la tabla de verdad de los operadores binarios AND y OR.

Teorema 1:Idempotencia.

(a) ( )a+a =a (b) a ⋅ a = a
FCE – BUAP 

Demostraciones con tablas de verdad Demostraciones con tablas de verdad

a 0 1

a+a 0 1

a  a a ∙ a 0 1

M.C. Héctor Santiago Ramírez

… Teoremas
Teorema 2: Elementos nulos.

(a) a + 1 = 1 (b) a ⋅ 0 = 0

Demostración

a + 1 = (a + 1) ⋅1 = (a + 1) ⋅ (a + a ) = a + (1⋅ a ) =a+a =1

Ejercicio: ¿Cuáles postulados se emplearonen cada línea de la demostración?
FCE – BUAP 
M.C. Héctor Santiago Ramírez

… Teoremas
Teorema 3: Absorción.

(a) a + ab = a (b) a ⋅ (a + b) = a

Demostración

a + ab = a ⋅1 + a ⋅ b = a ⋅ (1 + b) = a ⋅ (b + 1) = a ⋅ (1) =a

Ejercicio: ¿Cuáles postulados se emplearon en cada línea de la demostración?
FCE – BUAP 
M.C. Héctor Santiago Ramírez

… Teoremas
Teorema 4: Absorción delcomplemento.

(a) a + a ' b = a + b (b) a ⋅ (a '+b) = a ⋅ b

Demostración

a + a ' b = ( a + a ' ) ⋅ ( a + b) = (1) ⋅ (a + b) = a+b

Teorema 5: Fusión.

(a) ab + ab' = a ( ) (b) (a + b)(a + b' ) = a

FCE – BUAP 
M.C. Héctor Santiago Ramírez

… Teoremas
Teorema 6: DeMorgan. Teorema 8: Factorización.

(a) a + b = a ⋅ b (b) a ⋅ b = a + b

(a) a ⋅ b + a ⋅ c = (a + c) ⋅ (a + b) (b)(a + b) ⋅ (a + c) = a ⋅ c + a ⋅ b

Teorema 7: Consenso.

(a) ab + a' c + bc = ab + a' c ( ) (b) (a + b)(a'+c)(b + c) = (a + b)(a'+c) )( )( ) )(
FCE – BUAP 
M.C. Héctor Santiago Ramírez

Principio de dualidad
Establece que si una expresión es válida en el álgebra booleana, entonces, su expresión dual también es válida. , , p Determinamos la expresión dual de una expresión:
• Cambiando...