Ich versuche, ein Tic-Tac-Toe-Programm als eine mentale Übung zu erstellen, und ich habe die Board-Zustände als booleans wie folgt gespeichert:
Ich möchte diesen booleschen Ausdruck vereinfachen ...
%Vor%Meine ersten Gedanken waren, eine Karnaugh Map zu verwenden, aber es gab keine Online-Solver, die 9 Variablen unterstützten.
>und heres die Frage:
Zuallererst, wie würde ich wissen, ob eine boolesche Bedingung schon so einfach wie möglich ist?
und zweitens: Was vereinfacht die obige boolesche Bedingung?
Der ursprüngliche Ausdruck
%Vor%kann zu dem folgenden vereinfacht werden, wissend, dass & amp; ist prioritärer als |
%Vor% was 4 Zeichen kürzer ist, führt im schlechtesten Fall 18 & und | aus (das Original hat 23 gezählt)
Es gibt keine kürzere boolesche Formel (siehe unten). Wenn Sie zu Matrizen wechseln , können Sie möglicherweise eine andere Lösung finden.
Normalerweise ist es sehr schwierig, die kleinste Formel zu finden. Siehe dieses aktuelle Papier , wenn Sie mehr Interesse haben. Aber in unserem Fall gibt es einen einfachen Beweis.
Wir gehen davon aus, dass eine Formel das kleinste bezüglich der Formelgröße ist, wobei für eine Variable a , size(a)=1 , für eine boolesche Operation size(A&B) = size(A|B) = size(A) + 1 + size(B) und für die Negation% gilt. co_de% (also können wir annehmen, dass wir Negation Normalform kostenlos haben).
In Bezug auf diese Größe hat unsere Formel Größe 37.
Der Beweis, dass Sie nichts Besseres tun können, besteht darin, zuerst zu bemerken, dass es acht Zeilen zu prüfen gibt und dass es immer ein Paar Buchstaben gibt, die zwei verschiedene Zeilen unterscheiden. Da wir diese 8 Überprüfungen in nicht weniger als 3 Konjunktionen mit der verbleibenden Variablen zusammenfassen können, sollte die Anzahl der Variablen in der endgültigen Formel mindestens size(!A) = size(A) betragen, woraus wir die minimale Baumgröße ableiten können.
Detaillierter Nachweis
Nehmen wir an, dass eine gegebene Formel 8*2+3 = 19 die kleinste und NNF ist Format.
F darf keine negierten Variablen wie F enthalten. Beachten Sie, dass !a monoton sein sollte, dh wenn es "true" zurückgibt (es gibt eine gewinnende Zeile), dann ändern Sie eine der Variablen von F in false sollte dieses Ergebnis nicht ändern. Laut Wikipedia kann true ohne Negation geschrieben werden. Noch besser, wir können beweisen, dass wir die Negation entfernen können. Nach dieser Antwort könnten wir das DNF-Format zurück konvertieren und die negierten Variablen in der Mitte entfernen oder sie durch% ersetzen. co_de%.
F kann keine Unterstruktur wie eine Disjunktion zweier Variablen true enthalten.
Damit diese Formel nützlich und nicht austauschbar mit F oder a|b ist, würde es bedeuten, dass es widersprüchliche Zuordnungen gibt, wie zum Beispiel
a und b , deshalb wegen der Monotonie F[a|b] = true und F[a] = false . Wenn Sie in diesem Fall a = false in b = true umwandeln, wird die gesamte Formel b , weil false .
Daher gibt es eine Zeile, die an false vorbeikommt, was die Ursache der Wahrheit ist, und sie kann nicht durch false = F[a] = F[a|false] >= F[a|b](b = false) gehen, also zum Beispiel b und a .
Und die Prüfung dieser Reihe geht durch den Ausdruck e = true zum Testen von h = true . Es bedeutet jedoch, dass a|b wahr ist und alle anderen auf false gesetzt sind, b ist immer noch wahr, was dem Zweck der Formel widerspricht.
Jeder Unterbaum, der wie a,e,h aussieht, prüft eine eindeutige Zeile. Der letzte Buchstabe sollte also genau über der entsprechenden Disjunktion F erscheinen, oder dieses Blatt ist nutzlos und entweder a oder b können sicher entfernt werden. Nehmen wir an, dass a&b nicht oben erscheint, und das Spiel ist wo (a&b|...)&{c somewhere for sure here} ist c und alle anderen Variablen sind a&b&c . Dann gibt der Ausdruck, bei dem c oberhalb sein soll, true zurück, so dass false immer nutzlos ist. Es gibt also einen kürzeren Ausdruck, indem Sie false entfernen.
Es gibt 8 unabhängige Zweige, es gibt also mindestens 8 Teilbäume vom Typ a&b . Wir können sie nicht mit einer Disjunktion von 2 Konjunktionen neu gruppieren, da a&b , a&b und a niemals dieselben Zeilen teilen, also müssen 3 äußere Variablen vorhanden sein. f lässt 19 Variablen in der endgültigen Formel erscheinen.
Ein Baum mit 19 Variablen kann nicht weniger als 18 Operatoren haben, also muss die Größe mindestens 19 + 18 = 37 sein.
Sie können Varianten der obigen Formel haben.
QED.
Eine Möglichkeit ist, die Karnaugh Karte manuell zu machen. Da Sie 9 Variablen haben, ergibt das ein 2 ^ 4 mal 2 ^ 5 Gitter, das ziemlich groß ist und nach dem Aussehen der Gleichung wahrscheinlich auch nicht sehr interessant ist.
Bei einer Inspektion sieht es nicht so aus, als würde eine Karnaugh-Karte Ihnen nützliche Informationen liefern (Karnaugh-Karten reduzieren Ausdrücke wie ((!a)&b) | (a&b) in b ). In diesem Sinne der Vereinfachung ist Ihr Ausdruck bereits so so einfach wie es nur geht. Wenn Sie jedoch die Anzahl der Berechnungen reduzieren möchten, können Sie einige Variablen aus der Verteilungsfähigkeit der AND-Operatoren über ORs herausrechnen.
Der beste Weg, darüber nachzudenken, ist, wie eine Person darüber denken würde. Keine Person würde sich selbst sagen, "a und b und c, oder wenn d und e und f," usw. Sie würden sagen "Alle drei in einer Reihe, horizontal, vertikal oder diagonal."
Anstatt acht Überprüfungen (drei Zeilen, drei Spalten und zwei Diagonalen) durchzuführen, können Sie auch nur vier Überprüfungen (drei Zeilen und eine Diagonale) durchführen, dann die Karte um 90 Grad drehen und dann die gleichen Überprüfungen erneut durchführen.
Hier hast du am Ende. Diese Funktionen nehmen alle an, dass die Tafel eine drei-mal-drei-Matrix von booleschen Werten ist, wobei wahr ein gewinnendes Symbol und falsch ein nicht gewinnendes Symbol darstellt.
%Vor%Die Matrix rotieren ist von hier: Ссылка
Obwohl dieser Code etwas ausführlicher ist, ist jede Funktion in ihrer Absicht klar. Anstelle eines langen Booleschen Ausdrucks drückt der Code nun die Regeln von Tic-Tac-Toe aus.
Sie wissen, dass es so einfach wie möglich ist, wenn es keine gemeinsamen Unterbegriffe zu extrahieren gibt (z. B. wenn Sie "a & amp; b" in zwei verschiedenen Trios hatten).
Sie wissen, dass Ihre Tic-Tac-Toe-Lösung schon so einfach wie möglich sein muss, weil jedes Boxenpaar höchstens zu einer Gewinnlinie gehören kann (nur eine gerade Linie kann zwei gegebene Punkte passieren), also (a & amp; b ) kann in keinem anderen Gewinn, den du suchst, wiederverwendet werden.
(Auch "einfach" kann eine Menge Dinge bedeuten; zu spezifizieren, was Sie meinen, kann Ihnen helfen, Ihre eigene Frage zu beantworten.)
