ОК_Часть_1_2015 (С.А. Ложкин - Лекции по основам кибернетики (2015)), страница 4

Заметим, что сокращенная ДНФФАЛ f является ДНФ без поглощений и что ей соответ-§3. Сокращенная ДНФ и способы ее построения25ствует покрытие множества Nf всеми максимальными повключению гранями множества Nf этой ФАЛ. Указанноесоответствие позволяет строить сокращенную ДНФ на основе «геометрических» соображений.

Так, в соответствиис рис. 2.1 правая часть (2.10) является сокращенной ДНФФАЛ g, а из рис. 3.1a вытекает, что сокращенная ДНФ ФАЛg 0 (x1 , x2 , x3 , x4 ), для которой αeg0 = (1111 1011 1101 1010), имеет видg 0 = K10 ∨ . . . ∨ K70 ,(3.1)где K10 = x3 x4 , K20 = x2 x3 , K30 = x2 x4 , K40 = x1 x3 , K50 == x2 x4 , K60 = x1 x4 , K70 = x1 x2 , причем ЭК Ki0 , i = 1, .

. . , 7,соответствует грани Ni0 = NKi0 на рис. 3.1a. На рис. 3.1bприведена для наглядности «развертка» множества Ng0 исоставляющих его максимальных граней указанной ФАЛ g 0 .Легко видеть, что сокращенная ДНФ ЭК или ЭД совпадаетс ней самой.Чтобы сделать построение сокращенной ДНФ для ФАЛf, f ∈ P2 (n), более наглядным, часто используют ее представление в виде карты Карно, то есть в виде таблицы Π2,2 (f ),в которой наборы (10) и (11) переставлены, а противоположные стороны отождествлены по типу «тора». Заметим, чтолюбое ребро куба B 4 соответствует двум соседним клеткамуказанной таблицы, а любой квадрат в B 4 — либо квадрату,составленному из четырех соседних клеток таблицы, либоее строке или столбцу.

На рис. 3.2 приведена карта Карно ФАЛ g 0 (x1 , x2 , x3 , x4 ) и указаны все максимальные граниэтой ФАЛ.Теорема 3.1. Пусть A0 и A00 — сокращенные ДНФ ФАЛf 0 и f 00 соответственно, а ДНФ A без поглощений получается из формулы A0 · A00 в результате раскрытия скобоки приведения подобных. Тогда A — сокращенная ДНФ ФАЛf = f 0 · f 00 .26Глава 1. Дизъюнктивные нормальные формыe1` @@@@ β4β0β53 `c N@`3c`N50 `c @ @@@ @ N40@ @@@@0 α6N@α1`c `@@N70 @`c2 c` α2c``N60@α7@@@@@ @ N10 @@@ @@α@5@`c@`c`c @c`α4β0@ α3@@ x x2 3 x4 x@11@I 6@`c e0a)β` 3 = (1011)N30α3 ` = (0001)α2 = (1001) `N70N20β0 = (1000) `` α0 = e0N10α1 = (1100) `` α7 = (0011)N40` α4 = (0010) ` β4 = (0111)N60`α5 = (0100)N50`β5 = (1110)` α6 = (0110)b)Рис.

3.1: «геометрия» сокращенной ДНФ ФАЛ g 0§3. Сокращенная ДНФ и способы ее построенияРис. 3.2: карта Карно ФАЛ g 02728Глава 1. Дизъюнктивные нормальные формыДоказательство. Достаточно доказать, что в A входит любая простая импликанта ФАЛ f . Пусть ЭК K является простой импликантой ФАЛ f и, следовательно, является импликантой как ФАЛ f 0 , так и ФАЛ f 00 . Из свойств сокращенных ДНФ вытекает, что в A0 и A00 найдутся ЭК K 0 и K 00соответственно, которые имплицируются ЭК K. Таким обeразом, в ДНФ A войдет имплицируемая ФАЛ K 0 · K 00 ЭК K,которая получится в результате раскрытия скобок и приведения подобных в формуле A0 · A00 . Заметим, что при этомЭК K имплицирует ФАЛ K 0 ·K 00 и, следовательно, имплициe Поскольку ЭК Ke является импликантой ФАЛ fрует ЭК K.e = K, так каки, одновременно, имплицируется ЭК K, то KK — простая импликанта ФАЛ f .Теорема доказана.Следствие. Если ДНФ A без поглощений получается изКНФ B ФАЛ f в результате раскрытия скобок и приведения подобных, то A — сокращенная ДНФ ФАЛ f .Применяя следствие из теоремы 3.1 к ФАЛ g 0 , показанной на рис.

3.1-3.2, получим (сравните с (3.1))D = (x1 ∨ x2 ∨ x4 )·(x1 ∨ x2 ∨ x3 ∨ x4 )·(x1 ∨ x2 ∨ x3 ∨ x4 ) == (x2 ∨ x4 ∨ x1 x3 ) · (x1 ∨ x2 ∨ x3 ∨ x4 ) == x3 x4 ∨ x1 x4 ∨ x1 x2 ∨ x2 x3 ∨ x2 x4 ∨ x1 x3 ∨ x2 x4 .Следующий метод (метод Блейка [6]) позволяет получать сокращенную ДНФ ФАЛ f из произвольной ДНФ этойФАЛ с помощью эквивалентных преобразований на основетождества обобщенного склеивания:x1 x2 ∨ x1 x3 = x1 x2 ∨ x1 x3 ∨ x2 x3 .Любая ДНФ A0 , которую можно получить из ДНФ Aпутем формирования в ней с помощью тождеств ассоциативности и коммутативности подформул вида xi K 0 ∨ xi K 00 ,§3. Сокращенная ДНФ и способы ее построения29применения к этим подформулам тождества обобщенногосклеиванияxi K 0 ∨ xi K 00 = xi K 0 ∨ xi K 00 ∨ K 0 K 00(3.2)и последующего приведения подобных, называется расширением ДНФ A.

