К вопросу о сокращении переменнозначной логической функции

Тип работы:
Реферат
Предмет:
Физико-математические науки


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

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

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

УДК 519. 716. 325
К ВОПРОСУ О СОКРАЩЕНИИ ПЕРЕМЕННОЗНАЧНОИ ЛОГИЧЕСКОЙ ФУНКЦИИ
Д.П. Димитриченко
В настоящей работе предлагается метод сокращения логической функции, построенной по обучающей выборке исследуемой предметной области. Предложенные алгоритмы сокращения и восстановления логической функции окажутся полезными для эффективного хранения как обучающей выборки, так и логической функции без потери информации об объектах
В работе предлагается метод сокращения логической функции, построенной по обучающей выборке исследуемой предметной области. Предложенные здесь алгоритмы сокращения и восстановления логической функции окажутся полезными для целей сокращенного хранения как обучающей выборки, так и логической функции, без потери информации об объектах, а так же для быстрого приведения логической функции в исходный вид для корректного добавления в нее данных о новых объектах (или новых характеристик уже известных объектов).
В работе [1] был рассмотрен прикладной вопрос, касающийся интерпретации дизъюнктов переменнозначной логической функции, построенной по базе данных сетевых топологических структур. Здесь мы рассмотрим вопрос о минимизации логической функции, построенной по базе данных некоторой произвольной предметной области при условии сохранения свойства полноты, понимаемого в смысле [2], как свойство системы логических функций, построенных по обучающей выборке некоторой предметной области описывать все, содержащиеся в ней объекты. Задача анализа исследуемых объектов некоторой предметной области при помощи переменнозначных предикатов путем построения логических правил в общем виде формулируется следующим образом:
Пусть п количество логических переменных (актуальных характеристик), по которым описываются содержащиеся в базе знаний или обучающей выборке (ОВ) объекты. Такая выборка является основой для построения в общем случае системы логических функций, вид, которых заранее не задан.
Обучающая выборка может быть представлена следующей таблицей:
Димитриченко Дмитрий Петрович — НИИ прикладной математики и автоматизации (г. Нальчик), младший научный сотрудник
Таблица 1
X, X 2 X) хп IV
Х,(п,) X: (*',) X }(у& gt-1) хп («,) и»,
X ,(*2) Х](М& gt-2) Х)(Н'2) Х"(м& gt-2) IV-
X ,(wJ Х2(^т) Х}(м& gt-«) Хп (^т) И'-*
где каждый соответствующий признак в
общем случае кодируется предикатом к,-значности. к, & gt- 2, 1−1. п, ,/и.
Функция, построенная по такой ОВ, способом. предложенным в [2], будет иметь следующий вид:
/(*) = Лм (д1,)-& gt-"-,) =
(I)
Указанный вид функции следует из известного
тождества: а -» Ь = а V Ь. где, а коныонкция характеристик, определяющих объект, а Ь-предикат, равный единице, когда м", становится равным соответствующему определяемому объекту. В рамках данной статьи такие предикаты мы будем обозначать (), О-, О},… и называть объектными предикатами.
Дадим ряд необходимых определений. Определение 1. Предикаты х, (н,/), обладающие значностью к,. к/ & gt-2 называются
переменнозначными. ,
Определение 2. Функция /& lt-Х) вида (1), посгроенная на основе переменнозначных предикатов называется переменнозначной логической функцией.
Определение 3. Логическим рангом дизъюнкта называется число входящих в этот дизъюнкг логических переменных [3].
Определение 4. Продукционным рангом дизъюнкта называется количество оГ& gt--г-ных предикатов, входящих в этот дизъю
Определение 5. Классом называется дизъюнкт, являющийся конъюнкцией одной и более логических переменных (логический ранг которого больше либо равен единице) и продукционным рангом отличным от нуля.
Определение 6. Дизъюнкт, логический ранг которого равен нулю, а продукционный ранг равен т, т. е. числу всех, содержащихся в исходной базе данных объектов называется объектным.
Отметим, что во всякой логической функции, построенной по исходной базе данных, способом, изложенным в [4] это будет единственный дизъюнкт, представляющий собой конъюнкцию всех, содержащихся в базе данных объектов.
Определение 7. Два класса называются равными, если они характеризуют совпадающие множества объектов.
Определение 8. Если множество предикатов объектов первого класса целиком содержится во множестве предикатов объектов второго класса, то говорят, что второй класс строго больше первого класса, или, что тоже самое, что первый класс строго меньше второго.
Из данных определений следует, например, что продукционный ранг любого из дизъюнктов, характеризующих свободные знания равен нулю, а общим свойством дизъюнктов, характеризующих объекты по одному или нескольким свойствам, является одновременное неравенство нулю обоих из выше определенных рангов. Логический ранг объектного дизъюнкта, равен нулю, а его продукционный ранг равен т, т. е. общему числу объектов, содержащихся в базе данных.
В рамках нашего исследования мы будем исходить из следующих очевидных соображений-
1. Каждый объект характеризует-
ся единственным набором из п логических переменных х 1=1, …, п с соответствующими значениями к, к2.к.
12 ' п
2. Множество описываемых объектов конечно.
3. Логическая функция в силу свойства полноты описывает все содержащиеся в ОВ объекты.
Из выше сказанного вытекает следующая важная лемма:
Лемма. Каждая логическая переменная
Х1 по совокупности своих значений во всех
фазах в соответствии со значностью к, 1=1,2,…, п характеризует все множество содержащихся в обучающей выборке объектов.
128
Данная лемма дает возможность применить способ покрытия столбцов строками матрицы для нахождения минимального числа дизъюнктов, обеспечивающих свойство полноты логической функции при помощи метода Петрика.
Для этого из множества дизъюнктов логической функции выделим все дизъюнкты, являющиеся классами согласно определению 5. за исключением объектного дизъюнкта и перенумеруем их.
Такие дизъюнкты мы будем называть продукционными. Для каждой из п логических переменных построим матрицу, по столбцам которой выпишем все т объектов, входящих в исходную базу данных, а по строкам матриц отметим номера дизъюнктов, определяющих объект по данной переменной. На пересечении 1-й строки ]'--ого столбца будет стоять единица, если 1-й дизъюнкт содержит (определяет) }-й объект, предикат которого содержится в этом дизъюнкте, и ноль в противном случае. Тогда оптимальным покрытием столбцов строками каждой из матриц по каждой из п переменных, согласно методу Петрика, будет минимальное множество дизъюнктов, описывающих все объекты по этой переменной.
Выделенное при помощи метода Петрика минимальное множество дизъюнктов, характеризующее все множество объектов, по каждой из у переменных, мы будем называть базисным, а каждый из базисных дизъюнктов -базисным классом по соответствующей переменной. На практике базисные дизъюнкты редко совпадают с множеством продукционных дизъюнктов, но в большинстве случаев содержатся в их множестве. Поэтому следующим шагом нашего исследования является вопрос о возможности получения оставшихся продукционных дизъюнктов, содержащихся Е логической функции.
Докажем следующие теоремы.
Теорема 1. Если два различных класс- содержат предикаты общих объектов, то от порождают подкласс, являющийся конъюнк цией всех входящих в эти классы логически: переменных и содержащихся в них предикато общих объектов.
Доказательство проведем методом математической индукции. Построим функк-цию, описывающую три объекта, каждый из которых характеризуется набором из двух двузначных переменных. Обучающая выборка для такой функции будет иметь следующий вид, представленный в табл. 2.
Таблица 2
XI Х2 1 Объект
0 0 о, 1
1 о р
1 1 О,
Логическая функция, построенная по такой обучающей выборке, имеет следующий вид:
X* А *2 V XЛ ()? Л О у V х! Л О, Л О, V
V X, 1 А *2 Л 02 V 0{ А (А Л Оу
Заметим, что, в общем случае, логические переменные могут быть произвольной значно-сти. Выбор логической переменной с большей значностью, во-первых, не окажет влияние на формирование текущего подкласса, во-вторых, формальное изменение значности хотя бы одной из переменных без добавления новых объектов приведет лишь к появлению новых дизъюнктов во множестве переменных, описывающих свободные знания, т. е. такие значения логических переменных, которым не сопоставлен ни один объект, и опять-таки что не окажет влияние па уже сформированный подкласс. Если же увеличение значности будет сопряжено с добавлением новых объектов, то это вызовет лишь расширение уже существующих классов, и приведет к возможном) образованию новых подклассов без потери ранее образованных (подклассов с меньшими, существовавшими значениями логических переменных), и мы снова приходим к утверждению теоремы 1.
Предположим, что утверждение теоремы верно для функции, характеризующей объекты по / логическим переменным произвольных значностей. Чтобы обобщись этот результат на функцию от произвольного числа логических переменных, докажем, что угвержде-ние теоремы верно и для функций, содержащих 1+1 переменную. Действительно, предполагая 1−1 переменных несущественными, мы. тем самым, всегда сможем привести рассматриваемый случай, к ситу ации, когда три объекта образуют два класса, и при этом, общий для них объект будет выделен в самостоятельный третий подкласс, что и доказывает утверждение теоремы.
Следствие 1: Всякий подкласс строго меньше любого из порождающих его классов. Действительно, в противном случае такой подкласс, совпадающий по множеству объек-
тов с каким-либо из порождающих его классов. и обладающий большим чем у порождающего класса логическим рангом, т. е. имеющий в своем составе большее число логических переменных, был бы сокращен по закону поглощения, и, как следствие, не входил бы в состав логической функции. Порожденный класс не может быть и больше порождающего, поскольку, в этом случае он должен был бы сократиться по закону поглощения порождающим классом, так как он имел бы большие, чем у порождающего класса логический и продукционный ранги.
Следствие 2. Продукционный дизъ-юнкг, имеющий в своем составе единственный объект, не может породить ни какой подкласс.
Доказательство этого следствия непосредственно вытекает из следствия 1.
Следствие 3: Дизъюнкт, являющийся базисным, необходимо определяет максимальный класс по данному значению логической переменной.
Действительно, в противном случае, существовал бы более широкий порождающий класс, при наличии которого наш класс не мог бы является базисным, что и доказывает указанное следствие.
Следствие 4: Базисный дизъюнкт имеет логический ранг равный единице.
Действительно, дизъюнкт, обладающий логическим рангом два, и выше характеризует множество объектов, являющихся пересечением как минимум двух классов, при этом согласно теореме 1 такой класс хотя бы на один объект меньше любого из порождающих его классов, а с другой стороны, согласно следствию 3, базисный класс должен быть максимально широким. Отсюда следует, что дизъюнкт, обладающий логическим рангом, больше единицы не может быть базисным.
Теорема 2. При поиске минимального покрытия столбцов строками матрицы объектов по каждой из п логических переменных не могут найтись два различных покрытия.
Доказательство. Предположим, что это не так, и существуют два различных минимальных покрытия, характеризующих всю совокупность объектов по некоторой переменной х" 1−1,2.п. Тогда, в силу того, что по-
крытия различны, найдется хотя бы один объект, который одновременно принадлежит двум различным базисным классам, соответствующим двум различным фазам переменной х, в этих покрытиях. Однако это противоречит нашему допущению о том, что каждый объект
однозначно характеризуется набором из п логических переменных.
На основе всего выше сказанного, мы можем сформулировать следующие алгоритмы получения минимальной формы логической функции и способа восстановления из минимальной формы исходной логической функции.
Алгоритм сокращения продукционной части логической фу нкции:
1. По обучающей выборке построить логическую функцию, или систему таких функций-
2. Выделить из общего множества дизъ-юнкгов проду кционные и объектный-
3. Выбрать дизъюнкты, обладающие логическим рангом равным единице для образования множества базисных классов-
4. Для каждой логической переменной х удалигь базисный класс с наибольшим продукционным рангом (счигая. что объект, который не характеризуется ни одной из оставшихся значностей к,-1. охарактеризован переменной, отсутствующей среди аксиом значно-стью) —
5. Выделенные таким образом дизьюнкты составляют сокращенную форму продукционной части логической функции.
Алгоритм восстановления логической функции из сокращенной формы, полученной в результате работы предыду щего алгоритма:
1. Руководствуясь базовыми классами по каждой из переменных х" и объектным дизъюнктом восстановить отсутствующий базисный класс-
2. Попарно сравнивая базисные классы на наличие общих объектов последовательно строить подклассы второго и т. д. логических рангов, соответственно, пока продукционные ранги порожденных классов не станут равными единице-
3. Полученное таким образом множество порожденных подклассов и множество исходных дизьюнктов объединить в продукционную часть искомой логической функции.
Научно-исследовательский институт прикладной Балкарского научного центра РАН (г. Нальчик)
Замечание 1. И случае, когда при описании совокупности объектов некоторая фаза (некоторое из ее значений) какой-либо из переменных оказывается задействованной не полностью, для однозначного восстановления отсутствующего базисного класса пекле работы атгоритма сокращения на основе классов к, -I необходимо наличие логической переменной из группы свободных знаний с логическим рангом один.
Замечание 2. Определение логической функции от п переменных можно представить, как «-мерную область (или. точнее л-мерный параллелограмм), тогда всякой конъюнкции из Ь (2 & lt-= Ь & lt-= п) будет соответствовать пересечение из 1^ ортогональных плоскостей. При лом, в предельном случае, когда I. = п конъюнкция из п различных логических переменных определяет единственный объект. Это, в свою очередь, с одной стороны иллюстрирует наше допущение об однозначном представлении объекта набором из л переменных, а с другой стороны, следствием того факта, что всякий порожденный класс строго меньше любого из порождающих его классов.
Замечание 3. Необходимое наличие объектного класса как в указанных алгоритмах, так и в неявном виде в качестве столбцов матриц в методе Петрика свидетельствует о важности допущения о конечности множества описываемых объектов.
Литература
1. Димитриченко Д. П. К вопросу об интерпретации дизъюнктов переменнозначных логических функций, построенных по базе знаний сетевых топологических структур. / Вестник ВГТУ. 2008. Том 4. № 4. С. 81 — 85.
2. Лютикова Л. А. Моделирование баз знаний в терминах многозначной логики предикатов. Препринт-Нальчик, НИИ ПМА КБНЦ РАН, 2006. — 33 с.
3. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. М: Наука. Физматлит, 2000. — 554 с.
4. Лютикова Л. А., Тимофеев А. В. Развитие и применение многозначных логик и сетевых потоков в интеллектуальных системах. // Труды СПИИ РАН, вып. 2. 2005. С. 114- 126.
информатики и автоматизации Кабардино-
TO THE QUESTION ON REDUCTION VALUE LOGIC FUNCTION D.P. Dimitrichenko
In the present work the method of reduction of the logic function constructed on training sample of the investigated subject domain is offered. The offered algorithms of reduction and restoration of logic function will appear useful to effective storage both training sample, and logic function, without loss of the information on objects

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