О сложности контроля логических схем типа поста тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

О •. '¡5

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА^ ОРДЕРА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ

И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

На правах рукописи ДОЛОТОВА ОКСАНА АЛЕКСАНДРОВНА

УДК 519.7

О СЛОЖНОСТИ КОНТРОЛЯ ЛОГИЧЕСКИХ СХЕМ ТИПА ПОСТА 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

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

Москва 1991

Работа выполнена на кафедре дискретной математики Московского государственного университета им. М.В.Ломоносова

НАУЧНЫЙ РУКОВОДИТЕЛЬ - доктор физико-математических наук,

профессор Валерий Борисович КУДРЯВЦЕВ

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ - доктор физико-математических наук, профессор Михаил Михайлович ГЛУХОВ; кандидат физико-математических наук, ассистент Анатолий Иванович РЫБКО

ВЕДУЩАЯ ОРГАНИЗАЦИЯ - Саратовский государственный университет им. Н.Г.Чернышевского

Защита состоится НОЯ 6-Р? 199 _£г.

В 11 часов на заседании Специализированного Совета Д 053.05.38 в Московском государственном университете им. М.В.Ломоносова по адресу: 119899 Москва, ГСП, Ленинские горы, МГУ им.М.В.Ломоносова, 2-й гум.корпус, факультет ВМиК, ауд.685.

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

Автореферат разослан * О^ТЯбУЯ 199_£-г.

Ученый секретарь Специализированного Совета

профессор с^Ь^1— . Н.П.Трифонов

АВТОРЕФЕРАТ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Одной из актуальных проблем теории управляющих систем (УС) является проблема сложности контроля УС различных классов. Она была сформулирована и последовательно разрабатывалась в фундаментальных работах Яблонского C.B. и других авторов. Ее современное состояние отражено в работе "Некоторые вопросы надежности и контроля управляющих систем" Яблонского C.B. (Сб.: Математические вопросы кибернетики. Вып. 1.- М.: Наука, 1998). В настоящей работе рассматриваются множества Ut УС вида U =(z,f), где z - схема из функциональных элементов, f -функция, реализуемая схемой Г и принадлежащая некоторому классу К функций алгебры логики. Под влиянием источника неисправностей И схема Г переходит в одно из неисправных состояний Ео,Г1, ...,Ег , где £о=£. Этим схемам соответствуют функции fo,fj , . . . , f где f =f ■ которые называются функциями неисправностей. Рассматривается случай, когда г=2п+1, где п - число входов схемы х УС, или число переменных ее функции f, прйчем функции

неисправностей имеют вид: f0=f, f t (xt , . . . ,x ) = îixt.....x( i ,

0, x , . . . ,x ), f (x .....x ) = f(x ,...,x ,l,x .....x ),

1 + 1 n 1 21 1 ' n 1 * 1 - 1 * I + 1 • n •

i=l,...,n. Функция f существенно зависит от n переменных , функции f , i=l,...,2n не обязательно различные . Это соответствует классу одиночных константных неисправностей, типа обрывов или коротких замыканий на входах схемы, то есть подстановкам констант 0 или 1 вместо одной из переменных реализуемой схемой функции.

Контроль исправности УС и'^Е'Д') осуществляется с помощью совокупности Т наборов входных сигналов, позволяющих по значениям выходов УС установить совпадение или несовпадение реализуемой схемой , Е'е { г .....л } , функции , Г'«{Го , . . . ,^ ) с функцией £ исправной УС. Указанная совокупность наборов, различающая функции каждой пары С £ ,£ ),

1=1.....2п, называется проверяющим тестом Т для УС и=(Е,£) .

Поскольку данная УС может иметь несколько тестов, на множестве тестов Т для и=(г,Г) вводят функционал Ь(Т), обозначающий сложность теста Т. Этот функционал в данном случае определяется как число наборов входных сигналов, образующих тест Т. Функционал ЦТ) для каждой УС позволяет определить понятие минимального теста как теста, для которого значение ЦТ) минимально. Обозначим ЬШ- сложность минимального теста для УС и=(г,£). Проблема сложности контроля в данном случае сводится к оценке сложности минимальных тестов УС различных классов, в частности рассматриваемых здесь классов и ={и1=(Е,£),Г«К}. Далее вводят относящуюся к классу и^ в целом числовую функцию, характеризующую сложность контроля УС из этого класса - Ц,(п), равную минимально достаточной мощности множеств наборов, образующих проверяющие тесты для всех УС с п входами из множества и .

X

К настоящему времени в теории контроля Носковым В.Н., Погосяном Г.Р. и другими авторами получены значения Ь^Сп) для классов УС и=(г,£), реализующих функции алгебры логики и к-значные функции, а также значения КО для почти всех УС из этих классов в предположении достаточно общих источников неисправностей на входах УС (кратные константные неисправности, инверсии, слипания и другие), то есть эти результаты касаются классов УС ир={и=(г,£)Д«Рг} и ир={и=(г:,£) }, где Ра~ класс

всех функций алгебры логики, Р - класс всех к-значных функций.

В настоящей работе для описанного выше источника И одиночных константных неисправностей на входах УС рассматривается проблема контроля применительно к широкому спектру классов УС и =(е,П, соответствующих всем замкнутым классам К функций алгебры логики, или классам Поста . Полная структура этих классов была впервые описана Э.Постом в 1921г., соответствующие результаты он затем изложил в' монографии в 1941г. В настоящей работе для каждого класса Поста К изучается поведение функции ЦСп), оценивается значение ЦП для почти всех функций Г из данного класса, а также исследуется область возможных значений величины ЦП для всех функций £ класса К.

Для рассматриваемого источника неисправностей понятие теста для УС совпадает с понятием теста для функции из множества функций относительно множества пар функций (Г Д ),

1=1,..., 2п, поскольку тест не зависит от строения схемы Е. Поэтому ниже используем термин тест для функции.

Цель работы

Целью работы является сравнительный анализ сложности контроля УС, соответствующих различным классам Поста К на основе изучения для каждого из них поведения функции I. (п), оценок значений величин ЦП для почти всех функций Низ этиго класса, а также исследование области возможных значений величины ЦП для функций Г из класса.

Научная новизна

В настоящей работе проблема контроля УС решена применительно ко всем классам Поста при возможных константных неисправностях одиночного типа. Ранее эта проблема была решена применительно к одному классу Поста и к классу Р^ в предположении более общих источников неисправностей.

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

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

Апробация работы Результаты работы докладывались и обсуждались на третьем Всесоюзном семинаре по дискретной математике и ее приложениям (Москва, 1990), на V» Всесоюзном совещании по технической диагностике и отказоустойчивости (Саратов , 1990), на студенческой научной конференции механико-математического факультета МГУ (Москва, 1989), на семинарах в МГУ по теории автоматов (под руководством академика АТН РСФСР В.Б.Кудрявцева, 1986, 1991), по математической теории управляющих систем (под руководством чл.-кор. АН СССР С.В.Яблонского, 1991).

Публикации

Основные результаты работы содержатся в 6 публикациях автора, список которых приведен в конце автореферата.

Обьем и структура работы Диссертация содержит 101 машинописную станицу и состоит из оглавления, введения, четырех глав и списка литературы. Библиография включает 41 наименование. В работе используются 7 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Пусть Ег = {0,1] и f:Е^—> Ег , где EJj- единичный п-мерный куб. Рассмотрим функцию f{xt,...,x ) существенно зависящую от п переменных. Пусть множество T(f)c Е^ ; говорим, что ТСf) — проверяющий тест функции f(xit...,x ), если для любой функции

\i(x .....х^), полученной из функции f заменой некоторой ее

переменной константами 0 или 1, существует набор Си ...., и )« T(f) такой, что выполняется f(u ,...,u )#0(u ,...,u ). Мощность

1 п 1 n

множества T(f) называется сложностью проверяющего теста и

обозначается L(T(f)). Тест, имеющий наименьшую сложность

называется минимальным, его сложность обозначается L(f).

Введем функцию L (п) = шах L(f) , где К - некоторое k f Cxt_____xn )« К

множество функций алгебры логики, а максимум берется по

всем функциям множества К, существенно зависящим от п

переменных. Говорят, что данное утверждение выполняется для

почти всех функций из множества К, если отношение числа функций,

зависящих от п переменных из множества К, для которых данное

утверждение не выполняется, к числу всех функций из К, зависящих

от п переменных, стремится к нулю при п—»«. Функция

f"(х ,....х^) = Г(х ,...,х ) называется двойственной к функции

fix .....х ) . Функция f(x ,...,х ) называется самодвойственной,

In In

если f*(x,.....х„ ) = f (х, . ■ ■ ■ .х ). Функция f(x , . . . ,х )

называется монотонной , если для любых наборов (а ....,а ) и

1 п

(р , .. . ,/з ) таких, что а * р , i = l, . ,,п, имеет место

1 П |

соотношение f С ot] , . , . ) з f(p ,...,$ ) Функция f(x , . . ,х ) называется линейной, если имеет место соотношение f(x , .,,х )

