Методические указания к лабораторным занятиям для студентов специальности


НазваниеМетодические указания к лабораторным занятиям для студентов специальности
страница1/5
Дата публикации17.06.2014
Размер0.53 Mb.
ТипМетодические указания
referatdb.ru > Литература > Методические указания
  1   2   3   4   5
ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»
Кафедра «Автоматизированные системы управления»

ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания к лабораторным

занятиям для студентов специальности

23 01 02 «Автоматизированные системы

обработки информации и управления»





Могилев 2012

УДК 519.6

ББК 22.176

Д 48
Рекомендовано к опубликованию

учебно-методическим управлением

ГУ ВПО «Белорусско-Российский университет»
Одобрено кафедрой «Автоматизированные системы управления» «15» мая 2012 г., протокол № 9

Составитель канд. техн. наук, доц. А. И. Якимов
Рецензент канд. физ.-мат. наук, доц. Л. В. Плетнев

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

Учебное издание
^ ДИСКРЕТНАЯ МАТЕМАТИКА

Ответственный за выпуск С. К. Крутолевич

Технический редактор А. Т. Червинская

Компьютерная верстка И. А. Алексеюс
Подписано в печать . Формат 60х84/16. Бумага офсетная. Гарнитура Таймс.
Печать трафаретная. Усл.-печ. л. . Уч.-изд. л. . Тираж 31 экз. Заказ №
Издатель и полиграфическое исполнение

Государственное учреждение высшего профессионального образования

«Белорусско-Российский университет»

ЛИ № 02330/375 от 29.06.2004 г.

212000, г. Могилев, пр. Мира, 43
© ГУ ВПО «Белорусско-Российский

университет», 2012

1 Минимизация функций алгебры логики методом неопределенных коэффициентов, диаграмм Вейча (карт Карно) (лаб. раб. 09)
1.1 Задача минимизации булевых функций
Задачу поиска наиболее простой записи булевой функции называют задачей минимизации. Решение такой задачи основывается на понятии несущественности переменных. Переменная называется несущественной на паре наборов, если при изменении ее значения на противоположное булева функция сохраняет свое значение. Две конъюнкции, содержащие несущественную переменную, заменяются одной, в которой несущественная переменная отсутствует.

ДНФ булевой функции f(x1,…, xn) называют кратчайшей, если она содержит наименьшее число элементарных конъюнкций по сравнению с другими ДНФ этой же функции.

ДНФ булевой функции f(x1,…, xn) называют минимальной, если она имеет наименьшее число аргументов среди всех эквивалентных ей ДНФ.

Импликантой функции f(x1,…, xn) называется такая элементарная конъюнкция К над множеством переменных {x1,…, xn}, что К Ú f(x1,…, xn) = f(x1,…, xn). Импликанта называется простой, если при отбрасывании любого аргумента из К получается элементарная конъюнкция, не являющаяся импликантой функции f. Дизъюнкция всех простых импликант функции f называется сокращенной ДНФ функции f.

ДНФ булевой функции f(x1,…, xn) называют тупиковой, если отбрасывание любого слагаемого или аргумента приводит к неэквивалентной ДНФ.

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

Представим функцию f(x1, x2, x3) в виде следующей ДНФ:
(1)
Здесь представлены все возможные конъюнктивные члены, которые могут входить в дизъюнктивную форму представления f(x1, x2, x3). Коэффициенты k с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого дизъюнктивная форма была минимальной. Если теперь задавать все возможные наборы аргументов (x1, x2, x3) и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему из 23 уравнений для определения коэффициентов k:
(2)
Пусть таблично задана некоторая функция f(x1, x2, x3). Задание некоторой конкретной функции определяет значения правых частей системы (2): f(x1, x2, x3) = 0  1. Если функция f(x1, x2, x3) на соответствующем наборе переменных равна нулю, то все коэффициенты, входящие в уравнение, будут равны нулю. Это вытекает из того, что дизъюнкция равна нулю только тогда, когда все члены, входящие в нее, равны нулю.

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

Пример
.
Составим систему (2):

Из второго, третьего и четвертого уравнений в силу свойств дизъюнкции вытекает, что

После этого данная система имеет вид:

После этого получаем систему

Отсюда находим минимальную ДНФ для данной функции:

Описанный метод эффективен лишь для минимизации функций, число аргументов в которых не больше 5–6. Это связано с тем, что число уравнений равно .
1.3 Правила минимизации с использованием диаграмм Вейча (карт Карно)
В диаграммах Вейча (картах Карно) таблица истинности булевой функции представляется в виде координатной карты состояний, которая содержит 2n клеток (по числу входных наборов булевой функции n переменных). Переменные функции разбиваются на две группы так, что одна группа определяет координаты столбца карты, а другая – координаты строки.

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

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

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

2 Количество клеток внутри контура должно быть целой степенью двойки (1, 2, 4, 8, 16...).

3 При проведении контуров крайние строки карты (верхние и нижние, левые и правые), а также угловые клетки считаются соседними (для карт до 4-х переменных).

4 Каждый контур должен включать максимально возможное количество клеток. В этом случае он будет соответствовать простой импликанте.

5 Все единицы (нули) в карте (даже одиночные) должны быть охвачены контурами. Любая единица (нуль) может входить в контуры произвольное количество раз.

6 Множество контуров, покрывающих все 1 (0) функции, образуют тупиковую ДНФ (КНФ). Целью минимизации является нахождение минимальной из множества тупиковых форм.

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

Пример – Пусть функция f(x, y, z) = 1 на наборах 0, 1, 2, 3, 6, 7, 8, 15. Диаграмма Вейча для заданной функции представлена на рисунке 1.

Рисунок 1 – Минимальная ДНФ на диаграмме Вейча
Единицы функции, стоящие в соседних клетках, отличаются значением только одной переменной, следовательно, они склеиваются по этой переменной и образуют импликанту. В этом случае говорят, что импликанта покрывает соответствующие единицы булевой функции. Например, две единицы на наборах 7 и 15 покрываются импликантой yzt. Четыре единицы на наборах 2, 3, 7, 6 – импликантой . При этом соседними считаются также клетки, стоящие вдоль левого и правого края диаграммы (отличаются значением у) и вдоль верхнего и нижнего края (отличаются значением x).

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

Для функции, представленной на рисунке 1, минимальная ДНФ
.
Минимальная КНФ строится двойственно по диаграмме Вейча, заполненной нулями в пустых клетках. Для данной функции минимальная КНФ
.
1.4 Минимизация частично определенных булевых функций
Диаграммы Вейча могут использоваться для минимизации не только так называемых полностью определенных логических функций (когда функция в таблице истинности принимает только два значения – 0 или 1), но и для случая частичных (не полностью определенных) функций. При построении реальных цифровых устройств контроля и управления комбинационные схемы описываются, как правило, не полностью определенными булевыми функциями. В таблице истинности и, следовательно, в диаграммах Вейча такие функции кроме 0 и 1 будут содержать и «–»; это означает, что такой набор никогда на вход устройства не поступает. Следовательно, на месте «–» может быть произвольно поставлена 1 либо 0. Этот процесс называется доопределением булевой функции. Доопределение булевой функции желательно выполнять так, чтобы получить возможно более простое выражение. В этом случае реализованная комбинационная схема также оказывается более простой.
1.5 Практические задания
Найти минимальные ДНФ и КНФ булевых функций:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) ;

12) ;

13) ;

14) ;

15) ;

16) ;

17) ;

18) ;

19) ;

20) ;

21) ;

22) ;

23) ;

24) ;

25) .
2 Синтез и анализ логических схем (лаб. раб. 10)
2.1 Задача синтеза логической схемы
По заданной функции f требуется построить схему, реализующую данную функцию. Задача синтеза решается неоднозначно. Можно поставить в соответствие заданной функции f целое множество схем. Для построения логической схемы необходимо элементы, предназначенные для выполнения логических операций, указанных в логической функции, располагать в порядке, указанном в булевом выражении.

Пример – Построить логическую схему устройства, реализующего логическую функцию (рисунок 2).
2.2 Синтез логических устройств в заданном базисе
С целью уменьшения номенклатуры используемых микросхем часто пользуются функционально полной системой в составе двух логических элементов, выполняющих операции И-НЕ, ИЛИ-НЕ. Любую логическую функцию можно записать в заданном базисе логических элементов. Если задан базис И-НЕ, то путем двойного инвертирования исходного выражения или его части и применения теорем де Моргана логическая функция приводится к виду, содержащему только операции логического умножения и инвертирования. Если же задан базис ИЛИ-НЕ, исходную логическую функцию теми же приемами приводят к виду, содержащему только операции логического сложения и инверсии. Далее логическое выражение записывается через условные обозначения выбранных операций.

Рисунок 2 – Пример логической схемы устройства
  1   2   3   4   5

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

Методические указания по лабораторным занятиям и курсовому проектированию...
Составили: доцент С. З. Мастеров, ст преподаватель М. Е. Леоненко, ассистент С. В. Радченко
Методические указания к лабораторным занятиям дисциплины «Алгоритмы...
Приведите примеры символов Паскаля, которые являются словами в обычном понимании
Методические указания к лабораторным занятиям и кср при изучении специального курса
Альгология: метод указания к лабораторным занятиям и кср при изучении спецкурса / авт сост. А. К. Храмцов. – Минск : бгу, 2010. –...
Методические указания к лабораторным занятиям для студентов биологического...
Физиология микроорганизмов изучает жизнедеятельность микробных клеток, процессы их питания, дыхания, роста, размножения, закономерности...
И продовольствия республики беларусь департамент
Методические указания к лабораторным занятиям по ботанике для студентов агрономического и агроэкологического факультетов
Методические указания к лабораторным работам студентов по дисциплине:...
Методические указания к лабораторным работам рассматриваются как важнейший вид учебной работы, выполняемый в 2 семестре в процессе...
Методические рекомендации и указания к лабораторным занятиям по дисциплине...
«Ремонт технологических машин» для студентов специальности 050724 «Технологические машины и оборудование»
Методические указания к лабораторным работам по Геотехнике І для...
Методические указания к лабораторным работам по Геотехнике І для студентов специальности 050729 «Строительство» г. Алматы, Казгаса,...
Методические указания по предмету «Методика преподавания хорового...
Методические указания к практическим занятиям для студентов специальности «Музыкальное образование»
Методические указания ф со пгу 18. 2/05 к лабораторным работам
...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза