1 (С.А. Ложкин - Лекции по основам кибернетики (2017))

Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЛекции по основамкибернетикиВариант 2017 г. (гр. 320–328), глава 1Москва 2017ОглавлениеВведение41 Представление функций дизъюнктивныминормальными формами и связанныес ним задачи§1 Основные понятия, относящиеся кмножествам, матрицам, функциям,формулам . . . . .

. . . . . . . . . . . . . . . . .§2 Представление функций алгебры логики спомощью дизъюнктивных нормальных форм(ДНФ) и его «геометрическая» интерпретация.Совершенная ДНФ и разложение Шеннона,критерий единственности ДНФ . . . . . . . . .§3 Сокращенная ДНФ и способы ее построения .§4 Тупиковые ДНФ, ядро и ДНФ пересечениетупиковых. ДНФ Квайна и ДНФ сумматупиковых, критерий вхождения простыхимпликант в тупиковые ДНФ, его локальность§5 Особенности ДНФ линейных и монотонныхфункций. Функция покрытия, таблица Квайнаи построение всех тупиковых ДНФ .

. . . . . .§6 Градиентный алгоритм и оценка длиныградиентного покрытия. Использованиеградиентного алгоритма для построения ДНФ2771423313744Оглавление§7§83Задача минимизации ДНФ. Поведение функцийШеннона и оценки типичных значений для рангаи длины ДНФ . . . . . . . . . . . . . . . . . . . 47Алгоритмические трудности минимизации ДНФи оценки максимальных значений некоторыхсвязанных с ней параметров. ТеоремаЮ. И. Журавлева о ДНФ сумма минимальных 52Литература59ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр.

РАН С. В. Яблонский, читается на факультетеВМК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех бакалавров (интегрированных магистров) направления 01400 — «Прикладная математика и информатика».При этом объем и, в некоторой степени, программа курса«Основы кибернетики» варьируются в зависимости от профиля.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики.

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

Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкрет4Введение5ное функционирование (схема), либо как массовая задача,и тогда ее решением должен быть алгоритм нахожденияфункционирования (схемы). Задача синтеза имеет, как правило, множество решений, из которых выбирают решение,оптимальное по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих ее элементовили задержка схемы, понимаемая как максимальная сумма задержек для последовательно соединенных элементовсхемы.С содержательной точки зрения различные критерии оптимальности отражают различные параметры моделируемых электронных схем или программ.

Так, например, сложность может характеризовать стоимость, размеры или потребляемую мощность СБИС, а также время выполненияпрограммы на одном процессоре. При этом задержка схемыхарактеризует время срабатывания СБИС или время выполнения программы на параллельных процессорах и т. п.Если задача синтеза решена в одной модели, можно пытаться перенести это решение в другие модели с помощьюструктурного моделирования. Кроме того, полученное решение можно «улучшить» с помощью эквивалентных преобразований. С другой стороны, если задача синтеза решенадля одних функций, можно пытаться «разбить» (декомпозировать) новую функцию на уже рассмотренные и построитьиз синтезированных для них схем схему для новой функциис помощью операции суперпозиции.Указанные выше задачи рассматриваются в лекциях длявсех основных классов схем (дизъюнктивные нормальныеформы, формулы и схемы из функциональных элементов,контактные схемы), а также для некоторых модификацийэтих классов.Первая глава посвящена различным вопросам представления функций алгебры логики с помощью таблиц и дизъюн-6Введениективных нормальных форм (минимизация дизъюнктивныхнормальных форм).Вторая глава содержит описание структуры и функционирования схем из основных классов управляющих систем,а также из некоторых классов, представляющих собой ихобобщения или модификации.

В ней устанавливаются верхние оценки числа схем различных типов, рассматриваютсянекоторые вопросы их структурного моделирования.Во второй главе изучаются также эквивалентные преобразования схем на основе тождеств во всех основных классах управляющих систем. Для каждого из них приводитсясистема «основных» тождеств, доказывается полнота этойсистемы и изучаются вопросы ее избыточности.В третьей главе подробно рассматривается задача синтеза управляющих систем, а также изучаются особенностиприменения операции суперпозиции в различных классахсхем. В ней приводится целый спектр методов синтеза схем(от простейших до асимптотически оптимальных), устанавливаются нижние мощностные оценки функций Шеннона иоценки сложности ряда конкретных функций, доказываетсяминимальность некоторых схем.В четвертой главе представлены некоторые вопросы надежности и контроля схем (построение теств для таблиц,синтез самокорректирующихся контактных схем).Глава 1Представление функцийдизъюнктивными нормальнымиформами и связанные с ним задачи§1Основные понятия, относящиеся кмножествам, матрицам, функциям,формуламБудем считать известными основные понятия и обозначения из теории множеств, математического анализа, дискретной математики, теории вероятностей (см., например, [25,26, 28, 4]).

