Крючкова Е.Н. Основы математической логики и теории алгоритмов

Подождите немного. Документ загружается.

переводе на русский язык означает ”способ спуска”, т.к. правило вывода MP позво-

ляет последовательно спускаться по операции импликации к правой части формулы.

Пример. Следующая последовательность из пяти формул является выводом

формулы A → A:

1) A → ((A → A) → A) (аксиома A1 при β = A → A),

2) (A → ((A → A) → A)) → ((A → (A → A)) → (A → A)),

(аксиома A2 при β = A → A), γ = A,

3) ((A → (A → A)) → (A → A)) следует из 1 и 2 по MP,

4) A → (A → A) (аксиома A1 при β = A),

5) A → A следует из 3 и 4 по MP.

Фактичести мы доказали теорему об общезначимости формулы A → A или, что

то же самое, о выводимости в исчислении высказываний этой формулы. Приведем

краткую формулировку этой теоремы.

Теорема 1.1. ⊢ A → A.

1.2.5 Теорема о дедукции исчисления высказываний

В математике часто требуется выполнить доказательство утверждений типа ”из α

следует β”, где α и β — некоторые утверждения. Обычно такое доказательство прово-

дим по следующей схеме. Предполагаем, что α справедливо. Посредством некоторой

цепочки рассуждений устанавливаем, что и β справедливо. Тогда заключаем, что

из α следует β. В рассуждениях может участвовать ряд дополнительных предпо-

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

которая назывется теоремой о дедукции для исчисления высказываний.

Теорема 1.2 ( о дедукции). Пусть Γ — некоторый список формул и α — одна

формула. Тогда если Γ, α ⊢ β, то Γ ⊢ α → β.

Доказательство. Сначала сформулируем теорему подробнее следующим обра-

зом: если формула β выводима из списка гипотез Γ, дополненного формулой α, то

формула α → β выводима из списка гипотез Γ.

Теперь рассмотрим имеющийся по условию теоремы вывод β из Γ, α. Пусть это

вывод формул

, β

, ..., β

Индукцией по i покажем, что формула α → β

выводима из списка гипотез Γ.

Рассмотрим всевозможные варианты вывода очередной формулы β

. В соответствием

определением выводимости существует всего четыре варианта вывода β

а) β

— аксиома,

б) β

— гипотеза из Γ,

в) β

— гипотеза α,

г) β

— непосредственное следствие из некоторых β

и β

по правилу MP.

Заметим, что для первого шага вывода при i = 1 возможны только первые три ва-

рианта из вышеперечисленных. Рассмотрим общий случай — перечисленные четыре

варианта.

а) Если β

— аксиома, то продолжим вывод:

( аксиома),

→ (α → β

) ( аксиома A1),

α → β

( правило МР).

При любом i в выводе не участвует формула α , таким образом, в соответствии с

определением выводимости можем считать, что доказан вывод Γ ⊢ α → β

б) Если β

— гипотеза из Γ, то вывод строится точно также, за тем исключением,

что основанием для первого шага является принадлежность β

множеству Γ.

в) Если β

— гипотеза α, то вывод α → α мы выполнили при доказательстве

теоремы 1.1. Таким образом, доказали ⊢ α → β

и, следовательно, в соответствии с

определением выводимости Γ ⊢ α → β

г) Если β

— непосредственное следствие из некоторых β

и β

по правилу MP:

= β

→ β

Воспользуемся индукцией: значения m и k меньше значения i, следовательно, в со-

ответствии с индуктивным предположением из Γ выводимы формулы α → β

α → β

. Фактически, в силу равенства β

= β

→ β

, которое существует по причине

применимости правила MP в выводе, выводима формула α → (β

→ β

). Продолжим

этот вывод:

α → β

, ( по индукции),

α → (β

→ β

) ( по индукции),

(α → (β

→ β

)) → ((α → β

) → (α → β

)) ( аксиома A2),

(α → β

) → (α → β

) ( правило МР),

α → β

( правило МР).

Следовательно, и в этом четвертом случае существует вывод Γ ⊢ α → β.

Таким образом, рассмотрев всевозможные варианты вывода, мы установили, что

для любого i для всех вариантов вывода β

из Γ и α мы указали способ продолжения

вывода для того, чтобы получить Γ ⊢ α → β

. Таким образом, из Γ выводима и

формула α → β

, совпадающая с α → β. 

Теорема 1.3. α → β, β → γ ⊢ α → γ.

Доказательство. В соответствии с формулировкой торемы у нас есть две ги-

потезы α → β и β → γ. Пусть эти две гипотезы составляют множество гипотез Γ.

Рассмотрим вспомогательную гипотезу α и рассмотрим вывод:

1) α → β, ( гипотеза),

2) β → γ, ( гипотеза),

3) α, ( гипотеза),

4) β, ( правило MP из 1 и 3),

5) γ, ( правило MP из 2 и 4),

Таким образом, доказали

α → β, β → γ, α ⊢ γ.

В соответствии с теоремой о дедукции α → β, β → γ ⊢ α → γ. 

Полученное при доказательстве теоремы 1.3 правило выводимости можно запи-

сать как

α → β, β → γ

α → γ

Это правило называется правилом силлогизма или правилом S. В качестве упраж-

нения для самостоятельной работы Вам предлагается доказать следующие правила:

1) доказательство от противного (modus tollens)

α → β, ¬β

¬α

2) правило перестановки посылок

α → (β → γ)

β → (α → γ)

3) правило соединения посылок

α → (β → γ)

α&β → γ

4) правило разъединения посылок

α&β → γ

α → (β → γ)

5) правило исключения промежуточной посылки

α → (β → γ), β

α → γ

6) правила конъюнкции

α, β

α&β

α, β

7) простая конструктивная дилемма

α → γ, β → γ, α ∨ β

8) сложная конструктивная дилемма

α → γ, β → δ, α ∨ β

γ ∨ δ

9) простая деструктивная дилемма

α → β, α → γ, ¬β ∨ ¬γ

¬α

10) сложная деструктивная дилемма

α → β, δ → γ, ¬β ∨ ¬γ

¬α ∨ ¬β

11) правила двойного отрицания

¬¬α

Силлогизмом называется схема такая рассуждений, в которой заключение всегда

верно. Впервые силлогизмы исследовались еще Аристотелем. Все вышеприведенные

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

гизмов позволяет строить заключение.

1.3 Исчисление предикатов

1.3.1 Определение формальной теории исчисления предика-

тов

Перейдем к рассмотрению другой математической теории — исчисления преди-

катов, которое является развитием исчисления высказываний.

Каждое высказывание (или каждая формула исчисления высказываний ) имеет

значение ”истина” или ”ложь”. Исчисление высказываний оперирует с отдельными

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

на естественном языке, каждому из которых можно приписать одно из двух семан-

тических значений: ”истина” или ”ложь”. В естественном языке встречаются более

сложные повествовательные предложения, истинность которых может меняться при

изменении объектов и при неизменной структуре самого предложения. Например,

фраза ”студент x отлично учится” может иметь различные значения в зависимо-

сти от того, какое значение будет принимать переменная x. В математической логике

предложения, смысл которых меняется в зависимости от параметров, определяются

на формальном уровне с помощью предикатов.

Определение 1.3. Функция одной или нескольких переменных, которая прини-

мает логическое значение ”истина” или ”ложь”, называется предикатом. Переменные

предиката называются предметными переменными.

1.3.2 Алфавит и множество формул исчисления предикатов

Алфавит исчисления высказываний полностью входит в алфавит исчисления пре-

дикатов. Большие латинские буквы получают в исчислении предикатов новый смысл:

они могут обозначать как постоянные высказывания (например, A, B ), так и пере-

менные высказывания — предикаты (например, F(x), G(x, y) ). Кроме того, в алфа-

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

ний входят

— маленькие латинские буквы с возмжными индексами, называемые предметны-

ми переменными (например, y, x

, x

); они обозначают некоторые объекты, но, в

отличие от предметных констант, каждая из предметных переменных может обозна-

чать любой, совершенно произвольный объект;

— квантор всеобщности ∀;

— квантор существования ∃.

Операции ∀ и ∃ выражают собой утверждения всеобщности и существования со-

ответственно. Пусть R(x) — некоторый предикат, принимающий значение ”истина”

или ”ложь” для каждого элемента x в некоторой предметной области Ω. Тогда под

выражением

∀x R(x)

понимается: ”для каждого элемента x области Ω высказывание R(x) истинно”. А

под выражением

∃x R(x)

понимается: ”существует элемент x области Ω, для которого высказывание R(x)

истинно”.

Переменная x в этих выражениях называется связанной переменной. Иначе го-

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

Предметная переменная, не связанная никаким квантором, называется свободной пе-

ременной.

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

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

1.3.3 Множество аксиом исчисления предикатов

Определим теперь множество аксиом:

A1) α → (β → α),

A2) (α → (β → γ)) → ((α → β) → (α → γ)),

A3) (¬α → ¬β) → (β → α),

A4) ∀x α(x) → α(t)

A5) ∀x (α → β) → (α → ∀x β).

В аксиоме A4 переменная t должна быть свободной для предиката α. В аксиоме A5

предикат α не должен содержать предметной переменной x.

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

чтобы ввести в исчисление квантор существоания, свяжем его с квантором всеобщ-

ности определением:

∃x R(x) эквивалентно ¬(∀x ¬R(x)).

1.3.4 Правила вывода исчисления предикатов

В исчислении предикатов имеется два правила вывода: знакомое нам правило MP

α, α → β

и правило обобщения (Gen)

∀x α

Это правило позволяет навешивать квантор всеобщности по произвольной перемен-

ной. Если формула ∀x α включена в некоторый вывод на основании правила Gen, то

говорят, что в этом выводе использовано правило обобщения по переменной x.

1.3.5 Теорема о дедукции исчисления предикатов

Теорему о дедукции нельзя перенести на исчисление предикатов в том же виде,

в каком она была сформулирована для исчисления высказываний. Причина этого

кроется в наличии свободных и связанных переменных.

Теорема 1.4 ( о дедукции исчисления предикатов). Пусть Γ — некоторый

список формул и α — одна формула. Тогда если существует вывод Γ, α ⊢ β, в котором

правило обобщения Gen не применяется ни по какой из переменных, свободных в

формуле α, то существует вывод Γ ⊢ α → β, в котором правило Gen применяется по

тем же переменным, по которым оно применялось в исходном выводе Γ, α ⊢ β.

Доказательство. Пусть построен вывод формулы β из совкупности гипотез Γ, α:

, β

, ..., β

Так же, как и при доказательстве теоремы о дедукции для исчисления высказыва-

ний воспользуемся индукцией по i в выводе β из Γ, α. Дополнительно к вариантам,

рассмотренным при доказательcтве теоремы для исчисления высказываний, в исчис-

лении предикатов имеется еще только один вариант вывода: формула β

получена

в результате применения правила Gen к некоторой предшествующей формуле β

j < i. Тогда формула β

должна иметь вид ∀x β

и по условию теоремы переменная

x не должна входить в α свободно. По индуктивному предположению Γ ⊢ α → β

Рассмотрим вывод

∀x (α → β

) ( Gen),

∀x (α → β

) → (α → ∀x β

) ( аксиома A5),

α → ∀x β

( правило МР).

Так как β

= ∀x β

, то из Γ получили доказательство α → β

. 

Пример. Покажем α(t) → ∃x α(x):

1) α(t) (посылка),

2) ∀x ¬α(x) → ¬α(t), (аксиома А4)

3) (∀x ¬α(x) → ¬α(t)) → (α(t) → ¬∀x ¬α(x)), (аксиома А3) ,

4)α(t) → ¬∀x ¬α(x), ( MP 2,3)

5)¬∀x ¬α(x), (MP 4,1)

6)¬∀x ¬α(x) = ∃x α(x), (определение)

