Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Дизъюнктивные нормальные формы
Определение. Элементарной конъюнкцией называется конъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу.
Например, конъюнкции , , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая - 3, а третья - 0. Следующие конъюнкции: , , , , 0 не являются элементарными.
Определение.Элементарная конъюнкция булевой функции , содержащая n литералов, называется полной (или минтермом). Определение. Дизъюнкция любого конечного множества элементарных конъюнкций булевой функции F называется дизъюнктивной нормальной формой (ДНФ) функции F. Число элементарных конъюнкций (слагаемых, термов), составляющих ДНФ, называется длиной ДНФ.
Например, ДНФ имеет длину, равную 3.
Для произвольной булевой функции F существует, вообще говоря, много различных реализующих ее ДНФ, отличающихся друг от друга длиной, числом вхождений литералов и т.д. Определение. Две (или несколько) ДНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными).
Например, для функции , заданной булевым вектором w(F)=(00100111), существуют следующие эквивалентные ДНФ:
, (1) , (2) , (3) , (4) . (5) Определение. ДНФ булевой функции F, состоящая только из полных элементарных конъюнкций, называется совершеннойДНФ(СДНФ).
Например, (1) - СДНФ функции F. Отметим, что СДНФ является единственной (с точностью перестановки слагаемых) для конкретной булевой функции F .
Любую булеву функцию F, заданную формулой, можно с помощью основных равносильностей преобразовать к ДНФ, а затем к СДНФ. Пример.Привести к виду СДНФ булеву функцию F= .
Решение.С помощью основных равносильностей преобразуем к ДНФ: = = = = = - ДНФ.
Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции , до полных элементарных конъюнкций: = .
Так как , то после сокращения одинаковых конъюнкций, получаем СДНФ: F= . Составим таблицу истинности для булевой функции F= (функция из предыдущего примера). Отметим связь между СДНФ и таблицей истинности.
Таблица истинности СДНФ
В общем случае также можно вывести закономерности построения СДНФ по таблице истинности булевой функции, что является очень удобным.
СДНФ состоит из дизъюнкций полных элементарных конъюнкций наборов переменных , на которых функция принимает значение 1. Переменные берутся без отрицания, если им соответствует в таблице истинности 1, с отрицанием, если 0. Пример. По таблице истинности составить СДНФ
Решение: СДНФ: .
Пример. Для булевой функции, заданной в виде ДНФ , составить СДНФ и выполнить проверку по таблице истинности. Решение: Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции, до полных элементарных конъюнкций. Конъюнкцию дополняем в два этапа, так как не является элементарной конъюнкцией: . Так как , после сокращения одинаковых конъюнкций получаем СДНФ: .
Таблица истинности СДНФ
Минимизация ДНФ Определение. Элементарная конъюнкция u называется импликантой булевой функции F , если .
Например, элементарная конъюнкция является импликантой функции . Определение. Если никакая собственная часть импликанты u (т.е. ) булевой функции F не является импликантой F, то u называется простойимпликантой (т.е. если удаление из u хотя бы одного литерала нарушает условие , то u – простаяимпликанта).
Например, – простая импликанта булевой функции , а импликанта не является простой для этой функции , так как (собственная часть импликанты ) является импликантой функции F .
Определение. Дизъюнкция всех простых импликант булевой функции F называется сокращенной ДНФ (СкДНФ)функции F .
Например, – СкДНФ булевой функции . Отметим, что СкДНФ является единственной для конкретной булевой функции F . Определение.ДНФ булевой функции F , содержащая наименьшее число слагаемых среди всех ДНФ, реализующих функцию F , называется кратчайшей ДНФ (КрДНФ).
Например, – КрДНФ этой же булевой функции F .
Вообще говоря, для заданной булевой функции F существует несколько различных по числу вхождений литералов КрДНФ.
Определение.ДНФ булевой функции F , содержавшая наименьшее число вхождений литералов среди всех ДНФ, реализующих функцию F , называется минимальной ДНФ (МДНФ).
Отметим, что для заданной булевой функции F существует, вообще говоря, несколько МДНФ, отличающихся друг от друга числом слагаемых.
Более того, МДНФ не всегда совпадает с КрДНФ булевой функции n переменных F . Хотя для начальных значений n ( n = 2 или n = 3 ) МДНФ всегда совпадает с КрДНФ). Например, является КрДНФ и МДНФ рассматриваемой функции F. Задача минимизации булевой функции в классе ДНФ формулируется следующим образом: требуется для булевой функции n переменных F построить ДНФ с минимально возможным числом слагаемых (КрДНФ) или с минимально возможным числом вхождений литералов (МДНФ).
Причем, если раньше (при синтезе контактных схем) основное внимание уделялось построению МДНФ, то в настоящее время (при синтезе логических схем на элементах И,ИЛИ,НЕ, И-НЕ и др.) требуется построение КрДНФ.
Также отметим, что задача минимизации булевых функций n переменных F в классе ДНФ является чрезвычайно громоздкой и ее трудоемкость с ростом n возрастает по экспоненциальному закону.
К настоящему времени разработано около 200 различных методов минимизации булевых функций в классе ДНФ, наиболее известными среди которых являются метод Квайна - Мак-класки, метод Блейк-Порецкого, метод Нельсона, метод неопределенных коэффициентов и др. Пример. Составить по таблице истинности СДНФ булевой функции и минимизировать ее, применяя законы склеивания. Решение
СДНФ будет иметь вид . Минимизируем ее, применяя законы склеивания. Подчеркнем конъюнкции, которые можно склеить. Очевидно, что это можно сделать различными способами, например:
, , , . Выберем один из возможных вариантов склеивания, например: и минимизируем ДНФ: .
Замечание.При минимизации ДНФ достаточно часто (но не всегда!) удается получить лучшие результаты, если «нарастить» данную ДНФ, используя свойство идемпотентности дизъюнкции: .
Например, в рассматриваемом примере пятую, последнюю конъюнкцию можно было бы склеить со второй конъюнкцией . Добавив вторую конъюнкцию еще раз, мы не изменим саму булеву функцию, но получим в результате минимизации ДНФ более короткое ее представление:
. Пример. Составить СДНФ булевой функции, заданной вектором значений таблицы истинности w(F)=(10010010), и минимизировать ее, применяя законы склеивания. Решение.Так как вектор значений заданной булевой функции имеет 8=23 разрядов, следовательно, булевой функции соответствует следующая таблица истинности:
СДНФ будет иметь вид: .
К сожалению, минимизировать ее, применяя законы склеивания, невозможно. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2018-04-12; просмотров: 229. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |