Алгоритмическая разрешимость: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
VAP+VYK (обсуждение | вклад) →Связь разрешимости и полноты: пунктуация |
|||
Строка 30:
== Связь разрешимости и полноты ==
В [[Математическая логика|математической логике]], традиционно используется два понятия полноты: собственно полнота и полнота, относительно некоторого класса интерпретаций (или структур). В первом случае, теория полна, если любое предложение в ней является либо истинным, либо ложным. Во втором
Оба понятия тесно связанны с разрешимостью. Например, если множество аксиом полной теории первого порядка рекурсивно перечислимо, то она разрешима. Это следует из известной [[Теорема Поста|теоремы Поста]], утверждающей, что если множество и его дополнение оба рекурсивно перечислимы, то они также [[Рекурсивное множество|рекурсивны]]. Интуитивно, аргумент, показывающий истинность приведённого утверждения следующий: если теория полна, и множество её аксиом рекурсивно перечислимо, то существуют полуразрешающие процедуры, для проверки истинности любого утверждения, равно как и его отрицания. Если запустить обе эти процедуры [[Параллельные вычисления|параллельно]], то учитывая полноту теории, одна из них должна когда-нибудь остановиться и выдать позитивный ответ.
Если теория полна, относительно некоторого класса интерпретаций, это можно использовать для построения разрешающей процедуры. Например [[пропозициональная логика]] полна относительно интерпретации на [[Таблица истинности|таблицах истинности]]. Поэтому построение таблицы истинности по данной формуле будет примером разрешающего алгоритма для пропозициональной логики.
|