Исчисление высказываний
![]()
![]()
Удаление Þ
p
![]()
(Modus ponens)
![]()
Øq
![]()
(Modus tollens)
![]()
[p]
![]()
1.
2.
p
![]()
![]()
p
![]()
1.
2.
![]()
![]()
1.
2.
![]()
![]()
[p] [q]
![]()
r
Доказательство в исчислении высказываний есть по существу последовательность преобразований высказывания р с целью показать, что р общезначимо. Каждый шаг в доказательстве есть либо уже доказанное высказывание, либо высказывание, истинное по предположению и вводимое для последующих шагов. Каждый шаг , который является предположением, заключается в скобки [ ]. Все другие шаги должны быть доказаны. Последним шагом в доказательстве должно быть само высказывание р.
Докажем высказывание ![]()
[p]
p
Правило
I
Первым шагом мы делаем предположение, что р - общезначима. Тогда второй шаг
непосредственно следует из первого. Раз мы предположили общезначимость р на
первом шаге, то мы используем этот факт на втором. На третьем шаге мы
используем правила вывода I, которое устанавливает общезначимость высказывания
.
Доказательство с помощью правил вывода гибче, чем доказательство с помощью таблицы истиности. В первом случае мы можем проанализировать каждый шаг в цепочке доказательства. В то же время, неограниченный рост таблицы истиности не позволят нам этого сделать.
Присмотревшись внимательно к правилам вывода, можно увидеть, что они хорошо
согласуются с нашей интуицией. Например, возьмём правило VIII. Если на предыдущих
шагах была доказана общезначимость высказываний p и q, то очевидно что высказывание
- тоже общезначимо.
Итак, в дальнейшем при доказательстве мы будем использовать либо правила эквивалентности (в этом случае каждый шаг будет замещением правого вхождения в высказывании на левую часть правила) либо правила вывода.
5.2.4. Некоторые приёмы доказательства.
Дедуктивный вывод.
Доказать ![]()
[p] - Предположение
[q] - Предположение
р - 1.
- I, 2, 3
- I, 1, 4
Мы предположили общезначимость утверждений p и q и воспользовавшись правилом I. введение
.
Использование правила Моdus Рonens. Это правило хорошо работает когда надо доказать высказывания типа “Если в этом кинотеатре дают “Анаконду”, то я куплю билеты.” Если кто-то сделал это утверждение и вы увидели, что в кинотеатре идет “Анаконда”, то вы можете заключить, что этот человек купил билеты.
Доказать ![]()
- Предположение
- IX. Удаление
, 1
r
- IX. Удаление
, 1
р - III. Моdus Рonens, 2, 3
p
q
- IX. Удаление
, 1
q - III. Моdus Рonens. 4, 5
- I. Введение
, 1, 6
Использование Моdus Tollens.
Доказать ![]()
- Предположение
p
q - IX. Удаление
, 1
Øq
- IX. Удаление
, 1
Øp - III.2. Modus Tollens, 2, 3
- I. Введение
, 1, 4
Использование Введения Ø и Удаления Ø .
Докажем ![]()
-
Предположение
p
q - IX. Удаление
, 1
Øq
- IX. Удаление
, 1
[p] - Предположение
q - III. Моdus Ðonens, 4, 2
Øq - 3
F
- VI. Удаление
, 5, 6
Øp - V. Введение Ø 4, 7
- I. Введение Ø 1, 8
Доказательство от противного.
На использовании правила V. Введение Ø основан часто используемый прием доказательства - доказательство от противного. Мы его уже использовали несколько раз. Его идея состоит в следующем.
Пусть мы хотим доказать общезначимость высказывания Q :
“Треугольник со сторонами 2, 3, 4 - не прямоугольный.”
Предположим, что ØQ - общезначимо, т.е треугольник со сторонами 2, 3, 4 - прямоугольный. Тогда, используя теорему Пифагора, мы можем утверждать, что 4+9=16 , но 4+9 ¹ 16. Отсюда, используя правило VI.1 Удаление Ø , получаем F. Имея F и предположение об общезначимости ØQ, с помощью правила V, получаем общезначимость Ø(ØQ). Откуда, с использованием правила VII из таблицы 5.8., получаем общезначимость Q.
Доказать ![]()
- Предположение
- Закон импликации V.1, 1
- Закон Де Моргана IV.1
Øq
- IX.2. Удаление
, 3
- IX.1. Удаление
, 3
- IX.1. Удаление
, 5
p
- IX.2. Удаление
, 6
q - III.1. Моdus Рonens, 6, 7
F - V.1 Удаление Ø , 4, 8
- V. Введение Ø , 1, 9
Пример.
Во вторник, когда случилось ограбление, либо Петров был в операционном зале банка, либо Сидорова в бухгалтерии банка. Петрова никогда не видели в операционном зале без Иванова. Иванов покидал банк во вторник только когда он с Сидоровой ездил на встречу с клиентами. Если в ограблении участвовал Ерошкин, Иванова не было бы в банке. Ограбление произошло во вторник. Мог ли Ерошкин быть грабителем?
Обозначим:
p= Петров был в операционном зале;
q= Cидорова была в бухгалтерии;
s= Иванов был в операционном зале;
h= Ерошкин участвовал в ограблении;
u= Ограбление случилось во вторник.
Тогда исходные утверждения можно записать так:
uÞ(pÚq)
pÞs
ØsÞØq
hÞØs
u
Из 1, 5 п. Modus ponens получаем pÚq
Предположим [q]
Из 3, 7 п. Modus Tollens получаем s
Из 7, 8 и “введение Þ“получаем qÞs
Из 4, 10 п. Modus Tollens Øh
Итак, Ерошкин не мог участвовать в ограблении.