Лекция №8

Вид материала

Содержание

Использование равносильностей для упрощения формул.
По предположению индукции
A->a)->((a->b)->(a->ab)) (ii
A->b, b->c├─ a->c.
Ab->c ├─ a ->(b->c).
R->a)->(a->r) (iv

Подобный материал:

1 2 3 4

§ 9.3. Равносильность формул. Основные отношения равносильности.

Определение 9.3.1. Формулы А, В алгебры предикатов сигнатуры σ называются равносильными на алгебраической системе М(σ), если они принимают на М(σ) одинаковые значения при любом наборе значений предметных переменных, имеющих свободные вхождения переменных в А или В.

Из определения 9.3.1 видно, что равносильность тех или иных формул сигнатуры σ зависит от свойств алгебраической системы М(σ). Например, формулы xA и xA равносильны на любой одноэлементной системе, однако не равносильны в общем случае. Можно привести и менее тривиальные примеры. Изучение равносильностей, имеющих место для отдельных конкретных алгебраических систем, не отвечает целям и задачам математической логики как науки об общих закономерностях в рассуждениях. В связи с этим более ценным является следующее понятие равносильности.

Определение 9.3.2. Формулы алгебры предикатов сигнатуры σ называются равносильными, если они равносильны на любой алгебраической системе сигнатуры σ.

Равносильность формул А, В, как и равносильность высказываний будем обозначать в виде АВ.

Отметим следующие очевидные свойства равносильности формул.

1.Отношение равносильности формул является отношением эквивалентности на множестве всех формул сигнатуры σ, и, следовательно, все указанные формулы разбиваются на классы равносильных формул.

2.Если формула A’ получена из А заменой некоторой подформулы В равносильной ей формулой В’, то А’=А.

Приведем примеры равносильностей, называемых иногда основными равносильностями алгебры предикатов.

1. ABBA

2. AvBBvA 1, 2 – законы коммутативности

(AB)CA(BC)
(AvB)vCAv(BvC) 3, 4 – законы ассоциативности
A(BvC)ABvAC
AvBC(AvB)(AvC) 5, 6 - законы дистрибутивности
A(AvB)A
AvABA 7,8 – законы поглощения
AAA
AvA A 9, 10 – законы идемпотентности

__ _ _

ABAvB

____ _ _

12. AvB A B 11, 12 – законы де Моргана

_ _

A->BB->A закон контрапозиции

—

AA закон двойного отрицания

15.A v Aи закон исключенного третьего

16.AAл закон противоречия

17.(A->B)(B->C)->(A->C)и правило силлогизма

18. хуАухА 18, 19 – правила перестановки

19. хуАухА одноименных кванторов

___ _

20. хАxA 20, 21 – правила отрицания кванторов

___ _

21. xAxA

22. x(AB)xAxB 22, 23 – законы дистрибутивности

23. x(AvB)xAvxB кванторов ,  относительно

операций  и v (соответственно);

24. A->BA->B;

25. δxA*Bδx(A*B), где δ – квантор  или , *-операция  или v и формула В не содержит вхождений х;

26. δхА(х)δуА(у), где δ – квантор  или , А(х) – формула, не содержащая вхождений буквы у, а А(у) – формула, полученная из А(х) заменой всех свободных вхождений х на у.

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

Так, зачастую вместо теоремы вида А -> В доказывается равносильное утверждение А ->В. При этом используется закон контрапозиции 13. Закон исключенного третьего 15 обычно используется при доказательствах от противного, когда для доказательства теоремы А опровергают утверждение А и отсюда на основании равносильности A v A  и делают вывод об истинности А. Правило силлогизма 17 позволяет сводить доказательства теоремы вида А->С к доказательству цепочек более простых утверждений, например, А->В, В->С.

С другой стороны, в доказательствах иногда допускаются ошибки, состоящие в замене утверждения на равносильным ему предложением. Так по аналогии с равносильностями 18-19, разрешающими переставлять одноименные кванторы, иногда переставляют и разноименные кванторы. Этого делать нельзя, поскольку и в общем случае формулы вида

хуА и ухА (1)

не равносильны. Например формула ху(x < y) истинна на N, а формула ху(x < y) ложна.

Аналогичные ошибки допускаются с использованием правила дистрибутивности кванторов  и  относительно операций v и  (соответственно). Покажите в качестве упражнения, что формулы

х(A v B) и хА v xB,

a также формулы

х (A  B) и хА  xB

в общем случае не равносильны.

Заметим, что равносильность формул А, В эквивалентна истинности формулы

(A->B)  (B->A)

или двух формул

A->B, B->A.

Однако практически зачастую бывает так, что из двух последних формул истинна только одна. Так, приведенные выше формулы (1) в общем случае не равносильны, но формула

ухА -> хуА

истинна на любой алгебраической системе.

Если формула А->В истинна на системе М(σ), то при любом наборе значений предметных переменных, имеющих свободные вхождения в формулу А->В, формула В принимает истинное значение всякий раз, когда истинным является значение А. В связи с этим говорят, что формула В является следствием формулы А.

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

Определение 9.3.3. Пусть А – формула алгебры предикатов, не содержащая операции ->. Формула, полученная из А заменой всех вхождений  на ,  на ,  на ,  на , называется двойственной к А и обозначается через А*.

Очевидно, что (А*)*= А, и потому формулы А и А* называются двойственными. Двойственными называются и взаимозаменяемые операции  и , а также кванторы  и .

Теорема 9.3.4. Пусть А – формула алгебры предикатов p₁, …, p_s суть все различные элементарные формулы в А, т. е.:

A = A(p₁, …, p_s)

Тогда имеет место равносильность формул:

A*( p₁, …, p_s) = A(p₁, …, p_s).

Доказательство. Докажем теорему индукцией по рангу r формулы А. При r = 0 ее утверждение верно. Допустим, что оно верно для любой формулы ранга r < n и пусть r(A) = n+1.

Возможны 5 случаев:

A = A₁  A₂, A = A₁ v A₂, A = xA₁, A = xA₁, A =A₁.

A = A₁  A₂. Тогда, используя предположение индукции, закон де Моргана 11 и общие свойства равносильности, получим:

A*( p₁, …, p_s) = A₁*( p₁, …, p_s) v A₂*( p₁, …, p_s) 

 A₁ ( p₁, …, p_s) v A₂( p₁, …, p_s)  A ( p₁, …, p_s).

В трех следующих случаях рассуждения аналогичны. Вместо равносильности 11 в них используются соответственно равносильности 12, 20, 21. В последнем случае утверждение теоремы следует непосредственно из предположения индукции. Теорема доказана.

Следствие 9.3.5. (Принцип двойственности.) Для любых формул А, В алгебры предикатов:

A  B  A*  B*

Принцип двойственности позволяет вместо двух равносильностей A  B и A*  B* доказывать лишь любую одну из них.

§ 9.4. ^ Использование равносильностей для упрощения формул.

Равносильности 1-26 зачастую используются также для преобразования формул к равносильным им формулам нужного вида.

В качестве примеров рассмотрим преобразование формул алгебры предикатов к так называемым приведённым и предваренным формулам.

Определение 9.4.1. Формула алгебры предикатов называется приведенной, если в ней не используется операция ->, а отрицание или не используется совсем, или относится лишь к элементарным формулам.

Определение 9.4.2. Предваренной (или нормальной, или пренексной) формулой алгебры предикатов называется любая формула вида

δ₁x_i1δ₂x_i2…δ_kx_ik A, (1)

где δ₁, …, δ_k – кванторы, а А приведенная формула, не содержащая кванторов.

Теорема 9.4.3. Для всякой формулы А алгебры предикатов существует равносильная ей приведенная формула. Докажем теорему индукцией по рангу r(А) формулы А. Если r(А) = 0, то утверждение верно. Пусть r(А) > 0. Тогда по определению формулы А совпадает с одной из формул вида

A₁  A₂, A₁ v A₂, δxA₁, A₁ -> A₂, A₁ (2)

^ По предположению индукции формулы А₁, А₂ равносильны приведенным формулам. Заменив ими в (2) формулы А₁, А₂, мы в трех первых случаях сразу получим приведенные формулы. А так как A₁->A₂  А₁vА₂ (см. равносильность 24), то остается рассмотреть случай, когда A =A₁. Если А₁ – элементарна, то А – приведенная формула. Если же А₁ не элементарна, то она может иметь вид

B₁  B₂, B₁ v B₂, δxB₁, B₁ -> B₂, B₁,

где r(B_i) < r(A) - 2. Тогда по свойствам равносильности 11, 12, 20, 21, 24, 14 формула А равносильна одной из формул:

B₁ v B₂, B₁B₂, δ*xB₁, B₁vB₂, B₁ (3)

Остается применить предположение индукции к формулам B₁,B₁,B₂ и заменить их в (3) приведенными формулами.

Теорема 9.4.4. Для всякой формулы а алгебры предикатов существует равносильная ей предваренная формула.

Доказательство. По теореме 9.4.3, не теряя общности, можно считать, что А – приведенная формула. Снова применим индукцию по r(А). Для r(А) =0 утверждение верно. Пусть r(А) > 0. Тогда формула А может иметь вид

1) A₁  A₂, 2) A₁ v A₂, 3) δxA₁, 4) A₁

