AntiLogik Jul 27 2023 at 13:16

Как совместить логику и семантику в одной алгебраической системе

Medium

10 min

3.7K

Semantics*Algorithms*Mathematics*Artificial Intelligence

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

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

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

ПРИМЕР

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

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

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

Подсказку 1 можно выразить с помощью ДП $\{L,T,E \} \times \{L,E\} \times \{L,T\}$ , т. е. получим 12 вариантов.

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

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

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

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

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

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

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

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

Универсум отношения – это ДП доменов атрибутов, содержащихся в схеме отношения. Так, если для данного отношения определена схема отношения $[X_1X_2 \dots X_n]$ , то универсум этого отношения определен как ДП $U = X_1\times X_2\times \dots \times X_n$ .
Компонента – заданное подмножество домена атрибута. В их число входят две фиктивные компоненты:
- полная компонента — ( $\ast$ ), равна домену соответствующего (по месту ее расположения в кортеже) атрибута;
- пустое множество — ( $\varnothing$ ).

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

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

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

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

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

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

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

C-кортеж

Это n-местное отношение, равное ДП содержащихся в нем компонент, которые записаны в виде кортежа, ограниченного квадратными скобками.
Например, Подсказки 1 и 2 в ПРИМЕРе можно выразить как C-кортежи
$\quad \quad M_1[R_1R_2R_3] = [\ast \quad \{L,E\} \quad \{L,T\}]$ и
$\quad \quad M_2[R_1R_2R_3] = [\{L,T\} \quad \{L,E\} \quad \ast]$ ,
где символ $\ast$ обозначает множество, равное домену соответствующего атрибута, т.е. множество возможных вариантов содержимого в данной комнате, в нашем случае $\ast = \{L,T,E\}$ . Компонента $\ast$ в разных местах C-кортежа может представлять разные множества, так как она соответствует разным атрибутам в схеме отношения.
Если заданы однотипные C-кортежи, то, используя свойства ДП, можно проверить включение одного C-кортежа в другой или вычислить их пересечение. Например, пусть даны однотипные C-кортежи $A=[A_1 \quad A_2 \quad \dots \quad A_n]$ и $B=[B_1 \quad B_2 \quad \dots \quad B_n]$ . Тогда можно вычислить
$\quad \quad$ проверку включения C-кортежей:
$A \subseteq B$ , если и только если $A_i \subseteq B_i$ для всех $i = 1, 2,\ldots, n$ ;
$\quad \quad$ пересечение C-кортежей:
$A \cap B = [A_1 \cap B_1 \quad A_2 \cap B_2 \quad \dots \quad A_n \cap B_n]$ .
Если при вычислении $A \cap B$ окажется, что $A_i \cap B_i = \varnothing$ хотя бы для одного i, то $A \cap B= \varnothing$ .
Для объединения C-кортежей справедливо
$A \cup B \subseteq [A_1 \cup B_1 \quad A_2 \cup B_2 \quad \dots \quad A_n \cup B_n]$ , при этом равенство возможно лишь в следующих случаях

$A \subseteq B$ или $B \subseteq A$ ;
для всех $i = 1, 2,\ldots, n \quad A_i = B_i \quad$ за исключением одного из .

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

C-система

Это отношение, равное объединению однотипных C-кортежей, которое записывается в виде матрицы, ограниченной квадратными скобками.
Например, $R[XYZ]= \begin{bmatrix} A_1 & * & A_3\\ B_1 & B_2 & * \end{bmatrix}$ есть C-система, при этом $A_1 \subseteq X$ , $A_3 \subseteq Z$ и т. д. Данная C-система преобразуется в обычное отношение с помощью ДП следующим образом:
$R[XYZ] = (A_1 \times Y \times A_3) \cup (B_1 \times B_2 \times Z)$ .
С помощью C-кортежей и C-систем можно выразить любое многоместное отношение, но для вычисления их дополнений требуются новые структуры - D-кортежи и D-системы. Для определения этих АК-объектов используется промежуточная структура - диагональная C-система.

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

Это C-система размерности $n \times n$ , у которой все недиагональные компоненты полные.
Например, $Q[XYZ]= \begin{bmatrix} A & * & *\\ * & B & *\\ * & * & C \end{bmatrix}$ - диагональная C-система.

D-кортеж

