_учебник_ Журавлёв Ю.И. Математические основы теории пронозирования (2008) (1185334), страница 2
Текст из файла (страница 2)
. , Sq принадлежат K1 , а строки Sq+1 , . . . , Sm — классу K2 .Сопоставим столбцам 1, 2, . . . , n булевские переменные x1 , . . . , xn . Напишем систему изq · (m − q) булевых уравнений. Паре Si = (ai1 , . . . , ain ) ∈ K1 , Sj = (aj1 , . . . , ajn ) ∈ K2сопоставим уравнение_fij =xt ,i = 1, . . .
, q; j = q + 1, . . . , mait 6=ajtYfij = 1.i=1,...,qj=q+1,...,mWВыполняем умножение и приходим к д.н.ф. xu1 · . . . · xup , в которой проводим все упрощения K ∨ K · K̃ = K.Финальное уравнение_xl 1 · . . . · xl vопределяет все тупиковые тесты (l1 , . . . , lv ).Обоснование алгоритма см. в лекции 4.Процесс умножения при переходе к финальному уравнению и реализация функций вклассе д.н.ф. весьма трудоемки. В тестовом алгоритме последнее отсутствует, т.к. уравнения сразу задаются в виде д.н.ф. Процесс умножения можно существенно упростить,используя специфику булевой алгебры.
Укажем несколько упрощающих приемов.a) из двух уравнений f = 1, f · f˜ = 1. Второе можно удалить, т.к. оно является следствиемпервого.Qб) пусть даны уравнения f0 ∨ fi = 1, i = 1 . . . k; тогда ki=1 (f0 ∨ fi ) = f0 ∨ f1 · . . . · fk .Действительно: f0 · f0 = f0 , f0 ∨ f0 · fi = f0 . (правило поглощения)в) K · (K · K0 ) = K · K 0 ,Q ∨ Q = Q.Существует большое число других упрощающих правил. Эффективность трех приведенных выше продемонстрируем на примере, рассмотренном в алгоритме “Кора”.S1S2S3S4S5S611001102010001310100040101005001011S1 , S2 , S3 ∈ K1 ; S4 , S5 , S6 ∈ K27Имеем 9 уравнений, получаемых при сравнении строк Si , i = 1, 2, 3 со строками Sj ,j = 4, 5, 6.(S1 , S4 ) : x3 ∨ x4 = 1; (S1 , S5 ) : x3 ∨ x5 = 1;(S2 , S4 ) : x1 ∨ x2 = 1; (S2 , S6 ) : x4 ∨ x5 = 1;(S3 , S5 ) : x1 ∨ x3 = 1; (S3 , S6 ) : x2 ∨ x3 = 1;(S1 , S6 ) : x1 ∨ x2 ∨ x3 ∨ x5 = 1(S2 , S5 ) : x1 ∨ x2 ∨ x4 ∨ x5 = 1(S3 , S4 ) : x1 ∨ x3 ∨ x4 ∨ x5 = 1По правилу a) удаляются уравнения (S1 , S6 ), (S2 , S5 ), (S3 , S4 ).
Среди оставшихся выделимуравнения x3 ∨ x4 = 1, x3 ∨ x5 = 1, x1 ∨ x3 = 1, x2 ∨ x3 = 1. По правилу б) произведениелевых частей даст x3 ∨ x1 · x2 · x4 · x5 = 1. Перемножаем оставшиеся два уравнения(x1 ∨ x2 ) · (x4 ∨ x5 ) = x1 x4 ∨ x1 x5 ∨ x2 x4 ∨ x2 x5Перемножая левые части двух полученных уравнений и, используя в), имеем:x1 x3 x4 ∨ x1 x3 x5 ∨ x2 x3 x4 ∨ x2 x3 x5 ∨ x1 x2 x4 x5 = 1.К последней д.н.ф.
правило поглощения неприменимо, поэтому наборы(1, 3, 4), (1, 3, 5), (2, 3, 4), (2, 3, 5), (1, 2, 4, 5) образуют все тупиковые тесты.Классифицируем, как в алгоритме “Кора” набор S = (10101). По тесту (1, 3, 4) имеем совпадение с S1 ∈ K1 ; по (1, 3, 5) нет совпадений ни с одной строкой; по (2, 3, 4) —совпадение с S1 , S3 ∈ K1 ; по (2, 3, 5) — с S3 ∈ K1 ; по (1, 2, 4, 5) — с S5 ∈ K2 . СледовательноΓ(S, K1 ) = 3,Γ(S, K2 ) = 1.Вывод: при ν < 2 : S ∈ K1 , при ν ≥ 2 алгоритм откажется от распознавания.8Лекция 22.1Логические алгоритмы распознаванияДля избежания громоздких выкладок и привлечения теории функций k-значной логики ограничимся задачей распознавания с двумя непересекающимися классами K1 , K2 ,причем признаки будут принимать только значения 0,1.В дальнейшем объекты исходной информации I задаются бинарными наборамиS1 , .
. . , Sr , Sr+1 , . . . , Sm , где Si = (αi1 . . . αik . . . αin ), i = 1 . . . n. Объекты Si , i = 1 . . . r принадлежат K1 , объекты Si , i = r + 1, . . . , m — классу K2 .Напомним некоторые сведения из теории булевых функций (функций алгебры логики).Каждая f (x1 , . . . , xn ),Wвообще говоря, неоднозначно представима дизъюнктивной нормальной формой д.н.ф. Ki , где Ki — элементарные конъюнкции.
Если Ki = xσ1 1 , . . . , xσk k ,iто k — ранг конъюнкции,(x, если σ = 1;x =x, если σ = 0.σЕсли Nf — множество единиц f , NK — интервал, K - множество единиц конъюнкции K,ttWSто f =Ki ⇔ NKi =NKi . Интервал называется максимальным, а соответствующаяi=1i=1ему элементарная конъюнкция — простой импликантой, если не существует NK0 : NK ⊂⊂ NK0 ⊂ Nf .Пусть NKi , .
. . , NKc — совокупность всех максимальных интервалов функции f. Д.н.ф.Dc (f ) называют сокращенной д.н.ф. функции f . Каждая д.н.ф. минимальной сложностиlWполучается удалением из Dc (f ) некоторых э.к. (Dc (f ) =Ki ).i=1Напомним, что сложностью д.н.ф называется сумма рангов входящих в нее э.к.Построение минимальных д.н.ф подразделяется на следующие этапы:I.
строится произвольная д.н.ф. Df , реализующая fII. к Df применяются преобразования xi Ku ∨ xi Kv → xi Ku ∨ xi Kv ∨ Ku Kv ; K ∨ KK0 → Kдо тех пор, пока это возможно. Построенная д.н.ф. называется сокращенной.lWIII. в д.н.ф. Dc (f ) =Ki выбирается произвольный интервал NKj , 1 ≤ j ≤ l, такой,i=1Sчто NKj ⊂NKi . Э.к. Kj удаляются из Dc (f ), оставшиеся интервалы образуютi6=jпокрытие Nf ; поэтому Dc (f ) \ Kj реализует f . Процесс повторяется до тех пор, пока в покрытии не остаются только интервалы, не покрывающиеся суммой осталь-9ных NKU1 , .
. . , NKUp . Соответствующая д.н.ф называется тупиковой для f : D1 (f ) =pW=K Ui .i=1Процесс удаления конъюнкций (их интервалов из покрытия) не однозначен, поэтомучисло тупиковых д.н.ф. может быть велико. Очевидно, что среди тупиковых содержатсяи все минимальные д.н.ф.Для дальнейшего нам понадобятся несколько утверждений и алгоритмов:I. Как относительно нетрудоемко построить д.н.ф. приемлемой сложности, реализующую fII. Найти аналитический критерий, позволяющий легко проверить:NK ⊆q[NKi ,i=1что необходимо для построения тупиковых д.н.ф.SSσIII.
Как влияют на соотношения NK ⊆ NKi , NK 6⊆ NKi преобразования xi → xj ij , i— подстановка (преобразование взаимно однозначно), σij ∈ {0, 1}jПроверка соотношения NK ⊆lSNKi . Не ограничивая общности считаем, что в K иi=1Ki , i = 1 . . . l нет переменных xt в различных степенях. Т.е. если xσt ∈ K, то в Ki , i = 1 . . . lнет сомножителей xσt . Действительно, если бы xσi находится в Ki , то KKi ≡ 0, (NK ∩ NKi == ) и NKi не влиял бы на выполнимость проверяемого соотношения.Представим Ki в виде Ki1 · Ki2 ; в Ki1 входят все сомножители, общие с K, в Ki2 — оставшиеся. Если оставшихся нет, полагаем Ki2 = 1.Теорема 1 (Критерий поглощения) NK ⊆lSi=1≡ 1.NKi тогда и только тогда, когдаlWKi2 ≡i=1Доказательство. Достаточность.
Пусть α̃ ∈ NK : K(α̃) = 1. Но тогда очевидноKi1 = 1, i = 1 . . . l. Выделим в α̃ поднабор из координат, соответствующих переменным изlWKi2 , i = 1 . . . l. Так какKi2 = 1, то найдется Ku2 , 1 ≤ u ≤ l, равное 1 на этом наборе. Ноi=1lSв этом случае Ku1 · Ku2 (α̃) = 1, Ku (α̃) = 1. Следовательно α̃ ∈ NKu ⊆NKi . Достаточностьi=1доказана.lWНеобходимость.
ПустьKi2 6≡ 1. Тогда найдется поднабор β̃ координат переменных,i=1не входящих в K, такой, что Ki2 (β̃) = 0, i = 1 . . . l.Пусть K = Xtσ11 , . . . , Xtσvv . Сформулируем набор γ̃, положив в нем координаты t1 , . . . , tv ,равные, соответственно σ1 , . . . , σv , добавим значения координат из набора β̃; остальныекоординаты зададим произвольно. Тогда K(γ̃) = 1, Ki1 (γ̃) · Ki2 (γ̃) = 0, i = 1 . . . l, такlSKi2 (γ̃) = 0, i = 1 . . . l (Ki2 (β̃) = 0, а β̃ — часть набора γ̃). Имеем: γ̃ ∈ NK , γ̃∈ NKi .i=1Необходимость доказана.
iσijПусть π — преобразование xi → yj ,— подстановка, π(K) — результат преобраjзования K с помощью π.10Теорема 2 NK ⊆lSNKi ↔ Nπ(K) ⊆i=1lSNπ(Ki )i=1Доказательство. Пусть NK ⊆lSNKi . Тогдаi=1lWKi2 ≡ 1 (по т. 1). Но любая подста-i=1новка в функцию f (z1 , . . . , zm ), zi = ϕi (yi1 , . .
. , yiki ) приводит к f (ϕ1 , . . . , ϕm ) ≡ 1, еслиllSWf (z1 , . . . , zm ) ≡ 1. Проверка последнего тривиальна. Если NK 6⊆NKi , тоKi2 6≡ 1 (т.i=1i=11), и существует набор β̃: Ki2 (β̃) = 0, i = 1 . . . l. Это значит, что в каждой Ki2 есть сомножитель xσr , а r-я координата в β̃ равна σ. Если при π : xr → yt , то в новом набореt-я координата равна σ, а соответствующий сомножитель: ytσ . Очевидно, π(Ki2 (β̃)) = 0.Случай xr → y t разбирается аналогично.Сказанное выше применимо ко всем Ki2 , имеющим сомножитель xσr . Остальные Ku2 либоне имеют сомножителя от переменной xr , либо имеют сомножитель xσr .
Следовательно, вкаждой из этих Ku2 найдется сомножитель от xq , q 6= r, для которого проходят предыдущиеllSWNπ(Ki ) .выкладки. Таким образом π( Ki2 ) 6≡ 1 и Nπ(K) 6⊆i=1i=1Переходим к реализации I. Докажем сначала:(x1 ∨ . . . ∨ xn ) · (x1 ∨ . . . ∨ xn ) == x1 · x2 ∨ x2 · x3 ∨ . . . ∨ xi · xi+1 ∨ xi+1 · xi+2 ∨ . . . ∨ xn−1 · x ∨ xn · x1 )Легко видеть, что левая часть реализует функцию, равную на наборах (0 .
. . 0 . . . 0),(1 . . . 1 . . . 1). Действительно, на любом другом наборе либо найдется пара координатi, i + 1, таких, что αi = 1, αi+1 = 0 и тогда xi · xi+1 = 1, либо αn = 1, α1 = 0. Итогда xn · x1 = 1 (рассматривается набор α̃ = (α1 . . . αn ).Заметим, что умножение двух конъюнкций (xσ1 1 ∨. . .∨xσnn )·(xδ11 ∨. . .∨xδnn ) — произведениереализует функцию, равную 0 только на наборах (σ 1 . . . σ n ), (δ 1 , . . . , δ n ) — с помощьюпреобразования π можно привести к умножению двух конъюнкций(y1 ∨ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
