Материал: Алгебра_кортежей

множеств. Можно дать еще одну логическую интерпретацию системы S, оставив лишь ограничение C1 (при неоднозначности соответствия в системе появится неопределенность – одним и тем же набором параметров может характеризоваться более одного состояния системы). Можно рассматривать объединенное пространство D Y, среди отношений которого в разных проекциях может содержаться (или не содержаться) атрибут Y. Тогда множество элементарных кортежей объединенного пространства D Y разделится на два непересекающихся множества: множество допустимых (true) и множество недопустимых (false) состояний, определяемых в соответствии с конструктивными или технологическими особенностями моделируемой системы, и соответствие

окажется изоморфным модели многосортного исчисления предикатов, в которой отсутствуют ограничения на число состояний узлов и системы в целом. Если представить состояния Xi узлов и состояния Y системы "значениями истинности" (таких значений в некоторых вариантах неклассической логики может быть более двух, вплоть до бесконечности), то модель (2.5) можно рассматривать как многозначную логику, в которой, тем не менее, справедливы все законы алгебры множеств.

Таким образом, можно сказать, что с точки зрения интерпретации АК выходит за пределы многосортного исчисления предикатов. Для этого рассмотрим модель (2.5), в которой действует ограничение C1. Если отменить ограничение C1 в моделях (2.4) или (2.5), то получится система, в которой не соблюдается функциональное соответствие между состояниями узлов и "значениями истинности". Для такой системы, по-видимому, невозможно подобрать соответствующую логику среди известных логик, но в то же время такая система может представлять определенные реальные сущности, и в ней также не нарушаются законы алгебры множеств.

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

95

2.4.2. Соответствие между АК и исчислением предикатов

Конъюнкция одноместных предикатов с разными переменными интерпретируется в АК C-кортежами, в которых отдельные атрибуты не соотносятся с многоместными отношениями. Например, логической формуле H = P1(x) P2(y) P3(z) может быть сопоставлен C-кортеж P[XYZ] = [P1 P2 P3],

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

Домены атрибутов в АК могут быть любыми, не обязательно равными друг другу множествами. Это означает, что структуры АК могут интерпретировать формулы многосортного исчисления предикатов.

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

yF(x, z), полученную из формулы F(x, z) по правилу обобщения. Для C-кортежей и C-систем это соотношение очевидно, но аналогичное преобразование для D-кортежей и D-систем нужно доказывать, так как фиктивные атрибуты, добавляемые в D-систему, содержат пустые фиктивные компоненты ( ).

96

при условиях теоремы очевидна. Пусть R – C-система, содержащая C-кортежи R1, R2, …, Rn. Это означает, что R = R1 R2 … Rn. В исчислении предикатов отношение R служит интерпретацией формулы P = P1 P2 … Pn, где Pi – формулы, моделируемые C-кортежами Ri. Применив к R операцию –X , получим

–X(R) = –X(R1) –X(R2) … –X(Rn).

Правой части этого равенства соответствует следующая формула исчисления предикатов: x(P1) x(P2) … x(Pn), которая по правилам эквивалентного преобразования формул в математической логике равна

Доказательство. Пусть R – C-система, равная дополнению D-системы R. Ясно, что R удовлетворяет условиям теоремы 2.23 и моделирует формулу P. Предположим, что Q = –X(R). Из теоремы 2.23 следует, что Q соответствует формуле x( P). АК-объект Q равен D-системе, у которой все компоненты –

дополнения компонент Q. Отсюда Q = –X(R). Выражение Q служит интерпретацией формулы ( x( P)), которая в силу известного в математической логике соотношения равна x(P). Отсюда следует, что АК-объект –X(R) моделирует формулу x(P). Конец доказательства.

Следовательно, элиминация атрибута (например, X) из C-системы означает, что к этому объекту применен квантор x, а если атрибут элиминируется из D-системы, то это эквивалентно применению квантора x к данному объекту. Например, пусть даны C-система и ее дополнение, выраженное как D-система: