Голованов М.И. Нестандартные логики. Реляционная семантика

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

1. p → (q ∨ r) ` p → ((p → q) ∨ (p → r)) доказано в Lp,

2. (p → q) → ((p → q) ∨ (p → r)) аксиома A6,

3. (p → ((p → q) ∨ (p → r))) →

(((p → q) → ((p → q) ∨ (p → r))) →

((p ∨ (p → q)) → ((p → q) ∨ (p → r)))) аксиома A8,

4. p → (q ∨ r) ` ((p → q) → ((p → q) ∨ (p → r))) →

((p ∨ (p → q)) → ((p → q) ∨ (p → r))) из 1, 3 по m.p.,

5. p → (q ∨ r) ` (p ∨ (p → q)) → ((p → q) ∨ (p → r)) из 2, 4 по m.p.,

6. p ∨ (p → q) аксиома E,

7. p → (q ∨ r) ` (p → q) ∨ (p → r) из 5, 6 по m.p..

Лемма доказана.¥

Теорема 5.2. Логики Lp + P и Lp + E совпадают, т.е. в Lp ((p → q) → p) → p ≡

p ∨ (p → q).

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

Покажем предварительно, что в логике Lp + P справедлива эквивалентность:

(p → q) → p ≡ p. Секвенция p ` (p → q) → p очевидным образом следует из аксиомы

A1. Последовательность формул (p → q) → p, ((p → q) → p) → p, p является выводом

в логике Lp + P формулы p из гипотезы (p → q) → p.

Используя полученную эквивалентность покажем, что `

Lp+P

1. p → p ∨ (p → q) аксиома A6

2. ((p ∨ (p → q)) → q) → (p → q) по правилу контр.позиц. из 1,

3. ((p → q) → (p ∨ (p → q))) → (((p ∨ (p → q)) → q) → (p ∨ (p → q)))

по правилу контр.позиц. из 2,

4. ((p → q) → (p ∨ (p → q))) A7

5 (((p ∨ (p → q)) → q) → (p ∨ (p → q))) m.p.3,4

6 p ∨ (p → q) эквивалентно 5 в Lp + P

Для доказательства `

Lp+E

P воспользуемся эквивалентностью (p → q) → r ≡

r ∨p∧(q → r), доказанной в Lp +E: (p → q) → p ≡ p∨ p∧ (q → p) ≡ p, следовательно,

((p → q) → p) → p ≡ p → p. Теорема доказана. ¥

Теорема 5.3. Любая формула в языке логики Lp эквивалентна в логике Lp

неко-

торой формуле вида D

∧ · · · ∧ D

, где формулы D

являются дизъюнкциями пропо-

зициональных переменных и формул вида p → q, p и q также пропозициональные

переменные.

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

1. p → (q ∧ r) ≡ (p → q) ∧ (p → r).

2. p → (q ∨ r) ≡ (p → q) ∨ (p → r),

3. p → (q → r) ≡ (p ∧ q) → r.

4. ((p ∧ q) → r) ≡ ((p → r) ∨ (q → r)),

5. ((p ∨ q) → r) ≡ ((p → r) ∧ (q → r)),

6. (p → q) → r ≡ r ∨ p ∧ (q → r),

7. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r),

8. p ∨ q ≡ q ∨ p

Доказательство проведём индукцией по длине формулы. Для удобства форму-

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

нормального вида.

I. Для формул, совпадающих с пропозициональными переменными утверждение

очевидно.

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

Рассмотрим возможные варианты построения формулы α из более коротких формул.

1) Если α = α

∧ α

и формулы α

, α

имеют нормальный вид, то α также имеет

нормальный вид.

2) Если α = α

∨α

и формулы α

, α

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

валентности 7 и 8 из приведённого списка, через конечное число шагов мы приведём

их к нормальному виду.

3) Пусть α = α

→ α

и формулы α

, α

имеют нормальный вид.

а) Если α

= γ ∧ δ, то в силу эквивалентности 1 α ≡ (α

→ γ) ∧ (α

→ δ).

Поскольку формулы α

→ γ и α

→ δ являются более короткими чем α, то в силу

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

виду. В соответствии с п. 1) α также имеет нормальный вид.

б) Пусть α

= γ ∨ δ. Тогда в соответствии с эквивалентностью 2 из приведённого

списка α ≡ (α

→ γ)∨(α

→ δ). Если формулы α

, γ, δ являются пропозициональны-

ми переменными, то полученная формула уже имеет нормальный вид. Если же это

не так, то, приведя формулы α

→ γ и α

→ δ к нормальному виду, на следующем

шаге в соответствии с п. 2) мы сможем привести и всю формулу к нормальному виду.

в) Если α

= γ ∧ δ, то по эквивалентности 4 α ≡ (γ → α

) ∨ (δ → α

). Формулы

γ → α

и δ → α

более короткие чем α. Приведя их к нормальному виду, затем по п.

2) приведём к нормальному виду и всю формулу α.

г) Если α

= γ → δ, то согласно эквивалентности 3 α ≡ (α

∧γ) → δ и всё сводится

к предыдущему пункту в).

д) Если α

= γ∨δ, то по эквивалентности 5 α ≡ (γ → α

)∧(δ → α

). Приведя более

короткие формулы γ → α

и δ → α

) к нормальному виду, получим нормальный вид

всей формулы.

е) Пусть α

= γ → δ. Тогда по эквивалентности 6 α ≡ α

∨γ ∧(δ → α

). Поскольку

формулы α

, γ, δ → α

короче, чем α, то можно считать, что они уже приведены к

нормальному виду. Следовательно, формула γ ∧ (δ → α

) также имеет нормальный

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

виду.

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

Теорема 5.4. Логика Lk

совпадает с множеством тождественно истинных фор-

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

переменных с использованием только связок ∧, ∨, →.

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

тождествен-

но истинны и правило modus ponens сохраняет тождественную истинность формул.

Следовательно все доказуемые формулы Lk

тождественно истинны.

Обратно, пусть формула α тождественно истинна и β ≡ α, формула β имеет

нормальный вид. Так как утверждение β ≡ α эквивалентно утверждению ` (β →

α) ∧ (α → β), то формула β также тождественно истинна. Пусть β = D

