Статьи по вышке
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.50 (1 Голос)

Алгебраические модели

Как уже отмечено, объектом исследований в кибернетике является информация и информационные явления. «Инструментом» для переработки информации служит ЭВМ. Естественно, что для понимания и описания процессов преобразования информации требуется специальный математический аппарат. После серии попыток и исканий в качестве такого аппарата утвердилась алгебра, которая в данном смысле стала именоваться информационной алгеброй. Решающими работами в этом направлении для инженерных кругов явились публикации Кодда по реляционной алгебре, которые легли в основу математического описания так называемых реляционных баз данных.

Существует большое количество определений и концепций построения алгебр и логик.

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

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

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

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

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

Логико-алгебраические модели

Алгебраические модели отличает от моделей с исчислением (в которых присутствуют связанные переменные) наличие свободных переменных. Осуществим попытку объединения всех моделей на основе лингвистической концепции.

Лингвистическая концепция интересна тем, что она принципиально обеспечивает рассмотрение с единых позиций не только логико-алгебраических моделей, но и моделей автоматно-лингвистических и моделей СИИ. Благодаря положенной в основу построения любой логико-алгебраической исходной предпосылки, состоящей в том, что, прежде всего, необходимо составить описание предметной области (для которой создается модель) на неформальном U-языке (конкретизировать его), все многообразие существующих модулей удается подчинить единой идеологии. Кроме того, благодаря этому утверждается концепция существования бесконечно большого числа моделей, каждая из которых ориентирована на конкретную предметную область (так же как профессиональный искусственный интеллект).

1. Классификация логико-алгебраических моделей.

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

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

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

Наибольший интерес представляет лингвистическое направление, в основном развитое в работах Х. Карри[1]. Появление большого числа логико-алгебраических моделей, разработанных в математике, вызвано потребностями практики, стремлением описать все встречающиеся ситуации, реальные системы. Поэтому в логиках и алгебрах появилось понятие предметной области, под которой понимается совокупность реальных объектов, отношений между ними и т. д. Каждая модель должна быть ориентирована на определенный класс конкретных предметных областей. Для решения проблемы семантики и прагматики модели, как правило, необходима процедура интерпретации ее на конкретную предметную область. В связи с этим появилась лингвистическая концепция, в основе которой лежит неформальный U-язык. С помощью этого языка производится описание предметной области. После чего в работу включаются более формализованные языки: А-язык (строго формализованный в семиотическом смысле) и О-язык (язык объектов). В этих языках вводится серия понятий и конструкций, с помощью которых можно построить логико-алгебраическую модель любой предметной (или как иногда говорят, проблемной) области. При этом достигается адекватность модели исходной предметной области и определенный автоматизм ее составления.

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

В лингвистическом направлении чрезвычайно плодотворным оказалось появление понятий свободных и связанных переменных. Это позволило отделить от алгебраических моделей модели типа исчислений: l-исчисление, исчисление предикатов, реляционное исчисление Кодда, в которых присутствуют связанные переменные.

В более широком смысле любое исчисление является некоторой математической моделью процесса перехода от посылок к следствию, проводимого по определенным правилам вывода. Именно так термин исчисление используется во многих разделах математики. При этом связанные переменные могут отсутствовать, но во многих математических моделях использование связанных переменных (через кванторы, l-операторы и т. д.) делает процесс перехода от посылок к следствию существенно более эффективным.

Алгебраические модели только со свободными переменными составляют вторую ветвь лингвистического направления, объединяющую булеву алгебру, реляционную алгебру, алгебру нечетких множеств. Особую ветвь составляют различные лингвистические системы, которые в алгебраическом смысле представляют собой так называемые полусистемы Туэ. Один из вариантов освобождения от связанных переменных, сохраняющий в то же время эффективность, которую они обеспечивают, представляет комбинаторная логика. Комбинаторная логика представляет в некотором смысле промежуточное звено между лингвистическом и структурным направлениями. В зависимости от структуры множеств и операций над ними структурные логико-алгебраические модели делятся на три совокупности моделей: слабой и средней алгебраизации (собственно модели) и сильной алгебраизации (алгебры). Среди моделей слабой алгебраизации имеет место алгебра графов. Содержание моделей средней алгебраизации представляют полусистемы Туэ, лингвистические системы с разными грамматиками и автономными моделями. Эта совокупность наиболее удачно поддается описанию структурными методами. Раздел моделей сильной алгебраизации составляют те же модели лингвистического направления со свободными переменными: булева алгебра, реляционная алгебра, алгебра нечетких множеств.

2. Основы лингвистического метода построения логико-алгебраических моделей.

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

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

Введем в рассмотрение некоторые понятия. Теория – это некоторый аппарат, позволяющий выявлять истинные высказывания из набора всех высказываний. Система – частный случай теории. Для удобства работы с системами расплывчатый U-язык уточняется до А-языка, языка в так называемом семиотическом смысле, а последний еще более уточняется до языка объектов О-языка. В заключение рассмотрим понятие переменных, среди которых выделяются две группы: свободные и связанные, положенные в основу принятой классификации алгебраических моделей.

Результаты любого исследования предметной области одни люди сообщают другим посредством языка (назовем его U-языком). Невозможно исчерпывающе описать U-язык. Единственное, что утверждается – это то, что он содержит неопределенность, но всякое научное исследование связано с той же неопределенностью. Поэтому вместо исчерпывающего описания U-языка явно оговаривают лишь те случаи, которые могут быть неправильно истолкованы. U-язык обладает следующими особенностями:

1. для каждого конкретного контекста он единственен;

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

3. он развивается (можно вводить новые термины и символику, либо использовать старые термины в новом смысле);

4. он неясен, однако, пользуясь им, можно достичь любой разумной степени точности.

Целый ряд проблем создания модели решается путем изучения языка, на котором они выражены. Такие исследования являются предметом изучения семиотики, науки о символах. Основное его понятие – язык.

Язык задается следующим образом:

1. фиксируется алфавит как набор символов (букв);

2. определяются правила, как из букв образовывать выражения (слова).

3. Основные понятия языка

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

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

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

Основные виды функторов:

1. операторы (преобразуют имена в имена);

2. глаголы (преобразуют имена в предложения);

3. коннекторы (преобразуют предложения в предложения);

4. субнекторы (преобразуют предложения в имена).

Можно говорить, что фраза имеет значение (см. таблицу 1).

Таблица 1.

ФРАЗА

ЗНАЧЕНИЕ

Фраза

Значение, элемент

Имя

Объект

Предложение

Высказывание

Функтор

Функция

Оператор

Операция

Глагол

Предикат

Коннектор

Союз

Субнектор

Субнекция

Часть функторов употребляется в формальном смысле (см. таблицу 2).

Таблица 2.

 

Предписание определяет эффективный процесс для достижения определенной цели по отношению к элементу, если предписание (при условии, что элемент задан) однозначно определяет такую последовательность преобразований, что цель достигается за конечное число шагов. В соответствие с ранее изложенным, предложение может быть истинным или ложным.

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

4. Метод построения объектов

Посредством U-языка формируются свойства (или отношения), которые определяют содержательным путем совокупность элементов или понятий. Такие содержательные совокупности называют концептуальными классами (или отношениями).

Индуктивный класс X определяется начальными правилами и правилами порождения. Начальные правила определяют начальные элементы. Начальные элементы образуют класс B, называемый базисом X. Правила порождения определяют фиксированный класс способов комбинаций M. С каждым таким способом m связывается определенное число n, называемое его степенью, Это значит, что применение любого такого способа m степени n к последовательности n аргументов, каждый из которых является элементом X дает элемент X (предполагается, что вопрос о том, получается ли элемент описанным ранее способом из данных аргументов, является определенным, и что каждый элемент X может быть получен с помощью эффективного процесса, который начинается с определенных начальных элементов и на каждом шаге которого способ комбинации из M применяется к уже построенным аргументам). Понятия индуктивного класса можно употреблять, по крайней мере, в двух случаях:

1. когда элементы являются объектами, а способы комбинации – операциями;

2. когда элементы являются высказываниями, а способы комбинации – связками.

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

Процесс получения элемента X, принадлежащему индуктивному классу X, посредством итерации способов комбинации называется конструкцией элемента X (относительно X).

Определим понятие древовидной диаграммы D, которая состоит из узлов, соединенных друг с другом следующим образом. Имеется единственный узел, и каждый узел, не являющийся нижним узлом, соединен с единственным узлом, расположенным ниже. Каждому узлу, не являющемуся верхним узлом, приписана единственная операция m из M, и число узлов, соединенных с этим узлом и находящихся над ним, в точности равно степени m.

Пусть G – конструкция элемента X. Считают, что древовидная диаграмма D ассоциативна с G, если существует взаимно-однозначное соответствие между узлами D и элементами X, встречающимися в конструкции G, удовлетворяющее следующим условиям: нижний узел диаграммы D соответствует X, и если Y образован в конструкции G применением операции m к аргументам в указанном порядке, то узлу, соответствующему Y, приписывается та же операция m, и расположенные выше узлы, соединенные с данным узлом, при расположении слева направо в точности соответствуют .

В этом случае верхние узлы будут соответствовать начальным элементам.

Древовидная диаграмма D размечена (относительно конструкции G), если каждый узел диаграммы D сопоставлен с именем соответствующего элемента G. На практике, в качестве узлов выбираются экземпляры различных элементов из X, которым соответствуют эти узлы; над каждым узлом, не являющимся верхним, проводят горизонтальную линию, а справа от нее пишут имя операции, участвующей в образовании этого узла. Над чертой пишут узлы, соответствующие аргументам, к которым применялась операция, в том же порядке.

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

Теории. Пусть C – класс элементарных высказываний, то есть таких высказываний, которые образуют определенный класс.

Теория над классом C определяется как некоторый концептуальный класс таких элементарных высказываний.

Элементарные высказывания, принадлежащие теории Т, назовем элементарными теоремами Т (говорят, что эти элементарные высказывания истинны для Т).

Рассмотрим три разновидности теорий: непротиворечивые, разрешимые и дедуктивные, а в дедуктивных теориях особо выделим полные теории.

Теория – это способ выбора подкласса истинных высказываний из числа высказываний, принадлежащих классу C.

Теория Т2 является надтеорией Т1 (Т2 – расширение Т1); Т1ÍТ2, если каждая элементарная теорема Т1 является также элементарной теоремой Т2.

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

В инженерной (в том числе и инженерно-экономической) практике часто используют так называемые дедуктивные теории. Теория Т называется дедуктивной, если Т является индуктивным классом элементарных высказываний.

Очевидно, что исходные элементы образуют разрешающую теорию G. Элементы теории G называются аксиоматическими высказываниями (аксиомами). Способы комбинации образуют некоторое множество Â дедуктивных правил (правил вывода); каждое из них дает элементарную теорему, когда соответствующее число элементарных теорем дано в качестве посылок. Конструкция, удовлетворяющая всем перечисленным условиям, называется доказательством (формальным). Правила и аксиомы называют одним термином: постулаты.

Дедуктивная теория Т полна (в смысле Поста), если присоединение к ее аксиомам элементарного высказывания, не являющегося элементарной теоремой, при сохранении правил неизменными делает теорию противоречивой.

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

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

Интерпретация считается правильной, если интерпретант каждой элементарной теоремы (т. е. каждого истинного элементарного высказывания) является истинным.

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

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

Элементарные высказывания, на которых основана теория, являются формальными высказываниями, поскольку они содержат ряд неопределенных параметров.

Будем считать, что параметры появляются как неопределенные объекты, о которых делаются утверждения, что некоторые из них обладают определенными свойствами или, что между ними имеют место определенные отношения.

Теория, утверждения которой образуются таким образом (как изложено выше), называется системой.

Введем в рассмотрение определенный концептуальный класс объектов, называемых формальными объектами, и концептуальный класс предикатов (см. табл. 1.), называемых базисными предикатами, причем каждому из базисных предикатов сопоставляется определенное число, называемое его степенью.

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

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

