Cómo determinar efectivamente si la tabla de verdad dada es igual a otra (cuando tenemos en cuenta que pueden diferir en el orden de las entradas)

1

Estoy trabajando en un proyecto que no está realmente relacionado con los circuitos digitales sino más bien con el análisis de álgebra booleana.

En algún punto me atoré en el problema algorítmico o tal vez de la estructura de datos: Cómo determinar efectivamente si la tabla de verdad dada es igual a otra (cuando tenemos en cuenta que pueden diferir en el orden de las entradas).

Por ahora tengo tablas de verdad en vectores de bits por ejemplo, y la tabla de verdad se almacenará como: 1110 porque:

A | B | R
0 | 0 | *1*
0 | 1 | *1*
1 | 0 | *1*
1 | 1 | *0*

Sin embargo, para algunos circuitos, la tabla de resultados en mi representación puede verse muy diferente para el mismo circuito cuando se cambia el orden de las entradas. Por ejemplo:

simular este circuito : esquema creado usando CircuitLab

Tabla de la verdad:

A | B | C | R
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 0
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

pero cuando cambiamos A < - > Entradas C como:

simular este circuito

la tabla de verdad se convierte en:

A | B | C | R
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

Por lo tanto, es visible. No puedo comparar mi forma "sin procesar" de tablas de verdad para este caso porque 01010111! = 00011111, mientras que desde mi perspectiva estas tablas de verdad representan exactamente los mismos circuitos con solo entradas de diferencia de orden.

¿Hay alguna representación inteligente de tablas de verdad que me permita verificar este tipo de igualdad y decirme qué entradas de la primera tabla de verdad se asignan a qué entradas de la segunda?

Por ahora solo tengo la idea de generar todas las tablas de resultados "en bruto" basadas en las permutaciones del orden de las entradas para una tabla de verdad de "inicio" dada y durante la comprobación de comparación si alguna de estas permutaciones es igual, pero este método consume mucha memoria y es lento. .

¿Tienes alguna idea de cómo resolver este problema? Tal vez hay documentos científicos existentes sobre esto?

    
pregunta Tomasz Frydrych

2 respuestas

0

Ellos no representan el mismo circuito porque el intercambio de entradas puede no dar el mismo resultado. Las entradas no son iguales, de lo contrario, cambiarlas no tendría ningún significado.

Considere el caso donde ABC = 100 : en el primer circuito produce 0 , en el segundo produce 1 . Así que la lógica es diferente aunque las puertas sean iguales. Si el orden de las entradas no importara, ¿cómo diferenciaría entre ABC = 100 y ABC = 001 ya que producen una salida diferente en su caso?

    
respondido por el clabacchio
0

Después de algunas investigaciones, descubrí un algoritmo que de alguna manera resuelve mi problema (gracias por la sugerencia de @PlasmaHH), tal vez no lo más rápido posible, pero de todos modos, es bueno para mí. Lo implementé en C ++: enlace

Cambia la tabla de verdad (almacenada como bitvector) en algún tipo de forma normalizada. En la forma normalizada, intenta eliminar los alias contradictorios entre las variables para encontrar que las combinaciones de alias de variables en las que las condiciones dadas tablas de verdad son iguales.

    
respondido por el Tomasz Frydrych

Lea otras preguntas en las etiquetas