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

А.А. ВОРОНЕНКО
ОСНОВЫ 
КИБЕРНЕТИКИ
УЧЕБНОЕ ПОСОБИЕ
Рекомендовано Учебно-методическим советом ВО 
в качестве учебного пособия для студентов 
высших учебных заведений, обучающихся по направлениям подготовки 
 
01.03.02 «Прикладная математика и информатика»
и  02.03.02 «Фундаментальная информатика и информационные технологии»
Москва
ИНФРА-М
2025

УДК 007(075.8)
ББК 32.81я73
 
В75
А в т о р:
Вороненко Андрей Анатольевич, доктор физико-математических 
наук, профессор, профессор Московского государственного университета имени М.В. Ломоносова
Р е ц е н з е н т ы:
Дьяконов А.Г., доктор физико-математических наук, доцент, профессор Московского государственного университета имени М.В. Ломоносова;
Дайняк А.Б., кандидат физико-математических наук, доцент, доцент Московского физико-технического института
Вороненко А.А.
В75 
 
Основы кибернетики : учебное пособие / А.А. Вороненко. — 
Москва : ИНФРА-М, 2025. — 189 с. — (Высшее образование). — DOI
10.12737/textbook_5afd266f25b764.40369015.
ISBN 978-5-16-020744-5 (print)
ISBN 978-5-16-106666-9 (online)
В учебном пособии представлены материалы курса «Основы кибернетики», который автор читает на четвертом курсе факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, расширенные набором результатов из других 
курсов с тем же названием и современными научными результатами исследований. 
Учебное пособие рассчитано на студентов, обучающихся по направлениям подготовки 01.03.02 «Прикладная математика и информатика» 
и 02.03.02 «Фундаментальная информатика и информационные технологии».
Автор выражает благодарность всем своим коллегам за существенную 
помощь в подготовке пособия.
УДК 007(075.8)
ББК 32.81я73
ISBN 978-5-16-020744-5 (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остоящая из единиц этой элементарной конъюнкции.