Теория тестирования логических устройств

Кудрявцев В.Б.

Гасанов Э.Э.
Долотова О.А.
Погосян Г.Р.

Теория тестирования

логических
устройств

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.71
ББК 22.18
К 88

Издание осуществлено при поддержке
Российского фонда фундаментальных
исследований по проекту 06-01-14069д

Куд р я в це в В. Б.,
Га с а н о в Э. Э.,
Д о л о т о в а О. А.,
П о г ос я н Г. Р. Теория тестирования логических устройств / Под ред. В. А. Садовничего. — М.: ФИЗМАТЛИТ, 2006. — 160 с. — ISBN 5-9221-0727-5.

Тестирование логических устройств — активно развивающееся научноприкладное направление кибернетики, возникшее в середине прошлого столетия. Оно по праву связывается с именем С. В. Яблонского. Тематика направления группируется вокруг задач характеризации тестов и их построения
и фокусируется на устройствах, представленных на макро- и структурном
уровнях. В книге эта тематика раскрывается на модели логического устройства
в его макровиде. Решаются задачи описания сложности тестов для устройств,
реализующих булевы функции из классов Поста, а также функции
-значной
логики. Приводятся соответствующие процедуры построения таких тестов.
Для студентов, аспирантов и специалистов в области надежности и контроля управляющих систем.
Табл. 3. Ил. 8. Библиогр. 78 назв.

ISBN 5-9221-0727-5

c⃝ ФИЗМАТЛИТ, 2006

c⃝ В. Б. Кудрявцев, Э. Э. Гасанов,
О. А. Долотова, Г. Р. Погосян, 2006

ОГЛАВЛЕНИЕ

Оглавление . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Предисловие редактора . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Предисловие . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
8

I.
Сложность тестов для k-значных логических
устройств

Введение . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12

Г л а в а 1. Константные неисправности . . . . . . . . . . . . . . . . . . . .
15

1.1. Понятия и результаты . .. . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.2. Вспомогательные утверждения . .. . . . . . . . . . . . .. . . . . . . .
17
1.3. Верхние оценки для L(n, Ck) . . . . . . . . . . . . . . . . . . . . . .
27

1.4. Нижние оценки для L(n, Ck) . . . . . . . . . . . . . . . . . . . . . .
36

1.5. Подклассы из Ck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37

Г л а в а 2. Неисправности типа слипания . . . . . . . . . . . . . . . . . .
41

2.1. Результаты . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
2.2. Верхние оценки для L(n, Sk) . . . . . . . . . . . . . . . . . . . . . .
42

2.3. Нижняя оценка для L(n, Sk) . . . . . . . . . . . . . . . . . . . . . .
45

