О построении клонов алгебр функциональных




Скачать 273.11 Kb.
НазваниеО построении клонов алгебр функциональных
страница1/3
Дата публикации08.03.2013
Размер273.11 Kb.
ТипДокументы
uchebilka.ru > Информатика > Документы
  1   2   3

Теоретичні і методологічні основи програмування

УДК 519.3

О ПОСТРОЕНИИ КЛОНОВ АЛГЕБР ФУНКЦИОНАЛЬНЫХ

n-ОТНОШЕНИЙ
Л.М. Захария, Т.В. Луценко, Г.Е. Цейтлин

Институт программных систем НАН Украины, 03187, Киев, пр. Академика Глушкова, 40

tseytlin@vikno.relc.com

Рассматриваются клоны алгебр n-отношений. Данные клоны включают алгебры, равномощные алгебре Кодда. Особое внимание уделено распространению результатов, полученных ранее по полугрупповым (грамматическим и алгоритмическим) клонам на построенные клоны алгебр функциональных n-отношений; эти клоны определяются посредством соответствующих суперпозиций n-отношений и связанных с ними функций, соответственно. Очерчены одномерные и многомерные вычислительные структуры и ассоциированные с ними предметные области.

Clones of algebras of n-relations are examined. The given clones include algebras, equipotent to Codd algebra. High emphasis is placed on distribution of the results received on semigroup (grammatical and algorithmic) clones to the clones of algebras of functional n-relations. Both one-dimensional and multivariate computing structures and the subject domains associated with them are outlined.

Введение

Понятие клона относится к числу фундаментальных понятий универсальной и общей алгебры [1, 2]. Наряду с традиционным его использованием при функциональных построениях в многозначных логиках [3-5] понятие клона приобретает теоретический и прикладной интерес для алгоритмических и полугрупповых построений в алгоритмике [6, 7].

Под клоном понимается, обычно, одноосновная универсальная алгебра вида K=<A; SUPER>, где A – основа, представляющая собой множество однотипных функций; SUPER – сигнатура, состоящая из операции суперпозиции функций (подстановки одних функций вместо переменных в другие), а также операций отождествления и переименования переменных функции (более детально различные определения суперпозиции см. [3-5, 8, 9]).

Данная статья посвящена построению клонов алгебр функциональных n-отношений [8, 10, 11]. Следует отметить важное значение алгебр n-отношений [10] в реляционных базах данных и знаний [12, 13]. Функциональные n-отношения весьма важны и при проектировании различных объектов, характерных для построений в методологии и технологии современного программирования. Это, в частности, связано с ответами на вопросы "что?" и "как?" Ответ на первый вопрос сопряжён с точной постановкой решаемой задачи и может быть формализован в терминах теории отношений; а второй – с построением функций для её решения [11]. Дальнейшее развитие теории отношений имеет важное значение и для других перспективных разделов прикладного программирования [12, 13].

Материал статьи подчинён следующей структуре. В разд. 1 приведен ряд распространённых операций над n-отношениями: композиция бинарных отношений; свёртка де Моргана; транспозиция, отождествление и переименование столбцов и др.

Разд. 2 посвящён операции i-суперпозиции [8], которая является естественным обобщением на n-арный случай композиции бинарных отношений. В частности, отмечается связь между i-суперпозицией и функциональностью. Функциональные построения однородных и неоднородных преобразований вычислительных структур различной размерности приведены в разд. 3. Наконец, в заключении подведены итоги выполненного исследования и приведены постановки некоторых задач, определяющих перспективы дальнейшего развития работ по алгебре алгоритмики.

  1. ^ Операции над n-отношениями

Одной из распространённых операций теории бинарных отношений следует считать их композицию, состоящую в последовательном выполнении бинарных отношений.

Пусть R и G – бинарные отношения, определённые на множестве M, , где – декартова степень M. Под композицией R*G понимается новое бинарное отношение , состоящее из пар вида тогда и только тогда, когда в найдётся хотя бы один промежуточный элемент такой, что пара , а пара . Таким образом, W суть последовательное вычисление R и G.

Бинарное отношение R – функционально, если с ним связана функция так, что для любой пары выполняется . При этом если и – функциональны и с ними связаны функции и , то с композицией связана функция , которая служит суперпозицией функций и , . Иными словами, вычисление значения функции состоит в вычислении функции , а затем функции , т.е. значение функции состоит в последовательном вычислении функции , а затем .

Аналогом композиции для n-арных отношений служит свёртка де Моргана [10]. Под n-арным отношением (кратко, n-отношением) понимается подмножество n-мерного декартова произведения, . В частности, указанные множества могут быть равны , тогда подразумевается декартова степень M. Примерами n-отношения могут служить ведомости, часто используемые в экономических задачах. Например, информация о сотруднике может быть описана следующим -отношением: ,

где – множество табельных номеров сотрудников;

– множество фамилий сотрудников;

– множество дневных тарифов сотрудников;

– множество, состоящее из возможных размеров социальных льгот по налогу на доходы физических лиц,

а табель рабочих дней может быть представлен таким n-отношением: , где – множество целых чисел из интервала [0, 23], фиксирующее количество отработанных сотрудником дней в месяце.

Пусть и суть n-арные отношения, определённые на декартовых произведениях указанных множеств, где – непустое пересечение множеств и . Свёртка де Моргана определяется следующим образом: результирующее -арное отношение представляет собой совокупность кортежей вида

,

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


Табельный номер

Фамилия сотрудника

Дневной тариф

Количество социальных льгот

Количество отработанных дней


Положим, что n-отношение функционально по n-й компоненте, если с ним связана n-1-местная функция , областью значений которой служит множество . Так, для любого кортежа значений переменных данной функции она принимает значение в множестве , . Иллюстрацией функционального отношения служит отношение , где – множество начисленной заработной платы каждого сотрудника, определяемое функцией , .

Пусть n-отношения и – функциональны и с ними связаны функции и функция ; тогда в результате свёртки де Моргана получим также функциональное -арное отношение , с которым связана следующая суперпозиция функций:

.

Проиллюстрируем сказанное на примере расчета налога на доходы физических лиц для каждого сотрудника. Функция , где , определяет элементы множества значений налога на доходы физических лиц (подоходный налог составляет 13%, размер социальной льготы, не облагаемой налогом на доходы в 2005 году составил 131 грн, количество социальных льгот для каждого сотрудника определяется его социальным статусом – количество детей, инвалидность и т.п.), .

В результате свертки де Моргана отношений () по полю <табельный номер> получим следующее n-отношение, которое для наглядности представим в виде таблицы базы данных


Табельный номер

Фамилия сотрудника

Дневной тариф

Количество социальных льгот

Количество отработанных дней

Начислено

Налог на доходы

которое определяется следующей суперпозицией функций:

h(x1,x2,…,x6)=gналог(fначислено(w), x1,x2,…,x5)

(в выражении произведены отождествление и перестановка столбцов, x11, x2M 2, x3M 3, x4M 4, x5M 5, x6 M 6). Данный пример иллюстрирует процесс решения задачи начисления заработной платы в виде суперпозиции функций.

Таким образом, из проведенных построений вытекает справедливость следующего утверждения.

Теорема 1. Свёртка де Моргана функциональных -отношений и порождает новое функциональное отношение, связанное с суперпозицией исходных функций и , которая задана равенством (1).

Для n-отношений естественным образом вводятся операции перестановки, отождествления и переименования столбцов (по аналогии с введенными Мальцевым [5] одноименными операциями, которые применимы в функциональных построениях [3, 4, 8]). Тем самым справедливо утверждение.

Следствие 1. Циклическая перестановка столбцов в сочетании со свёрткой де Моргана функциональных -отношений снова порождает функциональные -отношения, согласно суперпозициям соответствующих этим n-отношениям функций.

В [10] рассмотрены и другие операции над -отношениями: проекция, фильтрация, теоретико-множественные булевы операции и др., которые широко используются в алгебрах структур данных, например алгебре Кодда [12].

Следствие 2. Теория -отношений служит математическим фундаментом в прикладном программировании при построении реляционных баз данных и знаний [12,13].

