Т. А. Сливина математическая логика и теория алгоритмов

§5. Доказательство некоторых законов логики

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

1. Закон перестановки посылок:
├ (1)
Доказательство: Так как из совокупности формул Н = {х(уz),у,х следует вывод х(уz), у, х, у  z, z, то из совокупности Н выводима формула z. Тогда по обобщенной теореме дедукции доказуема формула (1).
Из закона перестановки посылок вытекает правило перестановки посылок в доказуемых формулах:
Если ├ , то ├
Действительно, если ├ (2)
то из формул (1) и (2) по правилу заключения следует, что ├ .
2. Закон соединения посылок:
├ (3)
Доказательство: Так как из совокупности формул Н =  , } следует вывод , , , , , х, у, уz, z, то из совокупности Н выводима формула z. Тогда по обобщенной теореме дедукции доказуема формула (3).
Из закона соединения посылок вытекает правило соединения посылок в доказуемых формулах: Если ├ , то ├
Действительно, если ├ (4),
то из формул (3) и (4) по правилу заключения следует
├
3. Закон разъединения посылок
(5)
Доказательство: Так как из совокупности формул Н = {х, у, } следует вывод х, у, , , z, то из совокупности формул Н выводима формула z. Тогда по обобщенной теореме дедукции доказуема формула (5).
Из закона разъединения посылок вытекает правило разъединения посылок в доказуемых формулах: Если ├ , то ├ .
Действительно, если
├ (6)
то из формул (5) и (6) по правилу заключения следует ├ .
4. (7)
Доказательство: Сделаем подстановки в аксиомы I₁ и IV₁
и
В результате получим доказуемые формулы
├ (8)
├ (9)
Из формул (8) и (9) по правилу силлогизма следует ├ .
Используя закон соединения посылок, получим ├ .
Используя правило снятия двойного отрицания, получим ├ .
И, наконец, применяя закон разъединения посылок, получим формулу (7).