+7 (903) 100 31 62 kortunov@bk.ru

Приложение

Приложение

Основные законы логики:

Закон тождества A≡A

Закон непротиворечия: ¬(A˄¬A)

Закон исключенного третьего: A˅¬A

p⊃(q⊃p) – закон (утверждения) консеквента;

(p⊃q)⊃(¬q⊃¬p) – закон контрапозиции;

(¬p⊃¬q)⊃(q⊃p) – закон усиленной (обратной) контрапозиции;

((a˄b)⊃c)⊃((a˄¬c)⊃¬b) – закон сложной контрапозиции;

(p⊃(q⊃r))⊃((p⊃q)⊃(p⊃r)) – закон самодистрибутивности (материальной) импликации.

 

Прочие законы логики:

(a→b)→((b→c)→(a→c) – первый закон транзитивности

(a→b)→((с→a)→(c→b) – второй закон транзитивности.

a→(b→a) – закон консеквента

¬a→(а→b) – закон ложного имплицирования

(a→(b→c))→(b→(a→c)) — закон перестановки антецедентов

(a→(b→c))→(a˄b)→c)) – закон импортации

(a˄b)→c))→(a→(b→c)) – закон экспортации

(a˄b)˄c↔a˄(b˄c) — ассоциативность конъюнкции

(a˅b)˅c↔a˅(b˅c) – ассоциативность дизъюнкции

(a˄b)↔(b˄a) – коммутативность конъюнкции

(a˅b)↔(b˅а) – коммутативность дизъюнкции

a˄(b˅c)↔(a˄b)˅(а˄c) — дистрибутивность конъюнкции относительно дизъюнкции

a˅(b˄c)↔(a˅b)˄(а˅c) — дистрибутивность дизъюнкции относительно конъюнкции

a˄(a˅b)↔a – первый закон поглощения

a˅(a˄b)↔a – второй закон поглощения

a˄(b˅¬b)↔a – закон исключения истинного члена из конъюнкции

a˅(b˄¬b)↔a – закон исключения ложного члена из дизъюнкции

(a→b)→((a˄c)→(b˄c)) – закон ввода произвольной конъюнкции

(a→b)→((a˅c)→(b˅c)) – закон ввода произвольной дизъюнкции

Эквивалентности для логики высказываний:

приведение к импликации —

(a˄b)≡¬(a⊃¬b), ¬(b⊃¬a)

(a˅b)≡(¬a⊃b), (¬b⊃a)

(a↔b)≡(a⊃b), (b⊃a)

(a˅b)≡(¬a⊃b), (¬b⊃a)

приведение к конъюнкции —

(a⊃b)≡¬(a˄¬b)

(a˅b)≡¬(¬a˄¬b)

(a˅b)≡¬((a∨¬b)∧(¬a∨b))

(a↔b)≡(a∨¬b)˄(b∨¬a)

приведение к дизъюнкции —

(a˄b)≡¬(¬a∨¬b)

(a⊃b)≡(¬a∨b)

(a˅b)≡(a˄¬b)∨(¬a˄b)

(a↔b)≡(a∧b)∨(¬a˄¬b)

Эквивалентности логики предикатов:

∀x(P(x)⊃¬S(x))⊃¬Ǝx(P(x)˄S(x))↔

↔¬∀x(P(x)⊃¬S(x))˅¬Ǝx(P(x)˄S(x))↔

↔Ǝx¬(P(x)⊃¬S(x))˅¬Ǝx(P(x)˄S(x))↔

↔Ǝx(P(x)˄¬¬S(x))˅¬Ǝx(P(x)˄S(x))↔

↔Ǝx(P(x)˄S(x))˅¬Ǝx(P(x)˄S(x))↔

↔Ǝx(P(x)˄S(x))˅∀x¬(P(x)˄S(x))↔

↔Ǝx(P(x)˄S(x))˅∀x(¬P(x)˅¬S(x))

 

¬∀x(S(x)⊃P(x))↔∃x¬(S(x)⊃P(x))↔

↔∃x(S(x)˄¬P(x))↔∃x(¬S(x)˅P(x))

¬∃x(S(x)˄P(x))↔∀x¬(S(x)˄P(x))↔

↔∀x(S(x)⊃¬P(x))↔∀x(¬S(x)˅¬P(x))

Таблица истинности для логических знаков:

