Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Расчётный метод минимизации логических функций ⇐ ПредыдущаяСтр 8 из 8
Пусть нам требуется минимизировать ФАЛ, заданную выражением (1). 1 этап. Выполняем операции склеивания конституент единицы. Для упорядочения этой процедуры запишем выражение (1) в виде нескольких строк по следующему правилу: первая строка - это исходное уравнение, вторая строка - это вторая конституента и все последующие, третья строка - это третья конституента и все последующие и т.д. Это допустимо, так как в булевой алгебре действует закон тавтологии. Производится проверка на склеивание первого члена в каждой строке со всеми остальными в данной строке. В первой строке склеиваются первая и третья конституенты, во второй строке -первая со второй и четвертой, в третьей строке первая конституента с остальными не склеивается, и в последней строке конституенты склеиваются. Поскольку все конституенты участвовали хотя бы в одном склеивании, то в cокращенной ДНФ ни одной конституенты не будет. После этой процедуры получаем следующее выражение: Дальнейшее склеивание на может быть выполнено, так как все члены выражения (8) являются изолированными. 2 этап. Необходимо выявить лишние импликанты в выражении (8). Это можно сделать двумя способами. При первом способе развертывают одну импликанту до конституент единицы, а затем смотрят, не поглощаются ли эти конституенты остальными импликантами. Первая импликанта развертывается до суммы причем конституента не поглощается ни одной импликантой, следовательно, импликанта не является лишней. Вторая импликанта развертывается до суммы , причем обе конституенты поглощаются остальными импликантами, следовательно, импликанта лишняя. Продолжим эту процедуру, оставив пока импликанту в выражении (8). Импликанта раз- вертывается до суммы , причем обе конституенты поглощаются остальными импликантами, следовательно, импликанта лишняя. Продолжим, оставив в выражении (8) и эту импликанту. Развертывание последней импликанты дает сумму , в которой конституента не поглощается ни одной импликантой, следовательно, импликанта не является лишней. Выявлены две лишний импликанты, но это не значит, что обе они могут быть отброшены, так как каждая из них проверялась при вхождении второй в выражение (8). Следовательно, отбросить наверняка можно одну из них, а затем снова произвести проверку возможности отбросить и другую. Если отбросить импликанту , то проверка показывает, что импликанта не будет лишней, а если отбросить то не будет лишней. Итак, можно отбросить одну из выявленных двух импликант и в результате получаются две ТДНФ одинаковой сложности, содержащих по шесть букв:
3 этап. Выражение (9) можно записать в виде Аналогично можно упростить и выражение (10): Второй способ выявления лишних импликант заключается в следующем. На значение истинности функции влияет только та импликанта, которая сама равна 1. Любая импликанта принимает значение 1 только на одном наборе своих аргументов. Но если именно на этом наборе сумма остальных импликант также обращается в 1, то рассматриваемая импликанта не влияет на значение истинности функции даже в этом единственном случае, то есть является лишней. Применим это правило к выражению (8). Импликанта принимает значение 1 на наборе . Подставив этот набор в оставшуюся сумму , получим , что говорит о том, что первая импликанта не является лишней. Импликанта принимает значение 1 на наборе . Подставив этот набор в сумму , получим , что говорит о том, что импликанта лишняя. Оставим пока эту импликанту и продолжим анализ других импликант. Импликанта принимает значение 1 на наборе . Подставив этот набор в сумму , получим , что говорит о том, что импликанта лишняя. Оставляем и ее и продолжаем процедуру. Импликанта принимает значение 1 на наборе . Подставив этот набор в сумму Получаем , что говорит о том, что импликанта не является лишней. Как и в первом случае нельзя отбрасывать обе обнаруженные лишние импликанты, так как каждая из них проверялась при вхождении второй в оставшуюся сумму. Опустим рассмотрение дальнейших процедур, так как они аналогичны процедурам, выполненным первым способом. Можно сделать вывод, что даже для этого простого примера пришлось выполнять достаточно много однообразных действий, требующих внимания и времени, поэтому расчетный метод минимизации ФАЛ применяется в основном для ФАЛ, зависящих от двух или трех переменных.
|
||||||||||||
Последнее изменение этой страницы: 2021-04-12; просмотров: 195; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.142.53.216 (0.009 с.) |