Причем в случае 4 А₁ – элементарная формула и для нее утверждение теоремы верно. Рассмотрим случаи 1-3.

1. A = A₁  A₂. По предположению индукции А_i равносильна предваренной формуле B_i, i = 1,2, причем согласно равносильности 26 связанные переменные любой из формул В₁, В₂ можно считать отличными от всех переменных другой формулы. Таким образом, A = B₁  B₂, где можно считать

B₁= δ₁x₁…δ_kx_kC₁, B₂=δ_k+1x_k+1…δ_nx_nC₂

x₁, …, x_k не входят в С₂, x_k+1,…,x_n не входят в С₁, и формулы С₁, С₂ не содержат кванторов. Отсюда, используя равносильность 25, получим

Aδ₁x₁…δ_kx_kδ_k+1x_k+1…δ_nx_n(C₁  C₂).

2. A = A₁ v A₂, рассуждения двойственны.

3. A = δxA₁. По предположению индукции А₁ равносильна приведенной формуле

A  δ₁x₁…δ_kx_kB (4)

причем можно считать, что x  x₁, …, x_k. Возможны два подслучая:

а) В содержит свободные вхождения х. Тогда А равносильна предваренной формуле

δxδ₁x₁…δ_kx_kB;

б) В не содержит свободных вхождений х. Тогда из равносильности 4 следует, что значения формулы А₁ не зависят от значений переменной х, а потому АА₁ и теорема доказана.

§9.5. Построение исчисления предикатов.

1. Язык исчисления предикатов.

В качестве алфавита исчисления предикатов возьмем то же самое множество

Ҩ = σ U X U O

которое служило алфавитом при определении формул алгебры предикатов. За элементами множества σ, Х и О сохраним те же самые обозначения и названия, хотя здесь на все буквы алфавита Ҩ мы должны пока смотреть просто как на символы, не имеющие какого-либо содержательного смысла. Например, символ операции f здесь не обозначает какую-либо конкретную операцию, определенную на каком-либо конкретном множестве. То же относится и к символам предикатов. Термины же «символ операции» и «символ предиката» объясняются тем, что в приложениях исчисления предикатов к конкретным математическим теориям мы будем трактовать их (интерпретировать) как операции и предикаты на конкретном множестве. Аналогично, предметным переменным будут придаваться значения из этого множества.

