Математическая энциклопедия - пропозициональное исчисление

, исчисление высказываний, логическое исчисление, в к-ром выводимыми объектами являются пропозициональные формулы. Каждое П. и. задается набором аксиом (произвольных пропозициональных формул) и вывода правил. Формула, выводимая в данном П. и., наз. теоремой этого П. и. В качестве правил вывода обычно берут модус поненс и подстановку (произвольных пропозициональных формул вместо переменных). Иногда П. и. задают не аксиомами, а аксиом схемами;тогда правило подстановки оказывается излишним.

Классическое П. и. задается следующими аксиомами:

В этом П. и. пропозициональные связки не являются независимыми. Его можно задать с помощью только аксиом 1), 2), 9) и 10), основываясь на связках в качестве исходных. Тогда связки a и рассматриваются как сокращения:

а аксиомы 3) 8) становятся теоремами. Классическое П. и. наз. также полным П. и., поскольку добавление к нему любой невыводимой в нем формулы в качестве аксиомы приводит к противоречивому П. и., т. е. к такому, в к-ром выводимы все пропозициональные формулы. Часто классическое П. и. нач. просто П. и.

Интуиционистское (конструктивно е) П. и. получается из классического П. и. заменой аксиомы 10) более слабой аксиомой

П. и., получаемое из конструктивного П. и. добавлением конечного (или рекурсивного) числа аксиом, наз. промежуточным, суперинтуиционистским (или суперконструктивным). См. также Промежуточная логика.

Другими примерами П. и. являются импликативное пропозициональное исчисление, минимальное пропозициональное исчисление, позитивное пропозициональное исчисление.

Интерпретация П. и. осуществляется с помощью алгебр (матриц) вида

где М - множество истинностных значений, D - множество выделенных истинностных значений,

операции на М, соответствующие связкам и . Множество Dдолжно удовлетворять следующему условию: для любых , если и , то (согласованность с правилом модус поненс). Формула наз. общезначимой на матрице , если она принимает выделенное значение при любой интерпретации ее переменных элементами М. Простейшей матрицей является матрица , состоящая из двух элементов 1, 0 ("истина", "ложь") и одного выделенного значения 1, а операции определяются обычным образом (см. Алгебра логики). Пропозициональная формула, общезначимая на , наз. тавтологией. Формула является тавтологией тогда и только тогда, когда она является теоремой классического П. и.

Лит.:[1] Чёрч А., Введение в математическую логику, пер. с англ., М., 1960. С. К. Соболев.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985