Навигация
Доказательство: правила вывода
24949
знаков
11
таблиц
0
изображений
5.2.3. Доказательство: правила вывода.
Основной целью всякого рассуждения является установление истины в форме некоторого общезначимого утверждения, т.е. тавтологии. Для простых случаев, у нас есть метод таблиц истиности. Однако, он становится громоздким при числе переменных больше четырех.
Есть другой метод, называемый доказательством, который представляет собой последовательность логических выводов, правильность каждого из которых строго логически обоснован. Таким образом, рассуждение в этом методе принимает форму последовательности логических выводов.
Процесс доказательства, по существу, является развитием метода, который мы использовали для упрощения высказываний. Однако, доказательство включает важный дополнительный компонент: вывод из предположения. Вывод в доказательстве основан на небольшом числе правил вывода, корректность которых вне сомнений. Эти правила устанавливают, что одни высказывания могут следовать из других, истиность которых либо уже была установлена, либо считаются таковыми по предположению. Эти правила приведены в таблице 5.10.
Таблица 5.10.
Правила вывода
| I. | Введение Þ | II. | Введение Û |
| [p] | pÞq | ||
|
|
| ||
| 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, то очевидно что высказывание 
- тоже общезначимо.
Итак, в дальнейшем при доказательстве мы будем использовать либо правила эквивалентности (в этом случае каждый шаг будет замещением правого вхождения в высказывании на левую часть правила) либо правила вывода.
Похожие работы
... , которые используются при доказательстве теорем вручную, системы автоматического доказательства для фразовых форм используют единственное правило вывода — принцип резолюций, — впервые описанное Робинсоном ([Robinson, 1965]). Рассмотрим следующий пример из исчисления высказываний. В дальнейшем прописными буквами Р, Q, R,... будут обозначаться отдельные фразы, а строчными греческими U, ф и £ ...
... р {Допущение} 2) рÚ F(х) {ВД: 1} "х рÚ F(х) {В": 2} Докажем теперь формулу (38): "х F(х) ®$х F(х) Доказательство: 1) "х F(х) {Допущение} 2) F(у) {У": 1} $х F(х) {В$: 2} 5. ПОГРУЖЕНИЕ АРИСТОТЕЛЕВСКОЙ СИЛЛОГИСТИКИ В УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ В логике Аристотеля и его последователей вплоть до конца ХІХ столетия основная роль приписывалась четырем видам ...
... ; В) — при любой расстановке скобок в конъюнкции согласно правилам построения формул. В связи с отмеченной неразрешимостью логики предикатов особое значение приобретает здесь формализация понятий следования и закона логики посредством построения логических исчислений. Именно исчисление дает возможность во многих случаях синтаксическим образом решать вопрос, является ли некоторая формула законом, ...
... нормальная форма какой-то формулы. Она удовлетворяет условиям: a) в ней нет двух одинаковых конъюнкций; b) ни одна конъюнкция не содержит двух одинаковых дизъюнкций; c) ни одна конъюнкция не содержит переменного высказывания вместе со свои отрицанием; d) в каждой конъюнкции содержится в качестве дизъюнктивных членов все переменные входящие в формулу. Правила приведения пр
0 комментариев