Пример 1. Возьмем предложение: «Сократ есть человек» и проанализируем значение этого предложения, т. е. рассмотрим его как высказывание. Конструкция «_____ есть человек», или « есть человек» представляет собой предикат (сказуемое, глагол), а «Сократ» – субъект (подлежащее). Используем при анализе « есть человек» обозначение и будем иметь ввиду математическое понятие переменной.

В этом случае выступает в роли пропозициональной функции, т. е. такой функции, значениями которой служат высказывания (предполагается, что переменной она ставит в соответствие высказывание, которое может быть истинным или ложным). Например, если Сократ, истинно, в если дождь, то ложно.

Для представления системы в U-языке решают проблему обозначения формальных объектов и базисных предикатов, а также указывает средства для соединения их с целью образования U-предложения, выражающего основные утверждения. Эти обозначения в совокупности образуют язык в семиотическом смысле (А-язык).

Имена формальных объектов называют А-именами; глаголы, обозначающие базисные предикаты, называют А-глаголами. Предложения А-языка, выражающие элементарные высказывания, называют А-предложениями, А-язык добавляется к U-языку для использования его внутри этого языка.

Пример 2. Действительно, обозначение « есть человек» – более сжатая форма, чем «____ есть человек». Для установления связи между этими выражениями и U-языком их рассматривают как незаполненные места для подстановки слов, обозначающих объекты.

Так, фразы:

а). «Имеется некто, кто есть человек»;

б). «Никто не есть человек»;

в). «Всякий есть человек»

можно с помощью символов и перевести на А-язык:

а). , б). , в). .

Формальные объекты рассматриваются как выражения некоторого языка-объекта (О-языка). Имеется определенный запас О-символов, или букв, составляющих О-алфавит. Формальные объекты являются конечными последовательностями этих букв.

Введенные три разновидности языка образуют естественную иерархию. Можно считать, U-язык – некоторая расплывчатая среда, рамки которой устанавливаются посредством А-языка, а в рамки А-языка вкладывается О-язык.

Рис. 1. а). вложимость языков; б). шкала языков.

Разновидность синтаксической системы называется исчислением, если формальные объекты представляют с помощью операции сочленения Λ.

Пример 3. Если и буквы, есть , есть , то есть .

Дедуктивная теория, основанная на синтаксической системе, содержит два вида правил, называемых правилами образования и правилами преобразования. Этим объясняется происхождение названия исчисление предикатов, или более точно, исчисление пропозициональных функций.

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

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

Дедуктивная система, в которой объекты образуют индуктивный класс, называется об-системой. Элементы этого индуктивного класса называются обами, его начальные элементы – атомами, способы комбинации – операциями. Об, также как и конструкция, представляется древовидной диаграммой. В этом отношении об противопоставляется О-выражению, которое представляется в виде линейного ряда.

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

Пример 4. Пусть в U-языке имеется набор предложений: «Все люди бессмертны. Сократ есть человек. Следовательно, Сократ бессмертен».

Введем обозначения А-языка:

»Сократ»,

« есть человек»,

« бессмертен»,

«все такие, что…».

Вывод в О-языке имеет вид:

и получен по правилам образования и преобразования О-языка.

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

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

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

Система с единственным базисным одноместным предикатом, который выделяет некоторый класс формальных объектов, называется ассерторической (от assertion – утверждение).

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

Термин переменная применяется к определенным фразам U-языка, значение которых не фиксировано. Эти фразы называют U-переменными, в противоположность U-постоянным, значения которых фиксированы.

Ряд систем содержат обы, называемые переменными, потому что вместо них можно производить определенные подстановки. Их называют формальными переменными; они не являются А-выражениями, но могут быть выражениями О-языка. С точки зрения U-языка они являются объектами, а не символами.

Пример 5. Рассмотрим высказывание

Которое для некоторых истинно, а для других ложно.

Отметим, что в данном случае в процессе подстановки действительное истинное значение формулы в расчет не принимается. Подставим вместо :

Можно считать, что подстановка свелась к замене на . Обычно различают среди формальных переменных подстановочные и связанные.

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

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

Пример 6. Например, в равенстве

Следует учитывать ограничение в подстановках, производимых вместо : если подставить выражение, содержащее , то полученное равенство будет ложным.

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

Алгебраические модели - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

Google