Признак равносильности формул 4 страница

(1) (в аксиоме (А2) мы подставили вместо формул А, В, С соответственно формулы ;

(2) (в аксиоме (А1) вместо формулы В подставлена формула );

(3) (из (1) и (2) по правилу МР)

(4) (в аксиоме (А1) вместо В подставлена формула А);

(5) (из (3) и (4) по МР).

Пример 2.Покажем, что ├ .

(1) (гипотеза);

(2) (гипотеза);

(3) (подстановка в аксиому (А1) вместо формул А, В соответственно формул );

(4) (Аксиома (А2));

(5) (из (1) и (3) по правилу МР);

(6) (из (4) и (5) по правилу МР);

(7) (из (1) и (6) по правилу МР).

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

Теорема 1.Если F₁, ..., F_n–1, F_n ├ G, то F₁, ..., F_n–1 ├ F_n G. В частности, если F ├ G, то ├ F G.

Рассмотрим несколько примеров, где используется теорема о дедук­ции.

Пример 3.Покажем, что ├ .
Покажем сначала, что А├С.

(1) В (гипотеза);

(2) А (гипотеза);

(3) (гипотеза);

(4) (из (2) и (3) по МР);

(5) С (из (1) и (4) по правилу МР).

Итак, А├С, отсюда на основании теоремы о де­дукции заключаем, что ├ .

Пример 4. Покажем, что ├ .
Установим сначала, что А├С.

(1) (гипотеза);

(2) (гипотеза);

(3) А (гипотеза);

(4) В (из (1) и (3) по правилу МР);

(5) С (из (2) и (4) по правилу МР).

Поскольку А├С, то на основании теоремы о дедук­ции мы заключаем, что ├ .

Пример 5. Покажем, что формула является теоремой. Покажем сначала, что А ├ В.

(1) (гипотеза);

(2) А (гипотеза);

(3) (аксиома (A3));

(4) (из (1) и (3) по правилу МР);

(5) (аксиома(А1));

(6) (из (4) и (5) согласно примеру 4);

(7) (из (2) и (6) согласно правилу МР).

Итак, А ├ В. Применив теперь дважды теорему о дедук­ции, получаем требуемый результат.

Отметим ряд важнейших свойств аксиоматической теории высказы­ваний: полноту, разрешимость, непротиворечивость.

Теорема 2. (о полноте аксиоматической теории высказываний). Формула тогда и только тогда является теоремой аксиоматической теории высказываний, когда она является тавтологией алгебры вы­сказываний.

Определение 5. Аксиоматическая теория называется непротиворе­чивой, если ни для какого утверждения А, сформулированного в терминах этой теории, само утверждение А и его отрицание не могут быть теоремами данной теории. Если для некоторого утвер­ждения А теории оба утверждения А и – теоремы этой теории, то аксиоматическая теория называется противоречивой.

Заметим, что в противоречивой аксиоматической теории любая формула является теоремой.

Теорема 3. Аксиоматическая теория высказываний есть непротиво­речивая аксиоматическая теория.

Определение 6.Аксиоматическая теория называется разрешимой, если существует алгоритм, позволяющий для любой формулы этой теории, ответить на вопрос, будет или нет эта формула теоремой этой теории.

Так как, используя таблицу истинности, мы можем для данной фор­мулы эффективно определить, является ли она тавтологией или нет, то, как следствие теоремы 2, получаем следующие утверждение.

Теорема 4.Аксиоматическая теория высказываний есть разрешимая аксиоматическая теория.

Введем следующую важную характеристику аксиом аксиоматиче­ской теории.

Определение 7. Аксиома А данной аксиоматической теории называ­ется независящей от остальных аксиом этой теории, если она не может быть выведена с помощью пра­вил вывода из всех остальных аксиом. Система аксиом аксиоматиче­ской теории называется независимой, если каждая ее аксиома не за­висит от остальных.

Теорема 5. Система аксиом (А1), (А2), (АЗ) аксиоматической теории высказываний независима.

Упражнение. Используя результаты настоящего раздела показать, что следующие формулы являются теоремами аксиомати­ческой теории высказываний:

(1) ; (3) ;

(2) ; (4) .

4. ПРАВИЛО РЕЗОЛЮЦИЙ

Автор данного правила – американский математик Робинсон, 1965 год.

Правило резолюций: .
Введем новые понятия. Атом – это логическая переменная. Под дизъюнктом понимается элементарная дизъюнкция, то есть это дизъюнкция различных атомов или их отрицаний.

Это правило позволяет соединить две формулы, в одной из которых находится атом ( , а в другой отрицание атома ( . Получается новая формула без этого атома.

Доказательство. В логике высказываний имеет место тавтология:

По теореме о равносильных утверждениях отсюда получаем

.

Частные случаи:1)
­ 2)
3) , где □ – пустой дизъюнкт (т.е. ложь).