Т. А. Сливина математическая логика и теория алгоритмов

ИСЧИЛЕНИЕ ВЫСКАЗЫВАНИЙ

В алгебре высказываний, мы пользовались логическими значениями высказываний (истина, ложь). Но понятия истинности и ложности не математические. Эти понятия во многих случаях субъективны и скорее относятся к философии.

Учитывая это построим математическую логику, не пользуясь понятиями истинности и ложности. Необходимо также при этом построении не применять самих законов логики.
Исчисление высказываний – это аксиоматическая логическая система, интерпретацией которой является алгебра высказываний.
§ 1. Этапы построения исчисления высказываний. Понятие формулы исчисления высказываний
Описание всякого исчисления включает в себя описание символов этого исчисления (алфавита), формул, являющихся конечными конфигурациями символов, и определение выводимых формул.
Алфавит исчисления высказываний состоит из символов трех категорий:
1. Символы первой категории: х, у, z, ... x₁, х₂, ... . Эти символы будем называть переменными высказываниями.
2. Символы второй категории: v, &, , – . Они носят общее название логических связок. Первый из них – знак дизъюнкции или логического сложения, второй – знак конъюнкции или логического умножения, третий – знак импликации или логического следования и четвертый – знак отрицания.
3. Третью категорию составляет пара символов ( ), называемая скобками.
Других символов исчисление высказывания не имеет. Формулы исчисления высказываний представляют собой последовательности символов алфавита исчисления высказываний. Для обозначения формул будем пользо­ваться большими буквами латинского алфавита. Эти буквы не являются символами исчисления. Они представляют собой только условные обозначения формул.
Определение формулы исчисления высказываний:
1. Всякая переменная х, у, z, ... является формулой.
2. Если А и В - формулы, то слова (А& В), (A v В), (А В), - также формулы.
3. Никакая другая строчка символов не является формулой.
Переменные высказывания будем называть элементарными формулами.
Например:
Переменные высказывания х, у, z являются формулами согласно п. 1 определения формулы. Cлова (х&у), (xvz), (у z), являются формулами согласно п. 2 определения. По этой же причине будут формулами слова: (х&у), ((х z)&(y z)), ((х& у) (у )).
Очевидно, не являются формулами слова: , &х, (х&у, x у.
Одновременно с понятием формулы вводится понятие подформулы или части формулы.
1. Подформулой элементарной формулы является только она сама.
2. Если формула имеет вид , то ее подформулами являются: она сама, формула А и все подформулы формулы А.
3. Если формула имеет вид (А * В) (здесь и в дальнейшем под символом * будем понимать любой из трех символов v, &, ), то ее подформулами являются: она сама, формулы А и В и все подформулы формул А и В.
Например, для формулы ее подформулами будут:
подформула нулевой глубины,
, подформулы первой глубины,
подформулы второй глубины,
подформулы третьей глубины,
z подформула четвертой глубины.
Очевидно, что на самой большой глубине находятся лишь элементарные формулы. Однако элементарные формулы могут быть и на других глубинах.
Введем в запись формул некоторые упрощения. Будем опускать в записи формул скобки по тем же правилам, что и в алгебре высказываний.