В дальнейшем через N (через N0 ) обозначаетсямножество всех натуральных (соответственно целых неотрицательных) чисел. Множество всех целых чисел j, длякоторых a 6 j 6 b, где a, b — целые, называется отрезкоми обозначается через[a, b] = (a − 1, b] = [a, b + 1) = (a − 1, b + 1) .При этом отрезки вида[a1 , a2 ) , [a2 , a3 ) , . . . ,где a1 < a2 < a3 < . . ., называются последовательными.Напомним некоторые определения и обозначения, связанные с декартовыми произведениями множеств. Для множества A и n ∈ N положим(A)n = An = A| ×A×{z· · · × A},n раз78Введение— n-я декартова степень A, то есть множество наборов (строк,слов, выборок) длины n с элементами (буквами) из A или,иначе, множество упорядоченных n-ок элементов множестваA.Для множества A и s, n ∈ N через (A)s,n = As,n обозначается множество матриц с s строками, n столбцами и элементами из A.

При этом предполагается, что An = A1,n , и чтоAs,n — n-я декартова степень множества As,1 , элементы которого называются столбцами. Число столбцов (строк) матрицы M называется ее длиной (соответственно высотой).Для матрицы M ∈ As,n и I 0 ⊆ [1, s] , I 00 ⊆ [1, n] черезM hI 0 , I 00 i (при s = 1 и I 0 = {1} — через M hI 00 i) обозначается ее подматрица, расположенная в строках с номерамииз I 0 и столбцах с номерами из I 00 . Набор ∆ = (δ1 , . .

. , δp ), состоящий из непустых множеств, будем называть покрытиеммножества δ = δ1 ∪ . . . ∪ δp . При этом множества δ1 , . . . , δpсчитаются компонентами покрытия ∆, а число p — его длиной или рангом. Покрытие, состоящее из непересекающихсямножеств, называется разбиением.

Покрытие, в котором ниодна из компонент не содержится в другой компоненте (вобъединении остальных компонент), считается неприводимым (соответственно тупиковым) покрытием.Если A — конечное множество, то его мощность, то естьчисло элементов, обозначается обычно через |A|. Заметим,что при этом|An | = |A|n и |As,n | = |A|s·n ,где s, n ∈ N, а если |A| = a > n, то число выборок (слов)длины n из A, в которых все элементы различны, — такназываемых выборок без повторений, — равноa (a − 1) · · · (a − n + 1) .Каждое слово (набор) α = α1 . . . αn = (α1 , .

. . , αn ) изAn при всевозможных перестановках букв порождает множество слов, называемое сочетанием длины n из A или,Введение9иначе, неупорядоченной n-кой из A, и обозначаемое через{α1 , . . . , αn }. В частности, сочетание, связанное с (упорядоченной) парой (u, v), считается неупорядоченной парой{u, v}, сочетание, связанное с (упорядоченным) разбиением(δ1 , . . . , δp ), — неупорядоченным разбиением {δ1 , .

. . , δp }, итак далее. Заметим, что сочетание порождается перестановками букв из любого своего слова. При этом сочетание из Aбез повторений, то есть сочетание, порожденное словом изAn , все буквы которого различны, с содержательной точкизрения представляет собой «обычное» подмножество, а сочетание с повторениями — «кратное» подмножество множества A, то есть подмножество, в которое его элементы входят с определенной кратностью (в соответствующем числе«экземпляров»).Число различных сочетаний без повторений длины n измножества A, |A| = a, обозначается через na .

Как известно(см., например, [28]), aa!a (a − 1) · · · (a − n + 1)==,(1.1)nn! (a − n)!n!а число сочетаний с (возможными) повторениями длины nиз A равно a+n−1.nИндукцией по n легко показать, что n nn! >,(1.2)3а из формулы Стирлинга [26] следует, что1 n n √2πn.n! ∼e1Асимптотическое равенство a (n) ∼ b (n) означает, что limn→∞то естьa (n) = (1 + o (1)) b (n) .(1.3)a(n)b(n)= 1,10ВведениеИз (1.1) и (1.2) вытекает, в частности, неравенство na3a6,nnа из (1.1) и (1.3) — асимптотическое равенство1n2n+1n ∼ √.2πn2(1.4)(1.5)Напомним теперь некоторые понятия, связанные с функциями и отношениями. Пусть x = (x1 , . . . , xn ), где переменная xi пробегает значения из множества A и связана с i-йкомпонентой, i ∈ [1, n], декартовой степени An .