Reduzieren komplexer Filterregeln auf eine vergleichbare Form

Question

Ich möchte feststellen, ob ein Eingabearray von ganzen Zahlen einem Satz von Regeln "entspricht" oder nicht.

Der Matcher

Die Matcher aus einer Reihe von Hilfsmethoden gebaut Regeln für die Eingangsdaten zu beschreiben. Diese Regeln sind im Wesentlichen Logikgatter auf Arrays von ganzen Zahlen:

AND(1, 2) // Requires both 1 AND 2 be present in the input array. 
OR(3, 4, 5) // Requires that 3 OR 4 OR 5 be present in the input array. 
NOR(6, 7) // Requires that neither 6 NOR 7 be present in the input array. 
XOR(8, 9) // Requires that either 8 (X)OR 9 be present in the input array, but not both. 

So ich könnte sagen, dass angesichts der Eingangsanordnung:

[0, 1, 2, 3] 

ich bauen konnte ein Matcher wie:

AND(OR(0, 1), AND(1, 2) NOR(4)) 

Die Eingabe entspricht der Eingabe, da die Eingabe erfüllt:

OR(0, 1) // 0 or 1 is present 
AND(1, 2) // Both 1 and 2 are present 
NOR(4) // 4 is not present 

Und jeder von diesen erfüllt kumulativ die übergeordnete AND Regel.

Das Problem

muss ich Matcher auf die einfachste und grundlegende Form zu reduzieren, die nach wie vor die Regeln beschreibt. Zum Beispiel kann die oben Matcher gegeben, könnte eine Probe Reduktion sein:

rules = { 
    or: [1, 2], 
    xor: [], // No XORs 
    nor: [4] 
} 

Jeder rule hat drei Anordnungen von Unterregeln, die sich aus ganzen Zahlen oder rule s.

Beachten Sie, dass die ORs leer sind, da 1 sowieso erforderlich ist, was bedeutet, OR(0, 1) => [0, 1] ist redundant, weil es erfüllt sein muss.

Da Matcher s müssen vergleichbar sein (Ich muss in der Lage, eine Äquivalenz zwischen den zugrunde liegenden Regeln zu bestimmen), ist es etwas komplizierter wird, wenn ich zu bekommen: Jetzt

input = [1, 2, 5, 9, 11, 12, 13, 14, 17] 

XOR(OR(AND(1, 2), NOR(3, 4), XOR(3 11), AND(11, 14)), AND(1, 5, 17)) 

, eine große Menge Das ist überflüssig und/oder widersprüchlich. Was ich also denken konnte, war, dass ich es zuerst in eine baumartige Struktur bringen und es dann rekursiv darstellen und unnötige Einträge reduzieren konnte. Irgendwelche Ideen für einen besseren Weg, dies zu tun?

Ich bin speziell auf der Suche nach etwas Deterministisch (jede Menge von Regeln, die das gleiche bedeuten, die gleiche endgültige reduzierte Form). Wenn es eine bessere Möglichkeit gibt, dieses Problem auszudrücken, bin ich interessiert, und wenn Regeln widersprüchlich sind, ist es in Ordnung, wenn der Reduzierer bricht und eine Ausnahme auslöst. Dies ist für den gelegentlichen Gebrauch im Programm gedacht, so dass die Leistung kein großes Problem darstellt.

Answer 1

Was Sie hier eigentlich zu tun haben, ist propositional logic. Betrachten Sie die Ganzzahl, in der Ihre Aussagen entweder falsch oder wahr sind, je nachdem, ob sie im Eingabearray vorhanden sind.

Ihre Nebenbedingungen (XOR, AND usw.) bilden dann eine logische Formel, die entweder erfüllbar ist oder nicht. Es ist in der Tat schwierig, für irgendeine gegebene Formel herauszufinden, ob sie erfüllbar ist. Dies sollte Sie jedoch auf den ersten Blick nicht interessieren, denn Sie müssen nur prüfen, ob eine Eingabe die Formel erfüllt.

Leider, was Sie tatsächlich fragen, ist, wie Sie feststellen können, ob zwei Aussagen Formeln gleichwertig sind. Es stellt sich heraus, dass dies gleichermaßen schwierig ist: https://math.stackexchange.com/questions/1050127/how-to-efficiently-determine-if-any-two-propositional-formulas-are-equivalent