Труды КНЦ вып.7 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып.2 4/2011(7))

Теорема (Стоуна). Всякая конечная булева алгебра B изоморфна алгебре множеств [9]. Семейство L подмножеств опорного множества X называется решеткой подмножеств дляХ, если выполнены условия: I) X е L; 0 е L (эти множества играют роль единицы и нуля); II) из Л-i, Я ,2 е L следует Л 1 n Х 2 е L ; III) из l i , Х 2 е L следует Л 1 u Х 2 е L; IV) из Х\, Х 2 е L следует е L. Решетка подмножеств — это булева решетка с нулем, единицей и операцией дополнения X = Х \ Х е Л для любого Л е Л. При этом %\\%2 = Х\СЛ Х 2 . Отношение порядка в решетке подмножеств есть отношение включения Х\ е X, при этом: sup{Xx, Х2} = Xx yj Х2; inf{Xi, Х2} =Xi n Х2. Другими словами, чтобы обосновать принадлежность алгебраической системы к классу булевых алгебр, достаточно доказать, что выполнены свойства I-IV. 2. АК как булева алгебра Алгебра кортежей (АК) - это алгебраическая система, предназначенная для моделирования и анализа многоместных отношений. Носителем АК является произвольная совокупность многоместных отношений, выраженных в матрицеподобных структурах (С-системах, С-кортежах, .D-системах, ^-кортежах), которые называются АК-объектами . В отличие от матриц и реляционных таблиц, компонентами этих структур служат не отдельные элементы, а их множества. В качестве базовой структуры АК выступает С -кортеж, представляющий собой, по сути, изображение декартова произведения. В АК любое многоместное отношение можно “компактно” выразить как совокупность С-кортежей, то есть в виде С-системы. Для С-систем определены операции взятия дополнения, пересечения и объединения. Все операции в АК выполняются без разложения АК-объектов в набор элементарных кортежей, поскольку в основе законов алгебры кортежей лежат следующие свойства декартовых произведений [10]. 1. Пересечение декартовых произведений. Если даны декартовы произведения Xi xX 2 x...xXn и Yi xY 2 x...xYn, то их пересечение вычисляется как: (Х\хХ 2 х ...хХ„) n (Y, xY 2 x...xY„)=(X, n Yx)x(X 2 n Y 2 )x... х(Хп n Yn). Таким образом, надо сначала вычислить пересечение пар множеств, находящихся на соответствующих "местах" исходных декартовых произ­ ведений, а затем сформировать декартово произведение полученных множеств. Например, пусть заданы следующие декартовы произведения: {а, с , d}x{b, c}x{b, c , f \ и {а, Ь, с, d}x{a, с, d}x{b, с , d}. В соответствии с приведенным правилом вычисления пересечения декартовых произведений имеем: 115