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

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

В случаях а) и б) рассуждения те же, что и п. I. Предположим формула ψ

получена из предыдущих по правилу modus ponens, т.е. существуют формулы ψ

, такие что i, j < k и ψ

= ψ

→ ψ

. По предположению индукции существуют

выводы Γ ` α → ψ

и Γ ` α → ψ

. Пусть γ

, . . . , γ

, где γ

= α → ψ

, первый вывод и

, . . . , δ

, где δ

= α → ψ

, второй вывод. Вывод Γ ` α → ψ

построим в этом случае

следующим образом: γ

, . . . , γ

s−1

, α → ψ

, δ

, . . . , δ

t−1

, α → (ψ

→ ψ

), (α → (ψ

→

)) → ((α → ψ

) → (α → ψ

)), (α → ψ

) → (α → ψ

), α → ψ

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

Полагая в теореме 2.2 ψ

= β, получаем теорему 2.1.

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

1. Дайте определение правила вывода.

2. Постройте доказательство формулы p ∨ ¬p в классическом исчислении выска-

зываний.

3. Докажите теорему дедукции.

4. Используя доказательство теоремы дедукции, постройте доказательство фор-

мулы (x → (y → z)) → (x ∧ y → z).

5. Можно ли при построении вывода из гипотез применять правило подстановки

к гипотезам?

3 Лекция 3. Основные теоремы позитивной логики.

В этой лекции докажем ряд свойств логики Lp, которые пригодятся нам не только

в этой логике, но и в её расширениях.

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

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

ponens. Пусть формула α доказуема в логике L, ψ

, . . . , ψ

= α - её доказатель-

ство, и в процессе поиска вывода в логике L формулы β из множества гипотез

Γ мы построили вывод ϕ

, . . . , ϕ

= (α → β). Тогда последовательность формул

, . . . , ϕ

, ψ

, . . . , ψ

, β будет выводом в логике L формулы β из множества гипо-

тез Γ. Последняя формула в этом выводе получается примненением правила modus

ponens к формулам ϕ

и ψ

. Вместо указанного вывода формулы β мы будем за-

писывать более короткую последовательность ϕ

, . . . , ϕ

, α, β, которую тоже будем

называть выводом из Γ, или сокращённым выводом из Γ.

Теорема 3.1. Следующие секвенции доказуемы в Lp:

1) p, q ` p ∧ q,

2) p → q, q → r ` p → r,

Здесь и далее при построении выводов для их сокращения будем использовать

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

квенции 1) построим следующий вывод:

1. p гипотеза

2. p → (q → p) аксиома по схеме A1

3. q → p следует из 1, 2 по правилу m.p.

4. q → q доказуемая в Lp формула

5. (q → p) → ((q → q) → (q → p ∧ q)) аксиома по схеме A5

6. (q → q) → (q → p ∧ q) из 3 и 5 по m.p.

7. q → p ∧ q из 4 и 6 по m.p.

8. q гипотеза

9. p ∧ q из 7 и 8 по m.p.

Для доказательства секвенции 2) достаточно построить вывод p → q, q → r, p ` r ,

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

1. p гипотеза,

2. p → q гипотеза,

3. q следует из 1, 2 по правилу m.p.

4. q → r гипотеза,

5. r следует из 3, 4 по правилу m.p.

Отметим следующее: если в исчислении доказана секвенция

, . . . , p

), . . . , α

, . . . , p

) ` β(p

, . . . , p

то правило вывода

, . . . , p

), . . . , α

, . . . , p

)

β(p

, . . . , p

)

является допустимым в этом исчислении. Поэтому введём следующий термин: пра-

вило вывода

,...,p

),...,α

,...,p

)

β(p

,...,p

)

будем называть производным (или доказуемым),

если α

, . . . , p

), . . . , α

, . . . , p

) ` β(p

, . . . , p

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

изводные правила вывода

p, q

p ∧ q

− правило введения конъюнкции;

p → q, q → r

p → r

− правило сечения.

Отметим, что эти правила допустимы в любой логике, содержащей логику Lp и в

которой допустимы правило подстановки и modus ponens.

Теорема 3.2. Следующие секвенции доказуемы в Lp:

1) p → (q → r) ` (p ∧ q) → r,

2) (p ∧ q) → r ` p → (q → r).

Секвенция 1 получается из секвенции p → (q → r), p∧q ` r применением теоремы

дедукции. Поэтому достаточно построить вывод секвенции

p → (q → r), p ∧ q ` r.

