Введение к работе
-' :CxSISil3J
Актуальность темы
Одной из актуальных проблем теории управляющих систем (УС)
является проблема сложности контроля УС различных классов.
Она была сформулирована и последовательно разрабатывалась в
фундаментальных работах Яблонского СВ. и других авторов. Ее
современное состояние отражено в работе "Некоторые вопросы
надежности и контроля управляющих систем" Яблонского СВ. (Сб.:
Математические вопросы кибернетики. Вып. 1.- М.: Наука, 1998).
В настоящей работе рассматриваются множества и УС вида
U =(z,f), где z - схема из функциональных элементов, f -
функция, реализуемая схемой Г и принадлежащая некоторому классу
К функций алгебры логики. Под влиянием источника неисправностей
И схема Z переходит в одно из неисправных состояний Ео,Zj,
...,1 , где г =. Этим схемам соответствуют функции f ,f , . ,f
где f =f , которые называются функциями неисправностей.
Рассматривается случай, когда г=2п+1, где п - число входов
схемы х УС, или число переменных ее функции f, причем функции
неисправностей имеют вид: f =f, f (х ,...,х )= f(x х
1 " О '21-11' 'и Iі '1-І'
0,х ,...,х), f (х x) = f(x,...,x ,1.x х),
1+1 п ' 21 1' *п 1 ' I - 1 * 1 1 ' п
i=l,...,n. Функция f существенно зависит от п переменных , функции f , i=l....,2п не обязательно различные . Это соответствует классу одиночных константных неисправностей, типа обрывов или коротких замыканий на входах схемы, то есть подстановкам констант 0 или 1 вместо одной из переменных реализуемой схемой функции.
Контроль исправности УС U'=(E',f) осуществляется с помощью совокупности Т наборов входных сигналов, позволяющих по значениям выходов УС установить совпадение или несовпадение реализуемой схемой ', Е'е {,,..,Е }, функции f, f'«{f,f,...,f ) с функцией f исправной УС. Указанная совокупность наборов, различающая функции каждой пары (f„.ff),
i=l 2п, называется проверяющим тестом Т для УС U=(z,f) .
Поскольку данная УС может иметь несколько тестов, на множестве тестов Т для U=(r,f) вводят функционал L(T), обозначающий сложность теста Т. Этот функционал в данном случае определяется как число наборов входных сигналов, образующих тест Т. Функционал ЦТ) для каждой УС позволяет определить понятие минимального теста как теста, для которого значение L(T) минимально. Обозначим L(f)- сложность минимального теста для УС U=(r,). Проблема сложности контроля в данном случае сводится к оценке сложности минимальных тестов УС различных классов, в частности рассматриваемых здесь классов u =[U =(,f),f«K}. Далее вводят относящуюся к классу и в целом числовую функцию, характеризующую сложность контроля УС из этого класса - Ц,(п), равную минимально достаточной мощности множеств наборов, образующих проверяющие тесты для всех УС с п входами из множества u .
К настоящему времени в теории контроля Носковым В.Н., Погосяном Г.Р. и другими авторами получены значения L (п) для классов УС U=(z,f), реализующих функции алгебры логики и k-значные функции, а также значения L(f) для почти всех УС из этих классов в предположении достаточно общих источников неисправностей на входах УС (кратные константные неисправности, инверсии, слипания и другие), то есть эти результаты касаются классов УС up={U=(r,f),f«P2} и ttp={U=(s.f),f«Рк}, где Ра~ класс
всех функций алгебры логики, Р - класс всех k-значных функций.
В настоящей работе для описанного выше источника И одиночных константных неисправностей на входах УС рассматривается проблема контроля применительно к широкому спектру классов УС U =(z,f), соответствующих всем замкнутым классам К функций алгебры логики, или классам Поста . Полная структура этих классов была впервые описана Э.Постом в 1921г., соответствующие результаты он затем изложил в' монографии в 1941г. В настоящей работе для каждого класса Поста К изучается поведение функции L (п), оценивается значение L(f) для почти всех функций f из данного класса, а также исследуется область возможных значений величины L(f) для всех функций f класса К.
Для рассматриваемого источника неисправностей понятие теста для УС совпадает с понятием теста для функции из множества функций относительно множества пар функций (f ,f ), i=l.... ,2n, поскольку тест не зависит от строения схемы Е. Поэтому ниже используем термин тест для функции.
Цель работы
Целью работы является сравнительный анализ сложности контроля УС, соответствующих различным классам Поста К на основе изучения для каждого из них поведения функции L (п), оценок значений величин L(f) для почти всех функций Г'из этиго класса, а также исследование области возможных значений величины L(f) для функций f из класса.
Научная новизна
В настоящей работе проблема контроля УС решена применительно ко всем классам Поста при возможных константных неисправностях одиночного типа. Ранее эта проблема была решена применительно к одному классу Поста Рик классу Р в предположении более общих источников неисправностей.
Практическая ценность
Работа имеет теоретический характер. Однако разработанные в ней оценки и алгоритмы синтеза минимальных проверяющих тестов могут использоваться для контроля работы УС, если установлено, что их логические модели соответствуют тому или иному классу Поста.
Методика исследования
В работе используются модели и методы дискретной математики, математической кибернетики, теории вероятностей и математического анализа, а также общая методика теории контроля управляющих систем.
Апробация работы
Результаты работы докладывались и обсуждались на третьем Всесоюзном семинаре по дискретной математике и ее приложениям (Москва, 1990), на V» Всесоюзном совещании по технической диагностике и отказоустойчивости (Саратов , 1990), на студенческой научной конференции механико-математического факультета МГУ (Москва, 1989), на семинарах в МГУ по теории автоматов (под руководством академика АТН РСФСР В.Б.Кудрявцева, 1986, 1991), по математической теории управляющих систем (под руководством чл.-кор. АН СССР С.В.Яблонского, 1991).
Публикации
Основные результаты работы содержатся в 6 публикациях автора, список которых приведен в конце автореферата. Обьем и структура работы
Диссертация содержит 101 машинописную станицу и состоит из оглавления, введения, четырех глав и списка литературы. Библиография включает 41 наименование. В работе используются 7 таблиц.