Понятия терма и формулы сигнатуры σ в исчислении предикатов определяются буквально так же, как в алгебре предикатов.

Равенство формул, как и в алгебре предикатов, будем обозначать знаком =.

Из множества всех формул ниже особую роль будут играть формулы, не содержащие свободных вхождений предметных переменных. Они называются замкнутыми формулами, или предложениями.

Таким образом, нами полностью определен язык исчисления предикатов 1-й ступени сигнатуры σ. Обозначим его буквой α. При формул языка α будут использоваться те же правила сокращения скобок, что и в алгебре предикатов.

Заметим, что кроме исчисления предикатов 1-й ступени в математической логике и в теории моделей рассматриваются исчисления предикатов и логические языки 2-й ступени. В их алфавиты кроме перечисленных выше символов вводятся также символы функциональных и предикатных переменных и кванторы ,  могут навешиваться не только на предметные переменные, но и на функциональные переменные и предикатные переменные.

2.Аксиомы и правила вывода исчисления предикатов.

При построении исчисления предикатов с определенным выше языком α аксиомы и правила вывода могут выбираться по-разному. Мы выберем следующую систему аксиом. Аксиомы этой системы по используемым в них логическим операциям делятся на 5 подсистем, которые мы занумеруем римскими цифрами. В подсистемах l - lV под буквами А, В, С понимаются произвольные формулы языка α, ограничения на формулы системы V указываются в формулировках соответствующих аксиом.

1) A->(B->A)

2) (A->(B->C))->((A->B)->(A->C))

1) AB->A

2) AB->B
3) (A->B)->((A->C)->(A->BC))

lll. 1) A->AvB

2) B->AvB

3) (A->C)->((B->C)->(AvB->C))

—

IV. 1) A->A

—

2) A->A

3)(A->B)->(B->A)

V. 1)x A(x)->A(t)

2) A(t)->x A(x).

где A(x) – формула, содержащая свободные вхождения переменной х, A(t) – формула, полученная заменой в A(x) всех свободных вхождений x термом t, удовлетворяющим условию: ни одно свободное вхождение х в A(x) не находится в области действия квантора по какой-либо переменной, содержащейся в t (при этом условии говорят, что терм t свободен для х в формуле A(x)) (далее аксиомы будут обозначаться римскими цифрами с индексами. Например, ll₃ – аксиома 3 из подсистемы ll).

Сформулируем теперь правила вывода. Каждое такое правило позволяет из некоторого множества исходных формул получать новую формулы. Поэтому правило вывода записывают обычно в виде «дроби», у которой в «числителе» находятся исходные формулы, а в «знаменателе» – вновь получаемая формула.

l. Правило заключения:

A, A ->B ,

B

где А, В – любые формулы языка α.

ll. Правило -введения:

B -> A ,

B->xA

где А содержит , а В не содержит свободные вхождения переменной х.

lll. Правило -удаления:

A -> B ,

x A->B

где А, В – формулы, удовлетворяющие тем же условиям, что и в правиле ll.

Формула, находящаяся в «знаменателе» правила вывода, называется непосредственным следствием формул «числителя».

Заметим, что, подставляя в аксиому l₁ вместо А, В произвольные формулы, мы получим бесконечное множество формул. Таким образом, запись аксиомы l₁ является, по существу, схемой, по которой можно получать формулы. То же можно сказать об остальных аксиомах и о формулах из правил вывода.

Определив язык α и аксиомы с правилами вывода, мы определили тем самым логическое исчисление, называемое исчислением предикатов 1-й ступени сигнатуры σ. Меняя σ, т. е. меняя множество формул и сохраняя схемы аксиом и правил вывода, мы будем получать другие исчисления предикатов. В дальнейшем язык α будем считать фиксированным и соответствующее логическое исчисление будем обозначать той же буквой α.

§ 9.6. Выводимость и доказуемость формул.

Определение 9.6.1. Выводом формулы А из конечного или бесконечного множества формул Т в исчислении α называется конечная последовательность формул

А₁, А₂, …, A_n, ___

в которой A_n = A и каждая из формул A_i, i 1, n является или аксиомой, или формулой из Т (исходной формулой), или получается по некоторому правилу вывода из предыдущих формул последовательности (1).

Если существует вывод формулы А из множества формул Т исчисления α, то говорят, что в α А выводима из Т и пишут

Т ├─ А, или В₁, В₂, …, В_К ├─ А,

α α

если Т = {В₁, В₂, …, В_К}. При этом формулы из Т называют посылками вывода.

Особо важным является случай, когда Т – пустое множество.

Определение 9.6.2. Формула из А языка α , выводимая в исчислении α из пустого множества формул, называется доказуемой формулой, или теоремой исчисления α, а сам вывод формулы А из пустого множества формул называется ее доказательством. Если формула А доказуема в исчислении α, то пишут

├─ А.

α

Так как у нас исчисление α фиксировано, то букву α будем опускать и писать просто

Т ├─ А; В₁, В₂, …, В_К ├─ А; ├─ А.

Очевидно, что при выводах и доказательствах формул можно использовать не только аксиомы и исходные формулы, но и любые доказанные ранее формулы.

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

Теорема 9.6.3. ├─ А -> А для любой формулы А.

Доказательство.

1) (А->((В->А)->А))->((А->(В->А))->(А->А)), (l₂)

2) А ->((В->А)->А) , (l₁)

3) (А->(В->А))->(А->А), (l, 1, 2)

