Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
проводивший испытание (осмотр) Осмотр Статическое испытание Динамическое испытание Ф....полностью>>
'Документ'
1. Дмитриеву Л.Г., члена избирательной комиссии, о порядке проведения выборов (открытое или тайное голосование). Есть предложение проголосовать за фор...полностью>>
'Документ'
6.Классные часы, приуроченные к празднованию 70-й годовщины начала контрнаступления советских войск против немецко-фашистских войск в битве под Москво...полностью>>
'Документ'
Главным на данном этапе является формирование эффективной группы (2, в исключительных случаях 3 человека), распределение ролей и окончательное уточнен...полностью>>

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

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Оглавление

Предисловие 4

Введение 5

Глава1. Минимизация функций алгебры логики в классе ДНФ 7

  1. Геометрический метод 8

  2. Метод неопределенных коэффициентов 10

  3. Метод минимизирующих карт (Гарвардский метод) 13

  4. Метод Квайна 16

  5. Метод Квайна-Мак-Класки 23

  6. Метод карт Карно (Вейча) 25

  7. Абсолютно минимальные представления 31

Глава 2. Преобразования и минимизация в базисе, 32

состоящем из функции Вебба или из функции Шеффера.

Список литературы 42

Приложение 44

Задачи к практическим занятиям, выполнению

расчетно-графических работ и для самостоятельного

изучения методов минимизации ФАЛ.

ПРЕДИСЛОВИЕ

В алгебре логики, изучаемой в дисциплине “Дискретная математика”, задачу минимизации формул, описывающих функцию алгебры логики (ФАЛ), обычно называют задачей минимизации ФАЛ (или булевых функций).

В пособии излагаются принципы построения наиболее простых и распространенных методов минимизации, дополненные подробным разбором решений типовых примеров.

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

Появление новых технологий в создании и расширении элементной базы цифровых автоматов (дискретных преобразователей) вызывает интерес к рассмотрению методов минимизации и в других базисах (помимо классических): в частности – функций Шеффера, Вебба (Пирса).

Практикум включает материалы по методам минимизации, достаточные для решения задач на практических занятиях, в виде домашних заданий, на зачетах, экзаменах и особенно полезные при самостоятельном изучении курса “Дискретная математика”.

ВВЕДЕНИЕ

Функции алгебры логики (ФАЛ) называются также булевыми (логическими) функциями, двоичными функциями или переключательными функциями.

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

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

В настоящее время наибольшее распространение получил базис, состоящий из отрицания, конъюнкции и дизъюнкции {-,&}. Образующие его функции наиболее просты с точки зрения математических преобразований и технической реализации.

Минимизация булевых функций проводится обычно в классе ДНФ, но возможна и в других базисах. Алгоритм минимизации в классе ДНФ использует два закона:

1) закон склеивания (или , где - произвольная булева функция, - отдельный знак);

2) закон поглощения (или , где - любая булева функция, - отдельный знак).

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

Заметим, что речь идет о минимальном числе букв, а не переменных. Например, содержит 7 букв, но 3 переменных.

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

Введем некоторые необходимые понятия.

Рассмотрим функцию . Каждое из слагаемых соответствует только одной единицы в таблице истинности данной функции. Говорят, что каждое слагаемое покрывает единицу функции, а в совокупности они покрывают данную функцию, т.е. являются ее покрытием. Но заметим, что упростив функцию , получим более простое покрытие. Оба представления соответствуют одной и той же таблице истинности функции, т.е. обращаются в 1 и 0 на одних и тех же наборах переменных (табл. 2.1). Если обратиться к отдельным слагаемым 2-го представления, нетрудно заметить, что обращается в единицу на двух наборах (1, 0), (1, 1), а - на (0, 0), (1, 0), совместно они покрывают единицами все единицы данной функции. Отметим, что оба слагаемых и обращаются одновременно в нуль на наборе (0, 1), т.е. там, где функция равна нулю.

Таблица 2.1

0

0

1

1

1

0

0

1

1

0

1

1

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

0

1

1

1

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

Функция , являющаяся элементарным произведением и входящая в функцию , называется импликантой.

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

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

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

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

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

Приведем схему упрощения формы булевой функции

Таблица истинности


СДНФ


Сокращенная ДНФ


Тупиковая ДНФ


Минимальные ДНФ (МДНФ)

Кратчайшие ДНФ (КрДНФ)


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

ГЛАВА 1. МИНИМИЗАЦИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ В КЛАССЕ ДНФ1.

Из известных методов минимизации булевых функций в данной главе рассматриваются наиболее простые и распространенные в базисе {-,&}.

I Геометрический метод.

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

Изобразим область определения произвольной булевой функции трех переменных – это вершины трехмерного куба. Элементам куба можно поставить во взаимо-однозначное соответствие конъюнкции различного ранга: вершинам куба – конъюнкции третьего ранга, ребрам – второго, граням – первого. Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности. Конъюнкции большего ранга покрываются конъюнкциями меньшего ранга (см. рисунок 2-1).

Т

ак, например, конъюнкции и покрываются конъюнкцией (две вершины- ребро);конъюнкции , , , покрываются либо двумя конъюнкциями и , либои

л

ибо только (четыре вершины –либо два ребра, либо одна грань).

Б

рис. 2-1

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

Для функций и на приведенных рисунках 2-2 минимальными формами будут , или Для второй функции задача решается неоднозначно.











Рис. 2-2


Пример 1: Минимизировать функцию, заданную следующей таблицей истинности

Таблица 2-2

x1

0

0

0

0

1

1

1

1

x2

0

0

1

1

0

0

1

1

x3

0

1

0

1

0

1

0

1

f(x1, x2, x3)

1

0

1

1

0

0

1

1

Ее формула в СДНФ имеет вид:

x3

Отметим на рис. 2-3 вершины, соответствующие конъюнкциям, входящим в СДНФ данной функции.

З

Рис. 2-3

x2

x1

x2

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






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

  1. Учебно-методический комплекс по дисциплин е по направлению 230700. 62 “Прикладная информатика” (аннотация, информационная справка, темы самостоятепльных и контрольных работ,

    Учебно-методический комплекс
    ... учебных занятий (семинарских, практических) 01 ... работ, перечень примерных контрольных вопросов и заданий для самостоятельной работы ... Расчетно-графические работы по информатике : (теорет. и метод. вопр.) : учеб.-метод. пособие : утв. Эксперт.-метод ...
  2. Spacer type=block align=left (2)

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

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

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