Одной из основных проблем алгебры клонов является проблема функциональной полноты. Для алгебры логики L/2 доказана теорема о функциональной полноте Поста и построена решетка максимальных подалгебр. Между алгеброй логики L/2 и алгеброй отношений О/2, определенной на множестве пар, состоящих из нулей и единиц, существует связь, которая позволяет сформулировать теорему о функциональной полноте для алгебры О/2. Для алгебры логики L/2 естественно рассмотреть обобщённую свёртку де Моргана, как распространение обычной суперпозиции функций на случай n-отношений, тогда из принадлежности функций, участвующих в суперпозиции, к некоторому замкнутому классу следует, что и полученная в результате суперпозиции функция также принадлежит тому же классу. Например, пусть все функции из суперпозиции сохраняют константу 0, тогда соответствующие n-отношения содержат наборы, состоящие из нулей; этот факт имеет место и для отношения, соответствующего функции h, полученной в результате суперпозиции.

Другой пример: пусть все функции из суперпозиции самодвойственны, тогда и результирующая функция h также самодвойственна, но отношения, соответствующие функциям , содержат противоположные наборы; этому свойству удовлетворяет и отношение, соответствующее функции h.

Пусть алгебре логики L/2 соответствует алгебра отношений О/2, сигнатура операций которой содержит обобщённую свёртку де Моргана и унарные операции для отождествления и переименования переменных. Тогда для алгебры отношений О/2 может быть сформулирована следующая теорема.

^ Теорема Поста для алгебры О/2.

Произвольно выбранная система отношений функционально полна в алгебре О/2 тогда и только тогда, когда эта система содержит:

хотя бы одно отношение, не принадлежащее подалгебре О/0, сохраняющих константу 0;

хотя бы одно отношение, не принадлежащее подалгебре О/1, сохраняющих константу 1;

хотя бы одно отношение, не принадлежащее подалгебре О/c самодвойственных функций;

хотя бы одно отношение, не принадлежащее подалгебре О/m монотонных функций;

хотя бы одно отношение, не принадлежащее подалгебре О/л линейных функций.

Следствие 1. Каждой подалгебре алгебры логики L/2 соответствует подалгебра алгебры отношений О/2.

Следствие 2. Перечисленные в сформулированной теореме Поста для алгебры О/2 классы отношений являются для алгебры О/2 максимальными и соответствуют максимальным подалгебрам алгебры L/2.

Следствие 3. Алгебра О/2 имеет счётное множество подалгебр, решётка которых соответствует диаграмме Поста для алгебры L/2.
  1   2   3

Добавить документ в свой блог или на сайт

Похожие:

О построении клонов алгебр функциональных icon9 Центральные органы лимфоидной системы
Индуцированная взаимодействием с антигеном выработка антител и накопление антигенспецифических клонов лимфоцитов

О построении клонов алгебр функциональных iconРекомендации по применению эфирных масел для профилактики и лечения...
При функциональных нарушениях сердечно-сосудистой системы эфирные масла мяты, пихты, герани, лаванды

О построении клонов алгебр функциональных iconЛеонова А. Б. Психодиагностика функциональных состояний человека
Леонова А. Б. Психодиагностика функциональных состояний человека. — М.: Изд-во Моск ун-та. 1984. — 200 с

О построении клонов алгебр функциональных iconФинансовое планирование является важным элементом корпоративного...
Каждый менеджер, независимо от своих функциональных интересов, должен быть знаком с механикой и смыслом составления, выполнения и...

О построении клонов алгебр функциональных iconФинансовое планирование является важным элементом корпоративного...
Каждый менеджер, независимо от своих функциональных интересов, должен быть знаком с механикой и смыслом составления, выполнения и...

О построении клонов алгебр функциональных iconДинамическая теория эфира
Эти характеристики частиц обусловлены одной из алгебр Гейзенберга, лежащей в основе предлагаемой теории. С отсутствием в физике эфира...

О построении клонов алгебр функциональных icon1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр
Предложены алгоритмы диалогового конструирования алгоритмов и генерации программ на целевых языках программирования. Описан метод...

О построении клонов алгебр функциональных iconСжатие данных в пакете unitLib для систем ы компьютерной алгебр ы gap
Пусть k — поле из p элементов, g — конечная p-группа, — нормированная мультипликативная группа групповой алгебры kg. Она играет важную...

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

О построении клонов алгебр функциональных iconЛекция 1
Цель данной темы дать основные представления о построении, организации и использова­нии компьютерных сетей

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<