4) А-> (В->А), (l1)

5) А->А. (1, 3, 4)

Теорема 9.6.4. Если А – любая формула и В – доказуемая формула, то ├─ А->В.

Доказательство получается и добавлением к доказательству формулы В аксиомы l₁ и формулы А->В, получаемой из В и аксиомы l₁ по правилу l.

Теорема 9.6.5. ├─ АВ -> ВА для любых формул А, В.

Доказательство.

1) (АВ->В)->((АВ->А)->(АВ->ВА)), (ll₃)

АВ->В, (ll₃)
(АВ->А)->(АВ->ВА), (l, 1, 2)

4) АВ->А, (ll₁)

5) АВ->ВА.

Заменяя в доказательстве теоремы 9.6.5 ll₁ ll₃ соответственно аксиомами lll₁-lll₃, получим доказательство следующей формулы.

Теорема 9.6.6. ├─ АВ -> ВА для любых формул А, В.

______ ___

Теорема 9.6.7. ├─ x A(x) ->-x A(x) для любой формулы А(х), содержащей свободные вхождения переменной х.

Доказательство.

А(х)-> х А(х), (V2)

______ ___

2) (А(х)->х А(х))->(х А(х)->А(х)) (lV3)

______ ___

3) x А(x) ->А(x) (l, 1, 2)

______ ___

4) x А(x) -> x А(x) (l, 1, 3)

Даже из приведенных простейших примеров видно, что задача построения доказательств формул является сложной и зачастую весьма искусственной. То же относится и к построению выводов. Попытайтесь, для примера построить вывод

AC ->D ├─ A -> (C->D).

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

Ряд наиболее распространенных вспомогательных правил вывода можно получить из так называемой теоремы дедукции. Однако и ее формулировка и доказательство в общем случае сложны. Мы пока один ее ослабленный вариант.

Теорема об ограниченной дедукции. Пусть Т – произвольное множество формул, и А, В – произвольные формулы. Если

T, A├─ B (2)

и существует вывод формулы В из T U {A}, в котором не используются правила -введения и -удаления, то

T ├─ A -> B. (3)

Доказательство. Пусть

В₁, В₂, …, В_m = B

есть вывод формулы В из T U {A}, в котором не используются правила -введения и -удаления. Докажем утверждение (3) индукцией по длине вывода m.

Пусть m=1. Тогда В является или аксиомой, или посылкой. Если В – аксиома, то она, очевидно, доказуема, и по теореме 9.6.4 имеем ├─ A -> B для любой формулы А. Отсюда и следует (3). Пусть В – посылка. Если В=А, то (3) следует из теоремы 9.6.3. Если же ВТ, то можно указать следующий вывод формулы А->В из Т:

В->(А->В), (l₁)
В, (посылка)

3) А->В (l, 1,2)

Допустим, что теорема верна при m < n, и докажем ее для m = n + 1. В этом случае по условию формула В будет или аксиомой, или посылкой, или непосредственным следствием двух предыдущих формул B_i, B_Jпо правилу заключения. Если В – аксиома или посылка, то (3) устанавливается точно так же, как и при m=1. Пусть В получается из B_i, B_J по правилу заключения, т. е. B_J = B_i -> B. Так как i<n, j<n, то по предположению индукции имеем:

T├─ A -> B_i, T├─ A -> (B_i->B).

Применяя теперь к формулам

A->( B_i ->B), A-> B_i

и к аксиоме l₂

(A->( B_i ->B))->((A-> B_i)->(A->B))

дважды правило заключения, получим формулу А->В. Теорема доказана.

Докажем теперь ряд вспомогательных правил вывода, обозначая в них буквами А, В, С произвольные формулы α.

Правило умножения формул:

A, B ├─ AB.

Вывод.

^ (A->A)->((A->B)->(A->AB)) (II₃)
A->A (теорема 1)
(A->B)->(A->AB) (I, 1, 2)
B->(A->B) (I₁)
B (посылка)
A->B (I, 4, 5)
A->AB (I, 3, 6)
A (посылка)
AB . (I, 7, 8)

Правило силлогизма:

^ A->B, B->C├─ A->C.

Согласно теореме дедукции достаточно показать, что

A->B, B->C, A├─ C,

причем существует вывод С, не использующий правил -введения и -удаления. Таким выводом может служить последовательность формул:

А, А->В, В, В->С, С.

Для ее получения дважды применяется правило заключения к посылкам. Аналогично доказываются следующие правила.

Правило умножения посылок:

A->(B->C)├─ AB ->C.

Правило разделения посылок:

^ AB->C ├─ A ->(B->C).

Правило перестановки посылок:

A->(B->C)├─ B->(A->C).

Правило умножения заключений:

A->B, A->C├─ A->BC.

Правило сложения посылок:

A->C, B->C├─ A v B->C.

Правило введения посылки:

A├─ B->A.

Правило контрапозиции:

A->B├─ B->A.

Правило де Моргана:

_ _ __ ___ _ _

a) A v B ├─ AB, б) АВ ├─ A v B

а) Вывод:

AB->A (ll₁)

AB->B (ll₂)

_ __

A->AB (правило контрапозиции, 1)

_ __

B->AB (правило контрапозиции, 2)

_ _ __

A v B->AB (правило сложения посылок, 3, 4)

_ _

A v B (посылка)

AB (1, 5, 6)

б) Вывод:

_ _ _

A->A v B (lll₁)

_ _ _

B->A v B (lll₂)

──── ─

A v B ->A (правило контрапозиции, 1)

──── ─

A v B ->B (правило контрапозиции, 2)

─

A->A (IV₂)

─

B->B (IV₂)

────

A v B->A (правило силлогизма, 3, 5)

────

