Основы кибернетики

ОСНОВЫ 
КИБЕРНЕТИКИ

А.А. ВОРОНЕНКО

Москва
ИНФРА-М
2021

УЧЕБНОЕ ПОСОБИЕ

Рекомендовано Учебно-методическим советом ВО 
в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся по направлениям подготовки  
01.03.02 «Прикладная математика и информатика»
и  02.03.02 «Фундаментальная информатика и информационные технологии»

УДК 007(075.8)
ББК 32.81я73
 
В75

Вороненко А.А.
В75 
 
Основы кибернетики : учебное пособие / А.А. Вороненко. — 
Москва : ИНФРА-М, 2021. — 189 с. — (Высшее образование: Бакалавриат). — DOI 10.12737/textbook_5afd266f25b764.40369015.

ISBN 978-5-16-014004-9 (print)
ISBN 978-5-16-106666-9 (online)
В учебном пособии представлены материалы курса «Основы кибернетики», который автор читает на четвертом курсе факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, расширенные набором результатов из других 
курсов с тем же названием и современными научными результатами исследований. 
Учебное пособие рассчитано на студентов, обучающихся по направлениям подготовки 01.03.02 «Прикладная математика и информатика» 
и 02.03.02 «Фундаментальная информатика и информационные технологии».
Автор выражает благодарность всем своим коллегам за существенную 
помощь в подготовке пособия.

УДК 007(075.8)
ББК 32.81я73

А в т о р:
Вороненко Андрей Анатольевич, доктор физико-математических 
наук, профессор, профессор Московского государственного университета имени М.В. Ломоносова

Р е ц е н з е н т ы:
Дьяконов А.Г., доктор физико-математических наук, доцент, профессор Московского государственного университета имени М.В. Ломоносова;
Дайняк А.Б., кандидат физико-математических наук, доцент, доцент Московского физико-технического института

ISBN 978-5-16-014004-9 (print)
ISBN 978-5-16-106666-9 (online)
© Вороненко А.А., 2018

Оглавление

Введение . . . . . . . . . . . . . . . . . . . . . . . . . .
8

1 Дизъюнктивные нормальные формы
. . . . . .
10

1.1 Определение. Геометрическая интерпретация.

Совершенная ДНФ
. . . . . . . . . . . . . . . . .
10

1.2 Сложность ДНФ . . . . . . . . . . . . . . . . . . .
12

1.3 Функции Шеннона для ДНФ . . . . . . . . . . . .
12

1.4 Тупиковая ДНФ. Сокращенная ДНФ и методы ее

построения . . . . . . . . . . . . . . . . . . . . . .
14

1.5 Карты Карно. Геометрический подход
. . . . . .
18

1.6 ДНФ Квайна . . . . . . . . . . . . . . . . . . . . .
23

1.7 Пример функции с большим количеством

тупиковых и минимальных ДНФ
. . . . . . . . .
25

1.8 ДНФ сумма тупиковых . . . . . . . . . . . . . . .
27

1.9 Критерий вхождения конъюнкции

в ДНФ сумма тупиковых . . . . . . . . . . . . . .
29

1.10 Сокращенная ДНФ для монотонных

функций
. . . . . . . . . . . . . . . . . . . . . . .
30

1.11 Максимальная длина и сложность сокращенной

ДНФ
. . . . . . . . . . . . . . . . . . . . . . . . .
31

Оглавление

1.12 Алгоритм построения всех тупиковых покрытий

матрицы
. . . . . . . . . . . . . . . . . . . . . . .
33

1.13 Неразрешимость нахождения локальными алго
ритмами ДНФ сумма минимальных . . . . . . . .
34

2 Градиентный алгоритм . . . . . . . . . . . . . . . .
39

2.1 Оценка сложности покрытия градиентного

алгоритма
. . . . . . . . . . . . . . . . . . . . . .
39

2.2 Пример модификации градиентного

алгоритма
. . . . . . . . . . . . . . . . . . . . . .
41

3 Сложность реализации булевых функций

СФЭ и КС . . . . . . . . . . . . . . . . . . . . . . . .
46

3.1 Нижняя оценка функции Шеннона

для СФЭ . . . . . . . . . . . . . . . . . . . . . . .
46

3.2 Универсальный многополюсник.

Дешифратор . . . . . . . . . . . . . . . . . . . . .
50

3.3 Метод Шеннона для синтеза СФЭ

в базисе {&, ∨, ¬} . . . . . . . . . . . . . . . . . .
54

3.4 Метод О.Б. Лупанова для синтеза схем

в базисе {&, ∨, ¬} . . . . . . . . . . . . . . . . . .
55

3.5 Контактные схемы. Метод Шеннона . . . . . . . .
59

3.6 Нижняя оценка функции Шеннона

для КС . . . . . . . . . . . . . . . . . . . . . . . .
63

3.7 Метод каскадов для КС и СФЭ
. . . . . . . . . .
66

3.8 Самокоррекция контактных схем
. . . . . . . . .
71

Оглавление
5

3.9 Схема Кардо. Тестирование на размыкание
. . .
75

3.10 Самокорректирующиеся схемы Кардо . . . . . . .
77

4 Эквивалентные преобразования формул
. . . .
81

4.1 Эквивалентные преобразования формул

в базисе {&, ∨, ¬, 0, 1} . . . . . . . . . . . . . . . .
81

