Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2017-09-26 | 483 |
5.00
из
|
Заказать работу |
|
|
Не полностью определенными переключательными функциями называются функции, значения которых на некоторых наборах не определены, т.е. могут быть как нулями, так и единицами.
Наборы, на которых функция не определена, называется запрещенными или избыточными.
Форма представления функции существенно зависит от выбора значений ее на избыточных наборах.
Пример. Функция f(ABC) приведена в табл.1.20.
Таблица 1.20
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
f(ABC) 1 0 0 0 - 1 1 -
МДНФ
МДНФ
Рассмотрим общий метод получения МДНФ не полностью определенных булевых функций.
Пусть булева функция f(x1 x2 … xn) не определена на p наборах аргументов. Тогда полностью определенная функция φ(x1 x2 … xn) называется эквивалентной функции f(x1 x2 … xn), если ее значения совпадают со значениями функции f(x1x2…xn) на тех наборах, на которых последняя определена.
Если функция f(x1 x2 … xn) не определена на р наборах, то существует 2p различных функций, эквивалентных данной.
Задача минимизации не полностью определенных функций сводится к отысканию такой эквивалентной функции φi(x1x2…xn), которая имеет простейшую минимальную форму.
Введем эквивалентные функции φ0(x1x2…xn) и φ1(x1x2…xn), которые на всех запрошенных наборах функции f(x1x2…xn) принимают значения 0 и 1 соответственно.
Теорема. Минимальная ДНФ не полностью определенной функции f(x1x2…xn) совпадает с дизъюнкцией тех самых коротких импликант функции φ1(x1x2…xn), которые совместно поглощают все единицы функции φ0(x1x2…xn) и ни одна из них не является лишней.
Доказательство следующее.
Предположим, что φi(x1x2…xn) – некоторая эквивалентная функция. Тогда все минтермы СДНФ φi входят в СДНФ функции φ1. Поэтому любая импликанта функции φi(x1x2…xn) будет совпадать с импликантой функции φ1 или поглощаться ею, т.е. среди импликант функции φ1 всегда найдется такая, которая поглощает любую импликанту любой эквивалентной функции φ1. Следовательно, самыми короткими импликантами из всех накрывающих единицы функции f(x1x2…xn) будут импликанты функции φ1.
|
Среди всех эквивалентных функций φ0 имеет минимальное количество минтермов. Следовательно, и количество простых импликант (из набора импликант функции φ1), необходимых для поглощения минтермов φ0, будет минимальным. Дизъюнкция самых коротких импликант функции φ1, которые совместно накрывают все единицы φ0, представляет МДНФ f(x1x2…xn).
Пример. Найти МДНФ функции:
причем наборы < >, < >, < >, < > являются запрещенными.
Проводим процедуру, описанную в методе Квайна, используя минтермы как функциональных, так и запрещенных наборов функции:
Составляем импликантную матрицу (табл.1.21), используя минтермы только функциональных наборов функции.
Таблица 1.21
Минимальная форма исходной функции
Импликанта ACD не поглощает ни один минтерм функциональных наборов, так как образована из тех минтермов функции φ1, которые в φ0 не входят.
Пример. Найти МДНФ и МКНФ не полностью определенной функции
Причем наборы , и являются запрещенными.
Используем метод карт Вейча (рис.1.11).
Незаполненные клетки карты соответствуют запрещенным наборам.
Карта для обратной функции
приведена на рис.1.12.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!