Крейг интерполяция - Craig interpolation

В математическая логика, Интерполяционная теорема Крейга результат взаимосвязи между различными логическими теории. Грубо говоря, теорема утверждает, что если формула φ подразумевает формулу ψ, и оба имеют по крайней мере один общий символ атомарной переменной, тогда существует формула ρ, называемая интерполянтом, такая, что каждый нелогический символ в ρ встречается как в φ, так и в ψ, φ подразумевает ρ, а ρ следует ψ. Теорема была впервые доказана для логика первого порядка к Уильям Крейг в 1957 г. Варианты теоремы верны для других логик, таких как логика высказываний. Более сильная форма интерполяционной теоремы Крейга для логики первого порядка была доказана Роджер Линдон в 1959 г .;^[1]^[2] общий результат иногда называют Теорема Крейга – Линдона.

пример

В логика высказываний, позволять

{ Displaystyle varphi = lnot (P land Q) to ( lnot R land Q)}

{ Displaystyle psi = (S к P) лор (S к lnot R)}

.

потом ${ displaystyle varphi}$ тавтологически подразумевает ${ displaystyle psi}$ . В этом можно убедиться, написав ${ displaystyle varphi}$ в конъюнктивная нормальная форма:

{ Displaystyle varphi эквив (п лор lnot R) земля Q}

.

Таким образом, если ${ displaystyle varphi}$ держит, то ${ Displaystyle P lor lnot R}$ держит. В очереди, ${ Displaystyle P lor lnot R}$ тавтологически подразумевает ${ displaystyle psi}$ . Поскольку две пропозициональные переменные, встречающиеся в ${ Displaystyle P lor lnot R}$ встречаются в обоих ${ displaystyle varphi}$ и ${ displaystyle psi}$ , это означает, что ${ Displaystyle P lor lnot R}$ является интерполянтом для импликации ${ displaystyle varphi to psi}$ .

Интерполяционная теорема Линдона

Предположим, что S и Т две теории первого порядка. В качестве обозначений пусть S ∪ Т обозначают наименьшую теорию, включая обе S и Т; то подпись из S ∪ Т наименьший, содержащий подписи S и Т. Также позвольте S ∩ Т быть пересечением языков двух теорий; подпись S ∩ Т является пересечением подписей двух языков.

Теорема Линдона гласит, что если S ∪ Т невыполнимо, то существует интерполирующее предложение ρ на языке S ∩ Т это верно для всех моделей S и ложь во всех моделях Т. Более того, ρ обладает тем более сильным свойством, что каждый символ отношения, имеющий положительное происшествие в ρ имеет положительное вхождение в некоторую формулу S и отрицательное вхождение в некоторую формулу Т, и каждый символ отношения с отрицательным вхождением в ρ имеет отрицательное вхождение в некоторую формулу S и положительное вхождение в некоторую формулу Т.

Доказательство интерполяционной теоремы Крейга

Мы представляем здесь конструктивное доказательство интерполяционной теоремы Крейга для логика высказываний.^[3] Формально теорема гласит:

Если ⊨φ → ψ, то существует ρ ( интерполянт) такие, что ⊨φ → ρ и ⊨ρ → ψ, где атомы (ρ) ⊆ атомы (φ) ∩ атомы (ψ). Здесь атомы (φ) - множество пропозициональные переменные входящие в φ, а ⊨ - семантическое отношение следования для логики высказываний.

Доказательство.Предположим, что ⊨φ → ψ. Доказательство проводится индукцией по количеству пропозициональных переменных, входящих в φ, но не входящих в ψ, обозначенных |атомы(φ) - атомы(ψ) |.

Базовый случай |атомы(φ) - атомы(ψ) | = 0: Поскольку |атомы(φ) - атомы(ψ) | = 0, имеем атомы(φ) ⊆ атомы(φ) ∩ атомы(ψ). Более того, имеем ⊨φ → φ и ⊨φ → ψ. Этого достаточно, чтобы показать, что φ - подходящий интерполянт в этом случае.

Предположим, что для индуктивного шага результат был показан для всех х, где |атомы(χ) - атомы(ψ) | = п. Теперь предположим, что |атомы(φ) - атомы(ψ) | = п + 1. Выберите q ∈ атомы(φ) но q ∉ атомы(ψ). Теперь определите:

φ ': = φ [⊤ /q] ∨ φ [⊥ /q]

Здесь φ [⊤ /q] совпадает с φ с каждым вхождением q заменяется на ⊤ и φ [⊥ /q] аналогично заменяет q с ⊥. Из этого определения мы можем заметить три вещи:

⊨φ '→ ψ

(1)

|атомы(ф ') - атомы(ψ)| = п

(2)

⊨φ → φ '

(3)

Из (1), (2) и индуктивного шага имеем, что существует интерполянт ρ такой, что:

⊨φ '→ ρ

(4)

⊨ρ → ψ

(5)

Но из (3) и (4) мы знаем это

⊨φ → ρ

(6)

Следовательно, ρ - подходящий интерполянт для φ и ψ.

QED

Поскольку приведенное выше доказательство конструктивный можно извлечь алгоритм для вычисления интерполянтов. Используя этот алгоритм, если п = |атомы(ф ') - атомы(ψ) |, то интерполянт ρ имеет О(EXP(п)) более логические связки чем φ (см. Обозначение Big O для подробностей относительно этого утверждения). Подобные конструктивные доказательства могут быть предоставлены для основных модальная логика K, интуиционистская логика и μ-исчисление, с аналогичными мерами сложности.

Интерполяция Крейга может быть доказана и другими методами. Однако эти доказательства обычно неконструктивный:

теоретико-модельно, через Совместная теорема Робинсона: при наличии компактность, отрицание и соединение, совместная теорема Робинсона и интерполяция Крейга эквивалентны.
теоретически доказательство, через Последовательное исчисление. Если вырезать устранение возможно и в результате свойство подформулы то интерполяция Крейга доказывается индукцией по выводам.
алгебраически, с помощью слияние теоремы для разнообразие алгебр, представляющих логику.
через перевод в другие логики с использованием интерполяции Крейга.

Приложения

Интерполяция Крейга имеет множество приложений, в том числе доказательства непротиворечивости, проверка модели,^[4] доказательства в модульный технические характеристики, модульный онтологии.

дальнейшее чтение

Джон Харрисон (2009). Справочник по практической логике и автоматизированному мышлению. Кембридж, Нью-Йорк: Издательство Кембриджского университета. ISBN 0-521-89957-5.
Хинман, П. (2005). Основы математической логики. А. К. Питерс. ISBN 1-56881-262-0.
Дов М. Габбай; Лариса Максимова (2006). Интерполяция и определяемость: модальная и интуиционистская логика (Oxford Logic Guides). Оксфордские научные публикации, Clarendon Press. ISBN 978-0-19-851174-8.
Ева Хугланд, Определимость и интерполяция. Теоретико-модельные исследования. Кандидатская диссертация, Амстердам, 2001 г.
В. Крейг, Три использования теоремы Эрбранда-Генцена для связи теории моделей и теории доказательств, Журнал символической логики 22 (1957), вып. 3, 269–285.

[1] Линдон, Роджер, "Интерполяционная теорема в исчислении предикатов", Тихоокеанский математический журнал, 9: 129–142.

[2] Трельстра, Энн Сьерп; Швихтенберг, Гельмут (2000), Основная теория доказательств, Кембриджские трактаты по теоретической информатике, 43 (2-е изд.), Cambridge University Press, стр. 141, ISBN 978-0-521-77911-1.

[3] Харрисон стр. 426–427

[4] Визель, Ю .; Weissenbacher, G .; Малик, С. (2015). "Решатели логической выполнимости и их приложения в проверке моделей". Труды IEEE. 103 (11). Дои:10.1109 / JPROC.2015.2455034.

[1]

[2]

[3]

[4]