WWW.NAUKA.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, издания, публикации
 


«Ключевые слова: многосортная логика, модель, изоморфизм. Аннотация Пусть — многообразие алгебр, (H,, f ) — модель, где H — алгебра из, — множество символов отношений, f — ...»

Многосортная логика, модели

и логическая геометрия

Е. АЛАДОВА

Университет имени Бар-Илана, Рамат Ган, Израиль,

Пензенский государственный университет

e-mail: aladovael@mail.ru

А. ГВАРАМИЯ

Абхазский государственный университет, Сухуми, Абхазия

Б. ПЛОТКИН

Еврейский университет в Иерусалиме, Израиль

e-mail: plotkin@macs.biu.ac.il

Т. ПЛОТКИН

Университет имени Бар-Илана, Рамат Ган, Израиль

УДК 510.6

Ключевые слова: многосортная логика, модель, изоморфизм.

Аннотация

Пусть — многообразие алгебр, (H,, f ) — модель, где H — алгебра из, — множество символов отношений, f — интерпретация всех в H. Пусть X 0 — бесконечное множество переменных, — множество всех конечных подмножеств в X 0 (множество сортов), — многосортная алгебра формул. Эти данные определяют базу знаний KB(H,, f ). В статье рассматривается понятие изоморфизма баз знаний.

Приводятся условия на модели, которые являются достаточными условиями изоморфизма баз знаний. Изучается также вопрос нахождения необходимых и достаточных условий, обеспечивающих изоморфизм баз знаний.

Abstract E. Aladova, A. Gvaramia, B. Plotkin, T. Plotkin, Multi-sorted logic, models, and logical geometry, Fundamentalnaya i prikladnaya matematika, vol. 19 (2014), no. 3, pp. 5—22.

Let be a variety of algebras, (H,, f ) be a model, where H is an algebra from, is a set of relation symbols, f is an interpretation of all the symbols in H. Let X 0 be an innite set of variables, be the collection of all nite subsets in X 0 (the collection of sorts), and be the multi-sorted algebra of formulas. These data dene a knowledge base KB(H,, f ). In this paper, the notion of isomorphism of knowledge bases is considered. We give sucient conditions that provide isomorphism of knowledge bases. We also study the problem of necessary and sucient conditions for isomorphism of two knowledge bases.

Фундаментальная и прикладная математика, 2014, том 19, № 3, с. 5—22.

c 2014 Издательский дом «Открыты

–  –  –

1. Введение Говоря о знании, мы исходим из его представления в виде трёх компонент.

1. Описание знания представляет собой синтаксический компонент знания.

С алгебраической точки зрения описание знания — это набор формул T в алгебре формул (X), X = {x1,..., xn }. Сейчас мы только отметим, что (X) является одним из доменов многосортной алгебры (детали см. в [2, 11, 14], а также в разделе 2.6).

определения

2. Предмет знания представлен в виде модели (H,, f ), где H — алгебра из фиксированного многообразия алгебр, — множество символов отношений, f — интерпретация каждого в H.

3. Содержание знания — это подмножество в H n, где H n — декартова степень алгебры H. Каждое содержание знания A соответствует описанию знания T (X), |X| = n. Если рассматривать H n как аффинное пространство, то это соответствие может быть задано геометрически (см. раздел 2.3).

Для описания динамической природы баз знаний вводятся две категории:

категория описания знаний F (f ) и категория содержания знаний LG (f ). При определении этих категорий используется аппарат логической геометрии (см.

разделы 2.4, 2.

5 или [17]).

Следует подчеркнуть, что все используемые понятия относятся к произвольным многообразием алгебр, с которым связаны рассматриваемые алгебры, логика, геометрия базы знаний. Универсальная алгебраическая и логическая геометрии работают с произвольной алгеброй H из, а логическая геометрия изучает также произвольные модели (H,, f ), причём для каждого конкретного многообразия алгебр возникают свои интересные проблемы и решения.

Предметом настоящей статьи является, в частности, изучение связи между изоморфизмами баз знаний и изотипностью предметов знаний.

Меняя многообразие, мы приходим к множеству разных проблем. В частности, если — многообразие всех квазигрупп, интересно понять, какова связь между изотопностью и изотипностью для квазигрупп [1, 18].

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

–  –  –

ai = (xi ). Обозначим через H n аффинное пространство, состоящее из таких точек.

Точка может быть представлена как гомоморфизм : W (X) H, где W (X) — свободная алгебра над множеством X в многообразии. Таким образом, каждое аффинное пространство может быть рассмотрено как множество Hom(W (X), H) всех гомоморфизмов из W (X) в H.

Каждая точка, как гомоморфизм, имеет ядро Ker(), которое является бинарным отношением на множестве W (X). По определению элементы w, w W (X) находятся в отношении Ker() тогда и только тогда, когда w = (w ), где w — обозначение для (w).

Мы будем рассматривать также логическое ядро LKer() точки. Формула u (X) принадлежит LKer(), если точка удовлетворяет формуле u.

2.2. Расширенные булевы алгебры Нам понадобится понятие квантора существования на булевой алгебре.

Пусть B — булева алгебра. Квантор существования на B — это унарная операция : B B, такая что 1) 0 = 0,

2) a a, 3) (a b) = a b.

Квантор всеобщности : B B дуален к : B B, они связаны соотношением a = ¬ (¬a).

Определение 2.1. Пусть заданы набор переменных X = {x1,..., xn } и множество отношений. Булева алгебра B называется расширенной булевой алгеброй над W (X), если

1) на B определены кванторы x для всех x X так, что x y = y x для всех x, y X;

2) каждому отношению арности n и набору элементов w1,..., wn из W (X) соответствует 0-арная операция (константа) вида (w1,..., wn ) в алгебре B.

Таким образом, сигнатура LX расширенной булевой алгебры состоит из булевых операций, кванторов x и констант (w1,..., wn ):

LX = {,, ¬, x, MX }, где MX — множество всех (w1,..., wn ).

Одним из примеров расширенной булевой алгебры является алгебра формул (X) (см. [2, 11, 14]). Формула w w — одна из констант, где в качестве берётся отношение равенства. В зависимости от контекста она будет называться равенством или уравнением.

Рассмотрим другой важный пример расширенной булевой алгебры. Пусть задана модель (f ) = (H,, f ).

8 Е. Аладова, А. Гварамия, Б. Плоткин, Т. Плоткин

–  –  –

Этот гомоморфизм позволяет алгебраически определить такие понятия, как «точка удовлетворяет формуле» и «логическое ядро точки», и такой подход согласуется с индуктивным теоретико-модельным подходом (см. [7]).

