Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Моделирование факторов неопределенности с помощью матриц конечных предикатов В [9] даются основы алгебры кортежей (АК) и демонстрируется ее применение для унификации представления и обработки различных видов данных и знаний, а также решения различных задач логического и логико­ вероятностного анализа. Близкий подход применяется также в [10] для решения задач распознавания образов и упрощения баз знаний. Конечные предикаты в АК можно сжато представить с помощью двух типов структур: С- систем и D -систем. С помощью С- систем удобно моделировать дизъюнктивные нормальные формы (ДНФ) конечных предикатов. Продемонстрируем это на примере. Пусть задан конечный предикат: ф(х, у, z) = ( x=a,b ) л (у=а,с ) ѵ ( z=d ). Для простоты все переменные определены на одном и том же множестве {а, Ъ, с, с!). Здесь и далее будем использовать запись вида ( х=а,Ь ) для обозначения выражения (х=а) v (x=b). Учитывая, что область истинности одноместного предиката ( х=а,Ь ) есть {а,Ь}, то область истинности предиката ф(х, у. z) может быть представлена в виде следующей С-системы: R[XYZ\ = {a,b} {а,с} * * * {d} Атрибуты X, Y, Z С-системы R\XYZ\ соответствуют переменными х, у, z формулы ф(х, у, z). Заметим, что “*” - сокращенное обозначение всего диапазона возможных значений (домена) атрибута. С-систему R\XYZ\ можно преобра­ зовать в обычное многоместное отношение: ({а,Ь} х {а,с} х {a,b,c,d})^({a,b,c,d} х {a,b,c,d} х {d}). С помощью D -систем моделируются конъюнктивные нормальные формы (КНФ) конечных предикатов. D -система записывается как матрица компонент- множеств, которая ограничена перевернутыми прямыми скобками. D -системы позволяют легко вычислять дополнение С- систем: берется дополнение для каждой компоненты-множества. Например, —іф = (—і (x=a,b) v -л (y=a,c)) л -л (z=d), что равносильно -іф = (( x=c,d) v (y=b,d)) л ( z=a,b,c ), можно выразить в виде D -системы R \XYZ \: R[XYZ\ = {c,d} {b,d} 0 2 0 {a,b,c} Пустая компонента “0 ” - это фиктивная компонента, не содержащая ни одного значения. Системы ограничений с конечными доменами, обычно, удобно пред­ ставлять в виде D -систем, а решения задач CSP искать в виде С- систем. С помощью структур алгебры кортежей (С- и D -систем) можно моделировать и анализировать не только классические ограничения с конечными доменами, но и ограничения с недоопределенными параметрами. 77