Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2017-12-12 | 710 |
5.00
из
|
Заказать работу |
Будем полагать, что БФ задана таблично кодами конъюнкций D 1 и D 0.
Любая конъюнкция К из D 1 такова, что:
1) M 1 (К) Ç M 1 (F) ¹ Æ -конъюнкция К из множества М1 входит в множество М1(F).
2) M 1 (К) Ç M 0 (F) = Æ -конъюнкция К из множества М1 не входит в множество М0(F). Нет такого набора значений переменных, на котором БФ одновременно определяется равной и 1 и 0.
Если максимально укоротить конъюнкцию К так, чтобы условия 1) и 2) попрежнему выполнялись, то мы получим простую импликанту.
Выполнимость условия 1) вытекает из того, что если К* получена из К вычеркиванием букв, то M 1 (К*) É M 1 (К).
Доказательство.
Если переменная в конъюнкции К вызывает вхождение в M 1 (К) наборов со значением Х равным b, то вычеркивая Х, мы увеличим M 1 (К) за счет наборов с противоположным значением (1 - b).
Рассмотрим пример.
Пусть F = (X,Y,Z,W). K = K* =
Тогда M 1 (К) = (0101,0111).
M 1 (K*) содержит наборы M 1 (К) и кроме того наборы (1101,1111).
Процедура построения ДНФ эквивалентной D 1, но состоящей из простых импликант может быть такой:
1. Берем любую К конъюнкцию из D 1.
2. Максимально укорачивая К, строим простую импликанту и выписываем ее.
3. Удаляем из D 1 конъюнкции поглощаемые К.
4. Если D 1 пусто кончаем, иначе идем к пункту 1.
Примечание.
Конъюнкция А поглощает конъюнкцию В, если константные значения кода А, тоесть все значения кроме «-», входят составной частью в код В.
Рассмотрим пример.
А = (- 0 0 -);
В = (- 0 0 1);
Удаляя из К одну за другой буквы, мы должны проверять не нарушается ли условие 2).
Если нарушается, то букву восстанавливаем, если нет, то оставляем удаленной.
Проверив все буквы в К, мы добьемся ее максимального укорачивания, то - есть получения из нее простой импликанты.
Проверка 2) выполняется так.
После вычеркивания буквы, берется код К и поочередно сравнивается со всеми кодами конъюнкций D 0. Если для любой пары сравниваемых кодов хотя бы в одном разряде значения противоположны (0 и 1), то нет набора, на котором К и D 0 одновременно равны «1», а значит можно вычеркивать данную переменную.
В противном случае, вычеркнутая (пробно!) буква должна быть восстановлена, так как ее удаление приводит к нарушению условия 2).
Процедуру построения ДНФ из простых импликант проиллюстрируем примером.
X | Y | Z | W | F |
- | ||||
- | ||||
- | ||||
- | ||||
- | - | |||
- | ||||
D 1 =
D 0 =
Берем из D 1 первую конъюнкцию: (можно было бы взять и другую) и начинаем пробные вычеркивания букв.
(000 -)
?
(- 00 -)
Если конъюнкция (код - 00 -) такова, что М 1 () Ç М 0 (F~) ¹Æ, то тогда есть набор, который можно получить по коду (- 00 -) и одновременно по коду хотя бы одной конъюнкции из D 0.
Так как код (- 00 -) ортогонален каждому коду из D 0, то набора принадлежащего и М 1 () и М 0 (F~) не существует.
Ортогональность - наличие противоположных значений 0/1 хотя бы в одном разряде кодов.
Действительно:
( | - | - | ) | |||
( | - | - | ) | |||
( | - | - | ) | |||
( | - | ) | ||||
( | - | - | ) | |||
( | - | ) |
Отсюда имеем первое укорачивание и переход к следующему пробному вычеркиванию.
(000 -)
(- 00 -)
?
(-- 0 -)
Вычеркивание недопустимо, так как (-- 0 -) не ортогонально с (11 - 1). Отсюда следует, что набор 1101 принадлежит и М 1 и М 0, а этого быть не может. Следовательно, вычеркивание невозможно и нужно новое пробное вычеркивание. Восстанавливаем вычеркнутую букву.
Пробуем вычеркнуть
(- 00 -)
?
(- 0 --)
Вычеркивание недопустимо, так как (- 0 --) не ортогонально с (--11). Отсюда следует, что набор 0011 принадлежит и М 1 и М 0, а этого быть не может. Следовательно, вычеркивание невозможно.
В итоге мы получили .
Константные значения кода (- 00 -), то есть все значения кроме «-», входят составной частью в коды (000 -) и (- 000). Следовательно, эта конъюнкция поглощает конъюнкции .
После выполнения поглощения, мы получим следующую таблицу:
X | Y | Z | W | F |
- | ||||
- | ||||
- | - | |||
- | ||||
- |
Берем код 00-0 и выполняем пробное вычеркивание -0-0. Теперь выполним проверку на ортогональность с наборами из М0.
- | - | - | - | - | - | ||||||||
- | - | - | - |
Так как код (- 0-0) ортогонален каждому коду из D 0, то набора принадлежащего и М 1 () и М 0 (F~) не существует. Вычеркивание возможно.
Далее, попытаемся вычеркнуть следующую букву в коде -0-0. Выполним проверку на ортогональность с наборами из М0 кода ---0.
- | - | - | - | - | - | - | - | - | |||||
- | - | - | - |
Вычеркивание недопустимо, так как (---0) не ортогонально с (111-). Отсюда следует, что набор 1110 принадлежит и М 1 и М 0, а этого быть не может. Следовательно, вычеркивание невозможно и буква восстанавливается.
Теперь, попытаемся вычеркнуть другую букву в коде -0-0. Выполним проверку на ортогональность с наборами из М0 кода -0---.
- | - | - | |||||||||||
- | - |
Вычеркивание недопустимо, так как (-0--) не ортогонально с (0011). Отсюда следует, что набор 0011 принадлежит и М 1 и М 0, а этого быть не может. Следовательно, вычеркивание невозможно.
Таким образом, получаем уще одну простую импликанту , которая поглощает конъюнкцию .
В результате, у нас остается ода конъюнкция из М1.
X | Y | Z | W | F |
- | ||||
- | - | |||
- | ||||
- |
Берем оставшийся код 0-00 и выполняем пробное вычеркивание --00. Теперь выполним проверку на ортогональность с наборами из М0.
- | - | - | - | - | - | ||||||||
- | - | - | - |
Так как код (- 0-0) ортогонален каждому коду из D 0, то набора принадлежащего и М 1 () и М 0 (F~) не существует. Вычеркивание возможно.
Дальнейшие пробные вычеркивания выполняются аналогично.
В итоге получаем F~= .
Рассмотрим еще один пример.
X | Y | Z | W | F~ |
Берем из D 1 первую конъюнкцию: и начинам ее укорачивать. Будем работать не с конъюнкциями, а с их кодами.
0 0 0 1 | ||
- 0 0 1 | Все коды из D0 ортогональны | |
- - 0 1 | Нельзя, так как в как в D0 есть код 0101 | |
- 0 0 1 | Восстанавливаем вычеркнутую переменную | |
- 0 - 1 | Нельзя, так как в как в D0 есть код 0011 | |
- 0 0 1 | Восстанавливаем вычеркнутую переменную | |
- 0 0 - | Все коды из D0 ортогональны | Эта конъюнкция поглощает 0001 и 1001 из D1 |
Берем из D 1 следующую конъюнкцию: и начинам ее укорачивать. Будем работать не с конъюнкциями, а с их кодами.
0 0 1 0 | ||
- 0 1 0 | Все коды из D0 ортогональны | |
- - 1 0 | Все коды из D0 ортогональны | |
- - - 0 | Все коды из D0 ортогональны | Эта конъюнкция поглощает 0010 и 0110 из D1 |
Множество D 1 = Æ.
В результате получается F~=
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!