переменные результат их сравнения
A B ∧ ∨ ∨ ⊃ ↔
И И И И Л И И
И Л Л И И Л Л
Л И Л И И И Л
Л Л Л Л Л И И

Отрицание основных формул в логике высказываний:

¬(a˄b)↔¬a˅¬b,

¬(a˅b)↔¬a˄¬b,

¬(a⊻b)↔(a˄b)˅(¬a˄¬b),

¬(a→b)↔a˄¬b,

¬(a≡b)↔(a˄¬b)˅(b˄¬a),

¬¬a↔a

Отрицание в логике предикатов:

суждение ↔ его отрицание
¬(Все S суть P) ↔ Некоторые S не суть P
¬(Все S не суть P) ↔ Некоторые S суть P
¬(Некоторые S суть P) ↔ Все S не суть P
¬(Некоторые S не P) ↔ Все S суть P
суждение ↔ его отрицание
Все S суть P ↔ ¬(Некоторые S не суть P)
Все S не суть P ↔ ¬(Некоторые S суть P)
Некоторые S суть P ↔ ¬(Все S не суть P)
Некоторые S не P ↔ ¬(Все S суть P)

В более подробном написании:

суждение ↔ его отрицание
∀x(S(x)⊃P(x)) ↔ ∃x(S(x)∧¬P(x))
∃x(S(x)∧P(x)) ↔ ∀x(S(x)⊃¬P(x))
∃x(S(x)∧¬P(x)) ↔ ∀x(S(x)⊃P(x))
∀x(S(x)⊃¬P(x)) ↔ ∃x(S(x)∧P(x))

Непосредственные выводы из простых суждений:

суждение ↔ его превращение
Все S суть P ↔ Ни одно S не суть не P
Все S не суть P ↔ Все S суть не P
Некоторые S суть P ↔ Некоторые S не суть не P
Некоторые S не суть P ↔ Некоторые S суть не P
суждение ↔ его обращение
Все S суть P ↔ Некоторые P суть S
Все S не суть P ↔ Все P не суть S
Некоторые S суть P ↔ Некоторые P суть S
Некоторые S не P ≢ не обращается!
суждение ↔ противопоставление предикату
Все S суть P ↔ Ни одно не P не есть S
Все S не суть P ↔ Некоторые не P суть S
Некоторые S не суть P ↔ Некоторые не P суть S
суждение ↔ противопоставление субъекту
Все S суть P ↔ Ни одно P не суть не S
Все S не суть P ↔ Все P суть не S
Некоторые S суть P ↔ Некоторые P не суть не S

Формализация простых суждений:

Обще-утвердительные — ∀x(S(x)⊃P(x));

Частно-утвердительные — ∃x(S(x)∧P(x));

Обще-отрицательные — ∀x(S(x)⊃¬P(x));

Частно-отрицательные — ∃x(S(x)∧¬P(x)).

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

  1. Если одна из посылок – отрицательное суждение (¬), вывод также — отрицательное суждение (¬).
  2. Если обе посылки – утвердительные суждения, вывод также утвердителен.
  3. Если обе посылки – отрицательные суждения – вывод невозможен.
  4. Если одна из посылок частное суждение (∃), вывод также – частное суждение (∃).
  5. Если обе посылки – частные суждения (∃) – вывод невозможен.
  6. Если средний термин не распределен, хотя бы в одной из посылок – вывод невозможен.
  7. Термин, нераспределенный в посылках, не может быть распределён в заключении.

Система натурального вывода Куайна:

Правила вывода первого рода:

  1. а,b ⊧ a˄b – введение ˄ (В˄)
  2. a˄b ⊧ а – удаление ˄ (У˄)
  3. ¬(a˄b) ⊧ ¬a∨¬b — отрицание ˄ (О˄)
  4. а ⊧ а˅b – введение ˅ (В˅)
  5. а˅b, ¬a ⊧ b — удаление ˅ (У˅)
  6. ¬(а˅b) ⊧¬a∧¬b — отрицание ˅ (О˅)
  7. а⊃b, a) ⊧ b – удаление ⊃ (У⊃)¹
  8. а⊃b, ¬b) ⊧ ¬a– удаление ⊃ (У⊃)²
  9. a, b ⊧ (а⊃b), (b⊃a) — введение ⊃ (В⊃)
  10. ¬(а⊃b) ⊧ a˄¬b — отрицание ⊃ (О⊃)
  11. а⊃b, b⊃a ⊧ a≡b — введение ≡ (В≡)
  12. a≡b ⊧ а⊃b, b⊃a — удаление ≡ (У≡)
  13. а⊧ ¬¬а — введение двойного отрицания (В¬¬)

¬¬а⊧ а — удаление двойного отрицания (У¬¬)

Правила вывода второго рода:

  1. (а⊃с)˄(b⊃с)⊧(а˅b) →с – рассуждение разбором случаев (РРС)
  2. (b˄¬b)⊃а⊧¬а – сведение к абсурду (СА)
  3. ¬а⊃ (b˄¬b)⊧ а – доказательство от противного (ДОП)
  4. (Г, a⊧ b)⊧(Г⊧ a→b) — правило дедукции.

В другом написании:

В˄ а, b У˄ a˄b О˄ ¬(a˄b) В˅ а У˅ а˅b, ¬a О˅ ¬(а˅b)
a˄b а ¬a∨¬b а˅b b ¬a∧¬b
У⊃ а⊃b, a У⊃ а⊃b, ¬b В⊃ a, b О⊃ ¬(а⊃b)
b ¬a (а⊃b), (b⊃a) a˄¬b
В≡ а⊃b, b⊃a У≡ a≡b В¬¬ а У¬¬ ¬¬а
a≡b а⊃b, b⊃a ¬¬а a
РРС (а⊃с)˄(b⊃с) СА (b˄¬b)⊃а ДОП ¬а⊃(b˄¬b)
(а˅b)→с ¬а а
ПД Г, a ⊧b
Г⊧ a⊃b

Правила кванторов:

  1. ∀xP(x)⊧P(t) – схема удаления ∀(У∀)
  2. P(t)⊧ƎхP(x) – схема введения Ǝ (ВƎ)
  3. P(t)⊧∀xP(x) — схема введения ∀ (В∀) – х ограничен
  4. ƎxP(x)⊧P(t) – схема удаления Ǝ (УƎ) – х ограничен

В другом написании:

У∀ ∀xP(x) ВƎ P(t) В∀ P(t) УƎ ƎxP(x)
P(t) ƎхP(x) ∀xP(x) P(t)

Правила построения семантических таблиц:

— если мы имеем конъюнкцию — a˄b, то вписываем в выводе «a» и «b», не размножая таблицу;

— если мы имеем дизъюнкцию — a˅b, то размножаем таблицу и в одном столбце пишем «а», а в другом – «b».

Все остальные формулы мы преобразуем в конъюнкцию или дизъюнкцию по эквивалентностям:

(a⊃b)→ ¬a˅b

¬(a⊃b)→ a˄¬b

¬(a˄¬b)→ ¬a˅¬b

¬(a˅¬b)→ ¬a˄¬b

Правила построения аналитических таблиц:

T˄ {T(a˄b)} F˄ {F(a˄b)}
{Ta, Tb} {Fa}, {Fb}
T˅ {T(a˅b)} F˅ {F(a˅b)}
{Ta}, {Tb} {Fa, Fb}
T⊃ {T(a⊃b)} F⊃ {F(a⊃b)}
{Fa}, {Tb} {Ta, Fb}
T¬ {T¬a} F¬ {F¬a}
{Fa} {Ta}
T∃ {T∃xA(x)} F∃ {F∃xA(x)}
{TA(β)} {F∃xA(x), FA(β)}
T∀ {T∀xA(x)} F∀ {F∀xA(x)}
{T∀xA(x)}, TA(β)} {FA(β)}

Правила секвенциального исчисления:

Логические правила

˄L Г, A ⊦ Δ ˅R Г ⊦ A, Δ
Г, A˄B ⊦ Δ Г ⊦ A˅B, Δ
˅L Г, A ⊦ Δ | Σ, B ⊦ Π ˄R Г ⊦ A, Δ | Σ ⊦ B, Π
Г, Σ, A˅B ⊦ Δ, Π Г, Σ ⊦ A˄B, Δ, Π
⊃L Г ⊦ A, Δ | Σ, B ⊦ Π ⊃R Г, A ⊦ B, Δ
Г, Σ, A⊃B ⊦ Δ, Π Г ⊦ A⊃B, Δ
¬L Г ⊦ A, Δ ¬R Г, A ⊦ Δ
Г, ¬A ⊦ Δ Г ⊦ ¬A, Δ
∀L Г, A[x/t] ⊦ Δ ∀R Г ⊦ A[x/y], Δ
Г, ∀tA ⊦ Δ Г ⊦ ∀yA, Δ
∃L Г, A[x/y] ⊦ Δ ∃R Г ⊦ A[x/t], Δ
Г, ∃yA ⊦ Δ Г ⊦ ∃tA, Δ

