Часть 1 (1132843)
Текст из файла
Общефакультетский курс«Основы кибернетики»Осенний семестр 2017–2018 уч. г.группы 311–319лектор — профессор С. А. Ложкин(lozhkin@cs.msu.su)Информационная поддержка курса:http://mk.cs.msu.ru/index.php/Основы_кибернетики_(2-й_поток,_3_курс)I. Минимизация ДНФ исвязанные с ней задачи1. Представление функцийалгебры логики (ФАЛ)дизъюнктивныминормальными формами(ДНФ) и его«геометрическая»интерпретация. СовершеннаяДНФ и критерийединственности ДНФУтверждение 1.1. Совершенная ДНФФАЛ f , f 6≡ 0, f ∈ P2(n), являетсяединственной ДНФ от БП X (n), котораяреализует эту ФАЛ, тогда и только тогда,когда во множестве Nf нет соседних наборов.Следствие. Совершенная ДНФ ФАЛ `, `,является единственной ДНФ этой ФАЛ отБП X (n).2.
Сокращенная ДНФ испособы ее построенияУтверждение 2.1. Пусть A0 и A00 —сокращенные ДНФ ФАЛ f 0 и f 00соответственно, а ДНФ A без поглощенийЭК получается из формулы A0 · A00 врезультате раскрытия скобок и приведенияподобных. Тогда A — сокращенная ДНФФАЛ f = f 0 · f 00.Следствие. Если ДНФ A без поглощенийЭК получается из КНФ B ФАЛ f врезультате раскрытия скобок и приведенияподобных, то A — сокращенная ДНФ ФАЛ f .Утверждение 2.2.
ДНФ без поглощенийЭК является сокращенной ДНФ тогда итолько тогда, когда она не имеет строгихрасширений.Следствие. Из любой ДНФ A ФАЛ fможно получить сокращенную ДНФ этойФАЛ в результате построенияпоследовательных строгих расширений иприведения подобных до получения ДНФ безпоглощений ЭК, не имеющей строгихрасширений.x4x10011x2 x301100011111010011111010111101`@e@@4β3 `c N0 @@cβ` 3 `@@@@0@ @ N4@@@@0 @ α6N@α1`c ` N0@`cc`@`N70 @2α2c`6α7@@@@0@@N1@@ @ @@ α5 @@@`c``c @`cc α3αβ0@4@@ x x2 3 x4 x@11I@ 6`c @βc5 N50 `e0β` 3 = {1011}N30α2 = {1001}α3 =` {0001}`N20β0 = {1000}`N70`N10α1 = {1100}`α0 = e0` α7 = {0011}N40` α4 = {0010}` β4 = {0111}N60`α5 = {0100}N50` α = {0110}6`β5 = {1110}A01 = K10 ∨ K30 ∨ K40 ∨ K50 ,A02 = K20 ∨ K30 ∨ K40 ∨ K50 .g {x1 , x2 , x3 } = x1 x 3 ∨ x2 x 3 ∨ x 1 x2 ∨ x 1 x3 ∨ x 2 x3 ∨ x1 x 2 .|{z} |{z} |{z} |{z} |{z} |{z}K1K2K3K4K5K6N g = {{000}, {111}},`@{111}@`c N2c`@c` {011}N3@ {101}@N1@ {010}@ N4N@` N6 @c`` {001}5 c{100} c@@@`{110}{000}A1 = K1 ∨ K3 ∨ K5 ,A2 = K2 ∨ K4 ∨ K6 ,A3 = K1 ∨ K2 ∨, K4 ∨ K5 ,A4 = K2 ∨ K3 ∨ K5 ∨ K6 ,A5 = K3 ∨ K4 ∨ K6 ∨ K1 .3.
Тупиковые ДНФ, ядро иДНФ пересечение тупиковых.ДНФ Квайна, критерийвхождения простыхимпликант в ДНФ сумматупиковых, его локальностьУтверждение 3.1. Дизъюнктивнаянормальная форма ∩T ФАЛ f состоит изтех простых импликант ФАЛ f , которыесоответствуют ядровым граням этой ФАЛ.Следствие. Сокращенная ДНФ ФАЛ fявляется ее единственной тупиковой ДНФтогда и только тогда, когда f — ядроваяФАЛ, т.е. все ее максимальные грани входятв ядро.Утверждение 3.2. Простая импликантаK ФАЛ f входит в ДНФ ΣT тогда и толькотогда, когда грань NK не являетсярегулярной гранью этой ФАЛ.4.
Особенности ДНФлинейных и монотонныхфункций. Функция покрытия,таблица Квайна и построениевсех тупиковых ДНФУтверждение 4.1. Сокращенная ДНФ Aмонотонной ФАЛ f , f ∈ P2(n), являетсяединственной тупиковой ДНФ этой ФАЛ иимеет вид:_A(x1, . . . , xn ) =Kβ+(x1, . . . , xn ).β∈Nf+При этом все наборы из Nf+ являютсяядровыми точками ФАЛ f .Следствие. Монотонная ФАЛ являетсяядровой ФАЛ.Утверждение 4.2. Функция покрытияF (y1, . . . , yp ) матрицы M , M ∈ B p,s , безнулевых столбцов задается КНФ вида:s _^F (y1, .
. . , yp ) =yi .j =116i6pM hi ,j i=1Следствие. В результате раскрытияскобок и приведения подобных из этой КНФможно получить сокращенную ДНФФАЛ F (y ), простые импликанты которойвзаимно однозначно соответствуюттупиковым покрытиям матрицы M .5. Градиентный алгоритм иоценка длины градиентногопокрытия, лемма опротыкающих наборах.Использование градиентногоалгоритма для построенияДНФУтверждение 5.1 Пусть длядействительного γ, 0 < γ 6 1, в каждомстолбце матрицы M , M ∈ B p,s , имеется неменьше, чем γ · p , единиц.
Тогда покрытиематрицы M , получаемое с помощьюградиентного алгоритма, имеет длину небольше, чем1 +1ln (γ s ) + ,γγln x , если x > 1;где ln+ x =0,если 0 < x < 1.Утверждение 5.2 При любыхнатуральных n и m, m 6 n, в кубе B n всегданайдется подмножество мощности не более,чем n · 2m , протыкающее все грани ранга m.6.
Задача минимизации ДНФ.Поведение функций Шеннонаи оценки типичных значенийдля ранга и длины ДНФУтверждение 6.1 Для любого n, n ∈ N,имеют место соотношенияλ(n) = 2n−1, R (n) = n · 2n−1.Утверждение 6.2 Для почти всех ФАЛ f ,f ∈ P2(n), выполняются неравенства3λ(f ) 6 2n−1 1 + O n · 2−n/2 ,43n−1−n/2R (f ) 6 n · 21+O n·2.47. Алгоритмическиетрудности минимизации ДНФи оценки максимальныхзначений некоторыхсвязанных с ней параметров.Теорема Ю.
И. Журавлева оДНФ сумма минимальныхУтверждение 7.1 Число тупиковых(минимальных) ДНФ у ФАЛ f изP2(n), n > 4, видаf (x1, . . . , xn ) = g (x1, x2, x3) · (x4 ⊕ · · · ⊕ xn ),n−4где N g = {(000), (111)}, равно 52n−4(соответственно 22 ).Следствиеn−4τ ( n ) > 52,n−4µ(n) > 22.Утверждение 7.2λсокр. (n) > e13n,nNn−1αn−1 `αn `= e1Nn`αn+1где e1 — некоторая константа.α2`N1```α1α2n−2N2n−2α2n−1`e0Рис.: цепная ФАЛ длины (2n − 2) вкубе B nУтверждение 7.3 При любомn ∈ N, n > 3, в P2(n) существуют ФАЛ f 0 иf 00, имеющие общую простую импликанту K ,которая входит в ДНФ ΣM одной, но невходит в ДНФ ΣM другой из этих ФАЛ идля которой Sn−3(NK , f 0) = Sn−3(NK , f 00).Замечание 1 Из теоремы следует, чтокритерий вхождения ЭК в ДНФ ΣM неимеет такого локального характера, каккритерий вхождения ЭК в ДНФ ΣT .Замечание 2 Известно, что при n > 14 вP2(n) имеется цепная ФАЛ четной длиныt , t > 2n−11 − 4, на основе которойсправедливость теоремы можно установитьдля окрестности порядка ( 2t − 2)..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