2.4. Подкласс Sk(p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46

Г л а в а 3. Инверсные неисправности . . . . . . . . . . . . . . . . . . . . .
47

3.1. Результаты . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47

3.2. Верхняя оценка для L(n, F 2
in). . . . . . . . . . . . . . . . . . . . . .
48

3.3. Нижние оценки для L(n, F 2
in). . . . . . . . . . . . . . . . . . . . . .
50

3.4. Подкласс F 2
in(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52

Г л а в а 4. Разнотипные неисправности . . . . . . . . . . . . . . . . . . . .
57

4.1. Классы разнотипных неисправностей . .. . . . . . . . . . . . . . . .
57
4.2. Инвариантность функций относительно неисправностей . .. . .
60

Оглавление

II.
Сложность контроля логических схем типа
Поста

Основные понятия и результаты . .. . . . . . . . . . . . . . . . . . . . . . . . . .
66

Г л а в а 5. Асимптотика функций Шеннона для классов Поста . . .
72

5.1. Классы типов S, P и L . . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.2. Классы типов M и C . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
5.3. Классы типа F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
5.4. Классы типа D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
5.5. Оценки функций Шеннона для классов Поста. .. . . . . . . . . .
82

Г л а в а 6. Сложность минимальных тестов для почти всех функций из классов Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84

6.1. Классы M1, M2, M3, M4 . . . . . . . . . . . . . . . . . . . . . . . . .
84
6.2. Класс D2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
6.3. Классы D1, D3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
6.4. Классы F 2
2 , F 2
3 , F 2
6 , F 2
7 . . . . . . . . . . . . . . . . . . . . . . . . . .
107

6.5. Классы F 2
1 , F 2
4 , F 2
5 и F 2
8
. . . . . . . . . . . . . . . . . . . . . . . . .
119
6.6. Остальные классы типа F . . . . . . . . . . . . . . . . . . . . . . . .
127
6.7. Сложность тестов для почти всех функций из классов Поста
129

Г л а в а 7. О сложности минимальных тестов для классов Поста. .
131

7.1. Классы типов C, F и M . . . . . . . . . . . . . . . . . . . . . . . . .
131
7.2. Классы типа D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
134

Г л а в а 8. Алгоритмы построения минимальных тестов для классов Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
140

8.1. Классы типа C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
140
8.2. Классы типов L, S, P . . . . . . . . . . . . . . . . . . . . . . . . . . .
142
8.3. Классы типа M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
143
8.4. Классы типа F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
145
8.5. Классы типа D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
148

Г л а в а 9. Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
150

Список литературы . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
152

Памяти выдающегося русского ученого
Сергея Всеволодовича Яблонского
посвящается

ПРЕДИСЛОВИЕ РЕДАКТОРА

В предлагаемой читателям книге излагаются результаты по проблеме контроля логических устройств.
Эта проблема была поставлена в середине 50-х годов прошлого столетия выдающимся русским ученым С.В. Яблонским, который разработал оригинальный подход к ее исследованию, получивший название
комбинаторно-логического.
В основе этого подхода лежит введенное им фундаментальное понятие теста, с которым связана вся исследовательская тематика этого
направления. Сегодня оно охватывает не только логические устройства,
но и другие виды управляющих систем.
Научное направление надежности и контроля управляющих систем
представляет собой яркий пример раздела науки, которое возникло под
влиянием практики, развилось как математическая теория и служит
решению прикладных задач.
Этот стиль научной деятельности был характерен для С.В. Яблонского и реализовался им в других столь же важных разделах кибернетики, таких, как функциональные системы, синтез управляющих
систем, дискретная оптимизация и основания кибернетики, которые
были инициированы им и куда он внес выдающийся вклад.
Как теоретическое, направление надежности и контроля управляющих систем развивалось затем, главным образом, в МГУ им. М.В. Ломоносова и в Академии наук. В этой книге излагаются достижения
этого
направления,
принадлежащие
исследователям
механикоматематического факультета МГУ, представляющим научную школу
кафедры математической теории интеллектуальных систем.
В книге в качестве основной модели управляющей системы рассмотрены случаи реализации логическими элементами вычислительной
схемы функций двузначной и конечнозначной логик и главное внимание
сосредоточено на сложности обнаружения возможных неисправностей
в этих элементах с помощью тестов; обобщены постановки задач
тестового контроля логических устройств, принадлежащие различным
авторам, разработаны методы их решения, получены окончательные результаты по сложностной характеризации этих решений и предложены
соответствующие алгоритмы. Все результаты являются оригинальными.
Книга будет полезной для исследователей и учащихся в области
кибернетики.
Академик РАН
В. А. Садовничий

ПРЕДИСЛОВИЕ

Дискретные вычислительные системы без памяти, называемые также логическими устройствами, играют все большую роль как в самой
науке, так и в ее приложениях, а также в технике и быту.
Практически важной характеристикой таких устройств является
надежность их функционирования. Необходимость обеспечения этого
свойства привела к возникновению нового научного направления в кибернетике, которое получило название надежность и контроль управляющих систем и по праву связывается с именем С.В. Яблонского.
Здесь мы останавливаемся на изложении результатов по проверке
правильности функционирования логических устройств, рассматриваемых не на структурном, а на макроуровне.
Решение этой задачи осуществляется с помощью тестового подхода,
предложенного С.В. Яблонским [69]. Его суть состоит в следующем.
Имеется некоторое логическое устройство с n входами и одним выходом (см. рис. 1). Предполагается, что это логическое устройство
в исправном состоянии реализует функцию k-значной логики f от n
переменных.

x1

f

xn

x2

Рис. 1

Логическое устройство может сломаться, и при поломке оно «работает» иначе, реализуя другую функцию g (см. рис. 2), называемую
функцией неисправности.

x1

g

xn

x2

Рис. 2

Теперь если нам дано логическое устройство, то хотелось бы определить, не сломалось ли оно? То есть надо понять, какую функцию,
f или g, оно реализует? Это можно сделать, подавая на вход устройству

Предисловие
9

по очереди все kn наборов возможных значений входных переменных,
затем снимая значения, выдаваемые устройством и сравнивая эти значения со значениями функций f и g на этих входных наборах. Но эта
процедура в общем случае громоздка и становится еще более сложной,
когда поломки в логическом устройстве не единичны и приводят к целому классу возможных функций неисправностей.
С.В. Яблонский предложил сравнивать f с функциями неисправностей на подобласти их определения, при этом если f на ней отличается
от каждой из функций неисправностей, то подобласть называется тестом.
Структура множеств тестов, их построение, число тестов и элементов в них составили предмет исследований теории тестов.
Тесты позволяют определять, исправно ли логическое устройство
не только на макроуровне, но и исследовать его структурно, углубляясь в его схему с целью обнаружения в случае поломки логического
устройства самой неисправности.
Здесь мы предлагаем к рассмотрению две группы результатов.

В первом случае рассматриваются логические устройства, реализующие функции k-значной логики и выделяются классы типичных
неисправностей на входах логических устройств. Для каждого класса
неисправностей предлагаются процедуры построения тестов и доказывается, что построенные имеют минимальное число элементов.
Во втором случае уже только для обрывов и коротких замыканий
на входах логических устройств в случае реализации ими булевых
функций (т. е. функций 2-значной логики) для всей классификации
Поста строятся простейшие тесты.

Полученные результаты дают возможность понять, как влияет на
тесты и процедуры их построения значность рассматриваемой логики,
а для двузначного случая позволяют определить сложность простейшего теста для логического устройства, если известно, какому замкнутому классу Поста принадлежит реализуемая устройством функция.
Следует отметить, что тестовый подход к распознаванию неисправностей логических устройств, как позже выяснилось, распространим
и на более общую ситуацию, когда логическое устройство интерпретируется как образ, а неисправности логического устройства — как
искажения образа. В этом случае тестовый аппарат позволяет измерять
меру такого искажения и служит средством распознавания образа
с заданной точностью.
Излагаемые результаты выполнены на механико-математическом
факультете МГУ им. М.В. Ломоносова и обобщают результаты этого
направления, полученные ранее [47, 63, 69 и др.].
Книга может быть полезна для специалистов по надежности и контролю управляющих систем, для исследований и учебного процесса
в этой области.

Предисловие

Авторы выражают свою признательность коллегам по кафедре
математической теории интеллектуальных систем, интерес которых
к тематике книги стимулировал ее создание, а также Т. Д. Уваровой
и И. В. Кузнецовой, помогавшим авторам в ее подготовке.
Авторы благодарны Российскому фонду фундаментальных исследований за финансовую поддержку издания этой книги (грант РФФИ
№06-01-14069).