Conversion de déclarations mathématiques aux formules SAT

Question

est-il possible d'écrire une déclaration mathématique (comme la conjecture de Goldbach, par exemple) en tant que formule 3-SAT non traitée qui est satisfiable IFF de cette déclaration est vraie?iff c'est faux?iff il est indépendant des axiomes de ZFC?Ainsi, pour toute déclaration, vous auriez (au plus) 3 formules, pour lesquelles un seul peut être satisfait.Y a-t-il des travaux dans ce domaine (vous pouvez utiliser le théorème Pythagoreen comme exemple plus simple)?

Answer 1

Si vous voulez savoir s'il existe une méthode / algorithme générale qui peut convertir une déclaration mathématique donnée (par laquelle vous entendez des déclarations écrites dans la logique (par exemple la logique de premier ordre, la logique de second ordre ... etc.)) àUne formule SAT qui est true iff cette affirmation est vraie, la réponse est alors non.

La raison étant d'évaluer si une formule SAT est vraie ou false est décidable (en temps exponentiel si pas plus rapide), tandis que ces logiques sont généralement indéformables .Donc, aucun algorithme de ce type ne peut exister.

Bien sûr, il existe des logiques qui sont décidables et que l'énoncé de cette logique peut être converti en formule SAT (peut-être trivial comme vrai ou faux comme mentionné par @ D.W) par un algorithme spécifique.Voir: http://www.lsv.fr/~hase/documents/h18.PDF

Answer 2

Cela dépend de la déclaration mathématique. S'il a la forme

$$ \ existe x_1 \ dans s_1 \ CDOT \ Existe x_n \ in s_n. \ varphi (x_1, \ dots, x_n) $$

où $ \ varphi (x_1, \ dots, x_n) $ est une condition sur $ x_1, \ points, x_n $ et $ s_1, \ dots, s_n $ sont des ensembles finis, puis oui, il peut être exprimé en formule 3CNF de manière simple. < / p>

Cependant, des déclarations telles que $ \ existent x \ in s_1 \ Forall y \ in S_2. \ Varphi (x, y) $ ou $ \ existe x_1 \ in \ mathbb {r} \ cdots \ existez x_n \ in \ mathbb {r}. \ varphi (x_1, \ dots, x_n) $ sont plus difficiles.

Il y a un sens trivial dans lequel la réponse est oui: chaque instruction mathématique est vraie ou false, elle correspond à la formule 3cnf $ \ text {vrai} $ < / span> (c.-à-d. $ (x_1 \ lor \ neg x_1) $ ) ou la formule 3cnf $ \ text {faux } $ (c.-à-d., $ (x_1) \ terres (\ nge x_1) $ ). Cette réduction est non constructive et pourrait ne pas être calculable, cependant.

Vous pourriez être intéressé par https://fr.wikipedia.org/wiki/existiential_theory_of_the_reals.

Undecidable est une propriété de langues et non de déclarations mathématiques. Peut-être que vous voulez dire "indépendant des axiomes de zfc".