WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования “Оренбургский государственный университет” Кафедра вычислительной техники Т.З. АРАЛБАЕВ, И.В. ЖУКАЛИНА ТЕОРИЯ АВТОМАТОВ МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ДЛЯ СПЕЦИАЛЬНОСТИ 230101 “ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ, КОМПЛЕКСЫ, СИСТЕМЫ И СЕТИ” Рекомендовано к изданию Редакционно-издательским советом государственного образовательного учреждения высшего профессионального образования “Оренбургского государственного университета” Оренбург 2009 УДК 004.3(076.8) ББК 32/815я73 А 79 Рецензент:

доктор технических наук, профессор А.М. Пищухин Аралбаев, Т.З А 79 Теория автоматов: методические указания к практическим занятиям для специальности 230101 / Т.З. Аралбаев, И.В. Жукалина.

- Оренбург: ГОУ ОГУ, 2009. – 42 с.

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

методы минимизации Квайна и Мак-Класски, с помощью карт Карно; формы задания конечных автоматов; синтез комбинационных схем в базисе “И-НЕ” (“ИЛИ-НЕ”) на логических элементах серии К155 и К561.

Методические указания предназначены для организации практических занятий по курсу “Теория автоматов” для студентов 2-го курса по специальности 230101 “Вычислительные машины, комплексы, системы и сети”.

ББК 32.815я73 © Аралбаев Т.З., 2009 © Жукалина И.В., 2009 © ГОУ ОГУ, 2009 2 Содержание Введение......................................................................................................................4 1. Практическое занятие №1.

Способы представления логических функций……………………………….… 5 1.1 Табличная форма представления ЛФ ………………………………………….5 1.2 Аналитическая форма представления ЛФ …………………………………….8 2. Практическое занятие №2.

Алгебраическое преобразования формул логических функций………….…..2.1 Законы булевой алгебры………………………………………………………2.2 Аксиомы и теоремы булевой алгебры………………………………………..3. Практическое занятие №3.

Метод минимизации Квайна и Мак-Класски………….……………………….3.1 Нахождение всех простых импликант………………………………………...3.2 Построение таблицы покрытий матрицы Квайна……………………………3.3 Поиск минимального покрытия функции…………………………………….3.4 Получение минимальной формы ЛФ…………………………………………4. Практическое занятие №4.

Минимизация логических функций по картам Карно ………………………..4.1 Построение минимальных ДНФ ……………………………………………...4.2 Построение минимальных КНФ ……………………………………………...4.3 Минимизация не полностью определенных ЛФ……………………………..5. Практическое занятие № Формы задания конечных автоматов…………………………………….……..6. Практическое занятие № Синтез комбинационных схем в базисе «И-НЕ» («ИЛИ-НЕ»)……….………7. Практическое занятие №7.

Синтез комбинационных схем в базисе логических элементов серии К155 и К561………………………………………………………………………….……Список использованных источников......................................................................Приложение………………………………………………………………………... Введение Настоящие методические указания содержат материал для проведения практических занятий по одному из основных разделов дисциплины “Теория автоматов” – “Логические основы цифровых автоматов”.

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

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

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

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

1. Практическое занятие №1. Формы представления логических функций Существует несколько форм представления логических функций (ЛФ), используемых на различных этапах проектирования комбинационных схем, в частности: словесная, табличная, аналитическая, геометрическая, кубическая.

Целью практического занятия является изучение табличной и аналитической форм представления ЛФ и алгоритмов перехода от табличного описания ЛФ к аналитическому описанию.

1.1 Табличная форма представления ЛФ Логическая функция наиболее наглядно представляется посредством таблицы истинности (ТИ) и карты Карно.

Таблица истинности - это таблица, в которой каждому двоичному набору значений аргументов xi (i = 1, n) ставится в соответствие значение функции Y = f (x1, x2,..., xi,..., xn ) на данном наборе. В таблице 1.1 в качестве примера представлена ТИ функции для трех аргументов. Функция Y принимает значение или 0 на каждом наборе. Если значение функции не определено, то в соответствующей позиции ТИ ставится прочерк.

Таблица 1.1 – Таблица истинности логической функции N x1 x2 x3 Y 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 Иногда используют списочную форму представления ТИ, в которой приводится список единичных и нулевых наборов. Так, рассматриваемая в примере функция в списочной форме может быть представлена в виде:

Y F (x1, x2, x3) (0, 1, 3, 6, 7) Y (2, 4, 5) В скобках, приведены десятичные эквиваленты двоичных кодов наборов.

Карта Карно представляет собой прямоугольную таблицу, содержащую 2n клеток, причем каждая клетка находится на пересечении i - ой строки и j - ого столбца, ai и аj являются составными элементами двоичного набора n – местной ЛФ.



Карта Карно имеет следующие особенности:

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

2) в клетках карты Карно указываются значения функции на соответствующем наборе;

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

На рисунке 1.1 представлены два варианта карт Карно для трех переменных, соответствующие таблице истинности 1.1.

