Конструктивный метод доказательства логических выражений

Пример 6.2.

Имеется клауза

. (6.5)

Доказать ее справедливость.

Решение. Преобразуем ее к другому виду: и упростим , получили сразу аксиому порядка вида (6.4).

Доказанная элементарная клауза (6.5) известна еще со времен Аристотеля и имеет очень важное значение в логике высказываний. У нее даже есть специальное латинское название – modus ponens – правило отделения. Если в процессе доказательства справедливости какой-либо сложной клаузы удалось свести ее к клаузе (6.5), то считается, что доказательство состоялось.

Закон антисимметричности (если , то ) фактически определяет правила действия по переносу объектных высказываний относительно символа метаимпликации «». Два других закона отношения порядка сводятся к аксиоме порядка.

Закон рефлексивности () путем использования закона о единице () может быть записан так:

,

что является частным случаем аксиомы порядка (6.5).

Закон транзитивности (если и , ) также может быть представлен в другой форме

,

которую можно доказывать путем сведения ее к аксиоме порядка. Доказательство ведем следующим образом:

1) перенесем А влево за знак метаимпликации

;

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

;

3) затем еще раз воспользуемся этим же правилом, но для третьей посылки и вновь полученной, что приведет нас к аксиоме порядка в форме

.

Таким образом, закон транзитивности доказан.

Теперь убедимся в истинности тавтологии:

.

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

1) проведем эквивалентное преобразование

;

2) воспользуемся правилом отделения

;

3) еще раз воспользуемся правилом отделения и придем к аксиоме порядка в форме предыдущего примера.

Докажем справедливость клаузы, которая построена на основе тождественного закона склеивания:

.

После эквивалентных преобразований

она сводится к закону рефлексивности, то есть к частному случаю аксиомы порядка, рассмотренному выше.

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

1. ,

2. ,

3. ,

4. ,

5. , .

Первая из аксиом является нашей аксиомой порядка. Вторая «аксиома» доказана нами выше. Остальные «аксиомы» представляют собой тождества логики Буля, записанные в форме клауз.

Позднее Я. Лукасевич уменьшил число аксиом в системе Фреге до трех

1. ,

2. ,

4. .

Вместо третьей «аксиомы» в современной логике часто используют «аксиому» вида

,

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

отношения порядка;

коммутативности;

ассоциативности;

дистрибутивности;

нуля и единицы.

Необходимо отметить, что метадизъюнкция «;» не может разделять две различные посылки, а метаконъюнкция «,» - два различных заключения; это приводит к невозможности использовать аппарат логики высказываний.

Конструктивный метод доказательства логических выражений основан на таблицах истинности и является противоположным аксиоматическому.

Для его понимания достаточно составить таблицу истинности для какого-нибудь примера. Пусть имеется следующая легенда:

«Кассир Сидорова сказала, что она видела водителя контейнеровоза Иванова в комнате отдыха. Эта комната, по ее словам, находится рядом с помещением склада готовой продукции. Стреляли в складе. Водитель заявил, что он никаких выстрелов не слышал. Вывод следователя: если кассир говорит правду, то водитель вводит следствие в заблуждение; не могут кассир и водитель одновременно говорить правду».

Введем обозначения для высказываний:

А = «Кассир сказала правду»,

В = «Водитель находится в комнате отдыха»,

С = «Комната отдыха находится вблизи склада»,

D = «Водитель слышал выстрелы»,

Е = «Водитель сказал правду».

Посылки следователя:

«Если кассир сказала правду, то водитель находился в комнате отдыха»

.

«Если водитель находился в комнате отдыха, то он должен был слышать все, что делается на складе»

.

«Если он имел возможность слышать, что делается на складе, то он слышал и выстрелы»

.

«Если верить водителю, то он не слышал выстрелов»

.

Заключение следователя:

«Водитель меня обманывает при условии, что кассир говорит правду»

«Кассир и водитель одновременно говорят правду»

.

Формальная запись легенды записывается как метаконъюнкция всех посылок

.

Для доказательства истинности следствия аксиоматическим методом необходимо воспользоваться тождеством

и затем применить трижды закон транзитивности.

Заключение ошибочно, так как

,

что означает

или ,

а это противоречит аксиоме порядка (6.4).

Составим теперь таблицу истинности (табл.6.1), в которой под Р понимается конъюнкция всех Р_i.

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

Это требование выполняется для следствия , так как

.

Для оно не выполняется, так как и

С помощью скорректированных данных таблицы 6.1 можно установить справедливость тавтологии, составленной из этих же посылок:

Таблица 6.1

Таблица истинности, иллюстрирующая конструктивный

Дата добавления: 2017-02-01