= Co+Ci х(+ . . ,+CnXn , Ct с Е2 , i=0,l...n. Говорят, что функция удовлетворяет условию <а">, ц г 2, если любые и наборов, на которых функция обращается в нуль имеют общую нулевую компоненту; функция удовлетворяет условию <а°°>, если все наборы, на которых функция равна нулю, имеют общую нулевую компоненту. Логические суммы - это функции вида V х ,

I * 1 1

п

п=1,2,...; а логические произведения - функции вида & х ,

1 -1

п=1,2,...; функция f(xt.....х^) называется а-функцией, если

f(x.....х)=х и р-функцией, если f(x.....х)=1. Рассматривались

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

существенно зависящие от п переменных, они имеют обозначения:

S( , ie{l,3,5,6), Р( , i«{l,3,5,6}, L( , ie{l,2,3,4,5), ,

ic[1,2,3}, M( , i«[1,2,3,4}, С , i<{1,2,3,4}, i«(l.....8) ,

д=2,3.... Будем называть их соответственно классами типов

S,P,L,D,M,C,F. Опишем эти классы. Класс Ct содержит все функции

алгебры логики ; Mj - все монотонные функции ; D3 - все

самодвойственные функции; F" (F"), д=2,3,... - все функции,

удовлетворяющие условию <а">, ц=2,3,...(<а">); L - все линейные

функции; S(- i=l,3,5,6 - все логические суммы; Сг, М2, L2~ все а

и в - функции из соответственно классов С , М , L ; D , F", FM, r l'l'l'2'з'З'

2,3...- все монотонные функции из соответственно классов D , F", F", ц=2,3. . . ; С , II , D ,.L , Г", F", д=2,3____ F", F",- все

«' 4' ' « 4 ' 1 4 1' 2 ' ' ' 1 J '

о- функции соответственно из классов С , М , D , L , FM, F*1,

" V 1 3 1 3 4

(х=2,3..., F", F"; L4- все линейные самодвойственные функции; Сз . Мз, Ц, Р( , 1=1,3,5,6; F", FJ1, 1=5,6.7,8, и=2,3...- все функции, двойственные ко всем функциям соответственно из классов С , М2 , Ц. , i=l,3,5,6, F", F*, 1=1,2,3,4.

В главе! для всех рассмотренных выше классов К Поста изучалось поведение функций L,(n). Справедлива следующая

Теорема 1. Имеют место соотношения:

1.L (п)=2 для каждого класса К типа L;

2.LK(n)=n+l для каждого класса К типа S или Р;

3.L (п) 2п при п —» » для каждого класса К

типа D, М, С или F. В г л а в е 2 оценивалось значение величины L(f) для почти всех функций f из каждого класса Поста К. Получены следующие результаты:

Теорема 2. Для почти всех функций f из следующих классов К имеют место соотношения:

1.L(f)=2 для каждого класса К типа L;

2.L(f)=n+l для каждого класса К типа S или ?;

3.L(f)=4 при n-четном, L(f)«{4,6} при п-нечетном для D2 ;

4.L(f )«{2,3,4) для классов KefD^D^;

5.L(f)=4 для каждого класса X типа М;

6.L(f)=3 для каждого класса К типа С *);

7.L(f)e{4,5] для классоз K<={F",F",F",F",

гд Fu FM гд 3 4 }

1 4 5 8 ' ' '

8.3 з L(f) з 8 для классов Ke{F2,F2,F2,F2};

9.L(f)=5 для классоз Kt{F", F™,F",F",

рД рД ГД рД J 4 }.

2 ' 3 * * 6 ' "г ' ' ' '

10.L(f)=4 при n-нечетном, L(f)e{4,5) при п-четном

для классов Ке {F2, F2 , F2 , F2 }. " г ' з ' б т

Г л а в а 3 посвящена вопросу о возможных значениях величины L(f) для функций f из различных классов Поста. Получены следующие результаты:

*) 4.Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ.Вып.27.-Новосибирск: ИМ СО АН СССР,1975.-С.23-51.

_ - ,-i ."."я любой функции :, существенно зависящей от п г.еремеккых, из классов типа L;

2.L(f)=r.+l для любой функции f, существенно зависящей от л переменных, из классов типа S или Р;

3.Для. любых натуральных п и г таких, что с s г s t(n), где

а) t(n)=2n-4(р+1) при 2р+2р<п*2р"+2(р+1) ,p«N, то есть t(r.) L (п) при п —♦ « ;

б) ск=2 для каждого класса К типа С и классов D] ,D3; с =3 для каждого класса Кс{F",F",F",Г",

К " 14 5 8'

рд Fu FU ?и д=2,3,...}; 14 5 а

для каждого класса К типа М, D2, и классов Ke {F2 , F2 , F2 , F2 , F3 , F3, F3 , F3 ];

2 ' 3* б' 7 г 3 6 7

с =5 для каждого класса Кб[F",F",F",F",

к « « гз'б'7'

^ Fu Fu у=4,5, . . . )

существует функция feK , существенно зависящая от п переменных,

для которой L(f)=r .причем значение г для класса D2 может быть

только четным числом.

3 • г л а в е 4 предлагается система алгоритмов синтеза

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

изложенных выше результатов, структура которой отражает

взаимосвязь минимальных тестов и их сложности для функций

различных классов.

В заключении полученные в работе результаты

представлены в виде следующей обобщающей Таблице, в которой

представлено распределение величины L(f) для функций,

существенно зависящих от п переменных, из классов Поста.

г 1 2 3 4 5 6 7 8 9 "io n+2 ~2r: \

С, (n) i=l', 2,3,4 - + E + + 4* + + + 4- + -t- + j

Lt (n) i=l,2,3,4,5 - E - - - - - - - - - -

Si Cn),Pi (n) i=l,3,5,6 0 - - j

M( (n) I i=l', 2,3,4 - - - 0 + + + + + + + + f i

ni 2p - - - El + - + - + + - + j

2p+l - - - + 1 - i + - + - + + - + ;

(n),D3(n) - 1 + 1 + + + + + + + + + +

F-CnJ.FfCn) i=2,3,6,7 n=4,5____ - - - - E + + + + + + + + j

rj(n) i=2.3,6,7 - - - - 0* + + + + -t- +

