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

В качестве такого аппарата далее рассматривается алгебра кортежей (АК), представляющая собой общую теорию многоместных отношений [2, 3, 4]. Основы АК излагаются в [2]. Применение АК при решении различных задач логико-семантического анализа можно найти в [5, 6]. В настоящей работе приводятся некоторые сведения из дискретной математики и математической логики, необходимые для того, чтобы обосновать принадлежность АК к классу булевых алгебр и показать, что в АК соблюдаются все законы классической логики. Затем продемонстрировано, что средствами АК, не прибегая к помощи многозначных логик, можно решать основные задачи дедуктивного и недедуктивного анализа. Чтобы обозначить место АК среди других алгебраических систем, введем некоторые определения и понятия. 1. Решетки и булевы алгебры Сначала рассмотрим частично упорядоченные множества (ч.у.м., посеты, i’-множества) X. < >, которые можно представить как частный случай графов, где для элементов носителя задано отношение частичного порядка со свойствами рефлексивности, транзитивности и антисимметричности. Примерами ч.у.м. являются числа, упорядоченные по величине; слова с лексикографическим порядком; множества, упорядоченные по включению; целые числа с отношением делимости и т.д. Формально отношение частичного порядка определяется как заданное на множестве X бинарное отношение со следующими свойствами: 1) рефлексивности: a < a ; 2) транзитивности: если a < b и b < с, то a < с; 3) антисимметричности: из a < b и b < a следует a = b, где a, b и с - произвольные элементы X. Используя понятие частично упорядоченного множества, можно описать еще один фундаментальный класс алгебраических систем - решетки. Для этого введем несколько вспомогательных определений. Пусть X - ч.у.м. с частичным порядком <. Элемент х называется нижней гранью для a и b, если х < a и х < b. Аналогично, у называется верхней гранью для a и b, если a <у и b < у. Элемент х называется точной нижней гранью для a и b, если х - нижняя грань элементов a и b и для любой другой их нижней грани v выполняется v < х. Обозначение: х = inf(a, b). Элемент у называется точной верхней гранью для a и b , если у - верхняя грань элементов a и b и для любой другой их верхней грани и выполняется у < и. Обозначение: у = sup(a, b). Решеткой [7] называется ч.у.м. <Х, < >, для любых двух элементов а, b которого существует точная нижняя грань inf{a, b) е X и точная верхняя грань sup(a, b) е X. Другими словами, если в модель ч.у.м. добавить две двухместные операции in f и sup, то получим известную алгебраическую систему, которая называется решеткой. Примечательно, что решетка может быть представлена и как "чистая" алгебра <В, П, U>, если положить, что а ГлЬ = inf{a, b), a U b = sup(a, b), a отношение < заменить следующим образом: а <Ь <=> а СЛЬ = а или a KJ b = Ь 113