Контрольная работа : Минимизация неполностью определенных переключательных функций 


Полнотекстовый поиск по базе:

Главная >> Контрольная работа >> Математика


Минимизация неполностью определенных переключательных функций




БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра высшей математики

РЕФЕРАТ

на тему:

«Минимизация неполностью определенных переключательных функций»

В ЦВМ могут использоваться комбинационные схемы, закон функционирования которых определен неполностью. В таких схемах некоторые комбинации сигналов на ее входы не подаются и являются запрещенными.

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

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

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


x1

0

0

0

0

1

1

x2

0

0

1

1

0

1

x3

0

1

0

1

1

0

f(x1, x2, x3)

1

0

0

0

1

1

определена только на шести наборах. Клетки, соответствующие наборам 1,0,0; 1,1,1 остаются пустыми.

Форма представления функции f(x1, x2, x3) существенно зависит от выбора ее значений на запрещенных наборах, Например, для заданной функции, выбирая ее запрещенные значения равными нулю, можно получить минимальную ДНФ в виде

Если значения функции на запрещенных наборах принять равными единице, то форма представления упрощается

.

Рассмотрим общую методику получения минимальных ДНФ неполностью определенных переключательных функций

Определение Пусть переключательная функция f(x1, x2, …, xn) не определена на p наборах аргументов. Тогда полностью определенную функцию (x1, x2, …, xn) будем называть эквивалентной функции f(x1, x2, …, xn), если ее значения совпадают со значениями функции f(x1, x2, …, xn) на тех наборах, на которых эта функция f определена.

Существует 2p вариантов выбора значений функции на запрещенных наборах и, следовательно, 2р различных переключательных функций, эквивалентных функции f(x1, x2, …, xn).

Поэтому задача минимизации неполностью определенной функции f(x1, x2, …, xn) сводится к отысканию такой эквивалентной функции (x1, x2, …, xn), которая имеет простейшую минимальную форму.

Введем эквивалентные функции 0(x1, x2, …, xn) и 1(x1, x2, …, xn), значения которых на всех запрещенных наборах функции f(x1, x2, …, xn) равны, соответственно, нулю и единице.

Теорема. Минимальная ДНФ неполностью определенной функции f(x1, x2, …, xn) совпадает с дизъюнкцией самых коротких импликант эквивалентной функции 1(x1, x2, …, xn), которые совместно поглощают все конституенты единицы функции 0(x1, x2, …, xn) и ни одна из которых не является лишней.

Для доказательства теоремы рассмотрим СДНФ некоторой эквива­лент­ной функции i(x1, x2, …, xn). Конституенты единицы, входящие в эту форму, обязательно войдут и в СДНФ функции 1(x1, x2, …, xn). Поэтому любая простая импликанта функции i(x1, x2, …, xn) будет совпадать с импликантой функции 1(x1, x2, …, xn) или будет поглощаться ею. Другими словами, среди импликант функции 1(x1, x2, …, xn) всегда найдется такая, которая поглощает любую импликанту любой эквивалентной функции i(x1, x2, …, xn). Следовательно, самыми короткими произведениями, накрывающими единицы функции f(x1, x2, …, xn), будут импликанты 1(x1, x2, …, xn).

Среди всех ПФ, эквивалентных заданной, функция 0(x1, x2, …, xn) имеет минимальное количество конституент единицы. Следовательно, и количество простых импликант [из набора импликант функции 1(x1, x2, …, xn)], необходимых для поглощения конституент функции 0(x1, x2, …, xn), будет минимальным. Если составить дизъюнкции наиболее коротких импликант функции 0(x1, x2, …, xn), которые совместно накрывают все конституенты единицы функции 0(x1, x2, …, xn), то получим, очевидно, минимальную форму представления функции f(x1, x2, …, xn).

Ввиду того, что для накрытия единиц функции 0(x1, x2, …, xn) выби­раются импликанты другой функции, дизъюнкция этих импликант не равняется функции 0(x1, x2, …, xn). Однако, такая дизъюнкция обязательно равна одной из функций, эквивалентных функции f(x1, x2, …, xn).