Расширение A0 ДНФ A считается строгим, если A0 содержит ЭК, не являющуюся импликантой ни однойЭК из A. Заметим, что сокращенная ДНФ не имеет строгихрасширений и что в результате построения последовательных строгих расширений и приведения подобных из любойДНФ можно получить ДНФ без поглощений ЭК, которая неимеет строгих расширений.Теорема 3.2. ДНФ без поглощений ЭК является сокращенной ДНФ тогда и только тогда, когда она не имеетстрогих расширений.Доказательство.

Достаточно убедиться в том, что ДНФ Aбез поглощений ЭК, не имеющая строгих расширений, содержит все простые импликанты реализуемой ею ФАЛ f .Пусть X (n) = {x1 , . . . , xn } — множество БП ДНФ A, а K —простая импликанта f , которая не входит в A.

Рассмотриммножество K, состоящее из всех тех элементарных конъюнкций от БП X (n), которые являются импликантами f , но неявляются импликантами ни одной ЭК из A. Заметим, чтомножество K не пусто, так как содержит ЭК K в силу еесвойств, и что K не может содержать ЭК ранга n, поскольку любая ЭК вида xα1 1 · · · xαnn , где α = (α1 , . . . , αn ) ∈ Nf ,является импликантой той ЭК из A, которая обращается в1 на наборе α.Пусть, далее, k — ЭК максимального ранга в K, причем,как было отмечено, R (k) < n, и пусть буквы некоторой БПxi , 1 6 i 6 n, не входят в k. Тогда, в силу выбора ЭК k исвойств ДНФ A, ЭК вида xi · k (вида xi · k) должна быть импликантой некоторой ЭК вида xi ·K 0 (соответственно xi ·K 00 )30Глава 1. Дизъюнктивные нормальные формыиз A, где ЭК K 0 и K 00 состоят из букв ЭК k.

Следовательe равной K 0 · K 00 , а ЭКно, ЭК k является импликантой ЭК KeK, в свою очередь, является импликантой некоторой ЭК изA. Действительно, ДНФ A не имеет строгих расширений иe попоэтому содержит ЭК, которая имплицируется ЭК K,000лучающейся из подформулы xi K ∨ xi K в результате эквивалентного преобразования (3.2). Таким образом, ЭК kявляется импликантой некоторой ЭК из A и не может входить в K. Полученное противоречие доказывает, что ЭК Kвходит в A.Теорема доказана.Следствие. Из любой ДНФ A ФАЛ f можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подобных до получения ДНФ без поглощений ЭК, не имеющейстрогих расширений.Возьмем для примера в качестве ДНФ A совершеннуюДНФ ФАЛ голосования H (x1 , x2 , x3 ), которая имеет видA (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 .Применяя к A метод Блейка, получим:A = (x1 x2 x3 ∨ x1 x2 x3 ) ∨ x1 x2 x3 ∨ x1 x2 x3 == x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 = (x2 x3 ∨ x2 x1 x3 ) ∨ x1 x2 x3 == x2 x3 ∨ x1 x3 ∨ x1 x2 x3 = x2 x3 ∨ (x3 x1 ∨ x3 x1 x2 ) == x2 x3 ∨ x1 x3 ∨ x1 x2 .

(3.3)§4. Тупиковые и минимальные ДНФ§431Тупиковые ДНФ, ядро и ДНФ пересечениетупиковых. ДНФ Квайна и ДНФ сумма тупиковых, критерий вхождения простых импликант в тупиковые ДНФ, его локальностьБудем говорить, что ДНФ A, реализующая ФАЛ f , является тупиковой ДНФ, если f 6= A0 для любой ДНФ A0 , полученной из A в результате удаления некоторых букв или целых ЭК. Из определения вытекает, что в тупиковую ДНФA ФАЛ f могут входить только простые импликанты этойФАЛ, и что A является ДНФ без поглощений ЭК.

С «геометрической» точки зрения тупиковая ДНФ A ФАЛ f задаеттупиковое (см. §1) покрытие множества Nf максимальнымигранями ФАЛ f и обратно.Построение всех или некоторых тупиковых ДНФ для заданной ФАЛ f является, обычно, промежуточным этапомпри построении минимальной (кратчайшей) ДНФ ФАЛ f ,то есть ДНФ, которая имеет минимальный ранг (соответственно длину) среди всех ДНФ, реализующих f . Это связано с тем, что минимальная ДНФ обязательно являетсятупиковой, а среди кратчайших ДНФ всегда есть тупиковая.При построении тупиковых ДНФ ФАЛ f бывает полезнознать ДНФ пересечение тупиковых (ДНФ ∩T ) ФАЛ f , тоесть дизъюнкцию всех тех различных простых импликантэтой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛf.Набор α, α ∈ B n , называется ядровой точкой ФАЛ f (x1 , .