1 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 4
Описание файла
Файл "1" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2017)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2017)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Элементарная конъюнкция, которая имплицирует ФАЛ f , называется импликантой этой ФАЛ. Заметим, что отношение имплицируемостиявляется отношением частичного порядка и что f 0 имплицирует f 00 тогда и только тогда, когда f 00 = f 0 ∨ f 00 илиf 0 = f 0 · f 00 . Отсюда следует, в частности, что ЭК K 0 имплицирует ЭК K 00 тогда и только тогда, когда множество буквK 00 содержится во множестве букв K 0 , то есть K 0 = K 00 · Kдля некоторой ЭК K, не имеющей общих букв с ЭК K 00 .
Этоозначает, что в данном случае ЭК K 0 может быть «устранена» из ДНФ K 00 ∨ K 0 с помощью тождества поглощения(2.3).Дизъюнктивную нормальную форму A вида (2.6) будемназывать ДНФ без поглощений ЭК, если ни одна из гранейNK1 , . . . , NKs не содержится ни в одной из других гранейпокрытия (2.8). На «языке имплицируемости» это означает,что ни одна из ЭК Ki , i ∈ [1, s], не является импликантойЭК Kj , где j ∈ [1, s] и i 6= j.
Заметим, что с помощью тождества поглощения (2.3) из любой ДНФ A можно получитьb без поглощений ЭК.ДНФ A.Импликанта K ФАЛ f называется простой импликантой этой ФАЛ, если она не поглощается никакой другойотличной от нее импликантой ФАЛ f . Из определений и отмеченных выше фактов следует, что в простую импликантуФАЛ f не входят буквы несущественных БП этой ФАЛ и чтоиз любой импликанты ФАЛ f можно получить ее простуюимпликанту удалением некоторых букв. Последнее означает, что любая импликанта ФАЛ f имплицирует некоторуюпростую импликанту f . С «геометрической» точки зренияпростые импликанты ФАЛ f соответствуют максимальнымпо включению граням множества Nf .Дизъюнкция всех простых импликант ФАЛ f называется ее сокращенной ДНФ. Заметим, что сокращенная ДНФФАЛ f является ДНФ без поглощений и что ей соответ-Введение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Введение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Введение27Рис.
3.2: карта Карно ФАЛ g 028ВведениеДоказательство. Достаточно доказать, что в 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 ,Введение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Введениеиз 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)Введение§431Тупиковые ДНФ, ядро и ДНФ пересечениетупиковых. ДНФ Квайна и ДНФ сумма тупиковых, критерий вхождения простых импликант в тупиковые ДНФ, его локальностьБудем говорить, что ДНФ A, реализующая ФАЛ f , является тупиковой ДНФ, если f 6= A0 для любой ДНФ A0 , полученной из A в результате удаления некоторых букв или целых ЭК. Из определения вытекает, что в тупиковую ДНФA ФАЛ f могут входить только простые импликанты этойФАЛ, и что A является ДНФ без поглощений ЭК. С «геометрической» точки зрения тупиковая ДНФ A ФАЛ f задаеттупиковое (см.