7)∃x α(x), (подстановка 6 в 5)

8)α(t) → ∃x α(x), (теорема о дедукции)..

Получили дополнительное правило вывода в исчислении предикатов

α(t)

∃x α(x)

1.3.6 Теоремы о полноте

Мы уже упоминали понятие общезначимости формул, понимая под ними такие

формулы, которые принимают значение ”истина” при всех значениях входящих в

эту формулу переменных высказываний. Любая математическая теория интересна

не только сама по себе, но и с точки зрения ее приложения в практических це-

лях. Формулы исчисления высказываний могут иметь некоторый смысл и обозначать

некоторые высказывания естественного языка, если существует какая–либо интер-

претация математической теории. Говоря неформально, интерпретировать мате-

матическую теорию — это значит связать с ней некоторую предметную область и

указать соответствие формальных объектов математической теории и объектов дан-

ной предметной области. Дадим определение интерпретации на формальном уровне.

Определение 1.4. Интерпретация I математической теории T задается следую-

щим образом:

1) указано некоторое множество D — предметная область интерпретации I; D ̸= ∅;

2) каждой предметной константе (если они есть) из T сопоставлен некоторый

элемент D;

3) каждой функциональной букве (если они есть) из T сопоставлена операция

над элементами D, которая совокупности объектов области D ставит в соответствие

один элемент этой же области; число аргументов функциональной буквы теории T

и число аргументов операции над элементами D должны совпадать;

4) каждой n–местной предикатной букве (если они есть) из T сопоставлено кон-

кретное отношение над n элементами области D;

5) каждой пропозициональной букве (если они есть) из T сопоставлено одно из

двух логических значений ”истина” или ”ложь”.

В этом определении ничего не говорится о том, что может быть сопоставлено

предметным переменным. Предполагается, что предметная переменная может обо-

значать любой элемент области D.

Определение 1.5. Формула называется общезначимой, если она истинна при

любой интерпретации.

Логическая формальная теория называется полной, если любая формула выво-

дима в этой теории тогда и только тогда, когда она общезначима. Полнота теории

гарантирует, что во–первых, теория содержит все необходимое для формального вы-

вода, а во–вторых, что ничего лишнего и неверного в этой теории вывести нельзя.

Если теория полна, достаточно просто перебирать все варианты выводов в этой тео-

рии и получать различные общезначимые формулы (теоремы). Однако, история ма-

тематики показывает, что существуют очень трудные теоремы, поиск доказательства

которых требует больших творческих усилий и временных затрат. Это наводит на

мысль, что полнота маьематических теорий — достаточно редкое свойство. Так оно

и есть на самом деле. Исчисление высказываний является одной из весьма редких

теорий, для которых выполняется свойство полноты.

Сначала отметим, что формулы исчисления высказываний можно интерпретиро-

вать как формулы алгебры высказываний. Для этого будем трактовать свободные

переменные исчисления высказываний как переменные алгебры высказываний, т.е.

переменные в содержательном смысле, принимающие значения true, f alse. Если ло-

гические операции определим так же, как в алгебре высказываний, то всякая форму-

ла при любых значениях перемнных сама будет принимать некоторое значение true

или f alse, вычисленное по правилам алгебры высказываний.

Пусть α — некоторая формула исчисления высказываний, I — интерпретация, в

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

α, и, следовательно, определено значение V (α) этой формулы. Обозначим через ˜α

формулу, совпадающую с формулой α, если V (α) = true, и имеющую изображение

¬α, если V (α) = false. Таким образом, всегда V (˜α) = true.

Аналогичный смысл имеют обозначения

,...,

для формул β

, β

,...,β

—

любых подформул формулы α.

Теорема 1.5. Во введенных обозначениях для произвольной интерпретации I

имеет место

, ...,

⊢ ˜α.

Доказательство. Проведем доказательство по индукции по n — числу логиче-

ских связок в формуле α.

Если n = 0, то формула α не содержит логических связок, т.е. является элемен-

тарной формулой и состоит из одной пропозициональной буквы B

. Тогда значение

α совпадает со значением B

