Главная > Документ


Этап 5.

Найти существенные импликанты функции.

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

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

Для рассматриваемой функции существенными импликантами будут --11 и 1-00, так как только первичная импликанта --11 позволяет покрыть импликанту 0011 исходного набора, а первичная импликанта 1-00 необходима для покрытия импликанты 1100.

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

Первичные импликанты

Конституэты единицы

0011

0111

1000

1010

1011

1100

1111

--11

+

+

+

+

10-0

+

+

1-00

+

+

101-

+

+

-111

+

+

Этап 6.

Найти тупиковые дизъюнктивные нормальные формы и выбрать из них минимальные ДНФ.

Для получения тупиковых ДНФ необходимо отыскать минимальное количество первичных импликант, обеспечивающеее покрытие всех оставшихся столбцов таблицы.

Для анализа после этапа 5 остался только один столбец. Его покрытие может быть обеспечено включением в тупиковую форму либо импликанты 10-0, либо 101-, что приводит к двум тупиковым ДНФ. При наличии выбора в минимальную форму включается импликанта, зависящая от меньшего числа переменных. Обе полученные импликанты зависят от трех переменных, поэтому каждая из них может быть включена в минимальную форму. При равенстве рангов дополнительным фактором для включения той или иной импликанты в минимальную форму иногда служит меньшее число переменных, входящих в импликанту в инверсном виде, так как это в ряде случаев позволяет сократить объем оборудования для аппаратной реализации полученной функции. Мы в своем рассмотрении данный параметр в критерий минимальности включать не будем.

Таким образом, рассматриваемая функция имеет две различные минимальные дизъюнктивные формы:

f1МДНФ= cd v acd v abd

- -1 1 1-0 0 1 0 -0

f2МДНФ= cd v acd v ab с

- -1 1 1- 0 0 1 0 1 -

Пример 3.2

Минимизировать ФАЛ, заданую в виде совершенной конъюнктивной нормальной формы, методом Квайна – Мак-Класки:

f(a,b,c,d)СДНФ = (0,7,10,11,13,14,15)

Решение

Последовательность и содержание этапов, выполняемых при минимизации заданной в СКНФ логической функции, эквивалентны аналогичным этапам, выполнявшимся при минимизации логической функции, заданной в СДНФ (см. пример 3.1).

Этап 1.

Записать двоичное представление наборов, образующих СКНФ данной функции:

(0000, 0111, 1010, 1011, 1101, 1110, 1111)

Этап 2.

Разбить полученные коды на группы, содержащие одинаковое количество нулей в коде. Для ФАЛ, зависящих от n переменных, таких групп может быть n+1 (ни одного нуля в коде, один нуль, два нуля, ... , n нулей в коде). Расположить группы по возрастанию количества нулей. Если количество получившихся групп меньше n+1, то отсутствующие группы помечаются как пустые:

1111

0111

1011

1101

1110

1010

-------

0000

Этап 3.

Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода, отличающихся только в одном разряде (то есть они могут “склеиваться” между собой согласно (3.1.4)), то пометить их каким-либо особым символом, например, "; * ";, и в новую группу поместить код, сохраняющий значение в совпада­ющих разрядах и имеющий какой-либо особый символ, например ";-";, на месте несовпадающего разряда. При этом образуется n-1 новая группа кодов.

Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура “склеивания “ элементов соседних групп. Максимально возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два “склеиваемых” кода представляли собой термы, зависящие от одних и тех же логических переменных, то есть знаки ";-"; у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых термов для дальнейшего анализа следует оставить лишь один из них, исходя из соотношения (1.11).

1111*

-111

1-11*

11-1

111-*

1-1-

1-1-

0111*

1011**

1101*

1110**

101-*

1-10*

1010*

-------

-------

-------

0000

шаг 1

шаг 2

Результатом этого этапа является получение всех первичных имплицент функции и ее сокращенной конъюнктивной нормальной формы.

Этап 4.

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

В ячейку таблицы ставится какой-либо отличительный символ, например ";+";, если первичная имплицента, стоящая в заголовке строки, является собственной частью конституэнты нуля, стоящей в заголовке столбца. В противном случае ячейка остается пустой:

Первичные

имплиценты

Конституэты нуля

0000

0111

1010

1011

1101

1110

1111

1-1-

+

+

+

+

-111

+

+

11-1

+

+

0000

+

Простейший контроль правильности заполнения таблицы может быть проведен аналогично примеру 3.1.

Этап 5.

Найти существенные имплиценты.

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

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

