Задачник-практикум по исчислению высказываний

Оглавление

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

2. Система аксиомных схем 2

3. Правило вывода Modus ponens 3

4. Формальное доказательство и формальный вывод 3

5. Свойства отношений выводимости 7

6. Применение метода доказательства теоремы дедукции для преобразования данного вывода в результирующий вывод. 8

7. Установление доказуемости формул 10

8. Правила введения и удаления логических операторов 11

9. Использование правил введения и удаления и МТ1 при установлении существования доказательств и выводов в теории L. 12

Контрольные вопросы 14

Задания для самостоятельного выполнения 15

Литература 19

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

Исчисление, основанный на чётко сформулированных правилах формальный аппарат оперирования со знаками определённого вида, позволяющий дать исчерпывающе точное описание некоторого класса задач, а для некоторых подклассов этого класса (лишь для наиболее простых исчислений, совпадающих с ним) - и алгоритмы решения. С развитием математической логики возникла потребность в общей теории исчисления и в уточнении самого понятия исчисление, которое подверглось более последовательной формализации. Представление об исчислении (идущее от Д. Гильберта) заключается в следующем. Рассматривается некоторый алфавит, из элементов которого, именуемых буквами, с помощью четко сформулированных правил образования строятся формулы рассматриваемого исчисления (называемые также иногда словами, или выражениями). Некоторые из таких («правильно построенных») формул объявляются аксиомами, а из них с помощью правил преобразования (или, иначе, правил вывода) «выводятся» новые формулы, называемые теоремами данного исчисления, т. е. добавление к алфавиту и правилам образования аксиом и правил ввода даёт формальную систему.

Исчисление высказываний - раздел математической логики, в котором формально-аксиоматическим методом изучаются сложные (составные) высказывания, составленные из простых (элементарных, не анализируемых) высказываний с помощью логических связок «и», «или», «если..., то» и «неверно, что». Некоторые формулы принимаются в качестве аксиом, которые являются тавтологиями, а с помощью правила вывода modus ponens из истинных высказываний можно получить только истинные. Все остальные тавтологии можно получить из аксиом с помощью правила вывода ­- это так называемая теорема полноты логики высказываний.

2. Система аксиомных схем

Определение 1. Аксиомами теории L назовем всякие формулы, которые порождают нижеследующие формульные схемы при любом выборе формул А, В, С:

1. A  (B  A)

2. (А  В)  ((A  (В  С))  (А  С))

3. A  (B A  B)

4. A  B  A

5. A  B  B

6. A  A  B

7. B  A B

8. (А  C)  ((B  C)  ( A  B  С))

9. (А  B)  ((A   B)   A)

10.   A  A

11. (А  B)  ((B  A)  ( A  B ))

12. ( A  B )  (А  B)

13. ( A  B )  (B  A)

Каждая из схем (1)-(13) порождает счетное множество аксиом, если символы А, В, С заменять конкретными формулами. Поэтому записи (1)-(13) будем называть аксиомными схемами (АС).

Схемы (1)-(13) совпадают с первыми тринадцатью формульными схемами предложения 1.6.