∧ · · · ∧ D

Так как β тождественно истинна, то каждая подформула D

также тождественно

истинна. По определению D

является дизъюнкцией пропозициональных переменных

и формул вида p → q, где p и q также пропозициональные переменные. Выясним при

каких условиях формула D

тождественно истинна. Если D

содержит подформулу

вида p ∨ (p → q), p → p или (p → q) ∨ (q → r), то D

тождественно истинна.

Пусть в D

нет подформул вида p ∨ (p → q), p → p, (p → q) ∨ (q → r). То есть

= p

∨· · ·∨p

∨(q

→ r

)∨· · ·∨(q

→ r

), где множество переменных удовлетворяет

условиям: {p

, . . . , p

}∩{q

, . . . , q

} = ∅, {q

, . . . , q

}∩{r

, . . . , r

} = ∅. Положим p

· · · = p

= 0, q

= · · · = q

= 1, r

= · · · = r

= 0. В этом случае значение истинности

формулы D

равно 0, следовательно и значение β равно 0. Мы доказали, что формула

β тождественно истинна тогда и только тогда, когда каждый конъюнктивный член

содержит подформулу одного из видов p ∨ (p → q), p → p или (p → q) ∨ (q → r).

Формулы p ∨ (p → q) и p → p доказуемы в Lk

. Покажем, что формула (p →

q) ∨ (q → r) также доказуема в Lk

1. q → (p → q) аксиома A1,

2. (p → q) → ((p → q) ∨ (q → r)) аксиома A6,

3. q → ((p → q) ∨ (q → r)) по правилу сечения из 1, 2,

4. (q → r ) → ((p → q) ∨ (q → r)) аксиома A7,

5. (q → ((p → q) ∨ (q → r))) → (((q → r) → ((p → q) ∨ (q → r))) →

((q ∨ (q → r)) → ((p → q) ∨ (q → r))))

аксиома A8,

6. ((q → r ) → ((p → q) ∨ (q → r))) → ((q ∨ (q → r)) → ((p → q) ∨ (q → r)))

по m.p. из 3, 5,

7. (q ∨ (q → r)) → ((p → q) ∨ (q → r)) по m.p. из 4, 6,

8. q ∨ (q → r) аксиома E,

9. (p → q) ∨ (q → r) по m.p. из 7, 8,