Для рассматриваемой функции все содержащиеся в заголовках строк минтермы будут существенными, так как первичная имплицента 1-1- необходима для покрытия макстермов 1010, 1011, 1110 и 111 исходного набора, имплиценнта -111 – для покрытия макстерма 0111, имплиценнта 11-1 – для по­крытия макстерма 1101, а имплицента 0000 необходима для покрытия такого же макстерма в ис­ходном наборе.

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

Полученная единственная минимальная конъюнктивная нормальная форма имеет следующий вид:

f(x,y,z)СКНФ = (a Vc) & (b Vc Vd) & (a Vb Vd) & (aVbVcVd)

1 - 1 - - 1 1 1 1 1 - 1 0 0 0 0

Пример 3.3

Получить методом Квайна – Мак-Класки минимальные ДНФ и КНФ для ФАЛ, заданной в виде совершенной конъюнктивной нормальной формы:

f(x,y,z)СДНФ = (0,2,5,6,7)

Решение

Вначале получим минимальную конъюнктивную нормальную форму по схеме, изложенной в примере 3.2.

Этап 1.

Записать двоичные коды наборов, образующих СКНФ данной функции:

(000, 010, 101, 110, 111)

Этап 2.

Разбить полученные коды на группы, содержащие одинаковое количество нулей в коде. Расположить группы по возрастанию количества нулей:

111

110

101

010

000

Этап 3.

Выполнить склейку кодов, попарно сравнивая элементы соседних групп:

111*

11-

1-1

110*

101*

-10

010*

0-0

000*

Этап 4.

Составить имплицентную матрицу:

Этап 5.

Определить существенные имплиценты.

Для рассматриваемой функции существенными имплицентами будут 0-0 и 1-1.

Этап 6.

Найти тупиковые конъюнктивные нормальные формы и выбрать из них минимальные КНФ.

Из анализа имплицентной матрицы получим, что функция имеет две тупиковые конъюнктивные нор­мальные формы, каждая из которых является минимальной:

f(x,y,z)1МКНФ = (x Vz ) & (x V z) & (xV ¯y )

1 1 0 – 0 1 1

f(x,y,z)2МКНФ = (x Vz ) & (x Vz) & (¯y V z)

1 – 1 0 – 0 – 1 0

Теперь получим минимальную дизюнктивную нормальную форму.

Этап 1.

Записать двоичные коды наборов, образующих СДНФ данной функции:

(001, 011, 100)

Этап 2.

Разбить полученные коды на группы, содержащие одинаковое количество единиц в коде. Расположить группы по возрастанию количества единиц:

001

100

011

Этап 3.

Выполнить склейку кодов, попарно сравнивая элементы соседних групп:

001

100

0-1

011*

Этап 4.

Составить импликантную матрицу:

Первичные импликанты

Конституэты единицы

001

011

100

0-1

+

+

100

+

Этапы 5 и 6.

Анализ импликантной матрицы показывает, что все полученные первичные импликанты являются сущест­вен­ными и, сле­до­ва­тель­но, рассматриваемая ФАЛ имеет единственную минимальную дизъюнктивную нормальную форму:

f(x,y,z)МДНФ =xz V x ¯y ¯z

0-1 1 0 0



Скачать документ

Похожие документы:

  1. Библиографический указатель из фонда научной библиотеки

    Библиографический указатель
    ... -технических работ. МИФИ - городу Москве:Каталог.-М.,2001.-Б.п. 195. Московский государственный инженерно-физический ... .-26с. 4553. Гуров В.В. Синтезкомбинационныхсхем в примерах и решениях: Учеб.пособие/Гуров В.В.-М.:МИФИ,2001.-56с. 4554. Гусев ...
  2. Москва 2011 1 Цели и задачи дисциплины (3)

    Рабочая программа
    ... коммуникационные технологии Москва 2011 1. ... схемотехнических решений и ... и синтезасхем ЭВМ. Анализ комбинационныхсхем. Синтезкомбинационныхсхем: мультиплексор ... СПб.: БХВ-Петербург, 2001. 2. Пухальский Г.И., Новосельцева ... также примеры оценочных ...
  3. Программа обучения студентов ( syllabus ) (3)

    Программа обучения студентов
    ... домашних заданий, самостоятельное решение задач), итоги индивидуальных ... А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г. Информатика/ Под ... ДИАЛОГ-МИФИ,1993 Гуров В.В. Синтезкомбинационныхсхем в примерах М.: МИФИ, 2001 Гуров В.В., Ленский О.Д., ...
  4. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...
  5. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА (2)

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...

Другие похожие документы..