, поэтому ˜α совпадает со значением

β, следовательно,

вывод формулы ˜α из

,...,

состоит только из одного шага — гипотезы

β.

Допустим теперь, что для любого n ≥ 0 для всех формул, содержащих не более n

связок, утверждение теоремы справедливо. Докажем, что это утверждение справед-

ливо и для n+1. В соответствии с определением формулы исчисления высказываний

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

держит не более n логических связок, с помощью логической связки отрицания, им-

пликации, конъюнкции или дизъюнкции. Для доказательства надо рассмотреть все

четыре варианта образования формулы α с помощью четырех логических связок.

Пусть, например, α = ¬β. По индуктивному предположению

, ...,

⊢

β.

Если V (β) = true, то

β = β и указанный вывод

β превращается в

, ...,

⊢ β.

При этом V (α) = V (¬β) = false и, следовательно,

˜α = ¬α = ¬¬β.

Мы ранее доказали для любого высказывания γ справедливость вывода (см. правила

двойного отрицания)

⊢ γ → ¬¬γ,

поэтому к выводу

, ...,

⊢ β можно приписать вывод формулы ⊢ β → ¬¬β,

получив тем самым вывод ⊢ α.

Если же V (β) = false, то

β = ¬β, V (α) = V (¬β) = true, ˜α = α = ¬β, и, таким

образом, вывод

, ...,

⊢

β одновременно является и выводом ˜α.

Доказательство для остальных случаев оставляется читателю в качестве упраж-

нения. 

Теорема 1.6 ( о полноте исчисления высказываний). Формула α выводима

в исчислении высказываний тогда и только тогда, когда она общезначима.

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

1. Пусть формула исчисления высказываний α общезначима и B

, B

, ..., B

—

список всех входящих в нее букв. Возможны 2

различных интерпретаций, которые

ставят в соответствие этим буквам различные комбинации значений. На каждой из

этих интерпретаций α имеет значение V (α), истинное в силу общезначимости α. По-

скольку формула α истинна в любой из этих 2

интерпретаций, ˜α совпадает с α и из

теоремы 1.5

, ...,

⊢ α.

Будем последовательно сокращать список гипотез, применяя следующий прием. Сгруп-

пируем интерпретации попарно так, чтобы в каждой паре они отличались только

противоположным значением пропозициональной буквы B

. Тогда утверждения о

выводимости в каждой паре интерпретаций имеют вид:

, ...,

k−1

, B

⊢ α,

, ...,

k−1

, ¬B

⊢ α.

По теореме о дедукции перепишем эти утверждения в виде

, ...,

k−1

⊢ B

→ α,

, ...,

k−1

⊢ ¬B

→ α.

По правилу простой конструктивной дилеммы (см. стр. 13) имеем

, ...,

k−1

⊢ α.

Повторяя этот прием, получим

⊢ α.

2. Пусть формула α выводима в исчислении высказываний. Покажем, что она

общезначима. Рассмотрим вывод α:

, β

, ..., β

= α

Покажем по индукции, что все β

общезначимы. Если β

— аксиома, то она общезна-

чима. Если β

получена по правилу из общезначимых формул, она общезначима.

Отсюда и общезначима α. 

Логическое исчисление называется непротиворечивым, если в нем нельзя одно-

временно вывести формулу ¬α и формулу α.

Следствие. Исчисление высказываний непротиворечиво.

Доказательство. Пусть в исчислении высказываний имеется такая формула α,

что ⊢ α и ⊢ ¬α. Тогда по теореме о полноте формулы α и ¬α являются общезначи-

мыми, что невозможно. 

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

исчислении высказываний. Поэтому говорят о полноте в широком и в узком смысле.

Логическая система полна в широком смысле, если всякая тождественно истинная

формула выводима в этой системе. Логическая система называется полной в узком

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

аксиомы никакую не выводимую в ней формулу так, чтобы полученная при этом

система была непротиворечива. В отличие от исчисления высказываний для исчис-

ления предикатов существует недоказуемая там формула, которую без противоречия

можно присоединить к системе аксиом:

∃x(F (x)) → ∀x(F (x)).

Поэтому для исчисления предикатов теорема о полноте выглядит иначе.

Теорема 1.6. (Теорема о полноте исчисления предикатов, теорема Геде-

ля) Всякая тождественно истинная формула α выводима в исчислении предикатов.

Доказательство Вы можете найти в [37]. Таким образом, исчисление высказыва-

ний полно как в широком, так и в узком смысле, а исчисление предикатов полно

только в широком смысле.

1.3.7 Логическое следствие

Неполнота исчисления предикатов заставляет искать способ получения следствий

в этой теории, который можно было бы применить на практике.

Определение 1.6. Формула β называется логическим следствием формулы α

(или β логически следует из α) тогда и только тогда, когда для всякой интерпрета-

ции, на которой формула α истинна, β тоже истинна.

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

следствием формулы α, то можно построить таблицу истинности:

α β β является логическим следствием α

ложь ложь истина (если α ложь, то значение β может быть любым)

ложь истина истина

истина ложь ложь

истина истина истина

Полученная таблица совпадает с таблицей истинности логической операции ”→”,

поэтому если формула β называется логическим следствием формулы α , то можно

записать α → β = true .

Очевидно, что любая формула является логическим следствием самой себя, при-

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

является тавтология — тождественно истинная формула (или частный случай такой

формулы — константа true). С другой стороны, из ложных фактов можно вывести

любое утверждение.

На основании определения можно также сделать вывод, что логическим следстви-

ем формулы α является false тогда и только тогда, когда формула невыполнима.

При этом, если формула α невыполнима, то кроме false из нее можно получить

любые следствия.

Рассмотрим определение логического следствия не из одной формулы, а из мно-

жества формул. Естественно считать, что на истинность следствия должна оказы-

вать влияние истинность всех исходных формул одновременно. Поэтому имеет смысл

в качестве оценки истинности рассмотреть конъюнкцию посылок.

Определение 1.7. Формула β называется логическим следствием формул α

,..., α

(или β логически следует из α

, α

,..., α

) тогда и только тогда, когда для

всякой интерпретации, на которой формула α

&α

&...&α

истинна, β тоже истинна.

Понятие логического следствия лежит в основе машинных алгоритмов постро-

ения выводов. Одним из способов получения выводов является метод резолюций.

Предложенный в 1965 году Дж. Робинсоном этот метод позволяет получить макси-

мально сильное следствие множества формул с помощью систематической процеду-

ры последовательного построения логических следствий. Метод использует тот факт,

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

этой формулы — константа false.

Теорема 1.7. Пусть β — логическое следствие формулы α. Тогда α&β = α.

Доказательство. Пусть условие теоремы выполнено, тогда

α → β = true,

следовательно

α = α&true = α&(α → β) = α&(¬α ∨ β) = α&¬α ∨ α&β =

= false ∨ α &β = α&β



Определение 1.8. Резольвентой двух дизъюнктов D

∨L и D

∨¬L называется

дизъюнкт D

∨ D

Теорема 1.8. Резольвента является логическим следствием порождающих ее

дизъюнктов.

Доказательство. Пусть даны два дизъюнктов D

∨L и D

∨¬L. В соответствии

с определением логического следствия из множества формул рассмотрим форму-

лу (D

∨ L)&(D

∨ ¬L), логическое следствие из которой нам нужно рассмотреть.

По определению D

∨ D

является логическим следствием дизъюнктов, если при

истинности (D

∨ L)&(D

∨ ¬L) формула D

∨ D

истинна. Проверим этот факт,

воспользовавшись проверкой общезначимости выражения при любой интерпретации

((D

∨ L)&(D

∨ ¬L)) → (D

∨ D

) =

= (D

∨ D

(¬L) ∨ D

&L ∨ L&(¬L) → (D

∨ D

) =

= (D

∨ D

(¬L) ∨ D

&L) → (D

∨ D

) =

= ¬(D

∨ D

(¬L) ∨ D

&L) ∨ (D

∨ D