В данной статье речь, в основном, пойдет о логике, которая необходима каждому человеку хотя бы потому, что с ее помощью можно проверить правильность обоснования разных точек зрения, мнений, теорий и т. д. Также важно и то, что в наше непростое время логика очень нужна для того, чтобы противостоять интенсивно развивающимся технологиям интеллектуальных манипуляций, с помощью которых часто вторгаются в наше сознание многочисленные мошенники, аферисты, предвзятые СМИ и, разумеется, агитаторы и политтехнологи. Ситуация усугубляется тем, что логика не является общеобразовательным предметом, а современные методики обучения логике не выдерживают критики.

С логикой тесно связана разработанная сравнительно недавно алгебра кортежей (АК). Здесь будет показано, как с ее помощью решаются непростые логические задачи, а также обоснована связь между АК и семантикой. Более подробные сведения по теме данной статьи можно найти на сайте.

В основе АК лежат свойства Декартова (прямого) произведения множеств (ДП). Многие из этих свойств были впервые сформулированы и обоснованы в публикациях по АК. Для более понятного изложения свойств ДП и основных понятий АК будем использовать в качестве иллюстрации ПРИМЕР логической задачи.

ПРИМЕР

В данном ПРИМЕРе используются сюжеты некоторых задач из книги известного специалиста и популяризатора математической логики Раймонда Смаллиана «Принцесса или тигр?». В некотором царстве король заставлял узников решать логические задачи. В данном эпизоде (он отсутствует в книге Смаллиана) перед узником были три комнаты, в каждой из которых могла находиться одна из принцесс, либо поджидал свою добычу один из тигров. Могли быть и пустые комнаты. С помощью подсказок узник должен был решить, в какой комнате принцесса, и войти в нее. В этом случае он получал свободу и мог жениться на принцессе. Если он ошибался, то мог попасть в комнату с тигром. В данном случае в помощь ему были даны три подсказки, и также было известно, что одна из первых двух подсказок ложная (какая именно, неизвестно), а остальные две – истинные.

• Подсказка 1: Во второй комнате нет тигра, а третья комната не пуста.

• Подсказка 2: Первая комната не пуста, а во второй нет тигра.

• Подсказка 3: Принцесса находится, по крайней мере, в одной из комнат. То же самое известно и о тиграх.

Достаточно ли этих подсказок, чтобы определить, в какой из комнат находится принцесса? Решение задачи будет приведено ниже. Ее можно решить с помощью перебора вариантов. Однако решение значительно упрощается, если использовать структуры и операции АК. Пока же рассмотрим, как можно выразить некоторые условия задачи с помощью ДП. Обозначим комнату с принцессой L (lady), с тигром - T, а пустую комнату - E (empty). Перечисление всех возможных ситуаций в комнатах без учета выраженных в подсказках ограничений можно получить, вычислив ДП: .
Результатом вычисления ДП является множество всех кортежей (последовательностей) элементов, у которых на первом месте стоит элемент из первого множества, на втором – из второго множества и т. д. В данном случае мы получим 27 разных кортежей из трех элементов. Например, ситуацию, когда в первой комнате находится принцесса, а в двух других - тигры, можно выразить с помощью кортежа .

Подсказку 1 можно выразить с помощью ДП , т. е. получим 12 вариантов.

Основные определения в АК

Напомним, что n-местное отношение в математике определяется как подмножество заданного ДП, составленного из n множеств.

Свойства ДП позволяют представить отношения в структурах АК в сжатом виде и выразить в этих структурах многие методы и модели дискретной математики. Сжатые структуры АК могут быть преобразованы в обычные отношения с помощью определенных алгоритмов. Перейдем к определениям основных понятий АК.

• Алгебра кортежей – алгебраическая система, основанная на свойствах ДП, объектами которой являются выраженные в сжатом виде n-местные отношения.

• Операции в АК: дополнение, обобщенное объединение, обобщенное пересечение.

• Отношения в АК: обобщенное равенство, обобщенное включение.

• Домен – множество всех значений определенной переменной.

• Атрибут – имя определенного домена.

Термин обобщенный подразумевает возможность выполнения операций алгебры множеств и проверок соотношений равенства и включения для структур АК с несовпадающим составом атрибутов.

В ПРИМЕРе в качестве атрибутов можно использовать обозначения комнат: . Здесь домены каждого атрибута одинаковы: . В общем случае разные атрибуты в одной системе могут иметь разные домены. В АК можно использовать любые переменные: дискретные (символьные, числовые), непрерывные (в виде систем интервалов на числовой оси) и т.д.

• Схема отношения – заключенная в прямые скобки последовательность атрибутов, определяющих пространство, в котором определено данное отношение.

Для ПРИМЕРа основная схема отношения это .

• Универсум отношения – это ДП доменов атрибутов, содержащихся в схеме отношения. Так, если для данного отношения определена схема отношения , то универсум этого отношения определен как ДП .

• Компонента – заданное подмножество домена атрибута. В их число входят две фиктивные компоненты:

  • полная компонента — (), равна домену соответствующего (по месту ее расположения в кортеже) атрибута;

  • пустое множество — ().

В АК отношения представлены с помощью 4-х основных типов структур ( C-кортеж, C-система, D-кортеж, D-система ), называемых АК-объектами. Операции в АК полностью соответствуют операциям (пересечение, объединение, дополнение) с множествами. То же можно сказать и об отношениях (равенство и включение). Кроме перечисленных операций в АК используются операции с атрибутами. К этим операциям, в частности, относятся:

• добавление фиктивного атрибута;

• элиминация (удаление) атрибута из АК-объекта.

Их описания и интерпретация, приведены ниже.

• Однотипными называются АК-объекты, заданные в одном пространстве атрибутов.

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

Типы структур АК

Структуры АК состоят из элементарных кортежей, которые соответствуют кортежам элементов, содержащихся в многоместных отношениях. Например, ситуация в ПРИМЕРе, когда во второй комнате принцесса, а в остальных – тигры, записывается как элементарный кортеж .

C-кортеж

Это n-местное отношение, равное ДП содержащихся в нем компонент, которые записаны в виде кортежа, ограниченного квадратными скобками.
Например, Подсказки 1 и 2 в ПРИМЕРе можно выразить как C-кортежи
и
,
где символ обозначает множество, равное домену соответствующего атрибута, т.е. множество возможных вариантов содержимого в данной комнате, в нашем случае . Компонента в разных местах C-кортежа может представлять разные множества, так как она соответствует разным атрибутам в схеме отношения.
Если заданы однотипные C-кортежи, то, используя свойства ДП, можно проверить включение одного C-кортежа в другой или вычислить их пересечение. Например, пусть даны однотипные C-кортежи и . Тогда можно вычислить
проверку включения C-кортежей:
, если и только если для всех ;
пересечение C-кортежей:
.
Если при вычислении окажется, что хотя бы для одного i, то .
Для объединения C-кортежей справедливо
, при этом равенство возможно лишь в следующих случаях

1. или ;

2. для всех за исключением одного из .

Поскольку объединение C-кортежей равно единственному C-кортежу лишь в исключительных случаях, то возникает необходимость в определении структуры нового типа.

C-система

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

Диагональная C-система

Это C-система размерности , у которой все недиагональные компоненты полные.
Например, - диагональная C-система.

D-кортеж

Это отношение, равное диагональной C-системе, записанное как ограниченный перевернутыми квадратными скобками кортеж ее диагональных компонент.
Например, изображенную выше диагональную C-систему можно записать как D-кортеж:
.
Доказано, что диагональная C-система есть результат вычисления дополнения некоторого C-кортежа. В частности, C-система является дополнением C-кортежа . Отсюда ясно, что дополнением этого C-кортежа является D-кортеж: .
В ПРИМЕРе сказано, что одна из двух первых подсказок ложная. Предположим, что ложной является Подсказка 2. Рассмотрим, как можно ложную Подсказку 2 преобразовать в истинную. Для этого нужно вычислить ее дополнение:

Поскольку C-кортежи с пустыми компонентами можно исключить из C-системы, то получим в итоге:

D-система

Это отношение, равное пересечению однотипных D-кортежей, записанное как матрица компонент, в которой строками являются участвующие в операции D-кортежи.
С помощью D-систем легко вычисляется дополнение C-систем. Поскольку C-система есть объединение C-кортежей, то по закону де Моргана ее дополнением будет пересечение дополнений этих C-кортежей. Поскольку дополнениями C-кортежей являются соответствующие D-кортежи, то ясно, что для вычисления дополнения C-системы достаточно заменить в ней все компоненты их дополнениями, а вместо обычных квадратных скобок записать перевернутые.

Например, дополнение C-системы вычисляется как D-система

Операции АК

Операции алгебры множеств

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

Вычислительная сложность алгоритмов решения задач в АК соответствует вычислительной сложности решения аналогичных задач в дискретной математике, но в АК имеются свойства, которые позволяют значительно сократить число операций, в частности, при решении NP-полной задачи выполнимость КНФ.

Рассмотрим алгоритм вычисления пересечения C-кортежа с C-системой, который сформулирован и и доказан в виде следующей теоремы.

Теорема. Пусть даны однотипные C-кортеж P и C-система Q. Результатом их пересечения будет C-система, содержащая все непустые пересечения C-кортежа P с каждым C-кортежем из Q.

Эту теорему можно использовать для решения задачи из ПРИМЕРа. Рассмотрим случай, когда Посылка 2 ложная, а остальные истинные. Ложность посылки означает, что ее дополнение истинно. Поэтому для решения задачи требуется сначала вычислить в соответствии с Теоремой пересечение Посылки 1 с дополнением Посылки 2.

Полученный C-кортеж содержит всего 4 возможных варианта (элементарных кортежей): , , и . Нетрудно убедиться, что Подсказке 3 соответствует только 2-й кортеж . Это означает, что принцесса во второй комнате.
Для полного решения задачи необходимо рассмотреть вариант, в котором Посылка 1 ложная, а остальные две истинные. Тогда для решения задачи требуется найти пересечение дополнения Посылки 1 с Посылкой 2.

Вычислим ДП для полученного C-кортежа и получим следующие элементарные кортежи: , , и . Подсказке 3 соответствует только 3-й кортеж. Отсюда следует, что принцесса так же, как и в первом варианте решения, находится во 2-й комнате. Отсюда ясно, что узнику, если он желает выйти на свободу, нужно войти во 2-ю комнату.

Операции с атрибутами

Перечисленные выше операции с атрибутами (добавление фиктивного атрибута, элиминация атрибута) по сути, соответствуют кванторным операциям в математической логике.

• Добавление фиктивного атрибута (+X). При выполнении этой операции в схему отношения добавляется новый атрибут X, а в матричное представление на соответствующем месте – новый столбец с фиктивными компонентами, при этом в C-структурах новый столбец содержит полные компоненты (), а в D-структурах – пустые компоненты ().

В случае, когда АК-объект представляет логическую формулу, операция +X соответствует правилу обобщения (из формулы выводима формула ) в исчислении предикатов.

Например, если D-система: соответствует формуле исчисления предикатов, то, добавив в этот АК-объект фиктивный атрибут , получим АК-объект
который соответствует формуле , выводимой из формулы по правилу обобщения.

• Элиминация атрибута () осуществляется так: из схемы отношения АК-объекта удаляется атрибут X, а из его матричного представления – соответствующий столбец . Доказано, что в случае, когда АК-объекты представляют формулы исчислении предикатов, операция для C-кортежй или C-систем означает «навешивание» (т.е. приписывания к формуле) квантора в соответствующую формулу, а для D-кортежй и D-систем — «навешивание» квантора .

Обобщенные операции

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

С учётом этого предложено ввести в алгебру кортежей обобщённые операции и . Это те же операции алгебры множеств над отношениями с предварительным добавлением недостающих фиктивных атрибутов. Аналогично определяются обобщённые отношения и .

Тем самым обобщенные операции и проверки равенства и включения обеспечивает полноту алгебраической системы – любая пара АК-объектов может использоваться в операциях и проверках включения.

Доказано, что Алгебра кортежей с обобщёнными операциями и отношениями изоморфна алгебре множеств.

Связь АК с логикой

Доказано, что с помощью АК можно выразить все формулы и соотношения исчисления высказываний. Что касается исчисления предикатов, то здесь работа не завершена. С помощью АК можно решать логические задачи, у которых переменные имеют произвольное число значений, содержатся кванторы и даже не выраженные явно (т.е. в виде АК-объектов) предикаты. Однако многие задачи и соотношения исчисления предикатов пока что не выражены в структурах АК. Например, задача «Steamroller», которая используется в качестве тестовой задачи для алгоритмов логического вывода, пока что не сформулирована на языке АК. Не исследована также интерпретация на языке АК функциональных символов.

В то же время на языке АК сравнительно легко формулируются и решаются методы логического анализа, которые трудно выразить на языке математической логики. К ним, в частности, относятся:

• формулирование и проверка гипотез, вывод абдуктивных заключений;

• анализ неопределенностей;

• вывод следствий с заранее заданными свойствами.

Связь АК с семантикой

Некоторые авторитетные специалисты по математической логике (например, Э. Мендельсон (с. 65)) не без основания считают, что «семантические понятия носят теоретико-множественный характер». Понятия теории множеств такие как «подмножество», «декартово произведение множеств», «включение множеств», «непустое пересечение множеств» часто используются при обоснованиях логических законов и в интерпретации языка исчисления предикатов (с. 57). Трудности семантического анализа с помощью теоретико-множественных понятий выражаются в следующем.

Во-первых, в основе аксиоматической теории множеств лежит исчисление предикатов. В силу такого «подчиненного» статуса теорию множеств трудно представить в качестве интерпретации (т.е. по сути семантики) исчисления предикатов. Данная ситуация есть ничто иное как логическая ошибка «предрешенного основания» (petitio principii), когда в основе теории лежат понятия, определяемые на основе этой теории.

В-вторых, по словам Э. Мендельсона «теория множеств, по причине парадоксов, представляется в известной степени шаткой основой для исследований в области математической логики» (с. 65). Выходом из этой непростой ситуации может быть предложенный в АК выбор алгебры множеств в качестве оснований логики.

Целесообразность такого выбора обусловлена следующими соображениями:

• законы алгебры множеств соответствуют законам логики;

• эти законы можно обосновать без аксиом (см. книгу «Что такое математика?» (с. 134-142)). Более подробно об этом сказано в книге (с. 20-23);

• законы алгебры множеств лежат в основе АК, с помощью которой формализуются рассмотренные выше интересные и полезные методы логического анализа. В математической логике эти методы трудно применимы или неприменимы вообще;

• в отличие от теории множеств алгебра множеств не содержит парадоксов. Это означает, что нет никаких препятствий для использования алгебры множеств и изоморфной ей алгебры кортежей в качестве математической основы семантического анализа.