Это отношение, равное диагональной C-системе, записанное как ограниченный перевернутыми квадратными скобками кортеж ее диагональных компонент.
Например, изображенную выше диагональную C-систему можно записать как D-кортеж:
Q[XYZ] = ]A~ B ~C[ .
Доказано, что диагональная C-система есть результат вычисления дополнения некоторого C-кортежа. В частности, C-система Q[XYZ] является дополнением C-кортежа $[\overline{A} \quad \overline{B} \quad \overline{C}]$ . Отсюда ясно, что дополнением этого C-кортежа является D-кортеж: ]A~ B ~C[ .
В ПРИМЕРе сказано, что одна из двух первых подсказок ложная. Предположим, что ложной является Подсказка 2. Рассмотрим, как можно ложную Подсказку 2 преобразовать в истинную. Для этого нужно вычислить ее дополнение:
$\overline{M_2}[ R_1R_2R_3] = ]\{E\} \quad \{T\} \quad \varnothing[ = \begin{bmatrix} \{E\} & * & *\\ * & \{T\} & *\\ * & * & \varnothing \end{bmatrix}.$
Поскольку C-кортежи с пустыми компонентами можно исключить из C-системы, то получим в итоге:
$\overline{M_2}[ R_1R_2R_3] = \begin{bmatrix} \{E\} & * & *\\ * & \{T\} & * \end{bmatrix}.$

D-система

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

Например, дополнение C-системы $P[XYZ]= \begin{bmatrix} A & * & C\\ D & E & * \end{bmatrix}$ вычисляется как D-система
$\overline P[XYZ]= \biggl ] \begin{matrix} \overline A & \varnothing & \overline C\\ \overline D & \overline E & \varnothing \end{matrix} \biggr[.$

Операции АК

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

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

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

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

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

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

$M_1[R_1R_2R_3] \cap \overline{M_2}[ R_1R_2R_3] = [\ast \quad \{L,E\} \quad \{L,T\}] \cap \begin {bmatrix} \{E\} & * & *\\ * & \{T\} & * \end{bmatrix} = [\{E\}\quad \{L,E\} \quad \{L,T\}].$
Полученный C-кортеж содержит всего 4 возможных варианта (элементарных кортежей): (E,L,L) , (E,L,T) , (E,E,L) и (E,E,T) . Нетрудно убедиться, что Подсказке 3 соответствует только 2-й кортеж (E,L,T) . Это означает, что принцесса во второй комнате.
Для полного решения задачи необходимо рассмотреть вариант, в котором Посылка 1 ложная, а остальные две истинные. Тогда для решения задачи требуется найти пересечение дополнения Посылки 1 с Посылкой 2.

$\overline{M_1}[ R_1R_2R_3] = ] \varnothing \quad \{T\} \quad \{E\} [ = \begin{bmatrix} \varnothing & * & *\\ * & \{T\} & *\\ * & * & \{E\} \end{bmatrix} = \begin{bmatrix} * & \{T\} & *\\ * & * & \{E\} \end{bmatrix}.$
$\overline{M_1}[ R_1R_2R_3] \cap M_2[R_1R_2R_3] = \begin{bmatrix} * & \{T\} & *\\ * & * & \{E\} \end{bmatrix} \cap [\{L,T\} \quad \{L,E\} \quad \ast] = [\{L,T\} \quad \{L,E\} \quad \{E\}].$
Вычислим ДП для полученного C-кортежа и получим следующие элементарные кортежи: (L,L,E) , (L,E,E) , (T,L,E) и (T,E,E) . Подсказке 3 соответствует только 3-й кортеж. Отсюда следует, что принцесса так же, как и в первом варианте решения, находится во 2-й комнате. Отсюда ясно, что узнику, если он желает выйти на свободу, нужно войти во 2-ю комнату.

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

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

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

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

Например, если D-система: $G[XZ] = \left ]\begin{array} {cc} \{a,c\}& \varnothing \\ \{a,c,d\}& \{b,c\} \end{array}\right [$ соответствует формуле F(x, z) исчисления предикатов, то, добавив в этот АК-объект фиктивный атрибут , получим АК-объект $G_1[XYZ] = +Y(G[XZ]) = \left ]\begin{array} {ccc} \{a,c\}& \varnothing & \varnothing \\ \{a,c,d\}& \varnothing & \{b,c\} \end{array}\right [ ,$
который соответствует формуле $\forall y F(x, z)$ , выводимой из формулы F(x, z) по правилу обобщения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

законы алгебры множеств соответствуют законам логики;
эти законы можно обосновать без аксиом (см. книгу «Что такое математика?» (с. 134-142)). Более подробно об этом сказано в книге (с. 20-23);
законы алгебры множеств лежат в основе АК, с помощью которой формализуются рассмотренные выше интересные и полезные методы логического анализа. В математической логике эти методы трудно применимы или неприменимы вообще;
в отличие от теории множеств алгебра множеств не содержит парадоксов. Это означает, что нет никаких препятствий для использования алгебры множеств и изоморфной ей алгебры кортежей в качестве математической основы семантического анализа.

Tags:

Hubs: