Информационная система "Конференции"

Тезисы докладов

Теория моделей и теория множеств

В [1,2] были введены понятия ориентированных объемов квадратных булевых матриц над произвольной булевой алгеброй. Их булева сумма дает перманент булевой матрицы, произведение – общую часть объемов, а разности дают правый и левый (ориентированные) определители булевых квадратных матриц. Определителем булевых матриц называют сумму правого и левого определителя.

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

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

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

Множество вырожденных матриц, определяемое тем, что их определитель равен нулю, образует идеал в полугруппе квадратных матриц относительно булева произведения матриц. Множество неотрицательных матриц, определяемых условием обращения левого определителя в ноль, образуют подполугруппу булевых матриц с единицей [1,2]. Примерами неотрицательных матриц могут служить булевы матрицы, определяющие произвольные транзитивные или рефлексивные булевы бинарные отношения, а также любые четные степени произвольных булевых отношений на конечных множествах [2].

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

Среди интересных свойств понятий, представленных здесь, отметим лишь то, что свойства введенного здесь понятия «внутренности» булевой матрицы (или булева бинарного отношения на конечном множестве) схожи со свойствами «внутренности подмножества топологического пространства». От аксиом Куратовского [3], определяющих топологию через понятие «внутренность подмножества» их отличает только то, что внутренность пересечения двух булевых матриц содержится в пересечении их внутренностей (вместо равенства в топологическом случае). Тем не менее, это объясняет выбор термина «внутренность» для булевой матрицы.

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1. Поплавский В.Б. Ориентированные определители произведения булевых матриц// Математика, механика. Сб. науч. тр. , №6. Саратов: Изд-во Сарат. ун-та, 2004. C.111-114.

2. Поплавский В.Б. Определители степеней булевых матриц // Чебышевcкий сборник. Т.5, №3(11). 2004. С. 98-111.

3. Келли Дж. Л. Общая топология. М.: Наука, 1981.

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:44:52)