Об одном методе распознавания в классах функций алгебры логики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО

На правах рукописи

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

01.01.09 - Математическая киберенегака.

Автореферат на соискание- учной степени кандидата физико-математических наук

Саратов -1997

Работа выполнена на кафедре теоретических основ информатики Саратовского государственного университета им.Н.Г.Чернышевского . . '

Научный руководитель -

академик АЕН РФ, доктор т.н., профессор

А.М. Богомолов

Официальные оппоненты

чл.-корр. РАЕН, доктор т.н., АА. Сытник

чл.-корр. АТНУ, доктор т.н. профессор, Д.В. Сперанский - . кандидат физико-математических наук В. А.'Башмаков Ведущая организация ' Институт проблем точной

механики« управления РАН Защита состоится 1997года, в {У час.

на заседании Диссертационного совета К.063.74.04. при Саратовском государственном университете имени Н.Г.Чернышевского по адресу: 410026, г.Саратов, ул.Астраханская, 83, Саратовский государственный университет, механшсо-математичесжий факультет. . "

С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета.

Автореферат разослан ¿¿¿> 1997 года.

Ученый секретарь Диссертационного Совета, кандидат физико-математических наук,

доцент Недорезов П.Ф.

Общая характеристика работы

Актуальность. Развитие элементной базы, внедрение интегральной: технологии обусловили разработку козых математических моделей сложных технических'систгм-. Появление-и широкое использование однородных сред, систетл с переменной структурой требует создания" математических моделей, которые способны адекватно отражать их возможность реализации некоторого спектра законов функционировали'!, формальной точки зрения такого рода математические модели можно аденггпфкциропать как ушпзерсатьные й многофункциональные модули ;УЛМиМЛМ). ' •

Ряд азторов - М.Минсккй, В.Б.Кудрязцеа, Я.М.Бгрздипь,' МЛКрадо; • изучали проблему универсальности с точки зрения фунюзюяальЕОй юлкоты на множестве конечных автоматов. Бтсрой подход к проблема /нкг-ереалькостн связан с именем Шеннопа, который определил кваср .юдолей (универсальные мазкгаы Тыоракга), чолелируюжне фузгсцпо-афовагагэ произвольной машины Тьюргага при постройте универсальной «гшины соотаетстзугеннш входным гоздейстсисм (гедглесым номером). • \.А,Сытником я 1984 году была предложена модель уюгеерсаяьного ттомата, позволчюшач адекватно описывать футпзягогшрезшше дасх» зетпых систем с пзмятыо, обладающих способностью "настрггигагься" п • гаъедннлющая концепции Шишока и Минского - Кудрявцева па нюжгепе конечных автоматов. Задач;! синтеза комбшшшенкых УЛМ я \ЛЛМ рассматривались в работах Э. А. ЯкубаЯтаса, И.В. Прзнпшгяли, ^..М.Богомоло'ва В.И.Варшавск./го, В.Л.Артюхова, В.А.Мигцеихо и др.

