Логика высказываний (158493)

Посмотреть архив целиком

















ЛОГИКА ВЫСКАЗЫВАНИЙ



Важнейшей функцией логики является установление того, что из чего следует, а значит установление того, какие формулы являются теоремами, а какие нет. Это достигается с помощью аксиоматического метода. При аксиоматическом построении исчисления высказываний выбирают некоторое, небольшое количество формул, которые включают в систему без доказательства. Это аксиомы системы. Остальные формулы могут быть присоединены к системе только тогда, когда они следуют из аксиом или являются определениями. Существует много эквивалентных систем исчисления высказываний, различающихся аксиомами и исходными терминами. Здесь мы опишем систему Д. Гильберта и В. Аккермана. В исчислении высказываний определение формулы такое же, как и в алгебре высказываний.

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


  1. р qр

  2. р р q

  3. р q q  р

  4. (р q) ( r р  r q)

В этой системе принимаются три определения:


Д1 φ  ψ ≡φ →ψ

df

______

Д2 φ  ψ ≡φψ

df

Д3 (φ ≡ ψ) ≡ (φ →ψ)  (ψ →φ)

df


Здесь символ «» означает равносильные по определению.

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

α) Правило подстановки.

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

β) Схема заключения.

Из двух формул φ и φ → ψ получаем новую формулу ψ.

Из сформулированных правил и аксиом можно вывести новые правила вывода формул.

ПРАВИЛО I. Если φ  φ – доказуемая формула, то доказуема также формула φ.

Доказательство: Подставим в α) формулу φ. Получим φ  φ→ φ. Поскольку φ  φ доказуемая формула, то, по правилу β) доказуема и формула φ.

ПРАВИЛО II. Если φ – доказуемая формула, а ψ – любая другая формула, то формула φ  ψ является также доказуемой.

Доказательство: Подставим в в) вместо р формулу φ, а вместо q - формулу ψ. Получаем φ  φ  ψ. Схема заключения дает φ  ψ.

ПРАВИЛО III. Если φ ψ – доказуемая формула, то доказуема и формула ψ φ.

Доказательство: Получаем из с) заменой р на φ, q на ψ и применяем схемы заключения.

ПРАВИЛО IV. Если φ→ ψ доказуемая формула, то формула γφ→ γ  ψ также доказуема.

Доказательство : Получаем из α) заменой р на φ, q на ψ, r на γ и применяем схемы заключения.

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

Докажем, например, формулу:


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


Доказательство: Заменим в d) r наr. Получаем (p→q)→ ((rp)→(rq)), но по Д1 эта формула есть иная запись доказываемой формулы.

Доказательство: Подставим в формулу вместо р формулу ψ, вместо q формулу γ, вместо r формулу φ. Получаем: (ψ → γ )→(( φ→ ψ)→( φ→ γ)) .

Применяя два раза схему заключения, получаем: φ→ γ.

Легко доказать, что в предложенной аксиоматической системе выводимы формулы алгебры высказываний. Докажем например, что формула рp выводима.

Доказательство: Подставляем в в) вместо q переменную р , получаем формулу р→ рp. Из а) той же подстановкой получаем рp→ р. По правилу У выводим формулу p→ р. По Д1 эта формула представляет собой иную запись формулырp.

Аналогичным образом можно доказать остальные формулы алгебры высказываний.

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

Система исчисления высказываний может быть построена методом допущений. Этот метод ближе к обычным содержательно очевидным представлениям в том отношении, что доказательства в системах, построенных этим методом, почти не отличаются от математических доказательств и от рассуждений в других науках. Здесь оно излагается по книге Е. Слупецкого, Л. Борковского «Элементы математической логики и теории множеств».

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

  1. Правило отделения (обозначает ПО):


ПО φ→ ψ

;


Читается эта схема так: «Если в доказательстве имеются уже формула φ→ ψ и формула φ независимо от порядка, в каком эти формулы входят в доказательство, то к доказательству можно присоединить в качестве строки и формулу ψ».

  1. Правило введения конъюнкции


ВК φ

;


Способ чтения этой схемы аналогичен.


  1. Правило удаления конъюнкции:


УК ,


Правило УК можно записать в виде одной схемы:


УК

Ψ

Правило введения дизъюнкции:


ВД ,


  1. Правило удаления дизъюнкции:


УД φ ψ φ ψ

,


  1. Правило введения эквивалентности:


ВЭ φ→ ψ


6)Правило удаления эквивалентности:


УЭ ,


Прямое доказательство выражения φ1 →(φ2→( φ3→ …(φп-1 →φп)…) строится следующим образом:

              1. В первых n-1 строках выписываются последовательно выражения φ1, φ2,… φп-1 в качестве условий теоремы.

              2. К доказательству можно присоединить:

  1. ранее доказанные теоремы в качестве новых строк;

  2. новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

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

Косвенное доказательство выражения φ1 →(φ2→( φ3→ …(φп-1 →φп)…) строится следующим образом:

  1. а) В первых n-1 строках выписываются последовательно выражения φ1, φ2,… φп-1 в качестве условий теоремы.

  1. В n-ой строке выписывается выражениеφп в качестве допущения косвенного доказательства.

  1. К доказательству можно присоединить:

  1. ранее доказанные теоремы в качестве новых строк;

  2. новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

  1. Доказательство закончено, если в нем имеются две противоречащие строки. Окончание доказательства отмечается написанием в последней ненумерованной строке выражения «ПРТВРЧ» (сокращение слова «противоречие») с указанием справа номеров двух противоречащих строк.

Продемонстрируем приемы доказательства на ряде примеров. Их мы будем нумеровать с указанием слева Ті ( теорема номер і )

Т1 (Закон гипотетического силлогизма)


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


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


  1. p→q

  2. q → r Допущения

  3. р

  4. q ПО : 1,3

r ПО : 2,4

Т2 (Закон контрапозиции)


(p→q)→( q →р) (30)

  1. p→q Допущения

  2. q

  3. p Допущения косвенного доказательства

  1. q ПО : 1,3

ПРТВРч  2,4


Т3 (Второй закон гипотетического силлогизма)


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


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


  1. p→q

  2. q → r Допущения

  3. р

  4. q ПО : 1,3

r ПО : 2,4


Т4 ( Закон экспортации)


(pq → r) →(р→(q → r)) (32)

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


  1. pq → r

  2. р Допущения

  3. q

  4. pq ВК : 2,3

r ПО : 2,4

Т5

(p→q)( р → r) →(p→q  r) (32 )


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


  1. (p→q)( р → r) Допущения

  2. р

  3. p→q УК : 1 q  r

  4. р → r

  5. q ПО : 2,3

  6. r ПО : 2,4

q  r ВК : 5,6


Докажем теперь аксиомы a), b), c), d):


  1. pq→р


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


1) pq Допущения

р УД : 1


  1. р→ pq

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

1) p Допущения

рq ВД : 1


pq→ qр


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


1) pq Допущения

2) qр Допущения к.д.

ПРТВВРч 1, 2

  1. (р→ q) → (rр→ rq)


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


  1. р→ q Допущения

  2. rр

  3. р УД : 2

  4. q ПО : 1, 3

rq ВД : 4


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


Случайные файлы

Файл
104273.rtf
22464-1.rtf
47452.rtf
32795.rtf
10469.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.