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

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

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

Москва
ИНФРА-М
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остоящая из единиц этой элементарной конъюнкции.

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

Кодом этой грани называется набор (− . . .−σ1−. . .−. . .−σs−

. . . −) из символов 0, 1 и −, где каждая константа σj располо
жена на ij-й позиции. Для того чтобы набор из {0, 1}n попадал

в эту грань, все его ij-е координаты должны быть равны σj, а

остальные — произвольны.

Для функции f(x1, . . . , xn) можно рассмотреть разложение

по всем переменным:

f(x1, . . . , xn) =
(σ1,...,σn)
xσ1
1 & . . . &xσn
n &f(σ1, . . . , σn) =

=
(σ1,...,σn)|f(σ1,...,σn)=1
xσ1
1 & . . . &xσn
n .

Последнее представление является ДНФ, оно справедливо для

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

Вопросы и задания.

1. Дайте определения следующих понятий:

а) буква (литерал);

б) элементарная конъюнкция (ЭК);

в) дизъюнктивная нормальная форма (ДНФ);

г) совершенная дизъюнктивная нормальная форма (со
вершенная ДНФ).

* — задание повышенной сложности.

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

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

Для ДНФ используются различные меры сложности. Ко
личество букв в ДНФ D обозначается через L(D) и носит

название сложности ДНФ, а количество конъюнкций — че
рез l(D) и называется длиной. ДНФ для заданной функции f,

на которых достигается минимум данных функционалов, на
зываются соответственно минимальными и кратчайшими, а

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

f и обозначается L(f) (соответственно длиной функции l(f)).

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

Функция Шеннона L(n) для сложности определяется как

максимум по всем функциям n переменных величины L(f).

Функция Шеннона l(n) для длины определяется как макси
мум по всем функциям n переменных величины l(f). Факти
чески функция Шеннона определяется как мера сложности

самой сложной функции. Для ДНФ функцию Шеннона уда
ется вычислить точно как для функционала сложности, так и

для функционала длины.

Т е о р е м а 1.

L(n) = n · 2n−1, l(n) = 2n−1.

Д о к а з а т е л ь с т в о. Рассмотрим произвольную функ
цию f(x1, . . . , xn). Воспользуемся ее разложением по n − 1 пе

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

ременной:

f(x1, . . . , xn) =
(σ1,...,σn−1)
xσ1
1 & . . . &xσn−1
n−1 &f(σ1, . . . , σn−1, xn).

Данное разложение представляет любую функцию в виде

дизъюнкции не более чем 2n−1 конъюнкций не более n лите
ралов, что обеспечивает верхнюю оценку для обеих функций

Шеннона L(n) ≤ n · 2n−1, l(n) ≤ 2n−1. Для получения нижней

оценки рассмотрим функцию

g(x1, . . . , xn) = x1 ⊕ . . . ⊕ xn.

Поскольку изменение значения любой переменной меняет

значение функции g(x1, . . . , xn), любое слагаемое для ее ДНФ

должно содержать все литералы и обращаться в единицу ров
но на одном наборе (в одной точке). Количество единиц функ
ции g(x1, . . . , xn) равно 2n−1, поэтому число слагаемых в ДНФ

будет также не меньше 2n−1, а количество букв — не меньше

n · 2n−1. Из этого следует, что L(n) ≥ n · 2n−1, l(n) ≥ 2n−1. Из

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

Вопросы и задания.

1. Дайте определения следующих понятий:

а) сложность и минимальная сложность ДНФ;

б) длина и кратчайшая длина ДНФ;

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

в) функция Шеннона для сложности ДНФ (L(n)) и для

длины ДНФ (l(n)).

2. Сформулируйте теорему о функции Шеннона для слож
ности ДНФ и для длины ДНФ.

3∗. Может ли кратчайшая ДНФ не быть минимальной?

4∗. Получить верхнюю оценку длины кратчайших ДНФ и

верхнюю оценку длины сложности ДНФ для почти всех

функций.

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

и методы ее построения

Пусть задана ДНФ D = K1 ∨ . . . ∨ Kj, реализующая функ
цию f(x1, . . . , xn). Рассмотрим следующие преобразования.

1. Удаление множителя (буквы) из конъюнкции — замена

конъюнкции Ki = K′
ix на конъюнкцию K′
i.

2. Удаление конъюнкции из ДНФ.

Эти преобразования уменьшают сложность ДНФ, а второе

из них уменьшает также и ее длину. Однако применение любо
го из этих преобразований может привести к изменению реали
зуемой функции. Если ни одно из преобразований 1–2 нельзя

применить к ДНФ D, реализующей функцию f, без изменения

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

реализуемой функции, то ДНФ D называется тупиковой для

функции f.

Остановимся более внимательно на первой операции. Конъ
юнкцию K назовем допустимой для функции f (импликан
той функции f), если для любого набора x выполняется нера
венство K(x) ≤ f(x). Любая конъюнкция, входящая в ДНФ

для функции f, является импликантой этой функции.

Импликанта функции f называется простой, если при уда
лении любой буквы она перестает быть импликантой функ
ции f. Сокращенной ДНФ функции f называется дизъюнкция

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

импликантой функции f, сокращенная ДНФ любой функции

f также определяется однозначно (напомним, что различные

ДНФ функции определяются с точностью до порядков слага
емых и букв внутри конъюнкций).

По аналогии с дизъюнктивной нормальной формой (ДНФ)

вводится понятие конъюнктивной нормальной формы (КНФ).

Выражение S вида xσ1
i1 ∨ . . . ∨ xσs
is , где все ij различны, на
зывается элементарной дизъюнкцией. Дизъюнкции считаются

различными, если они отличаются набором литералов. Выра
жение вида S1& . . . &Sj, где все Si — различные элементарные

дизъюнкции, называется конъюнктивной нормальной формой

(КНФ).