Дискретно-непрерывная математика (стр. 25 )

аксиом X, имеющих то же множество теорем, что и исчисление

с непустым X и такимичто отличается от только наличием 0-посылочных правил вывода, обеспечивающих доказуемость всех подстановочных частных случаев формул из X. Таким образом, каждая «аксиома» представляет бесконечное множество аксиом и тогда правило подстановки оказывается излишним. Исчисления такого типа называются исчислениями со схемами аксиом. В дальнейшем, если не оговорено другое, под пропозициональным исчислением L будем понимать гильбертовское исчисление или, в более общем виде, где отношение выводимости для L есть бинарное отношение между множествами формул Fm и формулами Fm, т. е. удовлетворяющее следующим условиям Тарского для

Отношение называется структурным, если из следует

где е есть подстановка в Fm. Логика с отношением

выполняющим эти условия, называется логикой Тарского.

(В польской школе логиков получило распространение другое определение пропозициональной логики, введенное А. Тарским [Tarski 1930; 1930]. Пусть есть множество всех подмножеств множества А. Оператором замыкания на множестве А называются отображение которое удовлетворяет следующим условиям для каждого (см. [Кон 1968]):

Подмножество Х из А называется замкнутым подмнооюеством, если С(Х)=Х.

А. Тарский [Tarski 1930] находит применение оператору замыкания для изучения абстрактного отношения следования. Вводится дополнительное условие: оператор С на множестве А называется финитарным, если. .

Оператор замыкания с таким свойством в [Bui'fis and Sankappanavav 1981 называется алгебраическим оператором замыкания. Заметим, что (С4) влечет (СЗ). Теперь пусть А есть множество всех формул Fm в пропозициональном языке Тогда оператор замыкания С называется операцией присоединения следствий (consequence operation) и обозначается посредством Сп, т. е. Сп есть операция, которая, примененная к множествам формул, позволяет получать новые множества формул. В терминологии Тарского Сп(Х) называется дедуктивной системой и представляет собой множество формул, дедуцируемых из формул X, взятых в качестве посылок, посредством аксиом и правил вывода.

Операция присоединения следствий Сп называется структурной (или инвариантной относительно подстановки), если для всех подстановок е (эндоморфизмов) пропозиционального языка выполняется условие

Открытие того, что подстановки являются эндоморфизмами, и введение условия (С5) (см. [Los and Suszko, 1958]) было предназначено для того, чтобы выразить формальный характер логического следования.

Под логикой (пропозициональной) понимается пара где операция присоединения следствий Сп не обязательно финитарная, но структурная. Изучению основных свойств операции присоединения следствий посвящена фундаментальная монография Р. Вуйцицкого [Wqjcicki 1988]. Непосредственно в применении к многозначным логикам см. монографии [Zygnnmt 1984] и [Malinowskl 1993]. Связь между операцией Сп и обычным отношением выводимости очевидна:

Проблема нахождения конечного множества аксиом по каждой конечнозначной логической матрице является весьма сложной и будет обсуждаться в главе б.

Логические матрицы могут использоваться для того, чтобы определить понятие логики семантически. Пусть есть логическая матрица и отношение логического следования на множестве Fm определяется следующим образом:

т. т.т., когда для каждой оценки v на для всех следует, что

При этом отношение логического следования является инвариантным относительно подстановки (или структурным). Отсюда пара есть логическая система.

Пусть D идва непересекающихся множества в матрице такие, что и А и В произвольные формулы из Fm. Тогда

логическая матрица называется нормальной (см. [Lukasiewicz and TarsU 1930]), если всегда влекут

Таким образом, нормальная логическая матрица согласуется с правилом МР, т. е. МР сохраняет тавтологию. Приведенные выше

матрицы являются нормальными, а матрица с

двумя выделенными значениями не является нормальной. Нормальные матрицы играют особую роль при доказательстве независимости аксиом (см. раздел 2.3 и Приложение).

Следующее свойство логических матриц является также весьма существенным. Назовем матрицы С-расишряющими, если ограничения операций на подмножество {0, 1} множества V суть обычные классические операции отрицания, дизъ­юнкции, конъюнкции и импликации соответственно. Таким обра­зом, такие матрицы в качестве подматрицы содержат матрицу для С2, т. е., говоря неформально, на множестве {0, 1} они содержат классическую логику. Все рассмотренные нами ранее трехзначные логики, кроме являются С-расишряющими. В следующей главе мы рассмотрим самые известные не С-расширяющие логики (п- значные логики Поста).

Логическая матрица называется моделью логики L, если каждая доказуемая формула в L является тавтологией в Если же верно и обратное, т. е. что каждая тавтология в доказуема в L, то модель называется точной моделью или, по-другому, есть характеристическая матрица для L. Другими словами, называется характеристической матрицей для L, если формула А является тавтологией вт. т.т., когда А доказуема в L. Примерами

характеристических матриц являются для С2 и для

Пропозициональное исчисление может иметь характеристические матрицы различной мощности, где под мощностью матрицы понимается мощность множества V элементов матрицы. Поэтому, естественно, возникает нетривиальная проблема нахождения характеристической матрицы минимальной мощности для исчисления L.

Один из наиболее важных и общих результатов для логических матриц принадлежит А. Линденбауму (1930г.): каждая структурная логика имеет по крайней мере счетную

(нормалъную) матрицу адекватную для нее. Дальнейшее развитие теории логических матриц сделано в работах польских логиков [Los 1949], [Los and Suszko 1958] и [Wdjcicki 1969; 1973]. Во второй из указанных работ найдены достаточные и необходимые условия для того, чтобы структурная логика имела единственную характеристическую матрицу. В работах Р. Вуйцицкого доказано, что каждая структурная логика строго полна относительно определенного класса матриц. Этот результат основывается на введении Вуйцицким понятия обобщенной матрицы, которое оказалось очень полезным для построения различных теоретико-модельных конструкций, играющих важную роль в обосновании новых семантических подходов в современной логике (см. об этом ниже в разделе 10.4).