Лекции 2-11. Математическая логика (до колка) (Лекции 2014), страница 6

Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2). Таблицы состоят из упорядоченных множеств формул(списков). Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2). Таблицы состоят из упорядоченных множеств формул(списков). Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ i(L∀)?T1 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | χ1 ∨ χ2 , ∆ iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2).

Таблицы состоят из упорядоченных множеств формул(списков). Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ i(L∀)?T1 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | χ1 ∨ χ2 , ∆ iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2). Таблицы состоят из упорядоченных множеств формул(списков). Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ i(L∀)?T1 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | χ1 ∨ χ2 , ∆ i(R∨)?T2 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | ∆, χ1 , χ2 iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2).

Таблицы состоят из упорядоченных множеств формул(списков). Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ i(L∀)?T1 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | χ1 ∨ χ2 , ∆ i(R∨)?T2 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | ∆, χ1 , χ2 iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2). Таблицы состоят из упорядоченных множеств формул(списков).

Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ i(L∀)?T1 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | χ1 ∨ χ2 , ∆ i(R∨)?T2 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | ∆, χ1 , χ2 iPPPP(L →))PqT3 = h Γ, ∀xϕ, ϕ0 , ψ2 | ∆, χ1 , χ2 i T4 = hΓ, ∀xϕ, ϕ0 | ∆, χ1 , χ2 , ψ1 iПОЛНОТА ТАБЛИЧНОГО ВЫВОДА2). Таблицы состоят из упорядоченных множеств формул(списков).

Правила применяются к формулам в порядке ихрасположения в списках. Формулы, участвующие вприменении правил, помещаются в хвост нужного списка.Атомарные формулы просто переходят из головы списка вего хвост.T0 = h ∀xϕ, ψ1 → ψ2 , Γ | χ1 ∨ χ2 , ∆ i(L∀)?T1 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | χ1 ∨ χ2 , ∆ i(R∨)?T2 = h ψ1 → ψ2 , Γ, ∀xϕ, ϕ0 | ∆, χ1 , χ2 iPP(L →)PP)PqT3 = h Γ, ∀xϕ, ϕ0 , ψ2 | ∆, χ1 , χ2 i T4 = hΓ, ∀xϕ, ϕ0 | ∆, χ1 , χ2 , ψ1 iи. т.

д.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3). С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3).

С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,L0 = {c 0 , c 00 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3).

С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,L0 = {c 0 , c 00 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3). С каждой таблицей T ассоциирован списокиспользованных констант LT .

Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,(L∃)?T1 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∀y χ(y ), ∆ i,L0 = {c 0 , c 00 }L1 = {c 0 , c 00 , c1 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3).

С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,(L∃)?T1 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∀y χ(y ), ∆ i,L0 = {c 0 , c 00 }L1 = {c 0 , c 00 , c1 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3).

С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,(L∃)L0 = {c 0 , c 00 }?L1 = {c 0 , c 00 , c1 }?L2 = {c 0 , c 00 , c1 , c2 }T1 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∀y χ(y ), ∆ i,(R∀)T2 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∆, χ(c2 ) i,ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3).

С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,(L∃)L0 = {c 0 , c 00 }?L1 = {c 0 , c 00 , c1 }?L2 = {c 0 , c 00 , c1 , c2 }T1 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∀y χ(y ), ∆ i,(R∀)T2 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∆, χ(c2 ) i,ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3).

С каждой таблицей T ассоциирован списокиспользованных констант LT . Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,(L∃)?L1 = {c 0 , c 00 , c1 }?L2 = {c 0 , c 00 , c1 , c2 }T1 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∀y χ(y ), ∆ i,(R∀)T2 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∆, χ(c2 ) i,PP(L →)PP)qPT3 = h Γ, ϕ(c1 ), ψ2 | ∆, χ(c2 ) iL3 = {c 0 , c 00 , c1 , c2 }L0 = {c 0 , c 00 }T4 = hΓ, ϕ(c1 ) | ∆, χ(c2 ), ψ1 iL4 = {c 0 , c 00 , c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА3). С каждой таблицей T ассоциирован списокиспользованных констант LT .