1. p ∧ q гипотеза,

2. (p ∧ q) → p аксиома по схеме A3,

3. p из 1 и 2 по m.p.,

4. p → (q → r) гипотеза,

5. q → r ) из 3 и 4 по m.p.,

6. (p ∧ q) → q аксиома по схеме A4,

7. q из 1 и 6 по m.p.,

8. r из 5 и 7 по m.p..

Построим вывод второй секвенции. Опять вместо секвенции (p ∧ q) → r ` p →

(q → r ) выведем секвенцию (p ∧ q) → r, p, q ` r.

1. p гипотеза,

2. q гипотеза,

3. p ∧ q из 1, 2 по правилу введения конъюнкции

4. (p ∧ q) → r гипотеза,

5. r из 3, 4 по правилу m.p.

Применяя к полученной секвенции теорему дедукции, получим требуемое утвер-

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

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

утверждения α ` β и β ` α. В силу теоремы дедукции эти утверждения эквивалент-

ны утверждениям ` α → β и β ` α, соответственно. Утверждение "формула α

формально эквивалентна формуле β"символически будем записывать α ≡ β. Как

следует из только что доказанной теоремы, (p ∧ q) → r ≡ p → (q → r).

Теорема 3.3. Отношение формальной эквивалентности рефлексивно, симметрич-

но и транзитивно.

Доказательство. Рефлексивность вытекает непосредственно из определения выво-

да, поскольку α ` α для любой формулы α. Также непосредственно из определения

вывода вытекает симметричность. Пусть α ≡ β и β ≡ γ. Тогда, последовательно

записав вначале вывод α ` β и затем вывод β ` γ, мы получим вывод α ` γ. Ана-

логично поступив с выводами секвенций γ ` β и β ` α, получим γ ` α. То есть

α ≡ γ.

Из доказанной теоремы и определения формальной эквивалентности вытекает

Теорема 3.4. Если α ` β и β ≡ γ, то α ` γ. Если α ≡ β и β ` γ, то α ` γ.

Теорема 3.5. Следующие эквивалентности доказуемы в Lp:

1. p ≡ p ∧ p, 2. p ∨ p ≡ p,

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

5. p ∧ q ≡ q ∧ p, 6. p ∨ q ≡ q ∨ p,

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

1. Для доказательства первой эквивалентности построим следующие два вывода:

A) Вывод секвенции p ` p ∧ p

1. p гипотеза,

2. (p → p) → ((p → p) → (p → p ∧ p)) схема аксиом A2,

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

4. (p → p) → (p → p ∧ p) следует из 2, 3 по m.p.

5. p → p ∧ p следует из 3, 4 по m.p.

B) Вывод секвенции p ∧ p ` p

1. p ∧ p гипотеза,

2. (p ∧ p) → p схема аксиом A3 (или A4)

3. p следует из 1, 2 по m.p.

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

A) Вывод секвенции p ∨ p ` p

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

2. (p → p) → ((p → p) → ((p ∨ p) → p)) схема аксиом A8,

3. (p → p) → ((p ∨ p) → p) следует из 1, 2 по m.p.

4. (p ∨ p) → p следует из 1, 3 по m.p.

5. p ∨ p гипотеза,

6. p следует из 4, 5 по m.p.

B) Вывод секвенции p ` p ∨ p очевиден.

3. Докажем закон ассоциативности для конъюнкции.

A) Вывод секвенции (p ∧ q) ∧ r ` p ∧ (q ∧ r).

1. (p ∧ q) ∧ r гипотеза,

2. ((p ∧ q) ∧ r) → (p ∧ q) схема аксиом A3,

3. p ∧ q следует из 1, 2 по m.p.

4. (p ∧ q) → p схема аксиом A3,

5. p следует из 3, 4 по m.p.

6. (p ∧ q) → q схема аксиом A4,

7. q следует из 3, 6 по m.p.

8. ((p ∧ q) ∧ r) → r схема аксиом A4,

9. r следует из 1, 8 по m.p.

10. q ∧ r из 7, 9 по пр. введения конъюнкции

11. p ∧ (q ∧ r) из 5, 10 по пр. введения конъюнкции

B) Вывод секвенции p ∧ (q ∧ r) ` (p ∧ q) ∧ r аналогичен. Предлагается построить

его самостоятельно.

4. Докажем закон ассоциативности для дизъюнкции. Приведём вывод секвенции

p ∨ (q ∨ r) ` (p ∨ q) ∨ r. Вывод секвенции (p ∨ q) ∨ r ` p ∨ (q ∨ r) строится аналогично.

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

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

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

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

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

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

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

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

схема аксиом A8,

9. (r → ((p ∨ q) ∨ r)) → ((q ∨ r) → ((p ∨ q) ∨ r),

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

10. (q ∨ r) → ((p ∨ q) ∨ r из 7, 9 по правилу m.p.,

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

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

схема аксиом A8,

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

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

13. (p ∨ (q ∨ r)) → ((p ∨ q) ∨ r) из 10, 12 по правилу m.p.,

14. p ∨ (q ∨ r) гипотеза,

15. (p ∨ q) ∨ r из 13, 14 по правилу m.p..

5. Докажем закон коммутативности для конъюнкции.

1. p ∧ q гипотеза,

2. (p ∧ q) → q схема аксиом A4,

3. q, из 1, 2 по правилу m.p.,

4. (p ∧ q) → p схема аксиом A3,

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

6. q ∧ p ,из 3, 5 по правилу введения конъюнкции.

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

ми переменных p и q.

6. Ввиду симметрии всех построений, при доказательстве закона коммутативно-

сти для дизъюнкции проведём все построения только для одной секвенции p∨q ` q∨p.

1. p → (q ∨ p) схема аксиом A7,

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

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

схема аксиом A8,

4. (q → (q ∨ p)) → ((p ∨ q) → (q ∨ p)), из 1, 3 по правилу m.p.,

5. (p ∨ q) → (q ∨ p ) из 2, 4 по правилу m.p.,

6. p ∨ q, гипотеза,

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

7. Докажем первый закон поглощения p ∧ (p ∨ q) ≡ p. Секвенция p ∧ (p ∨ q) ` p

очевидна. Приведём вывод p ` p ∧ (p ∨ q)

1. p гипотеза,

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

3. p ∨ q из 1, 2 по правилу m.p.,

4. p ∧ (p ∨ q) из 1, 3 по правилу введения конъюнкции.

8. Докажем второй закон поглощения p ∨ (p ∧ q) ≡ p. Секвенция p ` p ∨ (p ∧ q)

очевидна. Приведём вывод p ∨ (p ∧ q) ` p

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

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

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

схема аксиом A8,

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

5. (p ∨ (p ∧ q)) → p из 2, 4 по правилу m.p.

6. p ∨ (p ∧ q) гипотеза,

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

Далее нам потребуется следующая

Теорема 3.6. (О замене эквивалентных) Если α ≡ β и формула Ψ получена из

формулы Φ заменой некоторого вхождения формулы α на формулу β, то Φ ≡ Ψ.

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

I. Пусть длина Φ совпадает с длиной α, т.е. Φ = α. В этом случае Ψ = β и

утверждение теоремы очевидно.

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

ждение теоремы справедливо. В этом случае Φ построена из более коротких формул

с помощью связок ∧, ∨, →. Рассмотрим соответствующие три случая.

1. Φ = Φ

∧ Φ

. Ввиду коммутативности связки ∧ достаточно рассмотреть слу-

чай, когда формула α содержится в Φ

. Пусть формула Ψ

получена из Φ

заменой

подформулы α на β. Поскольку Φ

короче чем Φ, то по предположению индукции

≡ Ψ

. Следовательно Φ

` Ψ

и по теореме дедукции ` Φ

→ Ψ

, то есть формула

→ Ψ

доказуема. Последовательность формул

1. Φ

∧ Φ

гипотеза,

2. Φ

∧ Φ

→ Φ

схема аксиом A3,

3. Φ

следствие 1 и 2 по m.p.,

4. Φ

→ Ψ

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

5. Ψ

следствие 3 и 4 по m.p.,

6. Φ

∧ Φ

→ Φ

схема аксиом A4,

7. Φ

следствие 1 и 6 по m.p.,

8. Ψ

∧ Φ

следствие 5 и 7 по правилу введения конъюнкции,

является квазивыводом формулы Ψ

∧ Φ

= Ψ из формулы Φ

∧ Φ

= Φ. То есть

Φ ` Ψ. Несложные изменения в построенном квазивыводе приводят к утверждению

Ψ ` Φ.

2. Φ = Φ

∨ Φ

. Ввиду коммутативности связки ∨ достаточно рассмотреть слу-

чай, когда формула α содержится в Φ

. Пусть формула Ψ

получена из Φ

заменой

подформулы α на β. Поскольку Φ

короче чем Φ, то по предположению индукции

≡ Ψ

. Следовательно Φ

` Ψ

и по теореме дедукции ` Φ

→ Ψ

, то есть формула

→ Ψ

доказуема. Последовательность формул

1. Φ

∨ Φ

гипотеза,

2. Φ

→ Ψ

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

3. Ψ

→ (Ψ

∨ Φ

) схема аксиом A6,

4. Φ

→ (Ψ

∨ Φ

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

5. Φ

→ (Ψ

∨ Φ

) схема аксиом A7,

6. (Φ

→ (Ψ

∨ Φ

)) → ((Φ

→ (Ψ

∨ Φ

)) → ((Φ

∨ Φ

) → (Ψ

∨ Φ

)))

схема аксиом A8,

7. (Φ

→ (Ψ

∨ Φ

)) → ((Φ

∨ Φ

) → (Ψ

∨ Φ

))

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

8. (Φ

∨ Φ

) → (Ψ

∨ Φ

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

9. Ψ

∨ Φ

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

является квазивыводом формулы Ψ

∨ Φ

= Ψ из формулы Φ

∨ Φ

= Φ. То есть

Φ ` Ψ. Несложные изменения в построенном квазивыводе приводят к утверждению

Ψ ` Φ.

3. Φ = Φ

→ Φ

. В этом случае придётся рассмотреть две возможности: а) α

содержится в Φ

, б) α содержится в Φ

а) В этом случае формула Ψ

, полученная из Φ

заменой α на β эквивалент-

на Φ

в силу предположения индукции. Нам необходимо доказать две секвенции

→ Φ

` Ψ

→ Φ

и Ψ

→ Φ

` Φ

→ Φ

. В силу теоремы дедукции для этого до-

статочно доказать секвенции Φ

→ Φ

, Ψ

` Φ

и Ψ

→ Φ

, Φ

` Φ

. Справедливость

этих секвенций следует из того, что ` Ψ

→ Φ

и ` Φ

→ Ψ

в силу определения

формальной эквивалентности.

б) В этом случае формула Ψ

, полученная из Φ

заменой α на β эквивалент-

на Φ

в силу предположения индукции. Нам необходимо доказать две секвенции

→ Φ

` Φ

→ Ψ

и Φ

→ Ψ

` Φ

→ Φ

. В силу теоремы дедукции для этого до-

статочно доказать секвенции Φ

→ Φ

, Φ

` Ψ

и Φ

→ Ψ

, Φ

` Φ

. Справедливость

этих секвенций следует из того, что ` Φ

→ Ψ

и ` Ψ

→ Φ

в силу определения

формальной эквивалентности.

Теорема 3.7. Следующие эквивалентности доказуемы в Lp:

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

2. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).

1. Для доказательства первого закона дистрибутивности p∧(q∨r) ≡ (p∧q)∨(p∧r)

выведем вспомогательные секвенции.

1. p гипотеза,

2. q гипотеза,

3. p ∧ q из 1, 2 по правилу введения конъюнкции,

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

схема аксиом A6,

5. (p ∧ q) ∨ (p ∧ r) из 1, 2 по правилу m.p..

Приведённый вывод является выводом секвенции p, q ` (p∧q)∨(p∧r). Несложные

изменения приведённого вывода дадут вывод секвенции p, r ` (p∧ q) ∨ (p ∧r). Приме-

няя к обеим секвенциям теорему дедукции, получим секвенции p ` q → ((p ∧ q) ∨ (p ∧

r)) и p ` r → ((p∧q)∨(p∧r)). Для сокращения записей положим D = (p∧q)∨(p∧r). В

силу доказанных секвенций последовательность формул p, q → D, r → D, (q → D) →

((r → D) → ((q∨r) → D)), (r → D) → ((q∨r) → D), (q∨r) → D, q∨r, D является ква-

зивыводом для секвенции p, q∨r ` (p∧q)∨(p∧r). В силу последней секвенции последо-

вательность формул p∧(q∨r), (p∧(q∨r)) → p, p, (p∧(q∨r)) → (q∨r), q∨r, (p∧q)∨(p∧r)

является квазивыводом для секвенции p ∧ (q ∨ r) ` (p ∧ q) ∨ (p ∧ r).