A v B->B (правило силлогизма, 4, 6)

────

A v B->AB (правило умножения заключений, 7, 8)

__ ────

AB->A vB (правило контрапозиции, 9)

───── _ _

A v B -> A v B (IV₂)

__ _ _

AB->A v B (правило силлогизма, 10, 11)

Правило -отрицания:

_____ ___

а) x A(x)├─ x A(x)

(следует непосредственно из теоремы 9.6.7);

___ _____

б) x A(x)├─ x A(x)

Вывод:

___ ___

x A(x)->A(x) (V₁)

─── ───

A(x) ->x A(x) (правило контрапозиции, 1)

──

A(x) -> A(x) (IV₁)

─────

A(x) -> x A(x) (правило силлогизма, 2, 3)

────

x A(x)-> x A(x) (lll, 4)

═════ ────

x A(x) ->x A(x) (правило контрапозиции, 5)

___ ═════

x A(x) -> x A(x) (IV₁)

___ ______

x A(x) ->x A(x) (правило силлогизма, 6, 7)

Правило -отрицания:

______ ___ ___ ______

а) x A(x) ├─ x A(x); б) x A(x)├─ x A(x).

Докажите в качестве упражнения.

Правило противоречия:

АА ├─ В (из противоречия выводима любая формула).

Распишем вывод произвольной формулы В из АА, используя при этом любую доказуемую формулу R, например, А->А.

A->(R->A) (l₁)

^ (R->A)->(A->R) (IV₃)

A->(A->R) (правило силлогизма, 1, 2)

AA -> R (правило умножения посылок, 3)

B->R ( теорема 2)

_ ─

R->B (правило контрапозиции, 5)

─

AA ->B (правило силлогизма, 4, 6)

═

B->B (IV₂)

AA->B (правило силлогизма, 7, 8)

AA (посылка)

B (1, 9, 10)

Правило (закон) исключенного третьего:

├─ A vA.

Доказательство (снова используем доказуемую формулу R).

A->AvA (lll₁)

A->AvA (lll₁)

_____

A v A->A (правило контрапозиции, 1)

_____ _

A vA->A (правило контрапозиции, 2)

─

AvA->A (IV₁)

_____

A vA->A (правило силлогизма, 4, 5)

_____

A vA->AA (правило умножения заключений, 7, 8)

AA->R (правило противоречия и теорема дедукции )

____

A vA ->R (правило силлогизма, 7, 8)

═ ═══

R-> A vA (правило контрапозиции, 9)

═

R->R (IV₁)

════

R->A vA (правило силлогизма, 10, 11)

════

A vA->A vA (IV₂)

R->A vA (правило силлогизма, 12, 13)

R (теорема)

A vA (1, 14, 15)

Воспользуемся вспомогательными правилами вывода для доказательства еще одного частного случая теоремы дедукции.

Теорема дедукции (для замкнутой формулы). Если Т произвольное множество формул, В – произвольная, А – замкнутая формулы и

T, A├─ B,

то

T├─ A->B.

Доказательство производится так же, как теоремы об ограниченной дедукции. В дополнение нам необходимо лишь рассмотреть два случая (при m = n + 1):

а) В получается по правилу -введения из формулы B_i;

б) В получается по правилу -удаления из формулы B_i.

В случае «а» имеем:

B_i= C->D(x), B = C->x D(x),

причем С не содержит свободных вхождений х. По предположении индукции имеем:

T├─ A->(C->D(x)).

Дополним вывод формулы A->(C->D(x)) следующими формулами до вывода формулы А->В:

AC-> D(x) (правило умножения посылок)

AC->x D(x) (правило -ввведения)

A->(C->x D(x)) = A->B (правило разделения посылок)

В случае «б»:

B_i = C(x) -> D, B =  x C (x) ->D,

где D не содержит свободных вхождений х. По предположению индукции

T├─ A->(C(x)->D).

Отсюда, используя правила перестановки посылок и -удаления, получим:

T├─ C(x)->(A->D)

T├─ x C(x)->(A->D)

T├─ A->(x C(x) ->D) = A->B.

Теорема доказана.

Укажем одно следствие теоремы дедукции.

Следствие. Если Т – любое множество формул, А – замкнутая, В – любая формулы и

T, A ├─ BB

то

T ├─ A. (4)

Доказательство. По теореме дедукции

T ├─ A -> BB.

Применяя правило контрапозиции, получим

___

T├─ BB -> A. (5)

Из правила де Моргана «а» и закона исключенного третьего следует, что

___

├─ BB (6)

Для любой формулы В. Из (5), (6) следует (4).

§9.7. Семантика исчисления предикатов.

Для уяснения содержательного смысла аксиом и правил вывода введем понятие интерпретации языка и исчисления α.

Определение 9.7.1. Под интерпретацией языка исчисления α понимают любое множество М с зафиксированным отображением  сигнатуры σ во множество операций и предикатов, определенных на М, при котором символу n-арной операции f из σ соответствует n-арная операция f^, определенная на множестве М, а символу n-арного предиката р из σ n-арный предикат р^ на М. Образ множества σ при отображении  обозначим через σ^. В частности, образом констант из σ при  будут нуль-арные операции на М, т. е. некоторые элементы из М.

Если (М, ) – интерпретация языка α, то, заменив в любой формуле языка α константы, символы операций и символы предикатов их образами при  и условившись переменным из Х придавать значения из множества М, мы получим формулу А^ алгебры предикатов на алгебраической системе М(σ^), и можно говорить о выполнимости, истинности или ложности этой формулы на системе М(σ^).

Определение 9.7.2. Формула А исчисления предикатов называется выполнимой, истинной, ложной в интерпретации (М, ), если соответственно выполнима, истинна, ложна формула А^ на алгебраической системе М(σ^).

