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

характеристическую матрицу с множеством истинностных значений {0, 1}.

Метод умножения матриц служит способом получения новых логических матриц с большим числом истинностных значений. В [Rose 1952] подобным образом строится 8-значная система, предназначенная для применения к геометрии. Здесь в качестве истинностных значений выступают элементы множества {1, 0} в третьей степени. Эти значения указывают на истинностный статус высказываний в трех системах геометрий: Евклида, Римана и Лобачевского.

Заметим также, что можно умножать различные матрицы друг на друга. Так, Е. Расёва [Rasiowa 1955] умножает истинностную двузначную таблицу для классической эквивалентности на трех­значную таблицу для импликации Лукасевича и дает аксиомати­зацию вновь полученной шестизначной логики. Н. Решер [Rescher 1969] в качестве примера рассматривает произведение Он также рассматривает для общего случая вопрос о классе тавтологий результирующей матрицы.

4.3.2. Другие операции. Финитная аппроксимируемость

Кроме рассмотренного метода получения новых матриц, мощность которых есть произведение мощностей сомножителей, Яськовский [Jaskowski 1936] вводит также операцию которая позволяет

получать n+1-значную матрицу на основе n-значной таким образом, что для произвольной матрицы

Делается это следующим образом.

Пусть есть некоторая исходная

матрица, гдеТогда матрица с

множеством значений и с тем же самым выделенным

элементом 1 определяется так:

где Г есть операция добавления нового элемента а* к множеству Vn, причем матричные операции в доопре-

деляются по общей схеме посредством введенной ниже функции область определения которой есть Vn:

Операции в определяются следующим образом:

В качестве примера применим операцию Г к матрице клас­сической двузначной логики где х = 1 или 0, у = 1 или 0 и пусть Тогдаимеет вид:

Аналогичным способом определяются операции В

результате мы получили не что иное, как характеристическую матрицу для трехзначной логики Рейтинга G3 (см. 2.2). Эта матрица получила название «первой матрицы Яськовского». В зависимости от того, как определяется можно получать различные логики. Например, Н. Решер [Rescher 1969] вводит другую операцию, а именно такую, что для произвольной матрицы

Комбинируя метод умножения матриц и способ получения n+1-значной матрицы на основе n-значной, С. Яськовский строит бесконечную последовательность конечных матриц,

определяемую так:

(классическая двузначная логика),

где- декартова n-ая степень с основным множеством

В соответсвии с определением матрицих основные мно­жества состоят соответственно из элементов исходной матрицы из упорядоченных пар этих элементов, из упорядоченных троек упорядоченных пар и т. д. Заметим, что матрицы Яськовского Ji имеют

элементов. В частности, имеют соответственно 2, 3,

10, 1001 и 1004006004002 элементов. Таким образом, число элементов в матрицах Яськовского растет исключительно быстро, но каждая из них конечна.

Рассмотренные операции над логическими матрицами были введены С. Яськовским для получения следующего результата: бесконечная последовательность матриц Ясъковского Ji является характеристической для интуиционистского пропозиционального исчисления Int (Об Int см. ниже в разделе 8.2.2). Еще говорят, что последовательность матриц Ji финитно аппроксимирует Int. Последнее означает, что для всякой формулы А, которая не выводима в Int, найдется в Ji матрица, на которой А не верна. Из свойства финитной аппроксимируемости следует важное свойство разрешимости исчисления. Роль разрешающего алгоритма играет параллельный перебор всевозможных выводов и всевозможных конечных матриц, чтобы найти вывод данной формулы в этом исчислении или ее опровергнуть. Однако не для всякого исчисления можно построить финитно аппроксимируемую модель или, по-другому, не всякое исчисление имеет финитно-модельное свойство (finite model property) [Harrop 1958].

Введем еще одно важное понятие, характеризующее логиче­ское исчисление L в терминах истинностных таблиц. Исчисление L' называется расширением исчисления L , если каждая доказуемая формула L также доказуема в L'. Расширение L' называется собственным расширением исчисления L, если L' непротиворечиво, но содержит формулу не выводимую в L. Например, исчисление классической двузначной логики С2 является собственным расширением исчисления Р1 и к тому же единственным (см. гл. 2). Исчисление L называется предтабличным, если все его собственные расширения табличны, т. е. являются конечнозначными логиками. Важные примеры предтабличных логик мы рассмотрим в гл 8.

4.4. Понятие решетки. Основные свойства

Поскольку, как уже говорилось, логическая матрица есть алгебрас множеством выделенных элементов D, то представ­ляется возможным привлечь свойства решеток для характеризации многозначных логик. Эта характеризация окажется весьма полезной, поскольку открывает внутренний смысл того, что какая-то формула А не является общезначимой в данной матрице или того, что какая-то логическая связка одной логики не выразима посредством логических связок в другой логике. Но, главное, позволяет классифицировать логики относительно их решеточных свойств.

Имеются два стандартных (эквивалентных) определения понятия решетки. В первом случае выделяется специальный вид частично упорядоченного множества и преимущество

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

с заданными на нем двумя бинарными операциями. Кратко рассмотрим первый случай, а затем акцентируем внимание на втором подходе (см. [Гретуер 1982]).

Отношения, обладающие свойствами рефлексивности антисимметричности (из и следует х = у) и

транзитивности (из следует называются

отношениями частичного порядка, а множества, на которых заданы такие отношения, называются частично упорядоченными множествами (кратко ч. у. множествами). Ч. у. множество которое обладает также свойством линейности называется цепью (его называют также линейно упорядоченным множеством). Далее определяются sup и inf в произвольном ч. у. множестве (т. е. в

Пусть Тогда х называется верхней границей