Большая советсткая энциклопедия Секвенций исчисление
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

Секвенций исчисление

Секвенций исчисление (позднелатинское sequentia — последовательность, следствие), секвенциальные исчисления, исчисления способов заключений, модификации понятия логического исчисления, в которых основными объектами преобразования являются не формулы, а т. н. секвенции, т. е. выражения вида A1,..., Al ® B1,..., Bm, где ® аналогична знаку выводимости, A1,..., Al и B1,..., Bm — произвольные формулы; первые — образующие антецедент секвенции, вторые — её сукцедент. При l, m ³ 1 секвенция A1,..., Al ® B1,... Bm интерпретируется как формула

A1&... &A1 ÉB1 Ú...Ú Bm.

(& — знак конъюнкции, É — импликации, Ú — дизъюнкции, см. Логические операции), секвенция с пустым антецедентом интерпретируется как истина, а секвенция с пустым сукцедентом — как ложь (и, следовательно, секвенция ®, состоящая из одной стрелки, — как противоречие). Аксиомами (исходными секвенциями) в С. и. являются все секвенции вида С ® С (и только они). Правила вывода делятся на т. н. структурные и логические. Первые кодифицируют допустимые изменения "формульного состава" антецедента и сукцедента, вторые — введение в секвенции различных логических символов. Структурные правила — это "уточнение" (добавление произвольной формулы к антецеденту или сукцеденту), "сокращение" (вычёркивание повторяющихся формул), перестановка произвольных формул в антецеденте или сукцеденте, а также "сечение"

(латинскими буквами обозначаются произвольные формулы, греческими — строчки формул, разделённых запятыми, над чертой пишется посылка правила, под чертой — заключение). Логические правила вывода имеют для секвенциального классического исчисления высказываний следующий вид:

; ;

.

Если и структурные, и логические правила вывода ограничить условием, согласно которому в сукцеденте каждой секвенции должно быть не более одной формулы, то получим секвенциальное интуиционистское исчисление высказываний: это условие оказывается достаточным для невыводимости в С. и. исключенного третьего принципа (а также закона снятия двойного отрицания). Секвенциальное исчисление предикатов получается присоединением к предыдущим правилам ещё двух пар правил введения кванторов общности и существования.

Основной результат немецкого математика Г. Генцена состоит в установлении возможности приведения каждого вывода в С. и. к "нормальной форме", не содержащей применений правила сечения и тем самым представляющей в некотором смысле "прямой" вывод. Из многочисленных приложений этого результата особенно важны доказательства непротиворечивости арифметических формальных систем, использующие математическую технику, выходящую за рамки гильбертовского финитизма (см. Аксиоматический метод, Метаматематика), и тем самым обходящие в известном смысле трудности, обусловленные теоремой К. Гёделя о неполноте формальной арифметики. Эта же основная теорема Генцена лежит в основе большинства алгоритмов выводимости для логических и логико-математических исчислений (см. Разрешения проблема), чем и обусловлена исключительная важность С. и. для интенсивно развивающихся исследований в области машинного поиска логического вывода, являющихся важным примером моделирования интеллектуальной деятельности человека.

Лит.: Генцен Г., Исследования логических выводов, пер. с нем., в кн.: Математическая теория логического вывода, М, 1967, с. 9—74; его же. Непротиворечивость чистой теории чисел, там же, с. 77—153; его же, Новое изложение доказательства непротиворечивости для чистой теории чисел, там же, с. 154—90; Карри Х. Б Основания математической логики. пер. с англ., М., 1969, гл. 5С, 6B, 7B и 8B; Алгорифм машинного поиска естественного логического вывода в исчислении высказываний, М. — Л., 1965.

Следующие

Секвестр (от лат. sequestro — ставлю вне, отделяю), в буржуазном гражданском праве запрещение или ограничение, налагаемое госуда… читать дальше



Секвестр (медицинский), омертвевший в результате нарушения кровоснабжения участок ткани, отделившийся от окружающей здоровой тка… читать дальше



Секвойя (Sequoia), род вечнозелёных хвойных деревьев семейства таксодиевых. Единственный вид — С. вечнозелёная (S. sempervirens)… читать дальше