F*(n) n= i=2,3 2p - - - hi+ - + + -t- + + + + 1

2p+l 6,7 - - - 0 + - + + + + + + + j

F"(n) .F^tn) i=l,4,5,S n=3,4____ - - + i + + + - + + + 1

Ff(n) i=l,4,5,8 - - + l +! 1 +l + 1. !,.,., I....1 + + + + -j- +

Использованы следующие обозначения: если в г-ом столбце напротив соответствующих классов стоит знак: + -то существуют функции у которых К£)=г,

но они составляют бесконечно малую долю в классах; -то в классах не существует функции у которой если знаки + или - из столбцов г ,г ....,г ^ объведены:

. . +1 сплошной линией, то все или почти все функции I из классов имеют г * ЬШ а г ;

1 I »к '

~Г+1 пунктиром, то существенные доли функций £ из классов

имеют г а Ь(£) з г

1 1 • к

Эти результаты позволяют осуществить сравнительный анализ сложности контроля УС, соответствующим различным классам Поста: проблема контроля УС в рассматриваемой постановке для различных классов Поста имеет количественно и качественно различные решения. В то же время просматриваются общие закономерности. Для счетного множества классов Поста почти все функции из этих классов имеют минимальные проверяющие тесты, состоящие из конечного числа наборов, но в каждом из них хотя и не существует функций, зависящих от п переменных, сложность минимальных тестов которых была бы равна в точности 2п, имеются функции, сложность минимальных тестов которых равна любому из промежуточных значений, начиная от некоторой определенной для каждого класса константы до величины, асимптотически равной 2п , то есть числу возможных неисправностей рассматриваемого типа. Таким образом, в каждом из этих классов имеются функции, у которых почти все из числа 2л неисправностей проверяются отдельным набором из минимальных тестов каждая. Только конечное число классов не имеет подобной структуры по сложностям минимальных тестов классов функций: в классах линейных функций типа Ь все функции имеют минимальные тесты сложности 2 , в классах

логических сумм и произведений типа S или Р сложность минимальных тестов всех функций f равна п+1, где п - число существенных переменных этих функций. И, наконец, для класса D2 - монотонных самодвойственных функций, характеристика сложности минимальных тестов отличается от описанной выше закономерности только тем, что функции из этого класса не могут иметь минимальных тестов, состоящих из нечетного числа наборов.

Автор выражает благодарность академику АТН РСФСР В.Б.Кудрявцеву за постановку задачи и научное руководство.

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

1.Долотова O.A. О сложности проверяющих тестов для классов Поста // Труды семинара по дискретной математике и ее приложениям.-М.:МГУ,1989.-С.233-244 .

2.Долотова O.A. О сложности контроля логических устройств, реализующих функции из классов Поста // Методы и системы технической диагностики.Саратов. :Изд-во Сарат.ун-та, 1990.выл. 14, ч.1,С.20-21.

3. Долотова O.A. 0 сложности проверяющих тестов монотонных функций // Межвузовский тематический сборник научных трудов. Калинин.:Изд-во Калинин.ун-та, 1989. /в печати/

4. Долотова O.A. О сложности проверяющих тестов функций из класса F* // Межвузовский тематический сборник научных трудов. Калинин.:Изд-во Калинин.ун-та, 1990. /в печати/

5 . Долотова O.A. 0 минимальных проверяющих тестах функций из класса F* // Тезисы докладов IX конференции "Проблемы теоретической кибернетики" . Волгоград, 1991.ч.4./в печати/ 6. Долотова O.A. 0 сложности единичных проверяющих тестов функций из классов Поста// Тезисы докладов IX конференции "Проблемы теоретической кибернетики" . Волгоград, 1991. ч.4. /в печати/

'^^ji^C it,",„„„;,„., к „,.„„„ Псе 9/ " ~ „ _________а ЮО__

Типографии МЭН, KpiKiiokaupMeiiHrfH, ¡з7