Преобразование математических утверждений для SAT формул

Question

Можно ли написать математическое утверждение (например, гипотеза Goldbach, например) в качестве нетривиальной формулы 3-SAT, которая является удовлетворенной IFF, что утверждение верно?IFF Это ложно?IFF Не зависит от аксиом ZFC?Итак, для любого утверждения вы бы (не более) 3 формула, для которых только один может быть удовлетворен.Есть ли работа в этой области (вы можете использовать теорему Пифагорена как более простой пример)?

Answer 1

Если вы хотите знать, существует ли общий метод / алгоритм, который может преобразовать любое данное математическое утверждение (с помощью которого вы имеете в виду заявления, написанные в логике (скажем, логика первого порядка, логика второго порядка ... и т. Д.))Формула SAT, которая верна IFF Это утверждение верно, то ответ нет.

Причина, которая оценивает, является ли формула SAT TRUE или FALSE, является RECIDABLE (в экспоненциальном времени, если не быстрее), тогда как эти логики обычно являются неразрешительными .Итак, такой алгоритм не может существовать.

Конечно, есть логики, которые являются разрешенными, и утверждение этой логики можно преобразовать в формулу SAT (возможно, тривиальные, такие как True или False, как упомянуто @ D.W) по определенному алгоритму.См.: http://www.lsv.fr/~thhaase/documents/h18.PDF

Answer 2

Это зависит от математического утверждения. Если он имеет форму

$$ \ \ Exists x_1 \ in s_1 \ cdots \ существует x_n \ in s_n. \ varphi (x_1, \ dots, x_n) $$

Где $ \ varphi (x_1, \ dots, x_n) $ - это некоторое условие на $ x_1, \ dots, x_n $ и $ s_1, \ dots, s_n $ - это конечные наборы, то да, его можно выразить в виде формулы 3CNF прямо. / P >.

Однако, как утверждения, такие как $ \ Exists x \ in s_1 \ forall y \ in s_2. \ varphi (x, y) $ или $ \ существует x_1 \ in \ mathbb {r} \ cdots \ существует x_n \ in \ mathbb {r}. \ varphi (x_1, \ dots, x_n) $ сложнее.

Существует тривиальный смысл, в котором ответа - это да: каждое математическое утверждение является либо верным, либо ложно, поэтому он соответствует ни одной формуле 3CNF $ \ Text {true} $ / span> (т.е. $ (x_1 \ lor \ neg x_1) $ ) или формула 3cnf $ \ text {false } $ (т.е. $ (x_1) \ land (\ neg x_1) $ ). Это уменьшение несогранично и может быть не вычисляемо, хотя.

Вам может быть заинтересован в https://en.wikipedia.org/wiki/existental_theory_of_the_reals.

Неразрешимый - это свойство языков, а не математических утверждений. Возможно, вы имеете в виду «независимые от аксиом ZFC».