Lógica – FCE CIRCUITOS LÓGICOS

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  dos operaciones  binarias,  + y *,  y una operación unitaria denotada    ; sean 0 y 1 dos elementos diferentes de B.   Entonces la[pic 2]

sextupla:

〈B, +, *,    , 0, 1〉[pic 3]

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[pic 4][pic 5]

1.3  Terminología y convenciones

∙   Las operaciones + y * se denominan suma y producto, respectivamente.

∙   La operación a se denomina complemento de a.[pic 6]

∙   El elemento 0 se denomina elemento cero (neutro respecto de la suma).

∙   El elemento 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    ; por ejemplo:[pic 7]

a + b * c    significa    a + (b * c)    y no    (a + b) * c a * b         significa    a * ( b )        y no    (a * b)[pic 8][pic 9][pic 10]

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 la definició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 una consecuencia 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 Boole B, se cumple: (i)        Idempotencia:

(5a)     a + a = a                                             (5b)     a * a = a

(ii)       Acotamiento:

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

(iii)     Absorción:

(7a)     a + (a * b) = a                                    (7b)     a * (a + b) = a

(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:

(iii)     (9a)      0 = 1                                                  (9b)     1 = 0[pic 11]

Teorema 1.4: Leyes de De Morgan

(10a)[pic 12][pic 13][pic 14][pic 15][pic 16][pic 17]

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, la suma 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:

...