Отметим следующий факт: если формула θ доказуема, то формула θ ∨ δ, где

δ произвольная формула, также доказуема. Это утверждение следует из аксиомы

A6: θ → (θ ∨ δ) и доказуемости θ. Таким образом каждый конъюнктивный член D

формулы β доказуем. В соответствии с правилом объединения посылок формула β

также доказуема. Поскольку α ≡ β, то α также доказуема. Теорема доказана. ¥

Вопросы и задания.

1. Докажите правило контрапозиции.

2. Какие аксиомы необходимы для доказательства правила контрапозиции?

3. В каких рассмотренных логиках справедливо утверждение: если p ` q, то q → r `

p → r?

4. Сколько неэквивалентных формул от n переменных можно построить в Lp

5. Будет ли число неэквивалентных формул от одной переменной различным в ло-

гиках Lp

и Lp

6 Лекция 6. Модальные логики, нормальные модаль-

ные логики.

6.1 Наименьшая нормальная модальная логика

Для задания алфавита модальной логики K достаточно к алфавиту классической

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

"необходимо". Однако во многих отношениях дополнительные удобства даёт исполь-

зование связки 3 - "возможно", которую мы будем рассматривать как обозначение

последовательности ¬2¬, т.е. записи 3α и ¬2¬α обозначают одно и то же.

Понятие формулы логики K определяется стандартным образом: 1) пропозицио-

нальная переменная является формулой, 2) если α и β – формулы, то (α ∧β), (α∨β),

(α → β), ¬α, 2α – формулы. Однако мы немного отступим от строгости, задава-

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

будем называть формулой. Мы не вводим символ 3 в основной алфавит логики K

с единственной целью - чтобы не усложнять аксиоматику логики дополнительными

аксиомами. Определённое таким образом множество формул будем обозначать F or

Аксиомы и правила вывода логики K получаются добавлением одной схемы ак-

сиомы и одного правила вывода к классическому исчислению высказываний.

Схемы аксиом

A1. (X → (Y → X))

A2. ((X → (Y → Z)) → ((X → Y ) → (X → Z)))

A3. ((X ∧ Y ) → X)

A4. ((X ∧ Y ) → Y )

A5. ((X → Y ) → ((X → Z) → (X → (Y ∧ Z))))

A6. (X → (X ∨ Y ))

A7. (Y → (X ∨ Y ))

A8. ((X → Z) → ((Y → Z) → ((X ∨ Y ) → Z)))

A9. (X → Y ) → ((X → ¬Y ) → ¬X)

A10. ¬¬X → X,

K. 2(X → Y ) → (2X → 2Y ).

Логика K имеет два правила вывода: modus ponens и правило

2α

, которое мы

будем называть правилом Гёделя.

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

добавив использование правила Гёделя в соответствующие определения для логики

Lp. Отметим, что все доказательства и выводы, построенные в классической логике

высказываний, остаются доказательствами и выводами в логике K. Обратное однако

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

и формулировка теоремы дедукции. Теорема дедукции немодальных логик является

частным случаем теоремы дедукции модальных логик.

Поскольку при доказательстве теоремы дедукции для логики Lp мы использо-

вали только схемы аксиом A1 и A2, и правило modus ponens, которые входят и в

определение логики K, то в K справедлива

Теорема 6.1. Если существует вывод формулы ψ из гипотез ϕ

, . . . , ϕ

, в котором

используется только правило modus ponens, то существует вывод формулы ϕ

→ ψ

из гипотез ϕ

, . . . , ϕ

n−1

, который также использует только правило modus ponens.

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

правило modus ponens, то правило сечения доказуемо и в логике K.

Формулы α и β будем называть формально эквивалентными, если в K доказуемы

формулы α → β и β → α. Как и ранее, запись α ≡ β означает, что формула α

формально эквивалентна формуле β.

Лемма 6.2. Отношение эквивалентности обладает следующими свойствами

1) α ≡ α,

2) если α ≡ β, то β ≡ α,

3) если α ≡ β и β ≡ γ, то α ≡ γ,

4)если α ≡ β, то а) ¬α ≡ ¬β, б) 2α ≡ 2β,

5) если α

≡ β

и α

≡ β

, то а) α

∧ α

≡ β

∧ β

, б) α

∨ α

≡ β

∨ β

