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

2.4.Логические исчисления и АК

2.4.1.АК как интерпретация логических исчислений

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

Пусть задана система S с множеством возможных состояний Y = {t1, t2, ..., tr}. Кроме того, в состав S входит некоторое множество V узлов или подсистем V = {V1, V2, ..., Vn}. В свою очередь, каждому узлу Vi соответствует некоторое множество Xi = {c1i , c2i , ..., ckii } его состояний, где ki – число состояний, в котором может находиться узел Vi, а множества Xi – произвольные конечные или бесконечные множества. Наглядно соотношения в этой системе можно представить с помощью схемы, показанной на рис. 2.1.

Рис. 2.1. Схема состояний системы.

Точная модель системы S дается соответствием между всеми возможными наборами состояний всех узлов и состояниями системы. Каждому состоянию tj Y системы соответствует некоторое множество элементарных кортежей из декартова произведения D = X1 X2 ... Xn. Математическая схема этого соответствия:

S: D Y. (2.4)

Однако модель (2.4) теряет практический смысл с увеличением числа узлов, а также с увеличением числа состояний узлов и самой системы, так как, даже в сравнительно небольших системах, число всех элементарных наборов

90

состояний может превзойти вычислительные ресурсы современных компьютеров. К тому же не совсем ясно, как к модели (2.4) можно применить мощные аналитические средства математической логики.

Чтобы уточнить соотношения между АК и различными вариантами исчислений, рассмотрим ряд ограничений, накладываемых на предметную область при ее представлении моделью (2.4).

Ограничение C1: соответствие D Y является однозначным (или функциональным) отображением. Это означает, что ни одному элементарному кортежу из D не может соответствовать более одного элемента из Y.

Ограничение C2: множество Y содержит ровно два элемента. Ограничение C3: множества Xi не отличаются друг от друга.

Ограничение C4: домены всех атрибутов и множество Y – двухэлементные множества {0, 1}.

Нетрудно обосновать следующие утверждения.

Случай 1. Система, удовлетворяющая ограничениям C1, C2 и C3, изоморфна некоторой модели классического исчисления предикатов. Здесь отношения, заданные в любой проекции пространства D, интерпретируются как многоместные предикаты или логические формулы. В этой системе каждая формула рассматривается как отображение соответствующего ей частного универсума на множество {T, F} логических констант: если некоторый элементарный кортеж принадлежит отношению, то он одновременно является выполняющей подстановкой соответствующей логической формулы, и ему соответствует константа T.

Случай 2. Система с ограничениями C1, и C2 соответствует многосортному исчислению предикатов.

Случай 3. Система с ограничениями C1 и C4 соответствует модели исчисления высказываний.

Рассмотрим подробнее эти интерпретации, используя понятия АК.

С каждой формулой классического исчисления предикатов (случай 1) связано некоторое (возможно, пустое) многоместное отношение, состав атрибутов которого идентичен составу свободных переменных в этой формуле. Пусть переменным x, y, z и т.д. сопоставлены атрибуты X, Y, Z, ..., а домены этих атрибутов в точности равны множеству S. Тогда каждый предикат, например, P(x, z), моделируется некоторым отношением P[XZ] на декартовом

91

произведении X Z = S S. Если в этой системе необходимо представить функцию, например, f(x, z) = y, то используется отображение F: X Z Y или, если учитывать равенство всех атрибутов, – F: S S S. Функцию также можно представить как отношение, например, F[XZY], в котором каждому элементарному кортежу из проекции [XZ] отвечает одно и только одно значение в проекции [Y].

Формулы, у которых предикаты соединены логическими связками, например, P(x, z) Q(y, z), можно выразить как результат операций АК над отношениями. В данном случае, если предикаты P(x, z) и Q(y, z) представлены АК-объектами P[XZ] и Q[YZ], то логической формуле P(x, z) Q(y, z), которую можно преобразовать в формулу (P(x, z)) Q(y, z), соответствует в АК следующее выражение:

+Y(P[XZ]) +X(Q[XY]) или P[XZ] G Q[XY].

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

Рассмотрим один из примеров интерпретации квантора (более подробно моделирование кванторов в АК описано ниже). Пусть задана формула

F = y(P(x, y) Q(y, z))

Предикаты P(x, y) и Q(y, z) можно представить как отношения P и Q на частных универсумах X Y и Y Z. Согласно методам АК, пересечение этих отношений с добавленными фиктивными атрибутами образует их соединение, схема отношения которого содержит три атрибута X, Y и Z. При этом возможны два варианта: полученное отношение может быть не пустым или пустым. Отношение пусто, если в P не существует элементарного кортежа, у которого значение атрибута Y совпадает со значением этого же атрибута в каком-нибудь элементарном кортеже из Q. Если теперь к этому трехместному отношению применить квантор y, то для пустого соединения отношений P и Q формула F ложна для всех значений X, Y и Z. При непустом соединении отношений P и Q формула F будет представлять уже не соединение, а композицию отношений.

В то же время логическое значение формулы F не изменится, если в ее интерпретации мы в композицию отношений P и Q вставим фиктивный атрибут

92

Y. В рамках законов логических исчислений и булевой алгебры это означает, что формула F заменяется на эквивалентную ей формулу F true. В АК логической константе true соответствует любой частный универсум, т.е. отдельный атрибут или произвольная проекция универсума D = X Y Z ...

Поясним сказанное примером. Пусть отношения P и Q заданы C-системами, и в результате вычисления композиции получен результат в виде C-системы R. Если добавить к этому отношению фиктивный атрибут Y, то получим уже другую C-систему.

отличаются только присутствием фиктивного атрибута Y в R1. С точки зрения традиционной теории отношений R R1. Но с точки зрения логики и АК они эквивалентны в том смысле, что для любого элементарного кортежа из этих отношений, взятого в проекции [XZ] (например, элементарный кортеж (a, f) из отношений R или R1), можно утверждать, что значение переменной y для него несущественно.

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

В терминах АК нетрудно выразить и исчисление высказываний (случай 3). Для этого достаточно установить для каждого атрибута только два возможных значения. Тогда доменом каждого атрибута будет множество {0, 1}.

Известно, что любую формулу исчисления высказываний можно представить как ДНФ или КНФ. Чтобы перевести в C-систему каждую формулу исчисления высказываний, выраженную в виде ДНФ, необходимо:

1)выделить множество всех литералов (xi, xi ), содержащихся в формуле;

2)вместо литералов xi и xi в формуле ввести соответственно

одноэлементные множества {1} и {0}; 3) в каждую конъюнкцию на соответствующих местах разместить

фиктивные компоненты " " вместо недостающих переменных;

93

4) расположить полученные C-кортежи вертикально в виде матрицы и получить C-систему.

Например, формула H = (x1 x3 ) (x2 x3 x4 ) (x4) преобразуется в C-систему

ДНФ, выраженные как C-системы, нетрудно представить в виде множества выполняющих подстановок этой формулы. Например, C-кортеж [{1} {0} ] содержит 4 выполняющие подстановки, которые можно получить, вычислив декартово произведение {1} {0, 1} {0} {0, 1}. Также несложно определить, является ли произвольно заданная подстановка выполняющей постановкой формулы. Например, подстановку x1 = T; x2 = F; x3 = F; x4 = T для формулы H можно преобразовать в элементарный кортеж (1, 0, 0, 1) и убедиться, что он принадлежит первой и третьей строкам C-системы R. А это означает, что заданная подстановка – выполняющая подстановка формулы H. Кроме того, легко убедиться, что дополнение R

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

Нетрудно убедиться, что в случаях 1-3 соблюдаются законы алгебры

94