Álgebra de Boole
Hola Eudemo, no sé si este álgebra tan rara es tu especialidad, pero a ver si me puedes ayudar con un problemilla que me viene comiendo la cabeza hace un buen rato.
El ejercicio dice: demostrar que el conector binario NOR es por sí mismo un conjunto suficiente de conectores.
Se entiende que hablamos de funciones de conmutación de 2 variables.
Por ahora lo que sé es que como hay 16 funciones de conmutación de 2 variables, hay que demostrarlo para 15 (pues la otra es la propia NOR).
He sido capaz de hacerlo para algunas, como para f(x, y)=x*y' (siendo y' el complemento de y), que podemos escribirla como f(x, y)=g(g(x, y), y), siendo g la función NOR. He sido capaz de demostrar esto partiendo de la expresión g(g(x, y), y), y no desde la función f(x, y). Por eso no me sale la mayoría: no se hacerlo a la inversa (el anterior me salió de potra).
¿Sabes si hay algún método sistemático que me permita demostrar la dependencia de cada f con respecto a g a partir de la propia f?
Gracias de antemano.
El ejercicio dice: demostrar que el conector binario NOR es por sí mismo un conjunto suficiente de conectores.
Se entiende que hablamos de funciones de conmutación de 2 variables.
Por ahora lo que sé es que como hay 16 funciones de conmutación de 2 variables, hay que demostrarlo para 15 (pues la otra es la propia NOR).
He sido capaz de hacerlo para algunas, como para f(x, y)=x*y' (siendo y' el complemento de y), que podemos escribirla como f(x, y)=g(g(x, y), y), siendo g la función NOR. He sido capaz de demostrar esto partiendo de la expresión g(g(x, y), y), y no desde la función f(x, y). Por eso no me sale la mayoría: no se hacerlo a la inversa (el anterior me salió de potra).
¿Sabes si hay algún método sistemático que me permita demostrar la dependencia de cada f con respecto a g a partir de la propia f?
Gracias de antemano.
1 Respuesta
Respuesta de eudemo
1
Ordenando las posibles entradas y cada posible salida tenemos una función distinta para cada una de las 16 posibles salidas. Veamos la tabla:
Ent salidas
yx 0 1 2 3 4 5 6 7 8 9 A B C D E F
00 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
01 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
10 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
11 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
A las 16 posibles funciones las llamaremos así:
F0 con salida0, f1 con salida1, f2 con salida2, f3 con salida3,..., fA con salidaA, fB con salidaB,..., fF con salidaF.
Primero vamos ha expresarlas en función de operaciones or , and y negaciones.
El or es un + y el and es un * y la negación un '
f0(x,y)=0
f1(x,y)=x'*y'=(x+y)'
f2(x,y)=x*y'=(x'+y)'
f3(x,y)=y'
f4(x,y)=x'*y=(x+y')'
f5(x,y)=x'
f6(x,y)=(x xor y)= x*y'+x'*y=(x'+y)'+(x+y')'
f7(x,y)=(x*y)'=x'+y'
f8(x,y)=x*y=(x'+y')'
f9(x,y)=(x xor y)'=(x*y'+x'*y)'=[(x'+y)'+(x+y')']'
fA(x,y)=x
fB(x,y)=(x'*y)'=x+y'
fC(x,y)=y
fD(x,y)=x'+y
fE(x,y)=x+y
fF(x,y)=1
La número 6 es un or exclusivo o xor.
A las and se las pueden trasformar en or aplicando la fórmula de De Morgan
x*y=(x'+y')
y por supuesto que una doble negación se anula
(x')'=x
Te dejo la tarea de expresarlo con g .El problema es que para indicar una simple negación debes usas x'=g(x, 0) o x'=g(x, x). Es mucho más simple usar, como en electrónica, el símbolo de compuerta nor y hacer el dibujo. Así se hacen en los circuitos reales. La idea es que con compuertas nor se puede implementar cualquier función lógica. Lo mismo usando compuertas nor. Te hago un par de ejemplos con g:
f4=(x+y')'=g(x,g(y,0))
f9=[(x'+y)'+(x+y')']'= g( g(g(g(x,0),y), g(x,g(y,0))),0)
Ent salidas
yx 0 1 2 3 4 5 6 7 8 9 A B C D E F
00 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
01 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
10 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
11 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
A las 16 posibles funciones las llamaremos así:
F0 con salida0, f1 con salida1, f2 con salida2, f3 con salida3,..., fA con salidaA, fB con salidaB,..., fF con salidaF.
Primero vamos ha expresarlas en función de operaciones or , and y negaciones.
El or es un + y el and es un * y la negación un '
f0(x,y)=0
f1(x,y)=x'*y'=(x+y)'
f2(x,y)=x*y'=(x'+y)'
f3(x,y)=y'
f4(x,y)=x'*y=(x+y')'
f5(x,y)=x'
f6(x,y)=(x xor y)= x*y'+x'*y=(x'+y)'+(x+y')'
f7(x,y)=(x*y)'=x'+y'
f8(x,y)=x*y=(x'+y')'
f9(x,y)=(x xor y)'=(x*y'+x'*y)'=[(x'+y)'+(x+y')']'
fA(x,y)=x
fB(x,y)=(x'*y)'=x+y'
fC(x,y)=y
fD(x,y)=x'+y
fE(x,y)=x+y
fF(x,y)=1
La número 6 es un or exclusivo o xor.
A las and se las pueden trasformar en or aplicando la fórmula de De Morgan
x*y=(x'+y')
y por supuesto que una doble negación se anula
(x')'=x
Te dejo la tarea de expresarlo con g .El problema es que para indicar una simple negación debes usas x'=g(x, 0) o x'=g(x, x). Es mucho más simple usar, como en electrónica, el símbolo de compuerta nor y hacer el dibujo. Así se hacen en los circuitos reales. La idea es que con compuertas nor se puede implementar cualquier función lógica. Lo mismo usando compuertas nor. Te hago un par de ejemplos con g:
f4=(x+y')'=g(x,g(y,0))
f9=[(x'+y)'+(x+y')']'= g( g(g(g(x,0),y), g(x,g(y,0))),0)
Hola Eudemo:
A lo largo del día de hoy me han estado saliendo casi todas; sólo me fallaron la EXOR y la EXNOR. Pero el problema seguía siendo que me salían un poco de potra. No me había dado cuenta del detalle simple de que x'=g(x,0)=g(x,x). A veces me despisto en tonterías.
Tu consejo me ha sido de mucha utilidad. Te agradezco tu tiempo y tus ganas gratuitas de ayudar.
Edúvatar.
A lo largo del día de hoy me han estado saliendo casi todas; sólo me fallaron la EXOR y la EXNOR. Pero el problema seguía siendo que me salían un poco de potra. No me había dado cuenta del detalle simple de que x'=g(x,0)=g(x,x). A veces me despisto en tonterías.
Tu consejo me ha sido de mucha utilidad. Te agradezco tu tiempo y tus ganas gratuitas de ayudar.
Edúvatar.