, в)

→ α

≡ β

→ β

6) если α

≡ β

, . . . , α

≡ β

, то для произвольной формулы γ(p

, . . . , p

) γ(α

, . . . , α

) ≡

γ(β

, . . . , β

Свойства 1) и 2) вытекают непосредственно из определения эквивалентности фор-

мул. Докажем свойство 3). В силу определения α ≡ β и β ≡ γ означают, что

α → β ∈ K и β → γ ∈ K. По правилу сечения имеем α → γ ∈ K. Аналогично

получаем вторую импликацию γ → α ∈ K. Таким образом α ≡ γ. Докажем свой-

ство 4). Эквивалентность α ≡ β означает доказуемость в K двух формул α → β и

β → α. Применяя к обеим формулам правило контрапозиции, получаем доказуемые

формулы ¬β → ¬α и ¬α → ¬β, соответственно. То есть ¬α ≡ ¬β. Приведём квази-

доказательство формулы 2α → 2β.

1. α → β доказуемая в K формула,

2. 2(α → β) из 1 по правилу Гёделя,

3. 2(α → β) → (2α → 2β) аксиома логики K,

4. 2α → 2β из 2, 3 по правилу m.p.

Вторая импликация 2β → 2α доказывается симметричным образом. Докажем пункт

5). В силу определения эквивалентности в K доказуемы импликации α

→ β

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

1. α

∧ α

→ α

аксиома A3,

2. α

→ β

доказуемая в K формула,

3. α

∧ α

→ β

по правилу сечения из 1, 2,

4. α

∧ α

→ α

аксиома A4,

5. α

→ β

доказуемая в K формула,

6. α

∧ α

→ β

по правилу сечения из 4, 5,

7. (α

∧ α

→ β

) → ((α

∧ α

→ β

) → (α

∧ α

→ β

∧ β

))

аксиома A5,

8. (α

∧ α

→ β

) → (α

∧ α

→ β

∧ β

)

из 3, 7 по правилу m.p.,

9. α

∧ α

→ β

∧ β

из 6, 8 по правилу m.p..

Обратная импликация доказывается симметричным образом. Далее теми же до-

казуемыми по условию формулами α

→ β

и α

→ β

воспользуемся для доказа-

тельства соответствующей эквивалентности для дизъюнкции.

1. α

→ β

доказуемая в K формула,

2. β

→ β

∨ β

аксиома A6,

3. α

→ β

∨ β

по правилу сечения из 1, 2,

4. α

→ β

доказуемая в K формула,

5. β

→ β

∨ β

аксиома A7,

6. α

→ β

∨ β

по правилу сечения из 4, 5,

7. (α

→ β

∨ β

) → ((α

→ β

∨ β

) → (α

∨ α

→ β

∨ β

))

аксиома A8,

8. (α

→ β

∨ β

) → (α

∨ α

→ β

∨ β

)

из 3, 7 по правилу m.p.,

9. α

∨ α

→ β

∨ β

из 6, 8 по правилу m.p..

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

Докажем свойство 5в).

1. β

→ α

по условию доказуема в K,

2. α

→ α

гипотеза,

3. β

→ α

по правилу сечения из 1, 2,

4. α

→ β

по условию доказуема в K,

5. β

→ β

по правилу сечения из 3, 4,

Так как в данном выводе правило Гёделя не использовалось, то можно применить

теорему дедукции. В результате имеем ` (α

→ α

) → (β

→ β

). Вторая импликация

` (β

→ β

) → (α

→ α

) доказывается аналогично.

Свойство 6) доказывается индукцией по длине формулы с использованием преды-

дущих свойств теоремы.

Для доказательства теоремы о замене эквивалентных в логике K достаточно до-

казать утверждение: если ` α → β, то ` 2α → 2β, которое является очевидным

следствием аксиомы K.

Теорема 6.3. 1) 2(p ∧ q) ≡ 2p ∧ 2q,

2) 3(p ∨ q) ≡ 3p ∨ 3q.

1. p ∧ q → p аксиома A3,

2. 2(p ∧ q → p) из 1 по правилу Гёделя,

3. 2(p ∧ q → p) → (2(p ∧ q) → 2p) аксиома K,

4. 2(p ∧ q) → 2p из 2, 3 по m.p.,

