Sean
un conjunto {0,1} y dos leyes de composición interna +
y ·, entonces se puede observar como funciona la
siguiente estructura:
- Para +:
- 0+0=0
- 0+1=1
- 1+0=1
- 1+1=1
- Para · :
- 0·0=0
- 0·1=0
- 1·0=0
- 1·1=1
Por
tanto cumple las siguientes propiedades:
- Para +:
- La asociativa: eg. 0+(1+0)=(0+1)+0
- La conmutativa: eg. 0+1=1+0
- La modular: eg. 1+0=1, 0+0=0
- Para · :
- La asociativa: eg. 0·(0·1)=(0·1)·1
- La conmutativa: eg. 0·1=1·0
- La modular: eg. 0·1=0, 1·1=1
Dadas
las propiedades, la estructura algebraica planteada es un semianillo
abeliano. Así se desarrolla la lógica matemática
aplicada digitalmente a circuitos integrados. En general se puede
establecer lo siguiente:
- Sean los elementos a, b ∈ {0,1}, entonces se cumple para +, es decir, la disyunción:
- La propiedad asociativa: a+(b+c)=(a+b)+c
- La propiedad conmutativa: a+b=b+a
- La propiedad modular: a+0=a; b+0=b
- Nótese que a+a=a, en efecto, 0+0=0 y 1+1=1
- Sean los elementos a, b ∈ {0,1}, entonces se cumple para ·, es decir, la conjunción:
- La propiedad asociativa: a·(b·c)=(a·b)·c
- La propiedad conmutativa: a·b=b·a
- La propiedad modular: a·1=a; b·1=b
- Nótese que a·a=a, en efecto, 0·0=0 y 1·1=1
- Dado que es un semianillo abeliano y con a, b, c ∈ {0,1}, se cumple lo siguiente para ambas leyes de composición:
- La propiedad distributiva: a·(b+c)=a·b+a·c
Ahora
bien, se pueden desarrollar funciones dentro del semianillo abeliano
que se ha observado:
- La función de negación se define y se caracteriza como sigue:
- ∀a | a ∈ {0,1}, a'={1. a'=0 | a=1, 2. a'=1 | a=0
- O sea, que para esta función y sólo ésta, la ley de disyunción no está definida cuando b=a.
- Nótese que a+a'=1, a·a'=0, (a')'=a.
- Para la función de disyunción exclusiva se tiene:
- ∀a, b | a, b ∈ {0,1}, a⊕b=a·b'+a'·b
- Es una función compuesta por otras funciones (negación, diyunción y conjunción) y por dos variables.
En
general todas las funciones, mientras sean deducidas con una variable
y varios parámetros y estén definidas en todas las
operaciones del semianillo, pueden ser deducidas a partir de las
condiciones que se marquen, por ejemplo:
- Sea la función como se muestra a continuación:
- f(0,0)=1, f(0,1)=1, f(1,0)=1, f(1,1)=0.
- Así que: f(a,b)=a'·b'+a'·b+a·b'
- Sólo se operan disyuntivamente los valores de la función iguales a 1 dado que en la disyunción el 0 es el elemento neutro y por tanto no es determinante para la estructura de la misma.
- Dado que sólo se toman los valores de 1 disyuntivamente, conjuntivamente se toman todos los casos 0 como funciones de negación de las variables y todos los casos 1 como las variables ya que así se procura la obtención de los 1 buscados. Así f(0,0) implica a'·b', f(0,1) implica a'·b, etc.
- Sea la función como se muestra a continuación:
- f(0,0,0)=1, f(0,0,1)=0, f(0,1,0)=1, f(0,1,1)=1, f(1,0,0)=1, f(1,0,1)=1, f(1,1,0)=0, f(1,1,0)=0, f(1,1,1)=0.
- Así que: f(a,b,c)=a'·b'·c'+a'·b·c'+a'·b·c+a·b'·c'+a·b'·c, f(a,b,c)=a'·c'·(b'+b)+a'·b·c+a·b'·(c'+c), f(a,b,c)=a'·c'+a'·b·c+a·b', f(a,b,c)=a'·(c'+b·c)+a·b'
- Se simplifica la función dada la propiedad distributiva y se halla al elemento neutro de la conjunción.
- De la función de negación de la disyunción exclusiva se entiende lo siguiente:
- ∀a, b | a, b ∈ {0,1}, a⨀b=a'·b'+a·b
- Se puede demostrar que a⨀b=(a⊕b)'
- Demostración: Se deduce la función dados los valores posibles (a⊕b)'=f(a,b); f(0,0)=1, f(0,1)=0, f(1,0)=0, f(1,1)=1. Así (a⊕b)'=a'·b'+a·b=a⨀b.
Háblese
ahora de las funciones de Morgan:
- Primera: (a+b)'=a'·b'=m₁(a,b)
- Demostración: m₁(0,0)=1, m₁(0,1)=0, m₁(1,0)=0, m₁(1,1)=0 ⇔ m₁(a,b)=a'·b'
- Segunda: (a·b)'=a'+b'=m₂(a,b)
- Demostración: Dada la primera función de Morgan, (a'+b')'=a·b, así (a·b)'=a'+b'
Estas
funciones pueden servir para demostrar nuevamente la negación
de la disyunción exclusiva:
- Sea a⨀b=(a⊕b)', dada la primera función de Morgan, a⨀b=(a·b'+a'·b)', a⨀b=(a·b')'·(a'·b)'.
- Con la segunda función de Morgan a⨀b=(a'+b)·(a+b'), a⨀b=(a'+b)·a+(a'+b)·b', a⨀b=a·a'+a·b+a'·b'+b·b'.
- Reduciendo las formas w·w' al elemento neutro de la disyunción, a⨀b=a·b+a'·b'. Como así se define la función a⨀b, la aseveración inicial es correcta.
Las
funciones de Morgan son universales, es decir, son definitorias de la
negación, la disyunción y la conjunción:
- Respecto a la primera función:
- Negación: ∀a | a ∈ {0,1}, a'=m₁(a,a)
- Conjunción: ∀a, b | a, b ∈ {0,1}, a·b=m₁(m₁(a,a),m₁(b,b))
- Disyunción: ∀a, b | a, b ∈ {0,1}, a+b=m₁(m₁(a,b),m₁(a,b))
- Respecto a la segunda función:
- Negación: ∀a | a ∈ {0,1}, a'=m₂(a,a)
- Conjunción: ∀a, b | a, b ∈ {0,1}, a·b=m₂(m₂(a,b),m₂(a,b))
- Disyunción: ∀a, b | a, b ∈ {0,1}, a+b=m₂(m₂(a,a),m₂(b,b))
Existe
para el semianillo abeliano definido una clase de equivalencia de las
funciones que comparten el mismo resultado con una función f
de n variables. Se les llama a los valores que toman dichas variables
códigos. Algunos ejemplos son:
- Código BCD: f(0,0,0,0)=b(0,0,0,0), f(0,0,0,1)=b(0,0,0,1), f(0,0,1,0)=b(0,0,1,0), f(0,0,1,1)=b(0,0,1,1), f(0,1,0,0)=b(0,1,0,0), f(0,1,0,1)=b(0,1,0,1), f(0,1,1,0)=b(0,1,1,0), f(0,1,1,1)=b(0,1,1,1), f(1,0,0,0)=b(1,0,0,0), f(1,0,0,1)=b(1,0,0,1), y de f(1,0,1,0) hasta f(1,0,1,1) la función b queda indefinida. Los valores que las variables de b pueden tomar son fundamentalmente el código.
- Código de exceso a 3 (XS-3): f(0,0,0,0)=x(0,0,1,1), f(0,0,0,1)=x(0,1,0,0), f(0,0,1,0)=x(0,1,0,1), f(0,0,1,1)=x(0,1,1,0), f(0,1,0,0)=x(0,1,1,1), f(0,1,0,1)=x(1,0,0,0), f(0,1,1,0)=x(1,0,0,1), f(0,1,1,0)=x(1,0,1,0), f(0,1,1,1)=x(1,0,1,1), y de f(1,0,0,0) hasta f(1,1,1,1) la función x está indefinida. Se caracteriza porque los valores que toman las variables en BCD tres combinaciones después en f son equivalentes en x, es decir, f(0,0,0,0)=x(0,0,1,1) pero tres combinaciones después de f se tiene f(0,0,1,1)=b(0,0,1,1) que es igual la combinación de BCD a la de XS-3.
- Código Gray: f(0,0,0,0)=g(0,0,0,0), f(0,0,0,1)=g(0,0,0,1), f(0,0,1,0)=g(0,0,1,1), f(0,0,1,1)=g(0,0,1,0), f(0,1,0,0)=g(0,1,1,0), f(0,1,0,1)=g(0,1,1,1), f(0,1,1,0)=g(0,1,0,1), f(0,1,1,1)=g(0,1,0,0), f(1,0,0,0)=g(1,1,0,0), f(1,0,0,1)=g(1,1,0,1), f(1,0,1,0)=g(1,1,1,1), f(1,0,1,1)=g(1,1,1,0), f(1,1,0,0)=g(1,0,1,0), f(1,1,0,1)=g(1,0,1,1), f(1,1,1,0)=g(1,0,0,1), f(1,1,1,1)=g(1,0,0,0). Se caracteriza porque de una combinación a otra de g sólo cambia de valor una variable, ejemplo: f(0,0,1,1)=g(0,0,1,0), f(0,1,0,0)=g(0,1,1,0).
26
de Diciembre de 2010
No hay comentarios:
Publicar un comentario