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

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 716
К ВОПРОСУ ОБ ИСПОЛЬЗОВАНИИ ПЕРЕМЕННОЗНАЧНЫХ ПРЕДИКАТОВ ДЛЯ ФОРМАЛИЗАЦИИ АЛГОРИТМОВ ХРАНЕНИЯ ИНФОРМАЦИИ В БИОСИСТЕМАХ
Л.А. Лютикова
В статье рассматриваются логические системы с переменнозначными предикатами, их применение для решения интеллектуальных задач в слабо формализованных областях. Предлагается способ построения решающей функции для заданной предметной области, рассматриваются ее свойства. Как частный пример переменнозначной логики рассматривается система четырехзначной логики, конкретно ДНК- логики
В настоящее время известно значительное количество программных систем, используемых для решения таких сложных задач, как оценка ситуации и выбор решения при управлении сложными процессами- оценка и выбор оптимальных проектных решений- техническая и медицинская диагностика- оценка кредитных и инвестиционных рисков. В силу интеллектуального характера решаемых задач, а также того, что самим системам присущи способности достигать высокого качества формируемых решений, обучаться и объяснять свои решения. Такие системы объединяют достаточно широкий круг программных продуктов и называются интеллектуальными системами (ИС). К ним относятся экспертные системы (expert systems), системы для численного обоснования принятия решения (decision support systems), системы для распознавания образов (текстов, изображения, речи) и некоторые другие.
Одной из основных проблем при создании интеллектуальных систем является выбор модели представления логических закономерностей (знаний). Именно модель представления знаний определяет архитектуру, возможности и свойства системы, а также методы приобретения знаний ИС. В настоящее время известен ряд базовых моделей представления знаний и их модификаций. Каждая из моделей позволяет получить интеллектуальную систему с некоторыми преимуществами, делая ее более эффективной в конкретных условиях, облегчая ее понимание и требуемые модификации.
Однако почти всегда перед разработчиком возникает задача, на базе какой модели представления знаний строить данную интеллектуальную систему применительно к данной конкретной задаче. Какова общая закономер-
Лютикова Лариса Адольфовна — НИИ прикладной математики и автоматизации (г. Нальчик), канд. физ. -мат. наук
ность и логическая связь, исследуемых данных.
Описание объекта представляет собой /7-мерный вектор, где п — число признаков, используемых для характеристики объекта, причем /-я координата этого вектора равна значению у-го признака,/=1,В описании объекта допустимо отсутствие информации о значении того или иного признака. При составлении •эффективной системы следует избегать двух крайностей: избыточности и недостаточности набора признаков. В первом случае важные результаты окажутся скрытыми в массе второстепенных или малозначимых. Во втором — критерий для однозначного опознания конкретных объектов останется не выявленным.
Совокупность объектов и характеризующих их признаков составляет базу данных. После создания базы данных строится база знаний, играющая главную роль в процессе распознавания объектов исследуемой предметной области.
Естественно представить данные в наиболее компактной форме, что позволит сократить время для процедуры вывода.
Задача состоит в разработке методов, позволяющих моделировать и минимизировать систему знаний по исходной базе данных.
Х) = {х, ^), х, (к,). -Х"(н>-/)} -вектор
качественных признаков, каждый элемент которого — фиксированный признак характеризуемого объекта.
т
IV — |^) V"'-: — множество характеризуе-
/¦=1
мых объектов.
Вид функции IV = /(X) не задан. Требуется восстановить неизвестную зависимость, но наблюдениям.
Каждый соответствующий признак в общем случае кодируется предикатом к,-значности (переменнозначным), /е/7 … п].
В работе будут рассматриваться признаки, кодируемые двузначными и переменно-
злачными и, как частный случай, четырехзначными предикатами.
Для нахождения значения функции IV- /(X) системе важно обращаться к базе знаний, которая по запросу
выдаст в случае если и& gt-- принадлежит исследуемой предметной области, или объект (группу объектов), наиболее соответствующих данном запросу.
Предлагаемый принцип моделирования систем знаний по базе данных состоит в следующем:
— совокупность зависимостей между объектами и их признаками будем рассматривать как множество тавтологий, т. е. как некую теорию-
— каждая логическая теория обладает своей аксиоматической системой и правилами вывода-
— в случае нахождения для заданной теории метода отбора её аксиом можно считать искомую базу знаний построенной.
Обычно по аксиоматике строится логическая теория, в данном случае, наоборот, предлагается по заданной теории найти одну из её аксиоматик.
Инверсия обеспечивает включение всех возможных интерпретаций отрицания в различных многозначных логических системах.
Дизъюнкцией двух элементов разной значности является следующая функция:
JH А,-1
4−1
X У.
ггч-----& gt------1
А--! А,-Г
функция:
X У.
tpi-----& lt------]
4−1 *,-Г
где /=¦
в грспивномапчж
Конъюнкцией двух элементов разной значности является следующая
V У
Л'-& amp-К=тп[-----]*/ 1=
V'- кг1 I
' А^-1 б грхптом спхчаг
Импликацию для переменнозначной логики зададим следующим выражением:
X -+У = ХчУ.
Проводя исследование, представляется возможным наблюдать лишь ограниченное число реальных объектов. Нередко и этого
нельзя сделать по каким — либо причинам, и
тогда объекты наблюдаются частично, а некоторые компоненты представляющих их векторов получают неопределенные значения — остается неизвестным, обладает объект данным признаком или нет.
Определение 1. Моделируемая система знаний является полной, если она обеспечивает вывод всех возможных решении.
Определение 2. Моделируемая система знании называется непротиворечивой, если на наборе признаков X, еХ, где X — пространство признаков, невозможно получить выводы X'] -?w! и X] -^ '--м.
Определение 3. Класс — группа объектов, выделенная по определенному признаку (группе признаков).
Каждый объект — представитель некоторого класса однотипных объектов, для которых класс определяет общие свойства: состав и структуру данных.
Дчя каждого случая исследуется возможность построения функции, разбивающей предметную область на классы, выделяющую систему аксиом в заданном пространстве объектов и характеризующих их признаков.
Утверждается, что совокупность исходных данных может быть представлена в следующем виде:
/(A'-) = & amp-7. 1(v^1x (w-)v w (),
где {X} -множество векторов, характеризующих качественные признаки заданных объектов, /^/-множество объектов.
При наличии функции, представляющей совокупность всех данных заданной предметной области (решающей функции), её целесообразно представить в наиболее компактном виде.
Результатом исследования моделируемой функции, п. 3.2 является следующее утверждение:
Утверждение 1. Если правило вида & amp- & quot-=] х (и,)-& gt- vv, , j е[1 ,. т], принадлежит заданной предметной области, то оно реатзовано функцией
/(Ar) = & amp-«,(v-olх{Wj)vw), причем f (X) =Wj,
Xj ={^(4'/X^(w)… -V1,(wy)}
После раскрытия скобок СКНФ получаем ДНФ, к которой применяем алгоритм сокращения. основанный на свойствах, описанных в главе 2.
Теорема 1. Функция:
/(A'-) = & amp-7"(v-«^rjvwz) где х/w?-соответствующий признак, xl (w/) е [0,1], и'-, eW -характеризуемый объект,
есть дизъюнкция всех возможных классов заданной БД.
При неполной, неточной, изменчивой информации рассуждения бывают предположительными и, следовательно, подлежащими пересмотру (модификации). Специализированные задачи высокого уровня (например, диагностика) гоже требуют обращения к модифицированным формам рассуждения. В рассматриваемой задаче данные предполагаются полными, но могут перестать быть таковыми при их наращивании. Проводимые рассуждения должны быть логически корректны, однако эти рассуждения должны быть модифицируемыми. гак как они основываются на изменчивом состоянии системы.
У функции
/(*) = & amp-7"К"*,(^)уид, дизъюнктами являются классы объектов анализируемой предметной области. После сокращения функции получаем базу знаний, не избыточное покрытие данной предметной области. В случае поступления новых данных (вектора признаков и характеризуемого им объекта) проверяем на возможность идентификации объекта или класса, к которому объект принадлежит.
** -& gt-
/(*, (& gt-•••*"(«*)*|-"-.)в
Если объект отсутствуют в исходной БД, новый объект и характеризующие его признаки представляются в виде соответствующего правила продукции. Это правило переводится в дизъюнктивную форму, и решающая функция умножается на данное функциональное представление нового правила. В результате чего возможна некоторая перестройка базы знаний (модификация).
Решающая функция может быть разбита на две функции _/} (X) и //Л). Функция /?(X) представляет собой некоторые комбинации признаков, не играющих роли при получении конкретного значения для данного набора признаков, но имеющих существенное значение при модификации функции, можно сказать, что /у (Х) — совокупность настроечных элементов функции/(X).
Для идентификации конкретного набора признаков с каким либо объектом или классом, представленном в базе данных, достаточно// (X).
Теорема 2. Необходимым и достаточным условием принадлежности объекта, характеризуемого набором
признаков Х] = !*|(& gt-у/),-с2(и'-)… _хДн^)} к классу
КГ является равенство: /?(X) = Кг, *(н)е[0,1] 100
В случаи многозначного кодировани решающая функция имеет вид:
/(Х) = & amp-. тм (ух, vw/) при уе[1. т]
Далее можно применить алгоритм крашения, адаптированный для многознач! логик.
Утверждение 2. Между заданны, пространством признаков и функцией / () существует взаимно однозначное соотвеп ствие.
Анализ построенной функции да возможность угверждать. что в результа применения метода получаем разбиение пр* метной базы на полный набор классов, т. е. «бор признаков, по которым те или иные объ& lt- ты идентичны.
В результате подробного анализа / становится очевидным рекурсивная сост- ляющая при построении, в результате чего I лучаем следующее представление: У (Х), I ИУ-у-моделируемая функция, 2У- характе] стика объектов на текущий момент, (),-стояние системы на текущий момент.
Полученную функцию /(X) можно пр ставить в следующем виде:
П'- (X) = 2Д**и& lt-4*) —
п ______
2* (9* = 2*., & amp- (/ х* (м& gt-() V и-4)
Л —
Ч (.| & amp- (V хк (н-,) V и-,) —
I» I
Я, = & lt-Ь-1 & amp- (V, **
п —
& lt-7, = V *,(*-,) — у = 2,. /и-21 = и-,.
Утверждение 3. Функция, предел ленная системой 1У (х)=2к (дкчкХ) и функция
/(Л'-) = & amp-т"|(^^(н'-^)'-ум'-) при у е[1. т]
х,(^у)е[0… Л,-1], *, е[ 2… Щ
эквивалентны.
В связи с возросшим интересом в учном мире к нано структурам вообщ структурам ДНК в частности, возникает требность фундаментального и приклад1 характера в построении ДНК-логики. Пр| нами такого интереса являются:
— биологическое функционирование ДНК лекул-
— теоретическое обоснование использов- четырехзначной логики для кодирования «тойчивой передачи биологической инфо Ш1и-
применение выявленных закономерностей ля организации параллельных вычислений- построение ДНК — компьютеров как вычис-ительных систем нового поколения, способах решать задачи большой вычислительной ложности.
Полученную в результате исследова-!ия логику назовем ДНК — логикой.
В молекулах ДНК имеется четыре ба-. овых основания: аденин (А), гуанин (О), ци-¦озин © и тимин (Т), связанных друг с дру-ом в цепочку. Здесь используется не двоич-шя, а четверичная логика. И подобно тому, сак в двоичной логике любую информацию ложно закодировать в виде последовательно-: ти нулей и единиц, в молекулах ДНК можно & lt-одировать любую информацию путем сочетания базовых оснований.
А — О С-1 С-2 Т-3
Целью является кодирование и обработка информации при помощи четырехзначных предикатов и моделирования логических операций исследуемой системы.
Комплементарность оснований заключается в том, что образование водородных связей при соединении одинарных цепочек ДНК в двойную цепочку возможно только между парами, А — Т и в — С.
х = К (х)~3& gt--х Операция дизъюнкции и коньюнкции будут задаваться следующим образом: х, & amp-х2 = гтп (х, х2)
х, vx2 = тах (х, х2)
Операция импликации так же как и в классической логике:
х,
х2 = X, V х2
Введем еще несколько функций:
1(х) = -
1 X — і О х*/
U*) = -
/з (*) =
[3 х = 3 І0 х*3
1
х = 3 х * 3
Особые значения в случае кодирования ДНК имеют следующие операции:
Операция ренатурации:
Л (х, Ф х2) = х, о х2 = Яе (х,, х2)
И операция копирования цепочки ДНК:
Сор (х) = х V х
Тогда решающая функция может быть записана в следующем виде:
F (X) = max[Rc ()К., Xt]
/-1
Литература
1. Лютикова Л. А. Моделирование баз знаний в терминах многозначной логики предикатов. Препринт- Нальчик, НИИ ПМА КБНЦ РАН, 2006. 33 с.
2. Закревский А. Д. Логика распознавания. -М: Едиториал УРСС, 2003. — 144 с.
3. Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений. М. Мир, 2004 — 643с.
Научно-исследовательский институт прикладной информатики и автоматизации КабардиноБалкарского научного центра РАН (г. Нальчик)
TO THE QUESTION ON USE VALUE PREDICATES FOR FORMALIZATION OF ALGORITHMS OF
THE INFORMATION STORAGE IN BIOSYSTEMS
L.A. Lyutikova
In article logic systems with value predicates, their applications for the decision of intellectual problems in poorly formalized areas are considered. The way of construction of decision function for the set subject domain is offered, its properties are considered. As the private example value logicians is considered system of four-unit logic, particularly DNA — of logic

ПоказатьСвернуть
Заполнить форму текущей работой