5. p ∧ q → q аксиома A4,

6. 2(p ∧ q → q) из 5 по правилу Гёделя,

7. 2(p ∧ q → q) → (2(p ∧ q) → 2q) аксиома K,

8. 2(p ∧ q) → 2q из 6, 7 по m.p.,

9. (2(p ∧ q) → 2p) → ((2(p ∧ q) → 2q) → (2(p ∧ q) → 2p ∧ 2q))

аксиома A5,

10. (2(p ∧ q) → 2q) → (2(p ∧ q) → 2p ∧ 2q)

из 4, 9 по m.p.,

11. 2(p ∧ q) → 2p ∧ 2q из 8, 10 по m.p.,

Отметим, что по правилу объединения посылок p, q ` p ∧ q. Применяя теорему

дедукции, получаем ` p → (q → p ∧ q).

1. p → (q → p ∧ q) доказуемая в K формула,

2. 2(p → (q → p ∧ q)) из 1 по правилу Гёделя,

3. 2(p → (q → p ∧ q)) → (2p → 2(q → p ∧ q))

аксиома K,

4. 2p → 2(q → p ∧ q) из 2, 3 по m.p.,

5. 2(q → p ∧ q) → (2q → 2(p ∧ q)) аксиома K,

6. 2p → (2q → 2(p ∧ q)) из 4, 5 по правилу сечения,

7. 2p ∧ 2q → 2p аксиома A3,

8. 2p ∧ 2q → (2q → 2 (p ∧ q)) из 6, 7 по правилу сечения,

9. 2p ∧ 2q → 2q аксиома A4,

10. (2p ∧ 2q → (2q → 2(p ∧ q))) →

→ ((2p ∧ 2q → 2q) → (2p ∧ 2q → 2(p ∧ q)))

аксиома A2,

11. ((2p ∧ 2q → 2q) → (2p ∧ 2q → 2(p ∧ q))

из 8, 10 по m.p.,

12. 2p ∧ 2q → 2(p ∧ q) из 9, 11 по m.p.

Утверждение 1) доказано. Утверждение 2) является следствием утверждения 1)

и теоремы о замене эквивалентных: 3(p ∨ q) = ¬2¬(p ∨ q) ≡ ¬2(¬p ∧ ¬q) ≡ ¬(2¬p ∧

2¬q) ≡ ¬2¬p ∨ ¬2¬q) = 3p ∨ 3q.

Теорема дедукции для логики K принимает следующий вид.

Теорема 6.4. Если Γ, α ` β, то существуют такое число m, что Γ ` α ∧ 2α ∧ · · · ∧

α → β

Пусть ϕ

, . . . , ϕ

вывод формулы β из гипотез Γ, α. Индукцией по индексу i до-

кажем

Лемма 6.5. Пусть m - число применений правила Гёделя в указанном выводе, тогда

справедливо утверждение Γ ` α ∧ 2α ∧ · · · ∧ 2

α → ϕ

I. Если i = 1, то ϕ

либо аксиома, либо принадлежит Γ, либо совпадает с α.

Все рассуждения, проведённые при доказательстве теоремы дедукции в Lp остаются

справедливыми и, следовательно, Γ ` α → ϕ

II. Пусть лемма справедлива для всех i < k. Докажем её для индекса k. Для фор-

мулы ϕ

возможны следующие утверждения: 1) ϕ

является аксиомой, 2) ϕ

прина-

лежит Γ, 3) ϕ

совпадает с α, 4) ϕ

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

modus ponens, 5) ϕ

получена из предыдущей формулы по правилу Гёделя.

В случаях 1)-3) остаются справедливыми все построения из логики Lp.

В случае 4) ϕ

является следствием формул ϕ

и ϕ

→ ϕ

, для которых справед-

ливо предположение индукции: Γ ` α ∧ 2α ∧ · · · ∧ 2

α → ϕ

и Γ ` α ∧ 2α ∧ · · · ∧

α → (ϕ

→ ϕ

). Обозначим для сокращения записей α

= α ∧ 2α ∧ · · · ∧ 2

α,

= α ∧ 2α ∧ · · · ∧ 2

α. Построим следующий квазивывод из гипотез Γ:

1. α

→ ϕ

выводимая из Γ формула,

2. α

∧ α

→ α

аксиома A3,

3. α