Структурные правила:

WL Г ⊦ Δ WR Г ⊦ Δ
Г, A ⊦ Δ Г ⊦ A, Δ
CL Г, A, A ⊦ Δ CR Г ⊦ A, A, Δ
Г, A ⊦ Δ Г ⊦ A, Δ
PL Г1, A, B, Г2 ⊦ Δ PR Г ⊦ Δ1, A, B, Δ2
Г1, B, A, Г2 ⊦ Δ Г ⊦ Δ1, B, A, Δ2
I (аксиома) CUT (сечение) Г ⊦ Δ, A | A, Σ ⊦ Π
A ⊦ A Г, Σ ⊦ Δ, Π

Правила вывода в модальной логике:

Правила первого рода:

  1. □A→A – правило удаления необходимости (У□)
  2. A→ ◊A –- введение возможности (В◊)
  3. ¬□A→¬◊A – отрицание необходимости (О□)
  4. ¬◊A→□¬A – отрицание возможности (О◊)
  5. □(A˄B)→□A˄□B – введение необходимости в конъюнкции (В□˄)
  6. □A˄□B→□(A˄B) – удаление необходимости из конъюнкции (У□˄)
  7. ◊(A˅B)→ ◊A˅◊B – введение возможности в дизъюнкцию (В◊˅)
  8. ◊A˅◊B→◊(A˅B) – удаление возможности из дизъюнкции (У◊˅)
  9. □A˅□B→□(A˅B) – удаление необходимости из дизъюнкции (У□˅)
  10. ◊(A˄B)→◊A˄◊B – введение возможности в конъюнкцию (В◊˄)
  11. □(A⊃B)→□A⊃□B – введение необходимости в импликацию (В□⊃)
  12. □A→□□A – введение дополнительной необходимости (В□□)
  13. □∀xA(x)→∀x□A(x) – перестановка необходимости от всеобщности (∀□)
  14. ∀x□A(x)→□∀xA(x) – перестановка необходимости к всеобщности (□∀)
  15. ◊∃xA(x)→ ∃x◊A(x) — перестановка возможности от существования (∃◊)
  16. ∃x◊A(x)→◊ ∃xA(x) – перестановка возможности к существованию (◊∃)
  17. ◊A→□◊A – введение необходимости возможности (В□◊)
  18. ◊A, □B→◊(A˄B) — замена необходимости на возможность (З□◊)
  19. (A↔B)→□(A↔B) – введение необходимой эквивалентности (В□↔)
  20. □(A↔B)→(A↔B) – удаление необходимой эквивалентности (У□↔)

Правило второго рода:

A→□A – правило введения необходимости (В□) – правило Гёделя

В другом написании:

У□ □A В◊ A О□ ¬□A О◊ ¬◊A
A ◊A ¬◊A □¬A
В□˄ □(A˄B) У□˄ □A˄□B В◊˅ ◊(A˅B) У◊˅ ◊A˅◊B
□A˄□B □(A˄B) ◊A˅◊B ◊(A˅B)
У□˅ □A˅□B В◊˄ ◊(A˄B) В□⊃ □(A⊃B) В□□ □A
□(A˅B) ◊A˄◊B □A⊃□B □□A
∀□ □∀xA(x) □∀ ∀x□A(x) ∃◊ ◊∃xA(x) ◊∃ ∃x◊A(x)
∀x□A(x) □∀xA(x) ∃x◊A(x) ∃xA(x)
В□◊ ◊A З□◊ ◊A, □B В□↔ A↔B У□↔ □(A↔B)
□◊A ◊(A˄B) □(A↔B) A↔B
ПГ A
□A

Эквивалентности модальной логики:

□A⇔¬◊¬A

◊A⇔¬□¬A

∇A⇔◊A˄◊¬A

Отрицания в модальной логике:

¬□А⇔◊¬ A;

¬◊A⇔□¬А;

¬∇А⇔□А∨□¬A