В данной статье речь, в основном, пойдет о логике, которая необходима каждому человеку хотя бы потому, что с ее помощью можно проверить правильность обоснования разных точек зрения, мнений, теорий и т. д. Также важно и то, что в наше непростое время логика очень нужна для того, чтобы противостоять интенсивно развивающимся технологиям интеллектуальных манипуляций, с помощью которых часто вторгаются в наше сознание многочисленные мошенники, аферисты, предвзятые СМИ и, разумеется, агитаторы и политтехнологи. Ситуация усугубляется тем, что логика не является общеобразовательным предметом, а современные методики обучения логике не выдерживают критики.
С логикой тесно связана разработанная сравнительно недавно алгебра кортежей (АК). Здесь будет показано, как с ее помощью решаются непростые логические задачи, а также обоснована связь между АК и семантикой. Более подробные сведения по теме данной статьи можно найти на сайте.
В основе АК лежат свойства Декартова (прямого) произведения множеств (ДП). Многие из этих свойств были впервые сформулированы и обоснованы в публикациях по АК. Для более понятного изложения свойств ДП и основных понятий АК будем использовать в качестве иллюстрации ПРИМЕР логической задачи.
ПРИМЕР
В данном ПРИМЕРе используются сюжеты некоторых задач из книги известного специалиста и популяризатора математической логики Раймонда Смаллиана «Принцесса или тигр?». В некотором царстве король заставлял узников решать логические задачи. В данном эпизоде (он отсутствует в книге Смаллиана) перед узником были три комнаты, в каждой из которых могла находиться одна из принцесс, либо поджидал свою добычу один из тигров. Могли быть и пустые комнаты. С помощью подсказок узник должен был решить, в какой комнате принцесса, и войти в нее. В этом случае он получал свободу и мог жениться на принцессе. Если он ошибался, то мог попасть в комнату с тигром. В данном случае в помощь ему были даны три подсказки, и также было известно, что одна из первых двух подсказок ложная (какая именно, неизвестно), а остальные две – истинные.
Подсказка 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-кортежей справедливо
, при этом равенство возможно лишь в следующих случаях
или
;
для всех
за исключением одного из
.
Поскольку объединение 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);
законы алгебры множеств лежат в основе АК, с помощью которой формализуются рассмотренные выше интересные и полезные методы логического анализа. В математической логике эти методы трудно применимы или неприменимы вообще;
в отличие от теории множеств алгебра множеств не содержит парадоксов. Это означает, что нет никаких препятствий для использования алгебры множеств и изоморфной ей алгебры кортежей в качестве математической основы семантического анализа.