∧ α

→ ϕ

из 1, 2 по правилу сечения,

4. α

→ (ϕ

→ ϕ

) выводимая из Γ формула,

5. α

∧ α

→ α

аксиома A4,

6. α

∧ α

→ (ϕ

→ ϕ

) из 4, 5 по правилу сечения,

7. (α

∧ α

→ (ϕ

→ ϕ

)) → ((α

∧ α

→ ϕ

) → (α

∧ α

→ ϕ

))

аксиома A5,

8. (α

∧ α

→ ϕ

) → (α

∧ α

→ ϕ

)

из 6, 7 по правилу m.p.,

9. α

∧ α

→ ϕ

из 3, 8 по правилу m.p.,

Мы показали, что Γ ` α

∧ α

→ ϕ

. Пусть n = max(m, r). Так как α

∧ α

≡

α ∧ 2α ∧ · · · ∧ 2

α, то Γ ` α ∧ 2α ∧ · · · ∧ 2

α → ϕ

Рассмотрим последний 5) случай: ϕ

получена из предыдущей формулы ϕ

по

правилу Гёделя, т.е. ϕ

= 2ϕ

. По предположению индукции Γ ` α∧2α∧· · ·∧2

α →

. Следовательно Γ ` 2(α ∧ 2α ∧ · · · ∧ 2

α → ϕ

). Формула 2(α ∧ 2α ∧ · · · ∧ 2

α →

) → (2(α ∧ 2α ∧ · · · ∧ 2

α) → 2ϕ

) является аксиомой K. В силу правила modus

ponens имеем Γ ` 2(2

α ∧ · · · ∧ 2

α) → 2ϕ

. Так как 2(2

α ∧ · · · ∧ 2

α) ≡

α∧· · ·∧2

α), то окончательно получаем Γ ` 2α∧2

α∧· · ·∧2

m+1

α → 2ϕ

Следовательно Γ ` α ∧ 2α ∧ 2

α ∧ · · · ∧ 2

m+1

α → ϕ

Лемма доказана. ¥

Заключение теоремы дедукции для K получим если положим в лемме i = n,

т.е. ϕ

является последней формулой в выводе ϕ

, . . . , ϕ

и совпадает с β. Отметим,

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

позволяет по данному выводу Γ, α ` β построить вывод Γ ` 2

α ∧ · · · ∧ 2

α → β.

Теорема дедукции доказана. ¥

6.2 Нормальные расширения логики K

Логику λ будем называть нормальной модальной логикой, если она содержит все

аксиомы логики K и замкнута относительно правил подстановки, modus ponens и

правила Гёделя. Запись K ⊕ {α

, . . . , α

} будет обозначать нормальную модальную

логику, полученную добавлением аксиом {α

, . . . , α

} к логике K.

Положим K4 = K ⊕ {2p → 22p}. Подставим в аксиому 2p → 22p вместо

переменной p формулу ¬p и к полученной формуле 2¬p → 22¬p применим правило

контрапозиции, в результате получим формулу 33p → 3p.

Подставив в аксиому 2p → 22p вместо переменной p формулу 2p, получим

формулу 22p → 222 p. По правилу сечения получаем 2p → 222p. Отсюда имеем

для любого k > 0 2p → 2

p. Далее нетрудно показать, что для любого набора

, . . . , n

положительных целых чисел формула 2p → 2

p ∧ · · · ∧ 2

p доказуема в

логике K4. В итоге теорема дедукции для логики K4 приобретает следующий вид

Теорема 6.6. Если Γ, α ` β, то Γ ` α ∧ 2α → β

Определим ещё две логики T и S4: T = K ⊕ {2p → p}, S4 = K4 ⊕ {2p → p}. Тео-

рема дедукции для этих логик справедлива и в той форме как оно сформулирована

для логики K. Но мы упростим её формулировку для этих логик.

Теорема 6.7. Если в логике T справедливо утверждение Γ, α ` β, то существует