Докажем далее секвенцию (p ∧ q) ∨ (p ∧ r) ` p ∧ (q ∨ r).

1. p ∧ q гипотеза,

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

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

4. (p ∧ q) → q схема аксиом A4,

5. q из 1, 4 по правилу m.p.,

6. q → (q ∨ r) схема аксиом A6,

7. q ∨ r из 5, 6 по правилу m.p.,

8. p ∧ (q ∨ r) из 3, 7 по правилу введения конъюнкции,

Мы построили вывод для секвенции (p ∧ q) ` p ∧ (q ∨ r). Применяя теорему

дедукции, получаем ` (p ∧ q) → (p ∧ (q ∨ r)). Аналогично доказывается ` (p ∧ r) →

(p ∧ (q ∨ r)). теперь построим квазивывод нужной нам секвенции.

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

2. (p ∧ r) → (p ∧ (q ∨ r)) доказуемая формула,

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

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

схема аксиом A8,

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

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

5. ((p ∧ q) ∨ (p ∧ r)) → (p ∧ (q ∨ r)) из 2, 4 по правилу m.p.,

6. (p ∧ q) ∨ (p ∧ r) гипотеза,

7. p ∧ (q ∨ r) из 5, 6 по правилу m.p.

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

и свойства отношения эквивалентности, докажем второй закон дистрибутивности

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

(p ∨ q) ∧ (p ∨ r) ≡

((p ∨ q) ∧ p) ∨ ((p ∨ q) ∧ r) ≡ в силу первого закона дистрибутивности

p ∨ ((p ∨ q) ∧ r) ≡ эквивалентность ?? и теорема о замене,

p ∨ ((p ∧ r) ∨ (q ∧ r) ≡ эквивалентность ?? и теорема о замене,

(p ∨ (p ∧ r)) ∨ (q ∧ r) ≡ ассоциативность,

p ∨ (q ∧ r) закон поглощения.

Для демонстрации эффективности использованного метода доказательства при-

ведём доказательство секвенции p ∨ (q ∧ r) ` (p ∨ q) ∧ (p ∨ r)

1. p гипотеза,

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

3. p → (p ∨ r) схема аксиом A6,

4. p ∨ q из 1, 2 по правилу m.p.

5. p ∨ r из 1, 3 по правилу m.p.

6. (p ∨ q) ∧ (p ∨ r) из 1, 2 по правилу введения конъюнкции.

Следовательно, справедлива секвенция p ` (p ∨ q) ∧ (p ∨ r). Построим вывод

секвенции q ∧ r ` (p ∨ q) ∧ (p ∨ r).

1. q ∧ r гипотеза,

2. (q ∧ r) → q схема аксиом A3,

3. (q ∧ r) → r схема аксиом A4,

4. q из 1, 2 по правилу m.p.

5. r из 1, 3 по правилу m.p.

6. q → (p ∨ q) схема аксиом A7,

7. r → (p ∨ r) схема аксиом A7,

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

9. p ∨ r из 5, 7 по правилу m.p.

10. (p ∨ q) ∧ (p ∨ r) из 8, 9 по правилу введения конъюнкции.

Теперь для доказательства утверждения p ∨ (q ∧ r) ` (p ∨ q) ∧ (p ∨ r) построим

квазивывод этой секвенции.

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

2. (q ∨ r) → ((p ∨ q) ∧ (p ∨ r)) доказуемая формула,

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

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

схема аксиом A8,

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

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

5. (p ∨ (q ∧ r)) → ((p ∨ q) ∧ (p ∨ r)) из 2, 4 по правилу m.p.

6. p ∨ (q ∧ r) гипотеза,

7. (p ∨ q) ∧ (p ∨ r) из 5, 6 по правилу m.p.

Теорема 3.8. Следующие эквивалентности доказуемы в Lp:

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

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

3. ((p → q) → q) → q ≡ p → q,

4. (p → q) ≡ [((p → q) → p) → q],

1. Для доказательства первой эквивалентности докажем вначале секвенцию ((p ∨

q) → r) ` ((p → r) ∧ (q → r)).

1. p, ((p ∨ q) → r) ` r m.p.A6

2. ((p ∨ q) → r ) ` p → r t.d.1

3. q, ((p ∨ q) → r) ` r m.p.A7

4. ((p ∨ q) → r ) ` q → r t.d.3

5. ((p ∨ q) → r ) ` (p → r) ∧ (q → r) m.p.2,4,A8.

Далее докажем секвенцию ((p → r) ∧ (q → r)) ` ((p ∨ q) → r).

1. (p → r) ∧ (q → r) ` p → r m.p.A3

2. (p → r) ∧ (q → r) ` q → r m.p.A4

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

4. (p → r) ∧ (q → r) ` (p ∨ q → r) m.p.1,2,3

2. Докажем вторую эквивалентность p → q ∧ r ≡ (p → q) ∧ (p → r)

p → q ∧ r, p ` q

p → q ∧ r ` p → q

p → q ∧ r, p ` r

p → q ∧ r ` p → r

p → q ∧ r ` (p → q) ∧ (p → r)

(p → q) ∧ (p → r), p ` q

(p → q) ∧ (p → r), p ` r

(p → q) ∧ (p → r), p ` q ∧ r

(p → q) ∧ (p → r) ` p → (q ∧ r)

3. Докажем третью эквивалентность ((p → q) → q) → q ≡ p → q.

Так как p → q, (p → q) → q ` q, то по теореме дедукции p → q ` ((p → q) → q) →

Докажем обратное. Применяя теорему дедукции к p, p → q ` q, получим p ` (p →

q) → q. Используя полученное правило построим вывод p, (p → q) → q, ((p → q) →

q) → q, q. То есть (( p → q) → q) → q, p ` q. В силу теоремы дедукции ((p → q) →

q) → q ` p → q.

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

p → q, (p → q) → p ` q и ((p → q) → p) → q, p ` q. Построим выводы указанных

секвенций.

1. p → q гипотеза,

2. (p → q) → p гипотеза,

3. p из 1, 2 по m.p.,

4. q из 1, 3 по m.p..

Докажем вторую секвенцию.

1. p гипотеза,

2. p → ((p → q) → p) аксиома вида A1,

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

4. ((p → q) → p) → q гипотеза,

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

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

Докажем ещё ряд свойств логики Lp.

Теорема 3.9. В логике Lp справедливы следующие утверждения:

1) (p → q) ∨ (p → r) ` p → (q ∨ r),

2) p → (q ∨ r) ` p → ((p → q) ∨ (p → r)),

3) ((p → q) → p) ` (p → q) → q,