Определение 9.7.3. Формула А исчисления предикатов α называется тождественно истинной, если она истинна во всех интерпретациях исчисления α.

Естественно возникает вопрос о соотношении между классами доказуемых и истинных формул исчисления предикатов. Ответ на этот вопрос можно получить из следующих теорем.

Теорема 9.7.4. Если каждая формула множества формул Т истинна в некоторой интерпретации (М, ) исчисления α и T├─ A, то А – истинна в (М, ).

Доказательство. Для простоты записей условимся считать, что операции и предикаты на М обозначены теми же буквами, что и соответствующие им символы операций из σ. Тогда  - тождественное отображение и в записи А^ индекс  можно опускать.

Из определения доказуемой формулы следует, что достаточно делать два утверждения:

а) все аксиомы – истинны;

б) формула, являющаяся непосредственным следствием по любому правилу вывода из истинных формул, является истинной.

Истинность аксиом первых четырех групп аксиом доказывается одним методом. Проиллюстрируем его на аксиоме

I₁: A -> (B->A).

Заменив в А, В свободные вхождения переменных элементами из М, получим высказывания, имеющие вполне определенные значения £ и ß (каждое из £, ß есть «и» или «л»). Перебирая всевозможные наборы значений «и» и «л» для £, ß мы непосредственной проверкой (пользуясь определением операции ->) убедимся в том, что при любых £ , ß

£ -> (ß->£)= и.

Отсюда следует, что аксиома l₁ истинна в интерпретации (М, ).

Докажем теперь истинность аксиомы

V₁ : x A(x) -> A(t),

где t – терм, свободный для х в А(х). Пусть х, х₁, …, х_n суть все переменные, имеющие свободные вхождения в А(х) и x_i1, …, x_im – все переменные, участвующие в образовании терма t. Так как t свободен для х в А(х), то все вхождения переменных x_i1, …, x_im в терм t останутся свободными при подстановке t вместо х в формулу А(х). В связи с этим запишем:

A(t) = A(t (x_i1, …, x_im), х₁, …, х_n).

Допустим, что формула V₁ не истинна в интерпретации (М, ). Это означает, что при некотором наборе значений переменных х₁=a₁, …, х_n=a_n, x_i1=a_i1, …, x_im=a_im формула x A(x) принимает значение «и», а формула A(t) – значение «л». Если обозначить через b значение терма t при x_i1=a_i1, …, x_im=a_im, то будем иметь: с одной стороны, A(х₀, a₁, …, a_n) является истинным высказыванием при любом значении х₀М, а с другой стороны, высказывание A(b, a₁, …, a_n) - ложно. Полученное противоречие и доказывает наше утверждение.

Аналогично доказывается, что правила вывода позволяют из истинных формул в интерпретации (М, ) получать снова истинные формулы, т. е.:

если истинны формулы А и А->В, то истинна и формула В;
если истинна формула В->А(х) и х не имеет свободных вхождений в В, то истинна формула В -> х А(х);
если истинна формула А(х)->В и х не имеет свободных вхождений в В, то истинна и формула х А(х) -> В.

Теорема доказана.

Следствие 9.7.5. Всякая доказуемая формула исчисления предикатов α является истинной в любой интерпретации (М, ) исчисления α.

Замечание. Теорема и следствие теряют силу, если в аксиомах V₁ и V₂ не накладывать ограничений на терм t или в правилах -введения и -удаления разрешить свободные вхождения х в В. Приведем соответствующие примеры.

1. Пусть множество натуральных чисел N, A(x) = y (x < y) и t = x + y – терм, не свободный для х в А(х), поскольку свободное вхождение буквы х в А(х) находится в области действия квантора  по букве у, входящий в терм t.

Нетрудно видеть, что формула

x A(x) ->A(t),

или подробнее,