Вариант 1 Вариант Рисунок 1.1 – Варианты карт Карно для трех переменных Во втором варианте для удобства построения и использования карты строки и столбцы, соответствующие единичным значениям переменных хj, отмечаются чертой, т.е. если столбец или строка отмечена чертой, то значение хj в этой строке или столбце равно 1, в противном случае - 0.

На рисунке 1.2 представлены два варианта карт Карно для двух (а), четырех (б) и пяти (в) переменных:

Вариант 1 Вариант а) Вариант 1 Вариант б) Вариант Вариант в) Рисунок 1.2 - Варианты карт Карно а) для двух переменных, б) четырех переменных, в) пяти переменных В случае шести переменных обычно используют четыре 16 - клеточные карты Карно. Для ЛФ с числом переменных n > 6 карты Карно становятся громоздкими и неудобными для практического применения.

1.2 Аналитическая форма представления ЛФ Аналитической формой представления ЛВ является формульное описание ЛФ, содержащее обозначение переменных, знаков операций и разделительных скобок. К основным операциям, используемым в формулах, относятся отрицание, конъюнкция и дизъюнкция. Причем, если в аналитическом выражении отсутствуют скобки, старшинство операций определяется следующим образом:

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

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

Составным элементом перечисленных форм являются элементарные конъюнкции (ЭК) и элементарные дизъюнкции (ЭД).

Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) переменных, каждая из которых входит в нее один раз в прямом или инверсном виде.

Число переменных, составляющих ЭК или ЭД, называют ее рангом.

x1 x2 x3 x4 - четвертого ранга.

Например, x1 x2 x3 - ЭК третьего ранга;

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

Например:

Y x1 x2 x3 x4 xВ теории автоматов часто используют следующие виды ДНФ:

1) совершенную ДНФ (СДНФ);

2) сокращенную ДНФ (СкДНФ);

3) тупиковую ДНФ (ТДНФ);

4) минимальную ДНФ (МДНФ).

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

Например:

Y x1x2x3 x1x2x3 x1 x2x3 x1 x2 xСкДНФ - это ДНФ в виде дизъюнкции всех ее простых импликант.

Импликантой ЛФ Y f (x1, x2,....xn ) называется функция Y f (x1, x2,....xn ), которая обращается в 1 на некотором подмножестве единичных наборов функции Y.

Например, импликантами являются ЭК в ДНФ функции.

Y f (x1, x2,....xn ) Простой импликантой функции называется импликанта, которая не поглощается никакой другой импликантой данной функции Y.

Например, функция Y1 x1 x2 x3 является имликантой функции Y x1x3 x1 x2 x3, а функция Y2 x1x3 является простой импликантой функции Y.

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

МДНФ - это ТДНФ, содержащая минимальное число букв среди возможных ТДНФ функции.

КНФ - это регулярное аналитическое выражение ЛФ в виде (произведения) элементарных дизъюнкций.

Например:

Y x1(x2 x3 x4) (x2 x4) СДНФ n-местной ЛФ является ДНФ, содержащая ЭК только ранга n.

CKНФ n-местной ЛФ является КНФ, содержащая ЭД только ранга n.

Каждой ЛФ соответствует одна СДНФ и одна СКНФ.

В общем случае СДНФ можно представить в следующем виде:

~ ~ ~ ~ F(x1, x2,..., xi,..., xn ) (x1, x2,...., xi,...., xn ); г де ~ xi, если xi xi, если xi xi x1 x2x3 xНапример, двоичному набору 1010 соответствует ЭК.

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

В общем случае СКНФ можно представить в форме:

~ ~ ~ ~ F(x1, x2,..., xi,..., xn ) (x1, x2,...., xi,...., xn ); где ~ xi, если xi xi, если xi xi Например, двоичному набору 1010 соответствует ЭД: x1 x2 x3 x4.

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

1) выбрать в ТИ такие входные наборы, на которых функция обращается в единицу;





2) записать конституенты единицы для выбранных входных наборов;

3) полученные конституенты единиц соединить между собой знаками дизъюнкции.

Например, для логической функции, представленной в таблице истинности 1.1, СДНФ имеет следующий вид:

Y x1 x2 x3 x1 x2x3 x1x2x3 x1x2 x3 x1x2xАлгоритм перехода от табличного задания логической функции к ее записи в виде СКНФ имеет следующий вид:

1) выбрать в ТИ такие входные наборы, на которых функция имеет нулевые значения;

2) записать конституенты нуля для выбранных входных наборов;

3) полученные конституенты соединить между собой знаками конъюнкции.

Например, для логической функции, представленной в таблице истинности 1.1, СКНФ имеет следующий вид:

Y x1 x2x3 x1x2x3 x1x2 xКонтрольные вопросы 1 Для чего нужны таблицы истинности и карта Карно 2 Как составляется таблица истинности 3 Как заполняется карта Карно 4 Дать определение элементарной конъюнкции, элементарной СДНФ, СКНФ.

5 Как построить СДНФ, СКНФ Упражнение №Построить таблицу истинности, карту Карно, СДНФ и СКНФ для следующих вариантов ЛФ, заданной списком единичных наборов:

1. (0, 2, 4, 6, 8, 10, 12, 14) 2. (1, 3, 5, 7, 9, 11, 13, 15) 3. (0, 1, 4, 5, 8, 9, 12, 13) 4. (1, 2, 5, 6, 9, 10, 13, 14) 5. (1, 5, 7, 9, 10, 12, 14) 6. (0, 2, 5, 8, 10, 13, 14, 15) 7. (1, 6, 8, 9, 10, 13,14, 15) 8. (0, 2, 3, 5, 8, 9, 11, 13, 15) 9. (0, 3, 5, 6, 8, 9, 10, 12) 10. (1, 4, 5, 7, 9, 13, 14, 15) 11. (3, 5, 6, 8, 9, 13, 14, 15) 12. (1, 2, 3, 4, 5, 11, 12, 13) 13. (0, 1, 2, 5, 6, 7, 12, 13, 14) 14. (6, 7, 8, 11, 12, 13, 15) 15. (0, 4, 8, 12, 13, 14, 15) 2. Практическое занятие №2. Алгебраическое преобразование формул логических функций Преобразование формул ЛФ производят, как правило, для достижения следующих целей:

1) для получения более простого аналитического выражения, описывающего комбинационную схему (КС), вследствие чего синтезируемая КС также имеет меньшую конструктивную сложность;

2) для преобразования формулы ЛФ к регулярному виду, используемому для регуляризации и сравнения КС;

3) для получения СДНФ и СКНФ ЛФ.

Целью практического занятия является изучение способов преобразования формул ЛФ.

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

2.1 Законы булевой алгебры 1 Закон коммутативности:

a b b a;

a b b a 2 Закон ассоциативности:

a (b c) (a b) c;

a (b c) (a b) c 3 Закон дистрибутивности (распределительный закон):

a (b c) a b b c;

a (b c) (a b) (a c) 2.2 Аксиомы и теоремы булевой алгебры 1 a 1, если a 0 ; a 0, если a 1;

2 0 0 0; 11 1;

3 11 1; 0 0 0;

4 1 0 0; 0 1 1;

5 0 1; 1 0;

6 a 0 a; a 1 a ;

7 a 1 1; a 0 0;

8 a a a ; a a a;

9 (a) a; (a) a;

10 a a 1; a a 0 ;

11 a b c a b c ; a b c a b c Для преобразования ЛФ используют следующие правила.

1). Правило склеивания для соседних элементарных конъюнкций (СЭК).

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

Например:

x1x2 x3 x1 x2 x и Правило склеивания является следствием распределительного закона и имеет следующий вид:

логическую сумму двух соседних ЭК ранга r можно заметить одной элементарной конъюнкцией ранга (r–1).

Например:

x1x2 x1x2 x2 x1 x2 x3 x1 x2x3 x1 x и 2). Правило склеивания для соседних элементарных дизъюнкций (СЭД).

СЭД – это две элементарные дизъюнкции одного и того же ранга, являющиеся функциями одних и тех же переменных.

Например:

x1 x2 x3 x1 x2 x и.

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

Например:

(x1 x2 x3 x4) (x1 x2 x3 x4) x2 x3 x.

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

Например:

(x1 x2 x3 x4 ) (x1 x4 ) x1 x4.

Это правило является следствием закона дистрибутивности.

Примеры алгебраического преобразования формул логических функций:

а) упрощение формулы ЛФ Y x1x2 x3 x1 x2 x3 x1 x2 x3 x1x2 x3 (x1x2 x3 x1x2 x3) (x1 x2 x3 x1 x2 x3) x2 x3 x2 x3 x б) преобразование формулы ЛФ к регулярному виду Y x1x2x3 x4 x1 x2x3 x4 x1x2x3 x4 x1x2x3 x4 (x1 x2x3 x4 x1x2x3 x4) x1x2x3 x4 x1 x2x3 x4 x1x2x3 x4 x1x2x3 x4 (x1 x2 x3 x4) (x1 x2 x3 x4) x1 x2x3 x4 x1 x2x3 x4 x1 x2x3 xв) преобразование ДНФ ЛФ в СДНФ Y f (x1, x2, x3) x1 x2 x3 x1 (x2 x2 ) (x3 x3) x2 x3 (x1 x1) x1 x2 x3 x1 x2 x x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 xг) преобразование КНФ ЛФ в СКНФ Y f (x1, x2, x3) x1(x2 x3) (x1 x2 x2 x3 x3) (x2 x3 x1 x1) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) Контрольные вопросы 1 Сформулировать законы и аксиомы булевой алгебры.

2 Сформулировать и доказать теоремы булевой алгебры.

3 Объяснить способы преобразования ДНФ в СДНФ и СКНФ.

Упражнение № 1 Упростить СДНФ и СКНФ ЛФ, приведенные в упражнении № 1.

2 Упростить СДНФ и СКНФ инверсных функций на примерах упражнения № 1.

3. Практическое занятие №3. Метод минимизации Квайна и Мак-Класски Метод получения тупиковых дизъюнктивных нормальных форм ЛФ, разработанный Квайном и усовершенствованный Мак-Класски, включает четыре основных этапа:

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.