4) p ` (p → q) → q,

5) ` (p → q) → ((q → r) → (p → r)),

6) Если p ` q, то q → r ` p → r,

7) q ≡ (((p → q) → p) → p) → q

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

1) p → q ` p → (q ∨ r)

p → r ` p → (q ∨ r)

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

2) Позже мы покажем что секвенция обратная к 1) неверна. А сейчас вместо неё

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

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

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

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

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

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

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

лы q из гипотез p → q, (p → q) → p. Применяя к полученной секвенции (p → q), ((p →

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

4) Данная секвенция получается применением теоремы дедукции к очевидному

утверждению p, p → q ` q.

5) Утверждение получается трёхкратным применением теоремы дедукции к оче-

видной секвенции p → q, q → r, p ` r.

6) Если p ` q, то ` p → q и в силу утверждения 5) ` (q → r ) → (p → r)), что

эквивалентно q → r ` p → r.

a) q ` (((p → q) → p) → p) → q

1. p ` (((p → q) → p) → p)

2. ((p → q) → p) → p ` ((((p → q) → p) → p) → q) → q

3. p ` ((((p → q) → p) → p) → q) → q, из 1,2

4. (((((p → q) → p) → p) → q) → q) → q ` p → q, из 3

5. (((p → q) → p) → p) → q ` p → q из 4

6. p → q ` (((p → q) → p) → p)

7. (((p → q) → p) → p) → q ` (((p → q) → p) → p) из 5,6

8. (((((p → q) → p) → p) → q) → q) → q ` ((((p → q ) → p) → p) → q) → q из 7

9. (((p → q) → p) → p) → q ` ((((p → q) → p) → p) → q) → q из 8

10. (((p → q) → p) → p) → q ` q из 9

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

1. Показать, что следующие формулы доказуемы в Lp

а) (b ∨ (b → a)) → (a → b) ∨ (b → a),

б) (a ∨ (a → b)) → (a → b) ∨ (b → a),

в) (a ∨ b) → (a → b) ∨ (b → a).

2. Какие эквивалентности алгебры высказываний справедливы в позитивной ло-

гике?

3. Сформулируйте основные свойства отношения эквивалентноти, доказуемые в Lp.

4. Докажите секвенцию p ` (p → q) → q.

5. Постройте полное доказательство формулы p → ((p → q) → q) в логике Lp.