x (y(x y (x + y
ложна в арифметике.

В той же интерпретации, положим B = ( x < y ), A = (x < y +1) .

Тогда имеем: формула В->А истинна на N, а формула В -> xА ложна, поскольку, например, при х=2, у=3 имеем

(2<3)  и, x (x < 4)  л.

Доказанная теорема свидетельствует о том, что логические средства исчисления предикатов выбраны разумно, поскольку с помощью их можно доказать только утверждения, истинные с содержательной точки зрения.

Следствие 9.7.6. Исчисление предикатов непротиворечиво, т.е. в нем не может быть доказуемой никакая формула А вместе с ее отрицанием, или никакая формула вида АА.

Действительно формула АА является ложной в любой интерпретации, тогда как доказуемые формулы истинны в любой интерпретации.

Теперь естественно возникает вопрос: не слишком ли мало аксиом и правил вывода мы взяли при построении исчисления предикатов? Так, из доказательства предыдущей теоремы видно, что если бы нашлась формула А, не доказуемая в исчислении предикатов, но истинная в любой его интерпретации, то, присоединив А к системам аксиом, мы получили бы более сильное и непротиворечивое логическое исчисление. Однако ниже будет показано, что такой формулы А не существует, а именно имеет место следующая теорема Геделя о полноте исчисления предикатов.

Теорема 9.7.7. Если формула исчисления предикатов истинна во всех его интерпретациях, то она доказуема в исчислении предикатов.

Для доказательства этой теоремы введем сначала некоторые понятия М докажем одно общее утверждение (см. теорему 9.7.11).

Определение 9.7.8. Множество формул Т исчисления α называется противоречивым, если существует такая формула А языка α, что

Т├─ АА.

В противном случае Т называется непротиворечивым.

Определение 9.7.9. Множество формул Т исчисления α называется выполнимым, если существует интерпретация, в которой все формулы из Т принимают истинное значение хотя бы при одной (общей для всех формул из Т) замене переменных.

Определение 9.7.10. Множество формул Т исчисления α называется полным, если для каждой замкнутой формулы языка α имеет место

Т├─ А или Т ├─ А.

Теорема 9.7.11. Всякое непротиворечивое множество S замкнутых формул исчисления α выполнимо.

Доказательство. Добавим к множеству символов языка α еще счетное множество констант (символов нуль-арных операций)

ß = {b₀, b₁, b₂, …} .

Получим новый язык α₁ в сигнатуре σ₁ = σ U ß. Заменяя в аксиомах и правилах вывода исчисления α формулы языка α₁, мы получим новое логическое исчисление, которое обозначим той же буквой α₁. Из определения языка α₁видно, что все доказанные факты об исчислении α (в частности, все доказанные формулы и дополнительные правила вывода) сохраняются и в α₁. Так как язык α₁ включает в себя α, то S можно рассматривать как множество предложений языка α₁. Легко видеть, что S будет непротиворечивым и в исчислении α₁. Действительно, если в α₁ из S выводима формула АА, то, заменив в формулах вывода АА из S все константы из ß переменными, не участвующими в этом выводе, мы получим вывод в α из S формулы ВВ , где В получается из А указанной заменой констант. Чтобы убедиться в этом, достаточно заметить, что указанная замена аксиомы переводит в аксиомы и сохраняет свойство формулы быть непосредственным следствием предыдущих формул. Таким образом, S непротиворечиво в α₁.

Теперь расширим определенным образом множество S. Для этого занумеруем все замкнутые формулы исчисления α₁:

А₀, А₁, А₂, …

По формуле А₀ и системе S построим множество формул S₀, положив:

 S U { А₀ }, если S├─ А₀

S₀ =  S U { А₀ }, если S├┼ А₀ и А₀  х В₀ (х)

 S U { А₀, B₀, (b_i0)}, если S├┼ А₀и А₀ = х В₀ (х),

где знаком ├┼ обозначено отрицание выводимости, а b_i0 – символ с наименьшим номером из ß, не встречающийся в А₀. Из определения S₀ имеем:

S  S₀ и S₀ ├─ А₀ или S₀ ├─ А₀

Покажем, что юю непротиворечиво. Допустим, что в α₁

S₀ ├─ ВВ

В соответствии с определением S₀ рассмотрим три случая.

А) S ├─ А₀. Тогда S₀ = S U { А₀ } и из (2) имеем:

S, А₀├─ BB.

Отсюда по следствию из теоремы дедукции получаем

─

S ├─ А₀, что невозможно в силу непротиворечивости S.

Б) S├┼ А₀ и А₀ не имеет вида х В₀(х). Тогда S₀ = S U {

А₀} и мы точно так же, как и в случае «а», получим S ├─

─

А₀, что противоречит условию.

В) S├┼ А₀и А₀ = х В₀ (х).

Тогда S₀ = S U { А₀, B₀, (b_i0)} , и потому

S, А₀, B₀, (b_i0) ├─ ВВ.

Так как формула B₀ (b_i0) замкнута, то тем же приемом, что и выше, получим

______

S, А₀ ├─ B₀ (b_i0).

Так как b_i0 не входит в А₀ и в формулы из S, то, повторив весь вывод с заменой b_i0 на переменную x_J, не входящую в участвующие в выводе формулы, мы получим

_____ _____

S, А₀ ├─ B₀ (x_J), или S ├─ А₀ -> B₀ (x_J).

______

Дополним вывод А₀ -> B₀, (x_J) из S формулами:

______

А₀ ->  x_J B₀ (x_J) (правило -введения)

_____ _____

 x_J B₀, (x_J) -> B₀ (x_J) (аксиома)

_____

А₀ -> B₀ (x) (правило силлогизма)

____

А₀ ->  x B₀ (x) (правило -введения)

____ _______

 x B₀ (x) ->  x B₀ (x) (правило -отрицания)

_______

А₀ ->  x B₀ (x) (правило силлогизма)

Поскольку  x B₀ (x) = А₀, то мы получили вывод из S формулы А₀ -> А₀, т. е. S, А₀ ├─ А₀. А так как S, А₀ ├─ А₀, то по правилу умножения формул S, А₀ ├─ А₀А₀. Отсюда следует S├─ А₀, и мы снова пришли к противоречию с условием. Тем самым мы закончили доказывать непротиворечивость множества формул S₀.

Далее, по А₁ и S₀ мы аналогично построим непротиворечивое множество S₁, такое, что:

S₀ S₁, S₁ ├─ А₁ или S₁ ├─ А₁.

Продолжая этот процесс, мы получим последовательность непротиворечивых множеств формул

S₀ S₁ S₂ …, 

таких, что S_i ├─ А_i и S_i ├─ А_i. Следовательно, T = U S_i есть непротиворечивое и полное множество формул. ⁱ⁼⁰

Теперь построим интерпретацию исчисления предикатов α, в которой истинны все формулы из α. В качестве основного множества возьмем множество М термов языка α₁, в которых нет предметных переменных – это так называемые замкнутые термы языка α₁. Определим на М операции f^ и предикаты р^, соответствующие символам операций f и предикатов р из α.

Если а – символ 0-арной операции из σ, то положим а^=а. Если f – символ n-арной операции из σ, p – символ n-арного предиката и t₁, …, t_n – термы из М, то положим

f^ (t₁, …, t_n)=f(t₁, …, t_n)

и, если Т ├─ р(t₁, …, t_n)

p^ (t₁, …, t_n)= 

л, если Т ├─ р(t₁, …, t_n)

Тем самым определена интерпретация (М, σ) исчисления α₁, а потому и α.