4.2 Теорема перехода
. . . . . . . . . . . . . . . . . .
84

4.3 Теорема Янова . . . . . . . . . . . . . . . . . . . .
87

4.4 Теорема Мучника . . . . . . . . . . . . . . . . . .
88

4.5 Пример Линдона. Свойства функции Линдона . .
90

4.6 Бесконечная полная система тождеств

для класса, порожденного функцией Линдона . .
91

4.7 Отсутствие КПСТ для замыкания системы

из функции Линдона
. . . . . . . . . . . . . . . .
92

5 Проблема контроля управляющих систем
. . .
94

5.1 Тесты для таблиц. Тривиальные оценки
. . . . .
94

5.2 Верхняя оценка длины диагностического теста

для почти всех таблиц . . . . . . . . . . . . . . . .
96

5.3 Алгоритм построения всех тупиковых

тестов . . . . . . . . . . . . . . . . . . . . . . . . .
97

6 Вопросы сложности алгоритмов . . . . . . . . . .
99

6.1 Проблема NP-полноты. Теорема Кука

(формулировка) . . . . . . . . . . . . . . . . . . .
99

6.2 Язык КЛИКА. NP-полнота языка КЛИКА . . . 102

6.3 NP-полнота языка 3-ВЫП . . . . . . . . . . . . . 103

Оглавление

6.4 Полиномиальность языка 2-ВЫП
. . . . . . . . . 105

6.5 Задача о кратчайшем остовном дереве. Жадный

алгоритм . . . . . . . . . . . . . . . . . . . . . . . 107

6.6 Свойства приближенных алгоритмов для задачи

МВП
. . . . . . . . . . . . . . . . . . . . . . . . . 108

7 Дополнительные вопросы . . . . . . . . . . . . . . 113

7.1 Сортировка массива. Сортировка слиянием
. . . 113

7.2 Об одновременном нахождении максимума

и минимума в массиве . . . . . . . . . . . . . . . . 116

7.3 Нахождение k-го наименьшего элемента

в массиве из n элементов . . . . . . . . . . . . . . 117

7.4 Задача тестирования линейности

булевой функции . . . . . . . . . . . . . . . . . . . 121

7.5 Задача
доказательства
нелинейности
булевой

функции
. . . . . . . . . . . . . . . . . . . . . . . 122

7.6 Дешифровка монотонных функций . . . . . . . . 123

7.7 Распознавание монотонности по вектор-столбцу . 130

7.8 Критерий кографа. Кографы и 2-деревья . . . . . 134

7.9 Каноническое дерево бесповторной функции

в элементарном базисе
. . . . . . . . . . . . . . . 140

7.10 Наличие запретных конфигураций у функции

Стеценко . . . . . . . . . . . . . . . . . . . . . . . 144

7.11 Повторность. Свойство Субботовской . . . . . . . 147

7.12 Наличие запретных конфигураций у функции

Субботовской . . . . . . . . . . . . . . . . . . . . . 149

Оглавление
7

7.13 Теорема В.А. Стеценко . . . . . . . . . . . . . . . 150

8 Задачи
. . . . . . . . . . . . . . . . . . . . . . . . . . 159

Библиографический список . . . . . . . . . . . . . . 185

Введение

Курс «Основы кибернетики» является продолжением курса

«Дискретная математика», читающегося во втором семест
ре для бакалавров факультета ВМК. Для освоения курса

«Основы кибернетики» необходимы минимальные знания

линейной алгебры и математического анализа (соответству
ющий материал полностью входит в программу первых

семестров соответствующих курсов). Из курса «Дискретная

математика» (см.[10]) необходимо знать разделы по булевым

функциям, теории графов и сложности схем. Основными

практическими навыками являются умение оперировать с

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

владение элементарными понятиями теории графов (путь,

цикл, орграф, изоморфизм и связанные с ними).

Ожидаемые навыки от слушателей по итогам курса.

1. Умение решать задачи на различные представления бу
левых функций в виде ДНФ.

2. Умение решать задачи, связанные с понятием NP
полноты.

3. Понимание проблематики задач на эквивалентные преоб
разования и умение решать задачи, связанные со свой
ствами абстрактных дискретных функций.

4. Углубленные знания по теории схемной сложности.

5. Знание элементарных результатов по тестированию (тео
рии надежности)

6. Понимание ряда нестандартных современных понятий,

близких к вышеизложенным (соответствующие разделы

читаются вариативно в объеме одной-двух лекций).

Глава 1

Дизъюнктивные нормальные

формы

1.1
Определение. Геометрическая интерпре
тация. Совершенная ДНФ

Через x0 обозначим отрицание переменной x (основное обо
значение — ¯x), а через x1 — саму переменную x. Произвольную

запись xσ, где σ принимает значения 0 или 1, назовем лите
ралом, или буквой. Выражение K вида xσ1
i1 & . . . &xσs
is , где все

ij различны, называется элементарной конъюнкцией. Конъ
юнкции считаются различными, если они отличаются набо
ром литералов. Выражение вида K1 ∨ . . . ∨ Kj, где все Ki —

различные элементарные конъюнкции, называется дизъюнк
тивной нормальной формой (ДНФ).

Конъюнкции K = xσ1
i1 & . . . &xσs
is , входящей в ДНФ функции

f(x1, . . . , xn), в булевом кубе соответствует грань размерности

n − s, cостоящая из единиц этой элементарной конъюнкции.