Представляют интерес УЛМ и МДМ, реализующие беспозтор-Ные формулы. Это ограничение на повтерноегь з содержательной интер-[ретаиии не является сушестаеккым, поскольку исследования показали,'

что настраиваемые логические модули для построения управляющих логических устройств промышленной автоматика, исходя из специфики булевых формул, описывающих алгоритмы их фушшдош1роваш1Я,.долгпн быть способны ргалкювать путем настроГош не произвольные фуЕкщш с перемекьых, а лишь только те ш них, дги которых булевы формулы бесповгорных или обладают малой швторностью пергмеЕных. Таким образом, во многих случаях можно ограничиться УЛМ н МЛМ, порозкдающгзе функции которых заданы бесповторными формулами ' алгебры логики. Задача диагностического обеспечения и контролепригодности для таких Модулей сводится к задаче распознавания беспозгорных булевых формул в заданном базисе.

Начало математической теории тестового контроля в даагаосткхв было положено С.В.Яблоис5а1м в 1955 году, который праддоаип обздкй алгоритм получения теста дна электрических с:&м. Проблемой изхагкдг-ыкя полного диагностического теста без перебора асах фуякцкй певсырав-Еогтей занимались Д.В.Сперанекий, В.И.Казыгчгев и др. Среда большого числа пубтшщкй Бахаю; место занимают работы В.Б.Кудрявцеза, ПЛ.Пар;;омекко, В.А.Твгрдахлгбова а др. Вопросы построе1шя тесгез ддг бегаоьторных контакт? цлх схем- рассматривались в работах X А-Мадатшга.

Цель рсбати. Целыо диссертационной работа гвдагтся:

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

2. Разработка методологического к аягоршгнжского обеспечения для решения задач построения полных тупиковых теегта в классах бесповторных булевских функций. -

3. Разработка диагностического обеспечения универсальных и шгого-фушецйоштышх Л01 кчееккх модулей, рсалазукзпйж дискретные функции.

Методы и средства исследований. В диссертационной работе «¡пользуется математический аппарат теории множеств и отношений,

V

иализа вычислительных алгоритмов и технической диагностики.

Научная новизна. В работе предлагается новые математические *етоды распознавания бесповторных формул, реализующих булевские эупкции в базисе {V,' &, 1 } и в классе кгазимонотонных функций. Методика основывается на специально» харакгеризации области щределения функции, называе.мсй а-сеойстзом. Разработан алгоритм юстроения полного минимального теста для бесповториых, формул в ¡азисе {V, &, 1}. Предложен алгоритм построения полного тупикового еста для бесповторных формул в класса квазимонотонных функций.

Апробация работы и публикации. По ;-еме диссертации опубли-овано 5 работ [1-5]. Основные результаты докладывались на семинарах в. Московском и Саратовском государственных университетах, на семинаре 1Ц АН СССР, на Всесоюзной конференции по теории и методам некор-ектно поставленных задач и их приложений (Саратов, 1985), на 8-ой всесоюзной конференции по теоретическим проблемам кибернетики Маратов, 1986), на Всесоюзной .конференции по методам синтеза и панирования развития структур крупно-масштабных систем (Саратов, 986), на школе-семинаре молодых ученых по теоретическим проблемам: ибернетики (Звенигород, 1987), на Всесоюзной конференции "Искус-гвенный интеллект в АОС" (Саратов, 1987), на Всесоюзной конференции Управление вычислительными « контрольно-измерительными комплех-ши" (Саратов, 1988), на 2-ой зимией школе по управлению вычисли-гльными« контрольно-измерительными комплексами (Саратов, 1990), на сесоюзной конференции "Экспертные обучающие системы" (Саратов, ?91), 7-ом Всесоюзном совещании по технической диагностике и гказоустойчивоста (Саратов, 1990), на 10-ой Международной конфе-

рсншш по проблемам теоретической кибернетики (СаратоЕ. 1993), на научном семинаре 'Зкспертные и обучающие системы" (Саратов, 1995).

Сирукевура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (6& наименований). Объем работы -133 страницы машинописного текста.

СоЗирххниг работы

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

В первой главе, состоящей из четырех параграфов, вводятся основные понятия, используемые в работе, исследуются свойства ошибок бесповтор-шах формул, рассматривается структура минимальных тестов для беспов-тсриых формул над системой функций {V, &, 1}.

В работе рассматриваются бесповторные формулы над заданным шюжестаом В функций алгебры логики (ф.а_л). Предполагается, что все функции из В существенно зависят от своих Беременных. Переменные формулы 1 обозначаются символами х с индексом, - множество индексов переменных формулы 1", Ег - область определения функции, реализуемо^ формулой £ .

Определение. Пусть 1 < к'< п и 1) <12 <...<4 ,где ^ е I* для 3=1,...к . Рассмотрим у,, ч, где у, £ ^0* 1 !• для 3=1,...,к и

при ¿^.Преобразование N. которое любому набору е = ( р1,...,рс) из множества Ег ставит б соответствие набор

е'=( Рь -.-.Р,,.!,'!',, ,Р,У,. ) из Ег будем называть ошибкой

твна [¿;~7,, .■■•А=7,,) кратности к и писать Ые=е'.. Множество всех преобразований такого вида называется множеством всех ошибок для формулы f и обозначается . Пусть задано произвольное преобразование

F <= Nf. Результат действия F иа Ef обозначим как Elf <F> и будем говорить, что Ef <F> - область задания f при заданном фиксировании F. г Положим Nf =NfUl, где I - тождественное преобразование. Намножестве

Nf определяется oimapnoe OTHOUieirae cr с Nf х N<-, которое будем называть отношением распознавания. ■

Ошибки N| и N; принадлежат ¡т тогда только тогда, когда

(Ve е.Ее <Р->) (ffN, е) « f(N, е)). Если (N,,N2) е ст, то будем писать NisNi, а противном случае - N) Nj. Очевидно, что с - отношение зюшпапеят-ностн и разбивает N ■ на непересекающиеся классы. Будем говорить, что ошибки Nt и расгГоз[гаготсл (не распознаются ), если они попадают з разные классы на N', (в один класс).

Определение. Пусть R с N J . Множество ТсЕ <F> будем называть тестом для f множества ошибок R и заданного фиксирования F, геля любые две распознающиеся ошибки распознаются на множестве Т, то есть, если выполняется условие:

(VN,eR) (VNjgR) (3 ееТ) ( N,*N2 ffN, еЬчШ2е)). Если R = N , то T будем называть полным тестом для £ Тест называется тупиковым, если никакое его подмножество ие яглвется тестом. Тест минимальной длины называется минимальным. Под длиной теста понимается мощность множества Т. Обозначим через Рб(1) множество всех песповторных ф.а.л, для которых найдется а е {0,1}, такое, что фугоагая тринимаег значение, равное г- на единственном наборе из Ef. Tasofi кз-5ор называется выделенным. Обозначим через Рб множество всех 5есповторкых формул над Рб(1).

