Логический артистика первого порядка определяет решаемость?

Question

Я прочитал логику первого порядка, в целом нерешимой, и это может быть определенным только при работе с неаричарными операторами. (Я думаю, что это пропозициональная логика, поправьте меня, если я ошибаюсь)

Вопрос в том Почему Arity приводит к неразрешимым проблемам?

Я хотел бы увидеть какой -то справочный материал или, по крайней мере, простые пример из этого, как способ думать в этом отрывке от unary до n-ary и почему это приводит к неразрешимым проблемам.

Answer 1

Логика с unary предикаты (не операторы), называется монадиский. Анкет То, что называется пропозициональный Логика имеет только нультарный предикаты, то есть константы true а также false, и никаких квантификаторов.

А неразрешимость предиката логики следует, потому что предикатная логика (по крайней мере, с одним бинарным предикатом) достаточно мощная, чтобы Опишите, как работает машина Тьюринга, и поэтому мы можем выразить в логике, достаточно сложных утверждениях о машинах Тьюринга, чтобы получить нерешительность. Напротив, в монадической логике, где у нас есть только уникальные предикаты, мы не можем описать работу машины Тьюринга. Я здесь намеренно расплывчаюсь, чтобы дать идею, не увязая в технических деталях.

Answer 2

Как указал Рафаэль в комментарии, вы, вероятно, спрашиваете о решаемости классической проблемы принятия решения для фрагментов логики первого порядка с уникальными предикатами.

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

Это был Лёвенгейм, который в 1915 году дал процедуру принятия решения о логике первого порядка с уникальными предикатами. Если вам интересно, вы можете найти интригующую экспозиционную бумагу под названием "По классической проблеме решения«Написано Юрием Гуревичем в форме диалога двух вымышленных символов. Документ был впервые опубликован в Бюллетене Eatcs.

В документе не только вводит проблему, но и объясняет, как поиск превратился в поиск полной классификации решаемых и неразрешимых фрагментов с точки зрения префиксов квантова.