Umwandlung mathematischer Aussagen in SAT-Formeln

Question

ist es möglich, eine mathematische Erklärung (wie beispielsweise Goldbachs Vermutung) als nichttriviale 3-Sat-Formel zu schreiben, die erfüllt ist, wenn diese Anweisung wahr ist?IFF ist es falsch?IFF ist unabhängig von den Axioms von ZFC?Für jede Anweisung hätten Sie also (höchstens) 3 Formeln, für die nur einer erfüllt sein kann.Gibt es in diesem Feld Arbeiten (Sie können den Pythagor-Theorem als einfacheres Beispiel verwenden)?

Answer 1

Wenn Sie wissen möchten, ob es einen allgemeinen Methoden / Algorithmus gibt, der eine bestimmte mathematische Erklärung konvertieren kann (mit der Sie in der Logik geschriebenen Anweisungen (Logik der Erste der ersten Ordnung, der Logik der ersten Ordnung))Eine Sat-Formel, die true iff ist, trifft zu, dann ist die Antwort nein.

Der Grund, dass die Bewertung, ob eine SAT-Formel true ist oder falsch ist, ist degable (in exponentiellen Zeit, wenn nicht schneller), während diese Logiken normalerweise unentgitterbar sind .Also kann kein solcher Algorithmus existieren.

Natürlich gibt es Logiken, die entschieden sind, und die Anweisung dieser Logik kann in SAT-Formel umgewandelt werden (vielleicht triviale, wie in @ d.w) von @ d.w) von einem bestimmten Algorithmus.Siehe: http://www.lsv.fr/~haase/documents/h18.pdf

Answer 2

Es hängt von der mathematischen Erklärung ab. Wenn es das Formular hat

$$ \ existiert X_1 \ in S_1 \ CDS \ existiert X_N \ in S_N. \ varphi (x_1, \ dots, x_n) $$ $$

wobei $ \ varphi (x__, \ dots, x_n) $ ein gewisser Zustand auf $ X_1, \ Punkte, X_N $ und $ s_1, \ dots, s_n $ sind endliche Sätze, dann kann es als 3cnf-Formel auf einfache Weise ausgedrückt werden. < / p>

Allerdings sind Anweisungen wie $ \ existiert X \ in S_1 \ nachall \ in S_2. \ varphi (x, y) $ oder $ \ existiert X_1 \ in \ mathbb {r} \ CDs \ existiert x_n \ in \ mathbb {r}. \ varphi (x_1, \ dots, x_n) $ sind härter.

Es gibt ein triviales Gefühl, in dem die Antwort yes ist: Jede mathematische Anweisung ist entweder true oder falsch, so dass entweder der 3CNF-Formel $ \ text {true} $ (dh $ (x__1 \ lor \ neg x_1) $ ) oder die 3cnf-Formel $ \ Text {FALSE } $ (dh $ (x_1) \ land (\ neg x_1) $ ). Diese Reduktion ist nicht berrukturig und ist jedoch möglicherweise nicht berechenbar.

Sie könnten interessiert sein an https://en.wikipedia.org/wiki/existential_theory_of_the_reals.

Unentschlossen ist eine Eigenschaft von Sprachen, nicht von mathematischen Anweisungen. Vielleicht meinst du "unabhängig von den Axiomen von ZFC".