В дальнейшем слова " i*~f(f{,...,fu) - бесповторная формула..." озяа-¡ают, что для суперпозиции f =f(f|,..^f(1) выполняется усаозаг:

ЬП и, П 1с,П ...Я 1г =0 и Со - выделенный набор.

и .

Пусть Г- бгеповторная формула над заданным множеством В и

задано фшесирозание Б . Каждой >4бК(;, 1е!г сопоставим ошибку N е

1 " 1 ¡Ы^ того гее -шла. Ошибки из N такого вида называются однородными.

Будем говорить, что однородная ошибка 1\т*е N имеет индекс ¡, если

^ 1 „1 ей соответствует ошибка К1еЫ г, . Очевидно, что любая ошибка N е N

однозначно представляется^ как произведете однородных ошибок, причем так, что все однородные ошибки имеют разные индексы. Тогда Ер <Р>=Е, <¥]> ХЕГ <Бг> х х ...хЕ <Би>. Это означает, что любой набор

1 . *2 <и

е'еЕр <Р> мо;;сио предсташпъ р виде копкатекгогз! наборов е^

е*=е1...ец, где ei6Ef <Р;>, ¡=1...и.

* -

Далее для формулы £ и заданного фиксирования Б определяются классы сшибок: . ' . ■ • "

Сг(0,Р).= { Ые Ы' 1 (V ее Ег<К>) = 0 }, Сг(1Д0 = .{ N6 N1-К^ ее Ет<Р>)1(Ые)= 1 }. В параграфе 1.2 исследуется условие распознаваемости ошибок. В параграфе 1.3 определяется понятие а-миожеств и доказывается необходимое и достаточное условие для того, чтобы множество наборов из области задания функции было тестом.

ПустъХеРБ,£ е Кг.'а е{0,1},М еИ} . Множество М Р >

называется , а-множестаом для ошибки N формулы £ и фиксирования Р, если (V с е М) (["(Не) = а). Множество всех а-множеств для N будем обозначать .

Обозначим через Зг (К,Р) - множество всех тупиковых тестов для Г гРв и заданных II с N5- и Р е N 'г . Положим Зг(Р) = Зг (Ы}- ,Р). '

Зусть ГНф,...,^), где с М^ , 1=1,...,п , [1К] я ^ВДС^ ( ai.Fi). Под ¡-той проекцией набора е*=е!...е„е~ Е^ <Р >

«лишается набор е Н г, <7{> и обозначается рг, е*=е;. Под 1-топ

*

роекиией множества М с Е^ <К > понимается множество, ямппсшееся бъедикением ьтых проеюиш всех наборов из М. ¿-тая проекция [иойсества М обозначается как рг,М. Пусть р(Е^<Р*> ) - множество всех

одатозкеств множества Е^<Р*>. е

,1

Теорема 1.3.3 Пусть ТсЕ(-< ¥ >, Для того, чтобы мно-

:ествр Т было тестом для £ ири заданном фкксгфепажш ?' и множестве 11 1

шибок К* = [ и К" ] = Ис', необходимо и достаточно чтобы выполнялось лговие .

. (V1 е ГГ) { (V Ы-еЙ.,)... К,ек„)

(3 Ме р(Е<Р*>)) [рг.МеЗ г; (К^) & ((^е 1Г) 0« Р^м Е АГ) (с^Д,^-))) & Мс Т] }. Теорема 1.3.3 показывает структуру теста для бегповториои суиерпо-шии формул над Рк( 1). •

Множество М будем называть а-множес1вом для функции f я задаи-■гх фиксирования Р и множества ошибок Я, если

w .

а-множество называется тупиковым, если никакое его.-себствгшюе подмножество не является а -'множеством.

Пусть A(f, a,F,R) - множество всех тупиковых а-мпспхесгв для f заданных фиксирования F и множества ошибок R. Положим A(£,aJr) =A(f, a,F. N'f ). Если a - множество содержит гдкнствсщгый набор, то о называется a-набором для f, РД.

В утверждениях 1 1.3.1-1,3.3 исследуется структура а-наборс (as {0,1)) и доказывается существование и единственно«ь.

Определение. Пусть ае {0,1} и е - а-набор для f е Pg и фиксирования F б N f. Будем гозорить, что f удовлетворяет свойству Р(а), если найдется ошибки, которые распознаются только на а- наборе.

• В параграфе 1.4 для формулы f определяется семейство Test(f*) тупиковых тестов для f* и заданного фиксирования F*. Основным результатом первой главы является теорема 1.4.1.

i •

Теорема 1.4.1. Пусть fе Р!; я FeNf. Тогда Test (f) - семейство все минимальных тестов для f и заданного фиксирования F.

Эта теорема в силу конструктивности определения семейства тесто Test ((), является методологическим обоснованием алгоритмов" синтез ми ни у. шъных тестов для формул из РБ.

Во второй главе Диссертации решается задача распознавани: квазиыонотонных функций. В параграфе 2.1 вводится определение

частичного порядка -< и квазямонотонной функции исследуются свойств; ошибок квазимонотонных функций.

Пусть а. (}, у е l' 0,1 К Будем писать (3 ч у, если имеет место один из грех случаев • ' 1-, {1 - cs и у =а " . -

л,

2. Р = а н у=а "

3. (}= а и у = а .

Пусть е,е',е"е Е2 . е = (аь...аД е' = (01,...рл), е" = (К,...Д). Определение. Будем гозорнть, что наборы е' и е" накопятся в

теопкягш -С, если (VI е ^ 1,...,д!>) ((},-< р.'). ё - единичный элемент, набор е - нулевой

Определение. Функцию £ будем называть кгозимопотоаной, если айдется набор еоеЕ(-такой, что на области определения функции Ег с

с,

кггачвъш порядком -< функция £ монотонно возрастает. Клгсс всех ¡азимонотонных функции из Р2 обозначим через КМ.

Пусть К*-множество минорант для мло.~естза Е/1), а К°-миожество гаггсрантдая множества Е;{0).

Каждому набору .е=( ) го многгестса К1 сопоставим набор

Такой набор р будем называть единицей функции Г, а множество всех сих наборов - множеством едюиш функции и обозначать 0! ■ - ■

Определение. Фуккгам Г из Р2 обладает а-свойством (ае1) 0,1 <•), ш найдется набор е., га Ег такой, что для любой ошибки е Кг! С^' а) ^ео) = а . Такой набор назовем а- набором.

Теорема 2.1.1. Класс функций пз Р2, обладаюпдгх а-саойств'ом, падает с классом квазимонотонных функго!й.

В параграфе 22 рзссматризагатся свонстса единиц и кулей 1имонотонных функций. В утверждениях 2.3.1. -2.3.7 параграфа 2.3

исследуются -условия распознаваемости ошибок квазимонотонных функций. ' '■ " ,

Теорема 2.3.1. Множество Т = К1 U К0 является полным тестом для f и множества ошибок Nf. '

Затем в работе показывается, что Т = К1 U К0 - тупиковый полный тест

.для f и множества'ошибок Nf.

В параграфе 2.4 рассматривается задача построения теста для беспов-торпй суперпозиции квазимонотонных функций.

Показывается, что бесповторная суперпозиция квазимоиотонных функций есть квазимонотонная функция (Утверждение 2.4.2). В утверждениях 2.4.3 - 2.4.5 исследуется связь ошибок для суперпозиции

f* =f(fi,...,f„) с ошибками функции f; , i=l,...,u.

Пусть Р = f(f|,...,fu) - суперпозиция квазимоиотонных функций , ео = =ai,...,au-0-набор для функции^ ео= ai,...., ац -Г-набор для f. Пусть '

Т=Т° U Т1-тест для функции f, Т,=Т°1)Т|'-тест для функции, f;, ielf. TJ -множество всех наборов из Т, на которых функция f принимает значение, равное нулю,' Т1- множество всех наборов из Т, на которых функция f

0 1

принимает значение, равное единице . Т i и \ - множества всех наборов из Ti, на f' хгорых функция f, принимает значения, равное нулю и единице соответственно. Каждому набору е =Pi,...,|3ueT сопоставляется два множества индексов bj(e) и 1|(е), определенные следующим образом:

IoieHielr I Pi=ài}, l-,(e)=-{ielf I р,= щ }.

Каждому набору ееТ1 сопоставляется множество наборов М(е), опреде- _ ленное следующим образом. М(е) с: Ef», М(е) =

UM^e) ,

icl,(»

M;(e>=S,x...xSu ,ГД2

е.

у .5-1

Е

е, -«¡-набор дня функпш! ^, т=1,...,и ^ - агнабор дня фупкщщ ^ , з=1,...,и. Каждому набору

ееГ

сопоставляется маогсестао наборов Це), определенное следузокшм образом. Це) с Ер Це)= и Ц(е), где Ь; (е)

1е10(г) 1

^¡х.^хС,,, где

а-Т1 1

С;=

Iе;} .Ое1о(е>'

I Л .

Определим -мнозсесгао • Т'СГь—Л\.) следующим образом.

т'ггь...,тв) =< и м(е)) и с и ад).

ееТ — сбТ0 ^

■ Теорема 2.4.!. Т*(Т,,...,Ти) - полный' тест для формулы

С содгржггельпой -шпаг зрения Теорема 2.4.1 означает, что знание полги« тестоз для подформул позволяет получить полный тест длч формулы. Далее, используя з качестве тестов для подформул £ тесты

"О . . ! т*

IV, и N, определяется ■гест 1 и доказывается подпета и туттихогость

В третьей глаз« формулируются алгоряшь» пбетрокгая Ш5янкагя.кнх тсстсз дня беспозторных формул из Рр. и тутакопых тесте» для бсспсзтср-

ных формул из КМ. В параграфе 3.1 доказывается теорема 3.1.1, которая позволяет строить тесты для бесповторной суперпозиции f( fi,..., fu), где е'о= = п\,..., ац - выделенный набор для f, f(e0) = a, f¡ - произвольные функ-цнн алгебры логики.

В параграфе 3.2 получена опенка длины минимального теста для формулы от п переменных из. Рв и фиксирования кратности к: Lfn-kl .

i-q , если п - к > 1

¡ т| <•! l - j

(п-к-М , если0<п-к<1 ,

«

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

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

1. Сагаева И.Д. Об одном методе построения теста для универсальны; модулей бзз памяти. Методы и системы технической диагностики. Вып.5 Издательство Саратовского университета. 1985 г.

2. Сагаеаа И.Д. Построение полного теста для частично-заданны; бесповторных формул. Методь; и системы технической диагностики Бып.6. Издательство Саратовского университета. 1987 г.

. 3. Сагаева И.Д. Об одной процедуре построгния тестов для бесповторны: логических схем. 1990 г. Методы и системы, технической диагностики Вып. 14. Издательство Саратовского университета. -1990 г. 4. Сагаева И.Д. Об одной процедуре построения тестов. Методы i -системы технической диагностики. Вып. 18. Издательство Саратовскоп университета. 1993 г.