Вначале в этот списоквключаются все константы, содержащиеся в таблице T0 .В случае применения правил (L∃) и (R∀) в списокпорожденной таблицы добавляется «свежая константа».В остальных случаях список наследуется без изменений.T0 = h ∃xϕ(x), ψ1 → ψ2 , Γ | ∀y χ(y ), ∆ i,(L∃)L0 = {c 0 , c 00 }?L1 = {c 0 , c 00 , c1 }?L2 = {c 0 , c 00 , c1 , c2 }T1 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∀y χ(y ), ∆ i,(R∀)T2 = h ψ1 → ψ2 , Γ, ϕ(c1 ) | ∆, χ(c2 ) i,PP(L →)PP)qPT3 = h Γ, ϕ(c1 ), ψ2 | ∆, χ(c2 ) iT4 = hΓ, ϕ(c1 ) | ∆, χ(c2 ), ψ1 iL3 = {c 0 , c 00 , c1 , c2 }L4 = {c 0 , c 00 , c1 , c2 }и.

т. д.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4). В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4). В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,L0 = {c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4). В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,L0 = {c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4).

В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,(L∀)?L0 = {c1 , c2 }T1 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∃y χ(y ), ∆ i,L1 = {c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4). В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,(L∀)?L0 = {c1 , c2 }T1 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∃y χ(y ), ∆ i,L1 = {c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4).

В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,(L∀)?L0 = {c1 , c2 }T1 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∃y χ(y ), ∆ i,(R∃)L1 = {c1 , c2 }?T2 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∆, ∃xχ(x), χ(c1 ), χ(c2 ) i,L2 = {c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4). В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,(L∀)?L0 = {c1 , c2 }T1 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∃y χ(y ), ∆ i,(R∃)L1 = {c1 , c2 }?T2 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∆, ∃xχ(x), χ(c1 ), χ(c2 ) i,L2 = {c1 , c2 }ПОЛНОТА ТАБЛИЧНОГО ВЫВОДА4).

В случае применения к таблице T правил (L∀) и (R∃) вкачестве подстановочных термов используются всеконстанты из списка LT .T0 = h ∀xϕ(x), Γ | ∃y χ(y ), ∆ i,(L∀)?L0 = {c1 , c2 }T1 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∃y χ(y ), ∆ i,(R∃)L1 = {c1 , c2 }?T2 = h Γ, ∀xϕ(x), ϕ(c1 ), ϕ(c2 ) | ∆, ∃xχ(x), χ(c1 ), χ(c2 ) i,L2 = {c1 , c2 }и. т. д.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДАПредположим, что указанная стратегия не приводит кпостроению успешного вывода для невыполнимой таблицыT0 = h Γ0 | ∆0 i. Тогда в дереве вывода либо существуетбесконечная ветвь, не содержащая закрытых таблицT0 −→ T1 −→ T2 −→ .

. . −→ Tn −→ Tn+1 −→ . . .либо существует ветвь, оканчивающаяся незакрытой атомарнойтаблицейT0 −→ T1 −→ T2 −→ . . . −→ Tatom −→ Tatom −→ Tatom −→ . . .Будем полагать, что в последнем случае последовательностьтаблиц также бесконечна.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДАНа основе бесконечной последовательности незакрытых таблицT0 , T1 , . . . , Tn , Tn+1 , . . .

, каждая из которых имеет видTn = h Γn | ∆n i построим три множества:∞S1). Γω =Γiмножество всех формул из левых частейтаблиц,∆iмножество всех формул из правых частейтаблиц,LTiмножество всех констант из списков констант, ассоциированных с таблицами избесконечной ветви.i=02). ∆ω =∞Si=03). Lω =∞Si=0Используя множества Γω , ∆ω , Lω , построим интерпретацию Iω ,в которой будет выполняться каждая таблицапоследовательности.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДАIω = hDI , Const, PrediDI = Lωпредметная область состоит из всех константных символов,входящих в состав формул из Γω и ∆ω ,Const : Const → Lωзначением c каждой константы c (как символа из алфавита)является ее собственное изображение c ( как элементмножества Lω ), т.

е. c = c,Pred : Pred → (Lω n → {true, false})для каждого предикатного символа P (n) и набора элементовci1 , . . . , cin из LωP(ci1 , . . . , cin ) = true ⇐⇒ P(ci1 , . . . , cin ) ∈ Γω .ПОЛНОТА ТАБЛИЧНОГО ВЫВОДАПокажем, чтолюбая формула ϕ, ϕ ∈ Γω , выполнима в интерпретации Iω ,любая формула ψ, ψ ∈ ∆ω , невыполнима в интерпретации Iω .Доказательство проведем при помощи индукции по числулогических операций (связок и кванторов) в формуле.ПОЛНОТА ТАБЛИЧНОГО ВЫВОДАБазис индукцииϕ, ψ — атомарные формулы.Во всех таблицах Ti содержатся только замкнутые формулы(почему ? ).Поэтому формулы ϕ, ψ имеют вид P(ci1 , .