Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Второй этап (получение минимальной формы).




Читайте также:
  1. A) Второй категории
  2. Академическое литературоведение второй половины 19 века.
  3. АНТИФАШИСТСКАЯ КОАЛИЦИЯ И ИТОГИ ВТОРОЙ МИРОВОЙ ВОЙНЫ
  4. Архитектура второй половины XIII-XV вв.
  5. Билет 10. Перерастание сословно-представительной монархии в абсолютную во второй половине XVII века.
  6. Билет 18.Кризис феодально-крепостнических отношений в России во второй четверти XIX века. Внутренняя и внешняя политика Николая I.
  7. Билет 23.Земский либерализм и народничество в общественном движении России во второй половине XIX века.
  8. Билет 28. Культура России во второй половине XIX-начале XX вв.
  9. Битва за Москву. Среди крупнейших событий второй мировой войны битва под Москвой занимает особое место. Именно здесь гитлеровская армия потерпела первое серьезное поражение.
  10. В 2005 г. объем прямых иностранных инвестиций рос второй год подряд, и эта тенденция наблюдалась в глобальном масштабе.

Сокращенная форма может содержать лишние члены, исключение которых из выражения функции не повлияет на значение функции.

Таким образом, дальнейшее упрощение логического выражения достигается исключением из выражения лишних членов. В этом и заключается содержание второго этапа минимизации. Покажем этот этап минимизации логического выражения на примере построения логического устройства для функции в табл. 3.6.

рис 3.27

 

Таблица 3.6

Совершенная ДНФ.данной функции

(3.14)

Для получения сокращенной формы проводим операции склеивания и поглощения

Полученное выражение представляет собой сокращенную форму логического выражения заданной функции, а члены его — простые импликанты функции. Переход от сокращенной формы к минимальной осуществляется с помощью импликантной матрицы, приведенной в табл. 3.7.

В столбцы импликантной матрицы вписываются члены СДНФ заданной функции, в строки — простые импликанты функции, т. е. члены сокращенной формы логического выражения функции.

Таблица 3.7
Простые импликанты Члены СДНФ
X X        
X   X      
    X X    
      X X  
        X X

Отмечаются (например, крестиками) столбцы членов СДНФ, поглощаемых отдельными простыми импликантами. В табл. 3.7 простая импликанта поглощает члены , , и в первом и во втором столбцах первой строки поставлены крестики; вторая импликанта поглощает первый и третий члены СДНФ, и поставлены крестики в первом и третьем столбцах второй строки и т. д. Импликанты, которые не могут быть лишними и, следовательно, не могут быть исключены из сокращенной формы, составляют ядро. Входящие в ядро импликанты легко определяются по импликантной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только данной импликантой.



В рассматриваемом примере ядро составляют импликанты и, (только ими перекрываются второй и шестой столбцы матрицы). Исключение из сокращенной формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую уже в нелишний член.

Для получения минимальной формы достаточно выбрать из импликант, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждой из этих импликант, которое обеспечит перекрытие всех столбцов импликантной матрицы, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвертый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту . Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции



(3.16)

Структурная схема, соответствующая этому выражению, приведена на рис. 3.28.

рис 3.28

Переход от сокращенной формы (3.15) к МДНФ (3.16) был осуществлен путем исключения лишних имплнкант и . Покажем допустимость подобного исключения членов из логического выражения.

Импликанты и обращаются в единицу соответственно при следующих наборах значений аргументов:

x1 = 0; х2 = 0; х3 = 0 и х2 = 1; х3 = 1; х4 = 0 (3.17)

Роль этих имликант в выражении сокращенной формы функции (3.15) заключается лишь в том, чтобы на приведенных наборах (3.17) значений аргументов присваивать функции значение 1. Однако при этих наборах функция имеет значение 1 из-за остальных импликант выражения (3.15). Действительно, подставляя значения (3.17) в (3.16), получаем:

при x1 = 0, x2 = 0, x3 = 0

 

при х2 = 1; х3 = 1; х4 = 0

Таким образом, доказана справедливость операции исключения из выражения (3.15) членов и .

До сих пор рассматривалось получение минимальной ДНФ. При использовании метода Квайна для получения минимальной конъюнктивной нормальной формы (МК.НФ) логической функции имеются следущие особенности:

исходной для минимизации формой логического выражения заданной функции является СКНФ;

пары склеиваемых членов имеют вид и ;

операция поглощения проводится в соответствии с выражением

Рассмотрим применение метода Квайна на примере минимизации функции, заданной таблицей истинности (табл. 3.8).

Совершенная КНФ рассматриваемой функции

Склеивающиеся пары членов:

первый и третий члены (результат склеивания );

первый и четвертый члены (результат склеивания ):



второй и третий члены (результат склеивания ).

Таблица 3.8
x1
x2
x3
f(x1,x2,x3)

 

Таблица 3.9
Простые импликанты Члены СДНФ
X   X  
X     X
  X X  

 

Проводя операции склеивания и поглощения, получаем

Члены операции склеивания

Полученное выражение явлиется сокращенной формой функции. Для перехода к минимальной форме строим иммлнк.шгную матрицу (табл. 3.9).

Все столбцы матрицы перекрываются импликантами и . Следовательно, член является лишним и минимальная конъюнктивная нормальная форма (МКНФ) заданной функции


Дата добавления: 2015-08-05; просмотров: 13; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.025 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты