Реферат: Исчисление высказываний

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. Некоторые приёмы доказательства.

Дедуктивный вывод.