Аксиоматическое исчисление высказываний

Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

;

;

;

;

;

;

;

;

;

;

.

вместе с двумя правилами вывода:

· Правило Modus Ponens (МР) – правило отделения, известное со времен Аристотеля:

· Правило подстановки:

Если в процессе доказательства удается свести сложную клаузу к MP, считают, что доказательство состоялось. Такой способ доказательства называется аксиоматическим. Исторически первой была система аксиом, предложенная Г. Фреге:

Исторически первой аксиоматической системой классической логики была система, предложенная Г. Фреге, содержащая пять аксиом:

1. ├
2. ├
3. ├
4. ├
5. ├ ├

Позднее Я. Лукасевич уменьшил число аксиом в системе Фреге до трех. Схемами аксиом являются следующие схемы формул:

– утверждение посылки;

– контрапозиция

Доказательства в PL. Аксиоматический метод

В логике PL утверждение, которое требуется доказать, оформляется в виде причинно-следственного отношения «если …, то …» и записывается в виде

Выражения такого вида называются клаузами. Клауза – это метапредложение, в котором использовано отношение порядка, оформленное в виде символа , который имеет смысл импликации. Если вместо букв в клаузе использовать конкретные высказывания, то клауза наполняется конкретным содержанием – семантикой (легендой).

· Доказательство аксиоматическим методом состоит из следующих этапов:

· Назначается некоторое множество аксиом, исходя из формулировки поставленной задачи.

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

· К имеющимся и вновь полученным правилам применяется правило МР до тех пор, пока не будет выведена секвенция, общезначимость которой требуется доказать.

Пример.

Доказать общезначимость:

1. Применим к аксиоме А1 правило подстановки

2. Применим к (1) аксиому А2:

3. Применив к (1) и (2) правило МР, получим новую тавтологию:

4. Применив к (3) аксиому А1 и правило МР, получим желаемый результат

Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

Дата добавления: 2014-11-08; просмотров: 887; Нарушение авторских прав

Мы поможем в написании ваших работ!