Теперь индукцией по рангу формулы А докажем, что для любой замкнутой формулы языка α₁:

Т├─ А в α1  А^  и в (М, σ). (3)

Для упрощения записи верхний индекс  у формул будем опускать.

Если А = р(t₁, …, t_n) – элементарная формула, то (3) верно по определению предиката р.

Пусть А – замкнутая формула ранга r > 0. В зависимости от последней операции в А возможны 6 случаев.

А = А₁А₂. Используя определение конъюнкции, предположение индукции и правила умножения и разделения формул, получим:

А  и А₁ = и, А₂ = и Т├─ А₁ ,Т├─ А₂ Т├─ А₁А₂.

А = А₁  А₂. Если А₁  А₂ и, то А₁ = и или А₂ = и. Тогда по предположению индукции Т├─ А₁ или Т├─ А₂, а поэтому и Т├─ А₁  А₂. Обратно, пусть Т├─ А₁  А₂. Если Т├─ А₁ или Т├─ А₂, то по предположению индукции А₁  и или А₂  и, а потому и А  и. В противном случае в силу полноты системы Т имеем:

Т├─ А₁ ,Т├─ А₂

Тогда по правилам умножения формул и де Моргана получим:

_____

Т├─ А₁А₂, Т├─ А₁  А₂

Итак, имеем: _____

Т├─ А₁  А₂, Т├─ А₁  А₂

что невозможно в силу непротиворечивости Т.

А = А₁. Учитывая предположение индукции и полноту системы формул Т, получим:

А  и А₁  л Т├─ А₁ Т├─ А.

А = А₁->А₂. В этом случае, используя предположение индукции и правила введения посылки, контрапозиции и двойного отрицания, получим:

А  и А₁  л или А₂  и Т├─ А₁ ,

или Т├─ А₂ Т├─ А₂ -> А₁ или Т├─ А₂ -> А₁ Т├─ А.

А=х А₁(х). Если А  и, то А₁(t)и при любом tM. Тогда по предположению индукции Т├─ А₁(t) для всех tM. Допустим, что

______ ___

T ├─ х А₁(х). Тогда по правилу -отрицания T ├─ х А₁(х) и по

____

построению множества Т в Т существует формула А₁(b) при некоторой константе bM. В итоге мы получили:

Т├─ А₁(t) при любом tM и Т├─ А₁(b) при bM,

что невозможно в силу непротиворечивости Т. Следовательно, T ├─ х А₁(х).

Обратно, пусть T ├─ х А₁(х). Если х А₁(х)и, то А₁(t)л при некотором tM. Тогда по предположению индукции ___

Т├─ А₁(t).

Отсюда по аксиоме V₂ и по правилу -отрицания получим

____ _______

T ├─ х А₁(х) и T ├─ х А₁(х),

что невозможно в силу непротиворечивости Т.

А = х А₁(х). Если А  и, то А₁(t)и при некотором tM и по предположению индукции Т├─ А₁(t). Отсюда, используя аксиому V₂, получим T ├─ х А₁(х), т. е. Т├─ А.

Обратно, если Т├─ А, то в силу непротиворечивости Т имеем Т├┼ А. Тогда по построению Т в Т содержится формула А₁(b) при некотором bM. По предположению индукции А₁(b)и, а потому и х А₁(х)=и.

Таким образом, все замкнутые формулы языка α, выводимые из Т, истинны в интерпретации (М, ). А так как ST, то и все формулы из S истинны в (М, ), т. е. множество S выполнимо и теорема доказана.

Теперь можно доказать и теорему Гёделя о полноте исчисления α.

Пусть А – формула исчисления предикатов α и А  и в любой интерпретации исчисления α. Если х₁, …, х_n суть все переменные, имеющие свободные вождения в А, то формула В = х₁, …, х_nА также истинна в любой интерпретации α, а потому формула В ложна в любой интерпретации α. Отсюда следует, что множество формул {B} невыполнимо.

Тогда по теореме о выполнимости множество {B} противоречиво, т. е. существует формула С языка α, такая, что

B ├─ CC.

Но тогда по следствию из теоремы дедукции ├─B. Теперь, применяя n раз аксиому V₁ и правило заключения, получим ├─A, что и доказывает теорему Гёделя.

В качестве других следствий теоремы о выполнимости докажем так называемую теорему о совместной выполнимости и локальную теорему Мальцева.

Теорема (о совместной выполнимости). Если замкнутая формула А исчисления α истинна в любой интерпретации α, в которой истинны формулы некоторого Т замкнутых формул, то Т├─ А.

Доказательство. Из условия видно, что множество формул Т’ = Т U{A} невыполнимо. Значит, по теореме о выполнимости множество T’ противоречиво, т. е. T, A├─ BB для некоторой формулы В. Отсюда по следствию из теоремы дедукции Т├─ А.

Теорема Мальцева. Множество замкнутых формул S исчисления α выполнимо тогда и только тогда, когда выполнимо любое его конечное подмножество.

Доказательство. Выполнимость конечных подмножеств выполнимого множества формул очевидна. Докажем обратное утверждение. Допустим, что выполнимо любое конечное подмножество формул множества S, а само S невыполнимо. Тогда по теореме о выполнимости оно противоречиво, т. е. найдется такая формула А, что S├─ AA.

Но тогда AA выводима лишь из конечного подмножества S₁ S формул, участвующих в выводе формулы AA из S. Следовательно, нашлось противоречивое конечное множество формул из S. Если бы S было выполнимым, то по теореме 9.7.4 нашлась бы интерпретация α, в которой была бы истинной формула AA, что невозможно. Полученное противоречие и доказывает теорему.

Blog

Лекция №8

Содержание