такое число m, что Γ ` 2

α → β

Теорема 6.8. Если в логике S4 справедливо утверждение Γ, α ` β, то Γ ` 2α → β

Теорема 6.9. В логике S4 доказуемы следующие формулы:

1) p → 3p, 2) 2p → 23p

Применяя к аксиоме 2p → p правило контрапозиции, получим ¬p → ¬2p. Под-

ставив в последнюю формулу вместо переменной p формулу ¬p и воспользовав-

шись эквивалентностью ¬¬p ≡ p, получим формулу 1). Так как p → 3p доказу-

ема, то 2(p → 3p) также доказуема. Применив к последней формуле и аксиоме

2(p → 3p) → (2p → 23p) правило modus ponens, получим формулу 2).

Модальностями назовём формулы вида M

p, где M

∈ {2, ¬}, причём связка 2

имеет не менее одного вхождения. Учитывая эквивалентности ¬¬α ≡ α, ¬2¬α ≡ 3α

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

p или M

¬p, где

∈ {2, 3}.

Теорема 6.10. В логике S4 справедливы следующие эквивалентности:

1) 2

p ≡ 2p,

2) 3

p ≡ 3p,

3) (23)

p ≡ 23p,

4) (32)

p ≡ 32p.

Эквивалентность 1) справедлива, поскольку обе импликации 2

p → 2p и 2p →

p являются аксиомами логики S4. Эквивалентность 2) вытекает из 1) и свойств от-

ношения эквивалентности. Подставив в доказуемую формулу p → 3p вместо p фор-

мулу 23p получим 23p → 323p. Применив к последней формуле правило Гёделя,

а затем к полученной формуле и аксиоме 2(23p → 323p) → (223p → 2323p)

правило modus ponens, получим формулу 223p → 2323 p. Применив к получен-

ной формуле и аксиоме 23p → 223p правило сечения, получим 23p → 2323p.

Приведём доказательство обратной импликации.

1. p → 3p доказуемая формула,

2. 2p → 32p подстановка в формулу 1,

3. 2(2p → 32p) из 2 по правилу Гёделя,

4. 2(2p → 32p) → (22p → 232p)

аксиома K,

5. 22p → 232p из 3, 4 по m.p.,

6. 2p → 22p аксиома S4,

7. 2p → 232p из 5, 6 по правилу сечения,

8. 23p → 2323p подстановка в 7.

Эквивалентность 3) доказана. Перейдём к доказательству последней эквивалентно-

сти.

1. p → 3p доказуемая формула,

2. 2p → 32p подстановка в формулу 1,

3. 2(2p → 32p) из 2 по правилу Гёделя,

4. 2(2p → 32p) → (22p → 232p)

аксиома K,

5. 22p → 232p из 3, 4 по m.p.,

6. 2p → 22p аксиома S4,

7. 2p → 232p из 5, 6 по правилу сечения,

8. ¬232p → ¬2p из 7 по правилу контрапозиции,

9. 323¬p → 3¬p эквивалентна 8, т.к. ¬2¬ = 3 и ¬3¬ = 2,

10. 323p → 3p подстановка ¬p в 9 и замена ¬¬p ≡ p,

11. 2(323p → 3p) из 10 по правилу Гёделя,

12. 2(323p → 3p) → (2323p → 23p))

аксиома K,

13. 2323p → 23p из 11, 12 по m.p..

Таким образом любая модальность эквивалентна одной из следующих: 2p, 3p,

23p, 32p, 323p, 232p, 2¬p, 3¬p, 23¬p, 32¬p, 323¬p, 232¬p.

Логику S5 определим как S4 ⊕ {3p → 23p}. Учитывая определение S4, можно

записать следующее S5 = K ⊕ {2p → 22p, 2p → p, 3p → 23p}. Теорема дедукции

для S5 имеет ту же форму, что и для S4. Изучим более подробно логику S5. По-

скольку S5 является расширением S4, то в S5 справедливы все эквивалентности S4.

Кроме того в S5 имеются более сильные эквивалентности.

Теорема 6.11. В логике S5 справедливы следующие эквивалентности:

1) 23p ≡ 3p,

2) 32p ≡ 2p,

3) 3(p ∧ 3q) ≡ 3p ∧ 3q.

4) 2(p ∨ 2q) ≡ 2p ∨ 2q,

1) Импликация 3p → 23p является аксиомой S5, а импликация 23p → 3p

получена из аксиомы 2p → p подстановкой 3p вместо p.

2) Импликация 2p → 32p получена из из доказуемой формулы p → 3p под-

становкой 2p вместо p. Применив к аксиоме 3p → 23p правило контрапозиции,

получиим 32¬p → 2¬p. Подставив в последнюю формулу ¬p вместо p и сняв двой-

ное отрицание, получим 32p → 2p.

3) Докажем импликацию 3(p∧q) → 3p∧3q, из которой нужная нам импликация

получается подстановкой 3q вместо q с учётом эквивалентности 33q ≡ 3 q.

1. p ∧ q → p аксиома A3,

2. 3(p ∧ q) → 3p из 1 по производному правилу,

3. p ∧ q → q аксиома A3,

4. 3(p ∧ q) → 3q из 3 по производному правилу,

5. (3(p ∧ q) → 3p) → ((3(p ∧ q) → 3q) → (3(p ∧ q) → 3p ∧ 3q))

аксиома A6,

6. (3(p ∧ q) → 3q) → (3(p ∧ q) → 3p ∧ 3q)

из 2, 5 по правилу m.p.,

7. 3(p ∧ q) → 3p ∧ 3q из 4, 6 по правилу m.p.,

Докажем импликацию 3p ∧ 3q → 3(p ∧ 3q).

1. (p → q) → (¬q → ¬p) доказуемая формула,

2. 2(p → q) → 2(¬q → ¬p) из 1 по производному правилу,

3. 2(¬q → ¬p) → (2¬q → 2¬p) аксиома K,

4. 2(p → q) → (2¬q → 2¬p) из 2, 3 по правилу сечения,

1. 2(p → 2¬q) → (23q → 2¬p) доказуемая формула,

2. 2(p → 2¬q) → (3q → 2¬p) эквивалентна 1,

3. 2(p → 2¬q) ∧ 3q → 2¬p) эквивалентна 2,

4. 3p → (¬2(p → 2 ¬q) ∨ 2¬q) из 3 по правилу контрапозиции,

5. 3p ∧ 2(p → 2¬q) → 2¬q ∧ 2(p → 2¬q)

из 4 по свойству импликации,

6. 2¬q ∧ 2(p → 2¬q) → 2¬q аксиома A3,

7. 3p ∧ 2(p → 2¬q) → 2¬q) из 5 и 6 по правилу сечения,

8. 2(p → 2¬q) → (3p → 2¬q) эквивалентна 7,

9. 2(¬p ∨ 2¬q) → (2¬p ∨ 2¬q) замена импликации в 8,

10. 3p ∧ 3q → 3(p ∧ 3q) по правилу контрапозиции из 9.

Эквивалентность 4) получается из 3) с помощью отрацания.

Вопросы и задания.

1. Содержится ли классическая пропозициональная логика в логике K?

2. Докажите формулу 2(p → p).

3. Справедливо ли утверждение 2(α → β), 2α ` β?

