О возможных представлениях матриц линейных логических операторов

УДК 519.7

А.Н. ГВОЗДИНСКИЙ, Н.А. ЯКИМОВА, В.А. ГУБИН

О ВОЗМОЖНЫХ ПРЕДСТАВЛЕНИЯХ МАТРИЦ ЛИНЕЙНЫХ ЛОГИЧЕСКИХ ОПЕРАТОРОВ

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

1. Введение

Устоявшиеся представления о математической логике как о науке, изучающей законы мышления с применением аппарата математики, главным образом, для нужд самой математики, в современных условиях становится слишком узким [1]. Объектами математической логики являются любые дискретные конечные системы, а ее главная задача - структурное моделирование таких систем. Человеческий язык, как явление дискретное, естественно должен описываться средствами дискретной математики.

Для описания естественного человеческого языка лучше всего подошел бы аппарат уравнений, подобный аппарату, используемому в математическом анализе, но отличающийся от последнего тем, что он предназначен для формализации не непрерывных, а дискретных процессов. Такой язык дают логические исчисления, а именно: исчисление высказываний и исчисление предикатов. Однако чтобы иметь возможность эффективно решать указанные уравнения, необходимо довести эти исчисления до уровня алгебраической системы [2, с.54]. В классической линейной алгебре широко используется аппарат матриц. Но мы имеем возможность записывать только двухмерные матрицы, не говоря уже о громоздкости этой записи, возрастающей по мере увеличения размерности матриц.

Актуальность исследования. С учетом особенностей логической алгебры становится возможным разработать методы представления булевых матриц, сокращающие их запись, а также допускающие отсутствие ограничений на арность матриц. Эти методы изложены в [3] и в данной статье.

2. Методы решения

Возьмем в качестве поля логических скаляров множество в = {0,1} . В качестве логических векторов рассмотрим множество конституент единицы по т переменным. Такое логическое пространство будем называть булевым. В то же время систему всех конечных предикатов арности т, заданных на декартовом произведении К = К1 х...х Кт, |К; | = к ¡, можно рассматривать как логическое пространство. Множество К; является алфавитом, на котором задан аргумент х; рассматриваемых предикатов. Полем логических скаляров для такого пространства может служить любая система всех конечных предикатов арности п < т . Однако алфавитами и для аргументов предикатов поля скаляров, и для аргументов предикатов множества векторов такого логического пространства должны служить одни и те же множества. Построенное таким образом пространство назовем предикатным логическим пространством или пространством t -местных предикатов над скалярным полем п-местных предикатов [3].

Рассмотрим пример логического пространства. В качестве поля логических скаляров возьмем множество р всех одноместных предикатов Р; (х), (1 = 0,..., 3 ), определенных на множестве К = {0,1}. Множество таких предикатов задано табл. 1.

__ Таблица 1

x Po Pi P2 Рз

0 0 0 1 1

1 0 1 0 1

Далее одноместные предикаты представляются строками P = (Р(0), P(1)). Тогда P0 = (0,0), P1 = (0,1), P2 = (1, 0), Pз = (1,1). Обозначим это скалярное поле через p . Тогда, например, логическая матрица [4] будет иметь вид:

Г Р P2 Pl 1

Po Pз Р

V P2 P0 P3 у

-

Г (0,1) (0,0) (0,1) > Г11 Po * 1

(0,0) (0,1) (0,1) _ Po Pl Р

V (0,0) (0,0) (0,1) у V р Po р1У

В качестве пространства логических векторов [5] возьмем множество двухместных предикатов Q](х, у) , ] = 0, „.,15, определенных на декартовом произведении K2 = {0,1}2 . Множество таких векторов, заданное табл. 2, будем записывать в виде матриц

(Q] (0,0) Q] (1,0) 1

QJ =

Q]

Таблица 2

X у д0 д 2 дз д4 д5 дб д7 д8 д9 дю рц р12 р13 р14 р15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Q1 V Q j =

p1QJ =

Согласно определению операции дизъюнкции векторов и операции умножения вектора на скаляр, для векторов такого пространства

Г р|(0,0) V Q j (0,0) Qi (1,0) V Q j (1,0) ^

ч Qi (0,1) V Q j (0,1) V Q j (1,1) у,

Г ^(0« j (0,0) Pi(1)Q j (1,0) ^ Pi(0)Qj(0,1) j(1,1)у .

Нулевые и единичные элементы в этом случае имеют вид: 0 = Po, 0 = Qo, 1 = Pз, 1 = Ql5. Обозначим это пространство через Q. Это пространство является полным. Приведем пример комбинации векторов Q1 и Q5:

г 0 01

Г 0 01 Г 0 0 PoQl V P2Q5 = (0,0) 10 1IV (1,0)11 1

1 0

= Q4.

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

мощность 2к1к2"'кп , а количество векторов, составляющих рассматриваемое предикатное

пространство, будет равно 2к1к2"'кт [6]. Согласно определению, любой вектор совершенного логического пространства можно единственным образом представить в виде линейной комбинации базисных векторов. Число таких комбинаций будет равно (2к1к2 "'кп)Р . С другой стороны, как было сказано выше, это число равно 2к1к2"'кт . Следовательно, имеет место равенство 2к1к2' 'к™ = (2к1к2"'кп )?, откуда, логарифмируя обе части этого равен-

P

ства по основанию 2, находим число базисных векторов описанного выше совершенного предикатного пространства:

Р = кп+1кп+2 • •"•кт.

Если же = •.. = |Кт | = к, то

Р = кт - п.

Рассмотрим предикатное пространство Q . Алфавитом в указанном пространстве служит множество К3 = {0,1}3 . Очевидно, что к = 2 , п = 1, т = 2 . Количество логических скаляров в этом примере равно четырем, а векторов - шестнадцати. Размерность этого

2 -1

пространства равна 2 = 2 .

В силу того, что векторы булева пространства можно понимать как множество консти-

туент единицы по т переменным, число векторов булева пространства равно 2т. Поле логических скаляров для булева пространства содержит два элемента: ноль и единицу.

Следовательно, справедливо соотношение 2Р = 2т, где Р - размерность булева пространства, т.е. количество его базисных векторов. Очевидно, что

Р = т .

Следует отметить, что в булевом пространстве существует единственный с точностью до перестановки набор векторов, который может служить базисом выбранного пространства, тогда как в предикатном логическом пространстве это не так.

В силу равенства (3), для булевых пространств любой матрице над полем в = {0,1} отвечает некоторый линейный логический оператор. Для предикатных пространств это не так. В случае таких пространств на размерность матриц, соответствующих линейным логическим операторам, накладывается следующее ограничение. Допустим, что некоторая логическая матрица А ^ над полем логических скаляров, элементами которого являются конечные предикаты арности п, представляет собой матрицу некоторого логического оператора А, переводящего векторы предикатного пространства W размерности Р в векторы предикатного пространства V размерности q. В силу равенства (1), для Р и q должны выполняться следующие соотношения:

Р = ктР-п • • •ктР,

^ = ктч-п • • •ктч ,

где тр и тч - арности предикатов, представляющих собой векторы пространств W и V соответственно. Следовательно, множество матриц линейных логических операторов в предикатном пространстве является подмножеством множества всех логических матриц над предикатным скалярным полем. Мощность этого подмножества для каждых конкретных пространств прообразов W и пространства образов V равна (2к1к2-кп )РЧ , где Р и q

- размерности пространств W и V соответственно. В случае к1 = •.. = к т = к, как следует из (2), соотношения (4) и (5) принимают вид

Р = к тР -п,

q = к ^ -п,

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

логических операторов в этом случае равна 2к РЧ.

Например, матрица

'

v

V

л

над полем одноместных предикатов над алфавитом К = {0,1} не соответствует ни одному линейному логическому оператору, так как число ее строк равно трем, а к = 2 . Матрица же

соответствует линейному логическому оператору в, переводящему векторы предикатного пространства W размерности 4 в векторы предикатного пространства V размерности 2. Учитывая соотношения (б) и (7), а также то, что к = 2, а п = 1, находим, что арность

предикатов, представляющих собой векторы пространства образов V, равна тч = 2, а

арность предикатов, представляющих собой векторы пространства прообразов W , равна

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

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

Научная новизна: по результатам проведенных исследований предложены различные формы представления матриц линейных логических операторов.

Практическая значимость: рассмотренные в статье возможные методы описания матриц линейных логических операторов позволяют упростить их компьютерное моделирование.

Список литературы:. 1. Сигорский В.П. Математический аппарат инженера. Киев: Техника. 1975. 768с.

2. Шабанов-Кушнаренко Ю.П. Теория интеллекта. Математические средства. Харьков: Вища школа. 144с. 3. Гвоздинская Н.А., Шабанов-Кушнаренко Ю.П. Предикатные логические пространства // Сб. науч. тр. по материалам 4-й международной конференции "Теория и техника передачи, приема и обработки информации. (Новые информационные технологии)". Туапсе: ХТУРЕ. 1998. С.239. 4. О логических матрицах./ Гвоздинская Н.А., Дударь З.В., Пославский С.А., Шабанов-Кушнаренко Ю.П. // Проблемы бионики. 1998. Вып. 48. С. 12 - 22. 5. О логических пространствах./ Гвоздинская Н.А., Дударь

3.В., Пославский С.А., Шабанов-Кушнаренко Ю.П. // АСУ и ПА. 1997. Вып. 106. С. 21 - 30. 6. Шабанов-Кушнаренко Ю.П. Неполные и полные логические пространства. // Проблемы бионики. 1991. Вып.46. С.10-17. 7. Гвоздинский А.Н., Якимова Н.А., Губин В.А. Представление булевых логических матриц в виде бинарных предикатов // Радиоэлектроника и информатика. 2007. Вып 2. С. 108 - 110. 8. Гвоздинский А.Н., Якимова Н.А., Губин В.А. Бинарное предикаты при описании булевых логических пространств // АСУ и ПА. 2012. Вып. 161. С. 108 - 118.

Поступила в редколлегию 12.09.2015 Гвоздинський Анатолий Николаевич, канд. техн. наук, профессор кафедры искусственного интеллекта ХНУРЕ. Научные интересы: методы оптимизации в организационном управлении. Адрес: Украина, 61166, Харьков, пр. Ленина 14, тел. 70-21-337.

Якимова Наталья Анатольевна, канд. техн. наук, доцент кафедры компьютерной алгебры и дискретной математики Одесского национального университета им.И.И. Мечникова. Научные интересы: логическая алгебра, искусственный интеллект. Адрес: Украина, 65001, 0десса-001, ул.Дворянская, тел.: 8(048)7238405.

Губин Вадим Александрович, старший преподаватель кафедры искусственного интеллекта ХНУРЕ. Научные интересы: интеллектуальный анализ текстовых данных. Адрес: Украина, 61166, Харьков, пр. Ленина 14, тел. 70-21-337.

B =