Исчисление высказываний

Исчисление высказываний

Исчисление высказываний

III.

Удаление Þ

p

IV. Удаление Û 1.

Исчисление высказываний

(Modus ponens)

1.

Исчисление высказываний

2.

Øq

Исчисление высказываний

(Modus tollens)

2.

Исчисление высказываний

V. Введение Ø VI. Удаление Ø 1.

[p]

Исчисление высказываний

1.

2.

p

Исчисление высказываний

Исчисление высказываний

VII. Введение Ù VIII. Введение Ú 1.

p

Исчисление высказываний

1.

2.

Исчисление высказываний

Исчисление высказываний

IX. Удаление Ù X. Удаление Ú

1.

2.

Исчисление высказываний

Исчисление высказываний

1.

            [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

Итак, Ерошкин не мог участвовать в ограблении.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: