Возможные интерпретации логической алгебры

В моделях (17) а и n имеют качественный характер. Так, а показывает, есть выбросы в независимых переменных или нет, а n — определяет малую, среднюю или большую длину выборки. Поэтому целесообразно исключить эти параметры из представления моделей в виде (17) и построить ряд моделей для конкретных значений а и n в следующем виде:

MSE a’ni = F;(X, ст),

an

MADa,ni = F'i (X,a),i = 1,2,...,8.

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

min MSEa,ni,i = 1,2,...,8, i

min MADa,ni,i = 1,2,...,8.

i

В связи с нелинейным характером зависимостей (18) для определения моделей в явном виде можно использовать регрессионный анализ с нелинейным видом уравнения регрессии или нелинейным относительно независимых переменных регрессии. Для параметрической идентификации существуют формальные методы, чего нельзя сказать о структурной идентификации. Чтобы преодолеть проблему структурной идентификации при построении моделей, можно использовать аппарат искусственных нейронных сетей (ИНС). ИНС целесообразно использовать потому, что он является универсальным аппроксиматором, который не требует структурной идентификации. Будем использовать ИНС в режиме обучения, что позволит определить ее синаптические веса. Далее, в соответствии с выбранной топологией ИНС, функциями активации и определенными синаптическими весами, формируются модели качественных показателей алгоритмов робастного оценивания в аналитическом виде.

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

Литература: 1.Meintanis, S.G. and G.S. Donatos. A comparative study of some robust methods for coefficient-estimation in linear regression, Computational Statistics & Data Analysis, 23, (1997). P. 525-540. 2. You Jiazhong, A Monte Carlo comparison of several high breakdown and efficient estimators, Computational Statistics & Data Analysis. Vol: 30, Issue: 2, (1998). P. 25-55. 3. Hennig C., Efficient high-breackdown-point estimator in robust regression: which function choose?, Statistics & Decision 13, (1995). P. 221-241. 4. Rousseeuw, P.J. and Yohai V.J., Robust regression by means of S-estimators, in: J.Franke, W.Hardle, R.D.Martin (Eds.), Robust and Nonlinear Time Series Analysis (Lecture Notes in Statistics 26) (New York: Springer-Verlag, 1984). P. 256-272. 5. Rousseeuw P.J., Hubert M. Recent development in PROGRESS, Computational Statistics & Data Analysis, 20, (1997). P. 321-340. 6. Rousseeuw, P.J. Least median of squares regression, J. Am. Statist. Assoc., 79, (1984). P. 871-880. 7. Rousseeuw P.J.,Croux C. Explicit Scale Estimator with High Breakdown Point, L1-Statistical Analisis and Reated Methods, (1992). P. 77-92. 8. Coakley C.W. and Hettmansperger T.P. A bounded influence, high breakdown, efficient regression estimator, J. Am. Statist. Assoc., 88, (1993). P. 872-880. 9. ХьюберП. Pобастность в статистике. М.: Мир, 1984. 302с

Поступила в редколлегию 12.03.2000

Рецензент: д-р техн. наук, проф. Путятин В.П.

Антонов Владислав Александрович, аспирант кафедры ИУС XTYP3. Научные интересы: робастная статистика. Адрес: Украина, 61172, Харьков, ул. С.Грицевца, 24, кв. 43, тел. 40-94-51.

Шамша Борис Владимирович, канд. техн. наук, доцент, профессор кафедры ИУС XTyP3. Научные интересы: обработка данных и управление. Адрес: Украина, 61166, Харьков, ул. Космонавтов, 5, кв. 32, тел. 3327-78.

УДК 519.7

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

ЯКИМОВА НА.__________________________

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

Pассмотрим несколько частных алгебр, которые можно представлять как алгебры логического типа. Одной из них является алгебра двоичных кодов. При такой интерпретации логической алгебры беремр-компонентные наборы (ax, ..., ap) цифр из двухэлементного множества G={0, 1}. Им соответ-

ствуют векторы булева пространства размерности р. При этом нулевому вектору соответствует нулевой набор (0, ..., 0), а единичному - единичный набор (1, ..., 1). В роли базисных векторов а1, ..., ар используются всевозможные двоичные наборы, в состав которых входит по одной единице: (1, 0, ..., 0), (0, 1, ..., 0), ..., (0, ..., 0, 1) [1]. Под дизъюнкцией

базисных векторов ail v g2 v...v ai( в алгебре двоичных кодов понимается набор, у которого на i1, i2, ..., i-х местах стоят единицы, а на остальных местах — нули. Таким образом, каждый двоичный код можно единственным образом представить в виде линейной комбинации базисных кодов.

Дизъюнкция векторов булева пространства отвечает дизъюнкции соответствующих двоичных кодов: (a1, ..., ap)v(b1, ..., bp)=(a!vb1, ..., apvbp). Конъюнкции векторов при двоично-кодовой интерпретации логической алгебры соответствует конъюнкция двоичных наборов: (ax, ..., ap)A(bx, ..., bp)=(axAbx,

P^ 2000, № 2

97

.арлЬр), а отрицанию вектора-отрицание соответствующего набора: (aj,..., ap) =(ai, ap ).

Роль скалярного поля, над которым задано рассматриваемое пространство, играет двухэлементное множество G={0, 1}. Легко убедиться, что все аксиомы логической алгебры в алгебре ^-компонентных двоичных кодов выполняются.

К алгебре булевых функций приходим, рассматривая пространство m-местных предикатов на алфавите Km={0, 1}m, заданное над скалярным полем G={0, 1}. Всего при этом алгебра булевых функций содержит 22 векторов. Нулевому вектору соответствует m-местная булева функция, тождественно равная нулю, а единичному—m-местная булева функция, тождественно равная единице. Очевидно, что размерностью логического пространства при такой его интерпретации является число 2m. В роли базисных векторов выступают различные булевы функции от m переменных, обращающихся в единицу лишь на одном наборе значений аргументов. Очевидно, что любая булева функция может быть единственным образом представлена в виде линейной комбинации базисных функций. Всего в алгебре m-местных булевых функций содержится 2m различных базисных векторов [1]. В роли операций дизъюнкции, конъюнкции и отрицания векторов выступают операции дизъюнкции, конъюнкции и отрицания булевых функций [2].

Рассмотрим теперь алгебру множеств. В этом случае роль векторного пространства играет множество всех подмножеств некоторого универсума U. Роль нулевого вектора играет пустое множество 0, а роль единичного — универсум U. В качестве базисных векторов можно взять систему всех одноэлементных подмножеств U универсума. Скалярным полем является двухэлементное множество G={0, 1}, причем 0- U=0, 1- U= Uj. Роль дизъюнкции векторов при теоретико-множественной интерпретации логической алгебры играет объединение множеств, роль конъюнкции — пересечение множеств, роль отрицания—дополнение множества до универсума U. Очевидно, что размерность пространства при этом будет равна мощности универсума U[3-5].

Алгеброй логического типа является также алгебра идей [6]. В качестве пространства векторов можно взять пространство m-местных предикатов, заданных на декартовом произведении К\х...хКт. Множество векторов такого пространства служит носителем алгебры идей L. В качестве скалярного поля, над которым задано рассматриваемое пространство, выступает двухэлементное множество G={0, 1}. Нулевая идея соответствует предикату, тождественно равному нулю, т.е. нулевому вектору, а единичная идея — предикату, тождественно равному единице, т.е. единичному вектору. Количество базисных идей, т.е. размерность логического пространства в этом случае будет равна p=k\-...-km, где kj — мощность множества Kj. Другими словами, в роли базисных идей выступают предикаты, обращающиеся в единицу только в одном разряде, т.е. при единственном наборе v значений аргументов [1]:

Q

1, (xj,..., Xm) = v ,

0, (xj,..., Xm) * v .

Дизъюнкции, конъюнкции и отрицанию векторов такого логического пространства соответствуют операции дизъюнкции [7], конъюнкции и отрицания идей [8].

К алгебре логического типа относится также реляционная алгебра. В качестве пространства векторов можно рассматривать множество всех m-арных отношений Rm, заданных на некотором декартовом произведении К=К\х...хКт. Единичный вектор при этом соответствует универсальному отношению Um, а нулевой вектор — нулевому отношению Om [9]. Дизъюнкции, конъюнкции и отрицанию векторов отвечает объединение и пересечение совместимых отношений [3] и дополнительное отношение соответственно. При построении реляционной модели данных отношения задаются таблично [10, 11]. Кортежами при этом служат те наборы значений аргументов, при которых значение соответствующего рассматриваемому отношению m-местного предиката равно единице. В качестве скалярного поля, над которым задано рассматриваемое пространство m-арных отношений, можно взять множество всех n-арных отношений, n<m.

Принцип построения базиса для такого пространства тот же, что и для построения базиса пространства m-местных предикатов над скалярным полем я-местных предикатов. В случае пространства отношений фиксируются значения последних m-n атрибутов, и в таблицы отношений записываются соответствующие кортежи и только они. Построенные таким образом отношения принимаются в качестве базисных векторов пространства. Аналогом операции умножения вектора на скаляр в реляционной алгебре служит операция выбора, позволяющая строить “горизонтальное” подмножество отношения, т.е. подмножество кортежей внутри отношения, обладающих заданным свойством, т.е. удовлетворяющих определенному предикату [3,10]. Очевидно, что при таком выборе базиса любое отношение Rm может быть единственным образом представлено в виде линейной комбинации базисных отношений. Очевидно, что размерностью такого логического пространства m-арных отношений является число p=kn+1-...-km, где kj=|Kj|, /=1, ..., m.

Алгеброй логического типа является также алгебра конечных предикатов произвольного порядка [ 12]. В качестве логических векторов рассмотрим множество всевозможных конечных предикатов m-го

порядка Q(x01, ..., x0t0 , хш ..., xit1, ..., Xm-1,1, ...,

xm-l/m_i), заданных на декартовом произведении

к00 х Kj1 x...x K& . Мощность множества Kобозначим через kj. Нулевому вектору соответствует тождественно равный нулю предикат, а единичному вектору — тождественно равный единице предикат. Дизъюнкции, конъюнкции и отрицанию векторов отвечают операции дизъюнкции, конъюнкции и отрицания соответствующих предикатов

98

РИ, 2000, № 2

m-го порядка. Скалярное поле, над которым задано рассматриваемое пространство, представляет собой полный набор конечных предикатов n-го порядка, причем n<m, заданных на декартовом произведе-

нии K0 х к^1 х...х • Операция умножения

вектора на скаляр для заданного таким образом логического пространства проводится по тому же правилу, что и для логических пространств m-местных предикатов первого порядка, заданных над скалярным полем n-местных предикатов первого порядка.

Количество векторов рассматриваемого простран СоС1. .ktm~l ства равно 2 о 1 '

т—1

k 0о k11 •...•k

а число элементов ска-

tn—1

лярного поля — 2по Л1 ли-1 . Следовательно, с

учетом формулы (4) из [13] размерность рассматриваемого пространства будет равна р=

= иtn i-tn+1 Cm—1

kn kn+1 '•••h

т-1

В качестве базисных берутся предикаты, подчиняющиеся условию, аналогичному тому, которое было введено для базисных векторов пространства предикатов первого порядка с той разницей, что в случае пространства предикатов m-го порядка при построении базисных векторов фиксируется не произвольное число переменных, а все переменные из некоторого множества уровней переменных J={t0, ..., tm-1}, т.е. все переменные некоторых уровней, количество которых, т.е. мощность множества J, равна m-n. Очевидно, что при таком выборе базиса любой предикат m-го порядка может быть единственным образом представлен в виде линейной комбинации базисных предикатов.

Охарактеризуем теперь алгебру предикатных операций. В качестве пространства векторов рассмотрим пространство предикатных операций Mm размерности m [ 14]. Предикатными переменными при этом служат t-местные предикаты X(x1,..., xt), i=1, ..., m, заданные на декартовом произведении K\... 'Kt, где I Kj\ =kj, j=1, ..., t. Мощностью универсума предикатов служит число 2k1'---kt .Однако, с другой стороны, универсум предикатов представляет собой алфавит, над которым заданы векторы рассматриваемого пространства. В роли операций дизъюнкции, конъюнкции и отрицания векторов выступают операции дизъюнкции, конъюнкции и отрицания соответствующих предикатных операций. Роль нулевого вектора играет константная предикатная операция, значением которой является тождественно равный нулю предикат Р(х1, ..., xt)e0, а роль единичного вектора — константная предикатная операция, значением которой является тождественно равный единице предикат Р(х1, ..., xt)e1. В качестве скалярного поля можно взять пространство предикатных операций M размерности n, n<m.

Количество векторов рассматриваемого логическо-

(2k1k2•--•kt )т

го пространства равно 2(2 ) . Количество

(2 k1k2 --kt)n

элементов скалярного поля равно 2 > .

Следовательно, размерность построенного таким образом логического пространства равна

р= (2 12 t) . Операция умножения вектора

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

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

Литература. 1. Кольцов В.П., Шабанов-Кушнаренко Ю.П. Об изоморфизме алгебр идей/ / АСУ и приборы автоматики. 1990. Вып. 96. С.71 - 77. 2. Шабанов-Кушнаренко Ю.П. Теория интеллекта. Технические средства. Харьков: Вища шк., 1986. 136с. 3. Горбатов В.А. Основы дискретной математики. М.: Высшая шк., 1986. 311с. 4. Колмогоров А.А., Драгалин А.Г. Введение в математическую логику. М.: Изд-во МГУ, 1982. 120с. 5. Мендельсон Э. Введение в математическую логику. М.: Наука, 1976. 320с. 6. Шабанов-Кушнаренко Ю.П. О понятии идеи// АСУ и приборы автоматики. 1990. Вып. 96. С.65 - 71. 7. ДюкаревМ.Ю., КольцовА.В., Шабанов-Кушнаренко Ю.П. Об аксиоматическом построении алгебры идей// АСУ и приборы автоматики. 1990. Вып.97. С.25 -29. 8.ДюкаревМ.Ю., Кольцов А.В., Шабанов-Кушнаренко Ю.П. Умножение и отрицание в алгебре идей// АСУ и приборы автоматики. 1992. Вып. 98. С.10 - 17. 9. Оре

О. Теория графов. М.: Наука, 1980. 336с. 10. Кокорева Л.В., Пенревозчикова О.Л., Ющенко Е.Л. Диалоговые системы и представление знаний. Киев: Наук. думка, 1993. 446с. 11. Атре Ш. Структурный подход к организации баз данных. М.: Финансы и статистика, 1983. 317с. 12. Шабанов-Кушнаренко Ю.П. Теория интеллекта. Проблемы и перспективы. Харьков: Вища шк., 1987. 160с. 13. Гвоздинская Н.А. Булевы и предикатные логические пространства// Проблемы бионики. 1999. Вып. 51. С.106-115. 14. Дударь З.В., Кравец НС, Шабанов-Кушнаренко Ю.П. О фундаментальной алгебре предикатных операций// Проблемы бионики. 1998. Вып. 49. С. 3-13.

Поступила в редколлегию 16.03.2000

Рецензент: д-р техн. наук, проф. Шабанов-Кушнаренко С.Ю.

Якимова Наталья Анатольевна, ассистент кафедры ПОЭВМ ХТУРЭ. Научные интересы: логическая алгебра, искусственный интеллект, формализация естественного языка. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-94-46.

РИ, 2000, № 2

99