Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Минимизация дизъюнктивных нормальных форм
Булеву функцию g назовём импликантом булевой функции f, если для любых наборов значений аргументов этих функций из равенства g = 1 следует равенство f = 1. Например, для функции f из примера (*) функция является импликантом. Действительно, функция g принимает значение 1 только при x = 0, y = 1, z = 0. Но и функция f при x = 0, y = 1, z = 0 также принимает значение 1. А для функции f из примера (*) функция не является импликантом. Ведь функция g = 1 при x = 1, y = 1, z = 0. Но f(1,1,0) = 0. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестаёт быть импликантом, то такой импликант называется простым. Проверим импликант на простоту. При отбрасывании в этой функции переменной x получим функцию , которая принимает значение 1 при y = 1, z = 0. Но функция f при y = 1, z = 0 может принимать и нулевое значение, например, f(1,1,0) = 0. При отбрасывании в функции переменной y получим функцию , которая принимает значение 1 при x = 0, z = 0. Но функция f при x = 0, z = 0 может принимать и нулевое значение, например, f(0,0,0) = 0. При отбрасывании в функции переменной z получим функцию , которая принимает значение 1 при x = 0, y = 1. Но функция f при x = 0, y = 1 может принимать и нулевое значение, например, f(0,1,1) = 0. Так как при отбрасывании любой переменной функция перестаёт быть импликантом функции f, то является простым импликантом функции f. Сокращённая ДНФ Сокращённая ДНФ функции f есть дизъюнкция всех простых импликантов функции f. Всякая функция реализуется своей сокращённой ДНФ. Для любой функции, не равной тождественно нулю, существует единственная сокращённая ДНФ. Алгоритм построения сокращённой ДНФ с помощью СКНФ. 1. По таблице истинности строим СКНФ функции f. 2. В СКНФ раскрываем скобки, удаляем дублирующие элементы (, ) и элементы, которые содержат переменную вместе с её отрицанием (). 3. Проводим поглощение () и удаляем дублирующие элементы. Сокращённая ДНФ функции f получена. Пример. Для функции из примера (*) построить сокращённую ДНФ. Решение: СКНФ . Раскроем скобки. Перемножение лучше начинать со скобок, которые отличаются всего одной переменной. Поэтому поменяем местами вторую и третью скобки. Затем перемножим первую и вторую скобки, а также четвёртую и пятую скобки. . В первой скобке слагаемое y поглощает все слагаемые, содержащие y, а слагаемое z поглощает все слагаемые, содержащие z. В третьей скобке слагаемое поглощает все слагаемые, содержащие , а слагаемое поглощает все слагаемые, содержащие .
Получим . Перемножим вторую и третью скобки, так как у них есть общий элемент : . Мы воспользовались правилом поглощения. Тогда . Таким образом, получена сокращённая ДНФ функции f, то есть сокр. ДНФ f = .
|
|||||
Последнее изменение этой страницы: 2017-01-26; просмотров: 187; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.118.144.69 (0.005 с.) |