4. Если формула α → β доказуема, то будет ли доказуема формула 2α → 2β?

5. Какие формулы можно вывести из гипотезы α применяя только правило Гёделя?

7 Лекция 7. Основные классы пропозициональных

логик

В данной лекции будут определены наиболее важные и изученные логики и классы

логик.

Логика Гейтинга H = Lj

+ p → (¬p → q)

Язык логики Гейтинга содержит логические связки ∧, ∨, →, ¬. Логика Гейтинга

задаётся следующими схемами аксиом

A1 (X → (Y → X)),

A2 ((X → (Y → Z)) → ((X → Y ) → (X → Z))),

A3 ((X ∧ Y ) → X),

A4 ((X ∧ Y ) → Y ),

A5 ((X → Y ) → ((X → Z) → (X → (Y ∧ Z)))),

A6 (X → (X ∨ Y )),

A7 (Y → (X ∨ Y )),

A8 ((X → Z) → ((Y → Z) → ((X ∨ Y ) → Z))),

A9 (X → Y ) → ((X → ¬Y ) → ¬X),

H X → (¬X → Y ),

и единственным правилом вывода

X,X→Y

. Поскольку все аксиомы логики Иоганс-

сона Lj

содержатся в логике Гейтинга и логика Гейтинга не содержит логических

связок и правил вывода, отличных от логики Иоганссона Lj

, то все теоремы фор-

мальной теории Lj

справедливы и в логике Гейтинга. Приведём сводку основных

утверждений логики Lj

Теорема дедукции, доказанная для логики Lp, справедлива и в логике Гейтинга.

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