Conversione di dichiarazioni matematiche per Sat Formules

Question

È possibile scrivere una dichiarazione matematica (come il congettura di Goldbach, per esempio) come una formula 3-sat non circiale che è soddisfatta che l'affermazione sia vera?IFF è falso?IFF è indipendente dagli assiomi di ZFC?Quindi, per qualsiasi affermazione, avresti (al massimo) 3 formule, per il quale solo uno può essere soddisfacente.C'è qualche lavoro in questo campo (puoi usare il teorema pitagorico come esempio più semplice)?

Answer 1

Se si desidera sapere se esiste un metodo / algoritmo generale che può convertire una determinata dichiarazione matematica (con cui intendi dichiarazioni scritte in logica (dire logica del primo ordine, logica del secondo ordine ... ecc.)) AUna formula sat che è vera iff Questa affermazione è vera, allora la risposta è no.

Il motivo è quello che valuta se una formula sat è vera o falsa è decidabile (in tempo esponenziale se non più veloce), mentre queste logiche sono solitamente indecidibili .Quindi, nessun algoritmo tali può esistere.

Naturalmente, ci sono logiche che sono decidabili e la dichiarazione di quelle logiche può essere convertita in formula SAT (forse banale come true o false come menzionato da @ d.w) da un algoritmo specifico.Vedi: http://www.lsv.fr/~ haase/documents/h18.PDF

Answer 2

dipende dalla dichiarazione matematica. Se ha il modulo

$$ \ esiste x_1 \ in s_1 \ cdots \ esiste x_n \ in s_n. \ VARPHI (X_1, \ DOTS, X_N) $$

dove $ \ varphi (x_1, \ dots, x_n) $ è qualche condizione su $ x_1, \ punti, x_n $ e $ s_1, \ dots, s_n $ sono set finiti, quindi sì, può essere espresso come formula 3CNF in modo diretto. < / P >.

Tuttavia, le dichiarazioni come $ \ esiste x \ in s_1 \ forlt y \ in s_2. \ VARPHI (x, y) $ o $ \ esiste x_1 \ in \ mathbb {r} \ cdots \ esiste x_n \ in \ mathbb {r}. \ Varphi (x_1, \ dots, x_n) $ sono più difficili.

C'è un senso banale in cui la risposta è sì: ogni dichiarazione matematica è vera o falsa, quindi corrisponde alla formula 3CNF $ \ testo {true} $ < / span> (cioè, $ (x_1 \ lor \ neg x_1) $ ) o la formula 3CNF $ \ text {false } $ (cioè, $ (x_1) \ Land (\ neg x_1) $ ). Questa riduzione non è non ombreggiabile e potrebbe non essere calcolabile, però.

Potresti essere interessato a https://en.wikipedia.org/wiki/existential_theory_of_the_reals.

Undecidable è una proprietà di lingue, non delle dichiarazioni matematiche. Forse intendi "indipendente dagli assiomi di ZFC".