Пример. Найти минимальную дизъюнктивную нормальную форму ПФ, заданной таблицей.

x1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

x2

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

x3

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

x4

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

f(x1, x2, x3, x4)

1

0

1

0

0

1

0

0

1

1

Полагая, что пустые клетки заполнены нулями, найдем СДНФ экви­ва­лентной функции 0(x1, x2, x3, x4):

.

СНДФ функции 1(x1, x2, …, xn), полученная после заполнения пустых клеток таблицы единицами, будет

Выполнив операции склеивания и поглощения, получим сокращенную ДНФ функции 1 (x1, x2, x3, x4), в которую войдут все ее простые импликанты:

Составим импликантную матрицу, включив в нее конституенты единицы функции 0(x1, x2, x3, x4) и импликанты функции 1(x1, x2, x3, x4).

Импли-

канты

Конституенты

x1 x2 x3 x4

x1 x2

x

x

x

x

x

x

x

x

x

Импликанта x1x2 обязательно должна входить в мин ДНФ, т.к. только она поглощает конституенту x1x2x3x4. Импликанты x1x2 совместно накрывают все конституенты, кроме ; последняя может быть накрыта импликантами или . Поэтому минимальные ДНФ функции f(x1, x2, x3, x4) будут:

Пример. Найти минимальную ДНФ функции f(x1, x2, x3, x4), эквивалентая функция 0(x1, x2, x3, x4) которой имеет вид:

а комбинации являются запрещенными.

Эквивалентную функцию 1(x1, x2, …, xn) можно получить, добавив к СДНФ функции 1(x1, x2, …, xn) запрещенные комбинации переменных:

Проведя операции склеивания и поглощения, найдем простые импликанты функции 1(x1, x2, x3, x4); x1x2x3, x1x3x4, , . Импликантная матрица функции f(x1, x2, x3, x4) имеет вид.

Импли-

канты

Конституенты

x

x

х

х

х

x1x2x3

х

x1x3x4

Функция f(x1, x2, x3, x4) имеет единственную минимальную ДНФ

В нижней строке импликантной матрицы крестики отсутствуют и, следовательно, импликанта x1x3x4 не поглощает ни одну из конституент единицы функции 0(x1, x2, x3, x4). Это связано с тем, что данная импликанта образовалась в результате склеивания конституент функции 1(x1, x2, x3, x4), которые в функцию 0(x1, x2, x3, x4) не входят.

Чтобы найти простейшее представление неполностью определенной ПФ, кроме минимальных дизъюнктивных форм следует получить минимальные конъюнктивные нормальные формы и выбрать из них ту, которая содержит наименьшее число букв.

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

Пусть задана неполностью определенная функция f(x1, x2, …, xn). Тогда для получения минимальной КНФ достаточно найти сокращенную КНФ эквивалентной функции 0(x1, x2, …, xn), а функцию 1(x1, x2, …, xn) записать в СКНФ. Затем следует составить ипликантную матрицу, включив в нее все конституенты нуля функции 1(x1, x2, …, xn) и все члены сокращенной конъюнктивной нормальной формы функции 0(x1, x2, …, xn). По импликантной матрице рассмотренным выше способом можно получить минимальные КНФ функции f(x1, x2, …, xn).

Пример. Найти минимальную КНФ функции, записанной таблицей.

x1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

x2

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

x3

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

x4

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

f(x1, x2, x3, x4)

0

1

1

0

0

1

0

1

0

1

1

1

1

СКНФ эквивалентной функции 1(x1, x2, x3, x4):

СКНФ функции

Сокращенная КНФ функции 0(x1, x2, x3, x4)

Импликантная матрица имеет вид:

Импли-

канты

1

2

3

4

5

х

х

х

х

х

х

х

Минимальная КНФ функции f(x1, x2, x3, x4)

Рассмотренная функция имеет четыре минимальные ДНФ

Здесь больше букв, чем в МКНФ.

ЛИТЕРАТУРА

  1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).

  2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.

  3. Петрова В.Т. Лекции по алгебре и геометрии. Учебник для ВУЗов: в 2 ч.– М.: Гуманит. изд. центр ВЛАДОС.– ч. 1 – 312 с., ч. 2 – 344 с. ISBN 5-691-00077-2. ISBN 5-691-00238-4 (I), ISBN 5-691-00239-2 (II).

  4. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).

Похожие работы:

  • Комбинационные схемы

    Реферат >> Коммуникации и связь
    ... Переключательные функции 3. Не полностью определенные переключательные функции 4. Построение комбинационной логической схемы по заданной переключательной функции 5. Минимизация переключательных функций ... При минимизации неполностью определенных функций ...
  • Булевы функции

    Контрольная работа >> Математика
    ... функцию, определенную на всех своих наборах, называют полностью определенной. Булеву функцию n переменных называют неполностью определенной ... дизъюнктивной нормальной формой переключательной функции( СДНФ). Наборы, на которых функция f принимает значение 1, ...
  • Дискретная математика

    Учебное пособие >> Математика
    ... 3.8 Методы минимизации логических функций 34 Контрольные вопросы 39 3.9 Неполностью определенные логические функции 40 3.10 ... вентилей а) б) в) г) д) е) Рис. 7. Условные обозначения переключательных функций двух переменных: а – элемент Шеффера; б – элемент ...
  • Основы анализа и синтеза комбинационных логических устройств

    Учебное пособие >> Информатика, программирование
    ... 1.3. Представить в СКНФ переключательную функцию четырех аргументов f(x1, ... Минимизация логических функций с помощью карт Карно При минимизации логических функций ... входных сигналов описывается неполностью определенными логическими функциями, значения которых ...
  • Компьютерная схемотехника

    Книга >> Коммуникации и связь
    ... Определение и способы задания переключательных функций 3.2 Переключательные функции одной переменной (n=1) 3.3 Переключательные функции двух переменных (n=2) 3.4 Базисные логические функции ... минимизации ПФ. 3.2 Переключательные функции ... быть неполными ( ...
  • Лабораторный практикум

    Реферат >> Цифровые устройства
    ... индивидуальные задания; минимизацию функции выбранным методом; аналитические ... полностью описано системой переключательных функций. Особенностью логических ... Минимизировать следующие логические неполностью определенные функции и составить принципиальные схемы ...
  • Логическое и функциональное программирование

    Учебное пособие >> Информатика, программирование
    ... определений функций. Функции ... функциями. Иногда такие функции называют переключательными ... 0 1 0 1 1 0 1 1 1 1 0 СДНФ: СКНФ: Минимизация булевых функции Под минимизацией булевых функций понимается нахождение наиболее простого ... функции. Пример: Операцию неполного ...
  • Конструкция p-i-n диода

    Курсовая работа >> Коммуникации и связь
    ... Вn, которые являются сложными функциями параметров р - и n ... трансцендентное уравнение для определения t1: , ... до 8*10-5 см2 Для минимизации вклада в пр и ... пленке. Неполное обеднение этих ... . 7. Способы сборки быстродействующих переключательных р-i-n- диодов: а) в ...
  • Математическая логика

    Контрольная работа >> Математика
    ... функций) положена в основу точных методов анализа и синтеза в теории переключательных ... функции превращает систему ФАЛ в неполную ... 5. Минимизация булевых функций Импликантой функции называют некоторую логическую функцию, ... булеву функцию 1 этап. Определение ...
  • Информационные системы в экономике

    Реферат >> Экономика
    ... обеспечивает выбранный инструментарий; минимизация затрат на разработку ... 2.3. Программное обеспечение. 2.3.1. Определение параметров генерации и настройки ... грязный, рваный, неполный ком- плект ... ), либо обозначение функции переключательного типа. В техпроцессе ...