circuitos logicos

Lógica – FCE

CIRCUITOS LÓGICOS

1. ALGEBRA DE BOOLE
1.1 Introducción
Tanto la teoría de conjuntos como la lógica de enunciados tienen propiedades
similares. Tales propiedades se utilizan para definir una estructura matemática denominada
álgebra de Boole, en honor al matemático George Boole (1813-1864).
1.2 Definición de álgebra de Boole
Sea B un conjunto en el cual se definen dosoperaciones binarias, + y *, y una
operación unitaria denotada ; sean 0 y 1 dos elementos diferentes de B. Entonces la
sextupla:
〈B, +, *, , 0, 1〉
se denomina álgebra de Boole si se cumplen los siguientes axiomas para cualesquiera
elementos a, b, c del conjunto B:
[B1]

Conmutatividad:
(1a) a + b = b + a

(1b)

a*b=b*a

[B2]

Distributividad:
(2a) a + (b * c) = (a + b) * (a + c)(2b)

a * (b + c) = (a * b) + (a * c)

[B3]

Identidad:
(3a) a + 0 = a

(3b)

a*1=a

[B4]

Complemento:
(4a) a + a = 1

(4b)

a* a =0

1.3 Terminología y convenciones
• Las operaciones + y * se denominan suma y producto, respectivamente.
• La operación a se denomina complemento de a.
• El elemento 0 se denomina elemento cero (neutro respecto de la suma).

1

• Elelemento 1 se denomina elemento unidad (neutro respecto del producto).
• Por convención, omitimos el símbolo *, usándose en su lugar la yuxtaposición; de este
modo, (2a) y (2b) se escriben:
(2a) a + bc = (a + b) (a + c)

(2b) a (b + c) = ab + ac

• Por convención, establecemos que + es más fuerte que * y * es más fuerte que
ejemplo:

a + b * c significa a + (b * c) y no
a* b
significa a * (b )
y no

; por

(a + b) * c
( a * b)

1.4 Dualidad
En un álgebra de Boole B, el dual de cualquier enunciado es el enunciado obtenido de
intercambiar las operaciones + y *, e intercambiar los elementos neutros 0 y 1 en el
enunciado original. Por ejemplo:
el dual de

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

es

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

Con esta definición de dualidad puede observarse que, en ladefinición de álgebra de
Boole, los axiomas del grupo (1) son duales de los axiomas del grupo (2) y viceversa. En
otras palabras, el dual de cualquier axioma de B también es un axioma. En consecuencia,
se cumple el siguiente teorema:
Teorema 1.1 (Principio de dualidad): En un álgebra de Boole, el dual de cualquier
teorema es también un teorema.
Esto significa que, si cualquier teorema es unaconsecuencia de los axiomas de un álgebra
de Boole, entonces el dual también es una consecuencia de estos axiomas ya que se puede
probar usando el dual en cada paso de la demostración original.
1.5 Teoremas básicos
Utilizando los axiomas de la definición de un álgebra de Boole, pueden demostrarse
los siguientes teoremas:
Teorema 1.2: Sean a, b, c elementos cualesquiera de un álgebra de BooleB, se cumple:
(i)
(ii)
(iii)

Idempotencia:
(5a) a + a = a

(5b)

a*a=a

Acotamiento:
(6a) a + 1 = 1

(6b)

a*0=0

Absorción:
(7a) a + (a * b) = a

(7b)

a * ( a + b) = a

2

(iv)

Asociatividad:
(8a) (a + b) + c = a + (b + c)

(8b)

(a * b) * c = a * (b * c)

Teorema 1.3: Sea a un elemento cualquiera de un álgebra de Boole B, se cumple:
(i)

Unicidad delcomplemento:
Si a + x = 1 y a * x = 0, entonces x = a

(ii)

Involución:
a =a

(iii)

(9a)

0 =1

(9b)

1 =0

Teorema 1.4: Leyes de De Morgan

(10a) a + b = a * b

(10b) a * b = a + b

Es importante insistir que el álgebra de Boole es la estructura algebraica de la lógica
de enunciados. En efecto, si se reemplazan las variables a, b, c, … por variables
proposicionales, lasuma y el producto por la disyunción y la conjunción respectivamente,
el complemento por la negación, la igualdad por el bicondicional, y 1 y 0 por V y F
respectivamente, todos los axiomas y teoremas del álgebra de Boole se transforman en
axiomas o teoremas de la lógica de enunciados. Por ejemplo:
(2b) a * (b + c) = (a * b) + (a * c)

p ∧ (q ∨ r) ↔ (p ∧ q) ∨ (p ∧ r)

(5a) a + a = a...