О.Б. Лупанов - Элементы математической кибернетики (1161667)
Текст из файла
⇒О. Б. ЛупановЭлементы математическойкибернетикиКонспект лекцийВерсия 1.0εγПамятиОлега БорисовичаЛупановаПредисловие к версии 1.0Данный конспект подготовлен на основе записей лекций одноименного курса естественно–научного содержания, который был прочитанавтором осенью 2003 года.Деление текста на главы и параграфы, теоремы и утверждения,примеры и доказательства во многом условно. Этому есть две причины.
Во–первых, в оригинале изложение практически не структурировалось, а во–вторых, несколько лекций указанного курса в порядкезамены читал Н. П. Редькин, поэтому и для удобства изучения, и дляприведения к единому стилю (так, например, у одного лектора тестбыл набором строк, а у другого — набором столбцов матрицы с закономерным транспонированием всего куска текста, посвященного тестам)были сделаны некоторые перестановки и переименования.
Схемы, корректирующиеся относительно замыкания/размыкания, были отнесенык теме о контроле работы схем вообще.В приложении приведены определения некоторых редко встречающихся (в том числе и в этом повествовании) отношений и задачи, предлагавшиеся на экзамене. Коллекция, как видно, пока невелика. Приведена также программа курса по состоянию на 2003–2004учебный год. Замечания и дополнения активно приветствуются здесь:epsgam@yandex.ru.Искренняя благодарность Диме Алашкевичу, любезно предоставившему в свое время записи первой лекции, сдуру прогулянной мной послучаю первого сентября.Юрий "epsgam" Епишин,Зеленоград, ноябрь 20061Глава 1Дизъюнктивные нормальныеформы§ 1.1.
Основные понятияБудем называть выражение xσi11 &xσi22 & · · · & xσikk элементарной конъюнкцией, если все i1 , . . . , ik различны, в противном случае — обобщенной конъюнкцией. Так, например, допускается обобщенная конъюнкция вида xi xi . Считаем, 1 — конъюнкция длины нуль.Дизъюнктивная нормальная форма (ДНФ) — дизъюнкция попарноразличных конъюнкций (в таком случае, x1 x2 ∨x2 x1 ДНФ не является).Обобщенная ДНФ — дизъюнкция обобщенных конъюнкций (слагаемыемогут повторяться). Пустая ДНФ тождественно равна нулю. Определим совершенную ДНФ булевой функции f (x1 , .
. . , xn ) как разложение_xσ1 1 & · · · &xσnn .(σ1 ,...,σn ),f (σ1 ,...,σn )=1Рассмотрим сложности ДНФ:1) LD (F ) — число символов переменных в ДНФ F . Например,LD (x1 x2 ) = 2. Если F — пустая ДНФ (или тождественно равная 1),то LD (F ) = 0. Так, LD (F1 ) = 5 для F1 = x1 x2 ∨ x2 x3 ∨ x4 ;2) L′D (F ) — число слагаемых в ДНФ. Например, L′D (F1 ) = 3. ЕслиF — пустая ДНФ, то L′D (F ) = 0, однако L′D (1) = 1.Утверждение 1. Пусть F ′ — обобщенная ДНФ. Тогда существуеттакая ДНФ F , что:1) F и F ′ эквивалентны, т. е.
реализуют одну и ту же функцию;2) LD (F ) 6 LD (F ′ ), и L′D (F ) 6 L′D (F ′ ).2Доказательство основывается на правилах упрощения типа xi xi = 0,K ∨ K = K.Обозначим LD (f ) = min LD (F ). Здесь минимум берется по всемF (f )ДНФ F , реализующим булеву функцию f . Затем LD (n) =maxf (x1 ,...,xn )LD (f ).Аналогично вводятся L′D (f ) и L′D (n).Теорема 1. L′D (n) = 2n−1 ,LD (n) = n2n−1 .Доказательство. Справедлива следующаяЛемма 1.
Для любой функции f (x1 , . . . , xn ) существует ДНФ F такая, что L′D (F ) 6 2n−1 .Докажем индукцией по n. Пусть n = 1. Все функции одной переменной таковы: 0, 1, x, x, и для них выполнено L′D (F ) 6 1. Допустим, чтонеравенство справедливо для n. Покажем, что оно справедливо и дляn + 1:f (x1 , . . . , xn , xn+1 ) = xn+1 f (x1 , . . . , xn , 1) ∨ xn+1 f (x1 , . .
. , xn , 0).По предположению индукции для функций f (x1 , . . . , xn , 1) иf (x1 , . . . , xn , 1) найдутся ДНФ с числом слагаемых, не превышающим2n−1 . Поэтому сложность ДНФ функции f (x1 , . . . , xn , xn+1 ) будет максимум вдвое больше, не превысив тем самым 2n . Лемма доказана.Вернемся к доказательству теоремы. Из утверждения леммы следует, что L′D (f ) 6 2n−1 , поэтому для другой меры сложности справедливаоценка LD (f ) 6 n2n−1 . Далее соответственноL′D (n) 6 2n−1 ,LD (n) 6 n2n−1 .Чтобы доказать теорему, осталось найти такую функцию, на которойдостигается равенство.
Рассмотрим, например,ln (x1 , . . . , xn ) = x1 ⊕ · · · ⊕ xn .На соседних наборах ln принимает различные значения, значит каждоеслагаемое в ДНФ должно содержать все переменные. Ну а посколькуединиц у функции ln ровно 2n−1 , то L′D (ln ) = 2n−1 и LD (ln ) = n2n−1 .Теорема доказана.Введем несколько определений.
Минимальной ДНФ для функцииf будем называть ту ДНФ, на которой достигается величина LD (f ).Определим также: конъюнкция K допустима для функции f , если3K 6 f; конъюнкция K минимальна для функции f , если она допустима для f , но при удалении любого множителя перестает быть допустимой.
Таким образом, минимальная ДНФ состоит только из минимальных конъюнкций. Тупиковая ДНФ для функции f состоит только изминимальных конъюнкций, но при удалении любой конъюнкции перестает реализовывать f . Так, минимальная ДНФ является тупиковой.А сокращенная ДНФ для функции f состоит из всех минимальныхконъюнкций функции f .Пусть Nf — множество наборов, на которых функция f принимаетединичные значения. С геометрической точки зрения это определенное множество вершин n–мерного куба.
В таком случае конъюнкцииK = xσi11 · · · xσikk будет соответствовать подкуб размерности (n − k), тоесть NK ⊆ Nf . Если K еще и минимальна, то подкуб будет максимальной размерности.Важно получить для каждой конкретной функции список всех минимальных ДНФ. Построить минимальную конъюнкцию можно следующим способом: если f (σ̃) = 1, где σ̃ = (σ1 , . . .
, σn ), то конъюнкцияxσ1 1 · · · xσnn допустима для f . Вычеркивая переменные до тех пор покаконъюнкция не перестанет быть допустимой, придем к минимальнойконъюнкции.Рассмотрим некоторые примеры.1. Пусть0, (x1 , x2 , x3 ) = (0, 0, 0), (1, 1, 1),ϕ(x1 , x2 , x3 ) =1, (x1 , x2 , x3 ) 6= (0, 0, 0), (1, 1, 1).Минимальными конъюнкциями (см. рис. 1) будут K1 = x1 x3 ,K2 = x1 x2 , K3 = x2 x3 , K4 = x1 x3 , K5 = x1 x2 , K6 = x2 x3 .
Тупиковые(но не минимальные) ДНФ: K1 ∨ K3 ∨ K4 ∨ K6 , K1 ∨ K2 ∨ K4 ∨ K5 ,K2 ∨ K3 ∨ K5 ∨ K6 . А минимальными ДНФ на равных условиях являются K1 ∨ K3 ∨ K5 и K2 ∨ K4 ∨ K6 .2. Пустьψ(x1 , . . . , xn ) = ϕ(x1 , x2 , x3 ) ln−3 (x4 , . . . , xn ).Функция ψ принимает единичные значения только на таких наборах (σ1 , . . . , σn ), что (σ1 , σ2 , σ3 ) 6= (0, 0, 0), (1, 1, 1), и среди σ4 , .
. . , σnнечетное число единиц. Выделим трехмерные подкубы, зафиксировавпоследние n − 3 переменные. Четных“ и нечетных“ подкубов бу””дет по 2n−4 штук. Для каждого из трехмерных подкубов необходимопроизвести выбор среди двух минимальных и трех тупиковых ДНФ(см. предыдущий пример). Значит, число всех минимальных ДНФ4(011)✟✉K1 ✟✟(001) ✟✟✟✉K6✟✟✟✟✉✟✟(111)(101)K2K5(110)(010)✟✉✟✟✟✟✟K3✟✉✟✟✟✟ K4✉✟(000)(100)Рис.
1n−4n−4функции ψ составит 22 , а тупиковых — соответственно 52 . А отношение количества тупиковых ДНФ к количеству минимальных будетn−4(5/2)2 .Вообще, если m(f ) — число минимальных ДНФ функции f , а t(f ) —число тупиковых ДНФ, и m(n) = max m(f ), t(n) = max t(f ), тоf (x1 ,...,xn )n−4m(n) > 22f (x1 ,...,xn )n−4t(n) > 52,.t(f )и h(n) = max h(f ), получим, что справедОбозначив h(f ) =f (x1 ,...,xn )m(f )лива оценка 2n−45.h(n) >2§ 1.2.
Преобразования ДНФБудем придерживаться двух основных операций:1) Kx ∨ Kx = K, где K — конъюнкция;2) K ′ x ∨ K ′′ x > K ′ K ′′ , где K ′ и K ′′ — конъюнкции. В самом деле, K ′ K ′′ = K ′ K ′′ x ∨ K ′ K ′′ x 6 K ′ x ∨ K ′′ x. Условимся говорить в этомслучае, что конъюнкция K ′ K ′′ получена из K ′ x и K ′′ x в результатеобобщенного склеивания.Определим пучок Pα̃ набора α̃ = (α1 , . . . , αn ) ∈ Nf как множествовсех минимальных конъюнкций функции f , которые принимают еди5ничные значения на наборе α̃.
Тогда[Pα̃α̃∈Nfесть множество всех минимальных конъюнкций функции f .Считаем, что конъюнкция K поглощает конъюнкцию K ′ , еслиσk+1K > K ′ . В частности, если K = xσi11 · · · xσikk , то K ′ = xσi11 · · · xσikk xik+1· · · xσill .Назовем ДНФ F = K1 ∨ . . . ∨ Ks замкнутой, если для любых двухконъюнкций Ki и Kj из F , к которым можно применить операциюобобщенного склеивания, полученная в результате конъюнкция поглощается некоторой конъюнкцией Kh из F , т.
е. Ki = K ′ x, Kj = K ′′ x, иK ′ K ′′ 6 Kh .Например, ДНФ x1 x2 ∨ x1 x3 ∨ x2 x3 замкнута, посколькуx1 x2 ∨ x1 x3 > x2 x3 .Утверждение 2. (основная лемма о замкнутой ДНФ) ПустьДНФ F = K1 ∨ · · · ∨ Ks функции f (x1 , . . . , xn ) замкнута. Тогда длялюбой допустимой конъюнкции K функции f существует такаяконъюнкция Ki из F , что K 6 Ki .Докажем методом от противного“. Предположим, что K не поглоща”ется конъюнкцией из F . Пусть M = {K1′ , . . . , Kz′ } — множество конъюнкций, обладающих свойствами: 1) они содержат только x1 , .
. . , xn ;2) Kj′ 6 K, j = 1, z; 3) всякая Kj′ не поглощается никакой Ki из F .Множество M непусто, так как содержит K. Выберем в M конъюнкцию K ◦ наибольшей длины. Покажем, что K ◦ не содержит некоторую переменную xl , l ∈ 1, n. В самом деле, допустим, что это нетак, и K ◦ = xα1 1 · · · xαnn . Но тогда f (α1 , .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