Сейчас только отметим, что для формулы u (X) её образ ValX ) (u)(f определён как множество точек : W (X) H, удовлетворяющих u. В этом случае формула u (X) принадлежит логическому ядру LKer() точки : W (X) H тогда и только тогда, когда ValX ) (u). Заметим также, (f что LKer() является булевым ультрафильтром в алгебре формул (X), содержащим X-элементарную теорию ThX (f ) модели (H,, f ). В этом смысле мы говорим, что LKer() есть LG-тип точки (см. [7] для теоретико-модельного определения типа и для определения LG-типа [19]). Напомним, что ThX (f ) состоит из всех u (X), выполняющихся на любой точке : W (X) H.

Таким образом, ThX (f ) = LKer().

Hom(W (X),H)

2.3. Соответствие Галуа Определим теперь соответствие между множествами T формул вида w w в алгебре формул (X) и множествами точек A из аффинного пространства Hom(W (X), H). Положим TH = A, где A состоит из всех точек : W (X) H,

–  –  –

таких что T Ker(). Другими словами, TH состоит из всех точек, удовлетворяющих всем формулам из T. Такое TH называется алгебраическим множеством, определённым множеством формул T.

С другой стороны, для заданного множества точек A определим множество формул T следующим образом:

–  –  –

Непосредственная проверка показывает, что u AL ) тогда и только тогда, когда (f A ValX ) (u). Можно заметить, что AL ) является фильтром в (X), такой (f (f фильтр называется H-замкнутым фильтром, определяемым множеством A.

Таким образом, описанные выше соответствия Галуа приводят к универсальной алгебраической геометрии, когда T является множеством равенств, и к логической геометрии, если T — произвольное множество формул.

Напомним, что множество A в Hom(W (X), H) Галуа-замкнуто, если, в зависимости от рассматриваемого соответствия Галуа, AH = A или ALL = A.

(f ) Конгруэнция T на W (X) Галуа-замкнута, если TH = T, фильтр T в (X) LL Галуа-замкнут, если T(f ) = T.

Таким образом, мы имеем взаимно-однозначное соответствие между алгебраическими множествами в Hom(W (X), H) и замкнутыми конгруэнциями на W (X), между определимыми множествами в Hom(W (X), H) и замкнутыми фильтрами в расширенной булевой алгебре (X).

2.4. Некоторые категории В этом разделе мы определим различные категории, необходимые для дальнейших рассмотрений.

10 Е. Аладова, А. Гварамия, Б. Плоткин, Т. Плоткин

–  –  –

2.4.4. Категории C (H) и F (f ) Объектами категории C (H) являются частично упорядоченные множества H-замкнутых конгруэнций на W (X). Они находятся во взаимно-однозначном соответствии с объектами AGX (H). Зададим морфизмы в C (H):

–  –  –

Здесь объекты категорий представленны как домены многосортных алгебр, а морфизмы s — как унарные операции между доменами. Полученные алгебры являются алгебрами Халмоша.

Замечание 2.8. Мы используем имя П. Халмоша, поскольку он был одним из создателей алгебраической логики. Он ввёл важное понятие полиадической алгебры. Вместе с другими понятиями универсальной алгебры и универсальной алгебраической геометрии полиадическая алгебра даёт начало теории, которая, в частности, используется и в этой статье.

Для того чтобы дать точное определение многосортных алгебр Халмоша, определим сначала сигнатуру этих алгебр.

–  –  –

3. Логическая геометрия и базы знаний

3.1. От логики и геометрии к теории знаний В предыдущем разделе мы ввели необходимую систему понятий. Все эти понятия естественно возникают и взаимодействуют. Дальнейшее изложение материала будет связано с приложениями к базам знаний.

3.2. Базы знаний Теперь мы будем трактовать категории F (f ) и LG (f ) как категории описания знаний и содержания знаний соответственно.

Напомним, что мы выделили три компонента в представлении знания:

— описание знания, — предмет знания, — содержание знания.

Следующие три математических объекта соответствуют этим компонентам:

— категория решёток H-замкнутых фильтров F (f ), — модель (H,, f ), — категория решёток определимых множеств LG (f ).

Определение 3.1. База знаний KB = KB(H,, f ) — это тройка (F (f ), LG (f ), Ctf ), где F (f ) — категория описаний знания, LG (f ) — категория содержания знаний и Ctf : F (f ) LG (f ) — контравариантный функтор.

Функтор Ctf переводит описание знания в содержание знания. Морфизмы категорий F (f ) и LG (f ) делают базy знаний динамическим объектом.

Замечание 3.2. Мы используем термин «базы знаний» вместо более точного термина «модель базы знаний».

Для заданной модели (f ) = (H,, f ) каждое конкретное знание — это тройка (X, T, A), где X из, T — множество формул из (X) и A — множество LL L L точек из Hom(W (X), H), такое что A = T(f ) = T(f ). Таким образом, T и LL T(f ) описывают одно и то же содержание A.

18 Е. Аладова, А. Гварамия, Б. Плоткин, Т. Плоткин

–  –  –

Теорема 3.8 даёт достаточное условие изоморфизма баз знаний.

Следующее предложение играет важную роль.

Предложение 3.16 [10]. Пусть для многообразия каждый автоморфизм категории 0 является внутренним. Категории алгебраических множеств AG (H1 ) и AG (H2 ), где H1, H2, изоморфны тогда и только тогда, когда алгебры H1, H2 AG-эквивалентны.

С точки зрения баз знаний предложение 3.16 даёт необходимые и достаточные условия изоморфизма баз знаний при условии, что множество символов отношений соответствующей базы знаний KB(H,, f ) содержит только символ предиката равенства. Общий же случай является проблемой.

Проблема 3.17. Пусть даны модели (H1,, f1 ) и (H1,, f2 ), где H1, H2.

Допустим, что для многообразия каждый автоморфизм категории является внутренним. Верно ли, что LG (f1 ) и LG (f2 ) изоморфны тогда и только тогда, когда H1 и H2 LG-эквивалентны.

В общем случае нахождение необходимых и достаточных условий требует изучения ситуации для конкретных многообразий. В связи с этим интерес представляет следующая задача.

Проблема 3.18. Изучить автоморфизмы категории для различных многообразий.

Заметим, что с точки зрения приложений особый интерес представляют многообразия полугрупп и групп. Мы закончим нашу дискуссию вопросом, который также имеет особое значение для приложений.

Проблема 3.19. Исследовать условия изоморфизма для конечных баз знаний.

Работа Е. Аладовой была осуществлена при поддержке Израильского научного фонда, грант 1207/12. Она благодарит также Исследовательский институт Эмми Нётер и фонд «Минерва» за частичную поддержку при подготовке данной статьи.

Литература [1] Гварамия А. А. Алгебры Халмоша и аксиоматизируемые классы квазигрупп // Успехи мат. наук. — 1985. — Т. 40, № 4. — С. 215—216.

[2] Плоткин Б. Алгебраическая геометрия в логике первого порядка // Итоги науки и техн. Сер. Соврем. мат. и её прил. — 2004. — Т. 22. — С. 16—62. — arXiv:math/ 0312485[math.GM].

[3] Aladova E., Plotkin B., Plotkin T. Similarity of models and knowledge bases isomorphism: Preprint.

[4] Aladova E., Plotkin E., Plotkin T. Isotypeness of models and knowledge bases equivalence // Math. Comput. Sci. — 2013. — Vol. 7, no. 4. — P. 421—438.

[5] Halmos P. R. Algebraic Logic. — New York: Literary Licensing, 1969.

22 Е. Аладова, А. Гварамия, Б. Плоткин, Т. Плоткин [6] Mac Lane S. Categories for the Working Mathematician. — Berlin: Springer, 1971. — (Grad. Texts Math.; Vol. 5).

[7] Marker D. Model Theory: An Introduction. — Berlin: Springer, 2002.

[8] Mashevitzky G., Plotkin B., Plotkin E. Automorphisms of categories of free algebras of varieties // Electron. Research Announcements AMS. — 2002. — Vol. 8. — P. 1—10.

[9] Plotkin B. Universal Algebra, Algebraic Logic and Databases. — Dordrecht: Kluwer Academic, 1994.

[10] Plotkin B. Varieties of algebras and algebraic varieties. Categories of algebraic varieties // Sib. Adv. Math. — 1997. — Vol. 7, no. 2. — P. 64—97.

[11] Plotkin B. Seven lectures on the universal algebraic geometry: Preprint. — 2002. — arXiv:math/0204245.

[12] Plotkin B. Algebras with the same algebraic geometry // Proc. Steklov Inst. Math. — 2003. — Vol. 242. — P. 176—207.

[13] Plotkin B. Algebraic logic and logical geometry in arbitrary varieties of algebras // Proc. Conf. on Group Theory, Combinatorics and Computing. — Providence: Amer.

Math. Soc., 2014. — (Contemp. Math.; Vol. 611). — P. 151—167.

[14] Plotkin B., Aladova E., Plotkin E. Algebraic logic and logically-geometric types in varieties of algebras // J. Algebra Appl. — 2013. — Vol. 12, no. 2. — Paper No. 1250146.

[15] Plotkin B., Plotkin E. Multi-sorted logic and logical geometry: some problems. — Demonstratio Math. — To appear.

[16] Plotkin B., Plotkin T. Geometrical aspect of databases and knowledge bases // Algebra Universalis. — 2001. — Vol. 46. — P. 131—161.

[17] Plotkin B., Plotkin T. Categories of elementary sets over algebras and categories of elementary algebraic knowledge // Pillars of Computer Science. Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday. — Berlin: Springer, 2008. — (Lect. Notes Comp. Sci.; Vol. 4800). — P. 555—570.

[18] Smith J. D. H. An Introduction to Quasigroups and their Representations. — Chapman and Hall; CRC Press, 2007.

[19] Zhitomirski G. On logically-geometric types of algebras: preprint. — arXiv:1202.

5417[math.LO].




Похожие работы:

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тюменский государственный нефтегазовый университет» Научно-исследовательский институт прикладной этики ВЕДОМОСТИ ПРИКЛАДНОЙ ЭТИКИ Выпуск сороковой ПРИКЛАДНАЯ ЭТИКА КАК ФРОНЕСТИКА МОРАЛЬНОГО ВЫБОРА Под редакцией В.И. Бакштановского, В.В. Новоселова Тюмень ТюмГНГУ УДК 17.034(082.1) ББК 87.75 П 759 Прикладная этика как фронестика морального...»

«( 19 декабря – 26 декабря 2014 г.) Выпуск № 44 – 12 ОГЛАВЛЕНИЕ ИВАН МИРОШНИЧЕНКО: АГРАРНЫЙ БЮДЖЕТ 2015 БУДЕТ САМЫМ МИЗЕРНЫМ ЗА ПОСЛЕДНИЕ ГОДЫ ПЕРЕТНУТО ФАРВАТЕР БУДІВНИЦТВА БУКСИРІВ ПРОЕКТУ 121 C НАЧАЛА 2014/15 МГ УКРАИНА ЭКСПОРТИРОВАЛА И ПОДГОТОВИЛА НА ЭКСПОРТ 8 МЛН. Т ПШЕНИЦЫ МИНАГРОПРОД ОТСТРАНИЛ ДИРЕКТОРА ЦЕНТРА СЕРТИФИКАЦИИ СЕМЯН З ПОЧАТКУ ГРУДНЯ УКРЗАЛІЗНИЦЯ НАВАНТАЖИЛА 2,3 МЛН ТОНН ЗЕРНОВИХ ВАНТАЖІВ УКРАИНА: ОБЪЕМЫ ОТГРУЗОК КУКУРУЗЫ ОТСТАЮТ ОТ ПРОШЛОГОДНИХ НА 3 МЛН. ТОНН ВР УКРАИНЫ В...»

«В. А. Мишнёв БОЛЬШОЙ УЧЕБНИК САКРАЛЬНОЙ АСТРОЛОГИИ «Спалах» Киев 2002 ISBN 966-512-151-0 Предлагаемый учебник является полным изложением оригинального подхода, базирующегося как на древнейших традиционных основах, так и на результатах последних разработок ученых-креацианистов и современных астрологов, к астрологическому исследованию человека. По сути, – это первая попытка очищения астрологии от многовековых искажений ее первоначального сакрального назначения. Но главное достоинство книги – ее...»

«ArctiChildren InNet Развитие электронной системы здравоохранения в школах Баренцева региона Редакторский коллектив: Эйри Солман, Катрин Костениус, Оле Мартин Йохансен, Инна Рыжкова, Минтту Меривирта Серия B. Отчеты 4/ ArctiChildren InNet Развитие электронной системы здравоохранения в школах Баренцева региона Эйри Солман, Катрин Костениус, Оле Мартин Йохансен, Инна Рыжкова, Минтту Меривирта (ред.колл.) ArctiChildren InNet Развитие электронной системы здравоохранения в школах Баренцева региона...»

«Помогите найти Гдз по английскому языку печатная тетрадь 5 класс кузовлев костина лапа дуванова кузнецова Гдз по английскому языку печатная тетрадь 5 класс кузовлев костина лапа дуванова кузнецова Гдз по английскому языку печатная тетрадь 5 класс кузовлев костина лапа дуванова кузнецова: Суть бюджетной системы Суть бюджетной системы_ Суть бюджетной системы Гдз по английский язык печатная тетрадь 5 класс кузовлев костина лапа дуванова кузнецова каждой стране основу государственных финансов...»

«Этнографическое обозрение Online Сентябрь 2008 http://journal.iea.ras.ru/online VII Конгресс этнографов и антропологов России «Многоэтничные общества и государства» Л.И. Никонова VII Конгресс этнографов и антропологов России «Многоэтничные общества и государства» состоялся 9–14 июля 2007 г. в г. Саранске (Республика Мордовия) на базе государственного учреждения «Научно-исследовательский институт гуманитарных наук при Правительстве Республики Мордовия» и при непосредственном участии Института...»

«ПРАВИТЕЛЬСТВО РОСТОВСКОЙ ОБЛАСТИ МИНИСТЕРСТВО ПРИРОДНЫХ РЕСУРСОВ И ЭКОЛОГИИ РОСТОВСКОЙ ОБЛАСТИ ЭКОЛОГИЧЕСКИЙ ВЕСТНИК ДОНА «О состоянии окружающей среды и природных ресурсов Ростовской области в 2014 году» РОСТОВ-НА-ДОНУ При использовании материалов ссылка обязательна Под общей редакцией: Василенко Вячеслава Николаевича – заместителя Губернатора Ростовской области; Урбан Геннадия Александровича – министра природных ресурсов и экологии Ростовской области; Куренкова Андрея Геннадьевича – первого...»

«Об утверждении новой редакции Положения о скидках со сформированной стоимости обучения, предоставляемых студентам и учащимся, обучающимся в учреждениях образования комплекса БГУ На основании пункта 2 «О скидках по оплате за обучение для определенных категорий иностранных обучающихся» решения ректората от 12.05.2015 № 2 2 ПРРЖАЗЫВАЮ: 1. Внести изменения в Положение о скидках со сформированной стоимости обучения, предоставляемых студентам и учащимся, обучающимся в учреждениях образования...»

«Новосибирская государственная областная научная библиотека Новосибирская областная юношеская библиотека Новосибирская областная детская библиотека им. А. М. Горького Новосибирская областная специальная библиотека для незрячих и слабовидящих Центральная городская библиотека им. К. Маркса г. Новосибирска БИБЛИОТЕКИ НОВОСИБИРСКОЙ ОБЛАСТИ в 2010 году Обзор деятельности Новосибирск ББК 78.3 Б 594 Ответственный за выпуск: Н. М. Анфиногенова, учёный секретарь НГОНБ Библиотеки Новосибирской области в...»

«ОАО «НПО «Стример»ГОДОВОЙ ОТЧЕТ ГОДОВОЙ ОТЧЕТ 2012 ОАО «НПО «Стример» СОДерЖАНие Обращение руководства ОаО «нпО «стример» О компании Обзор основных событий 2012 года международная активность позиция ОаО «нпО «стример» на рынке оборудования молниезащиты воздушных линий электропередачи: российский рынок оборудования молниезащиты l воздушных линий электропередачи продуктовый портфель ОаО «нпО «стример» l позиции ОаО «нпО «стример» l Дистрибьюторская сеть ОаО «нпО «стример» l Основные конкуренты l...»








 
2016 www.nauka.x-pdf.ru - «Бесплатная электронная библиотека - Книги, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.