- •1. СТАНОВЛЕНИЕ ТЕОРИИ АВТОМАТОВ
- •1.1. Взаимосвязь теории автоматов и других
- •1.2. Подходы к определению конечного автомата
- •1.3. Сущность метода "черного ящика"
- •1.4. Основные задачи теории автоматов
- •2. ФОРМАЛЬНАЯ КЛАССИФИКАЦИЯ АБСТРАКТНЫХ АВТОМАТОВ И ИХ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
- •2.1. Словесные определения автоматов
- •2.2. Формальное определение абстрактного автомата
- •2.3. Формальная классификация автоматов
- •2.4. Математические модели автоматов
- •2.4.1. Модель Мили
- •2.4.2. Модель Мура
- •2.4.3. Модель совмещенного автомата (С-автомата)
- •2.4.4. Модель микропрограммного автомата
- •3. СТРУКТУРНЫЕ МОДЕЛИ ПЕРВОГО УРОВНЯ АБСТРАКТНЫХ АВТОМАТОВ
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3. Структурная модель С-автомата
- •3.4. Структурная модель микропрограммного автомата
- •4. СПОСОБЫ ЗАДАНИЯ АБСТРАКТНЫХ И СТРУКТУРНЫХ АВТОМАТОВ
- •4.1. Начальные языки
- •4.1.1. Язык регулярных выражений алгебры событий
- •4.1.2. Язык логических схем
- •4.1.3. Язык граф – схем алгоритмов
- •4.2. Автоматные языки
- •4.2.1. Таблицы переходов и выходов
- •4.2.2. Матрицы переходов и выходов
- •4.2.3. Граф автомата
- •4.3.2. Язык временных диаграмм
- •5. Минимизация абстрактных автоматов
- •6. МАТЕМАТИЧЕСКИЕ ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
- •6.1. Формальное определение алгебры логики
- •6.2. Аксиомы, теоремы и законы алгебры логики
- •6.2.1. Аксиомы алгебры логики
- •6.2.2. Теоремы алгебры логики
- •6.2.3. Законы алгебры логики
- •6.3. Основные понятия и определения
- •6.4. Формы представления логических функций
- •6.4.1. Словесная форма представления логических функций
- •6.4.2. Табличная форма представления логических функций
- •6.4.3. Аналитическая форма представления логических функций
- •7. Минимизация логических функций
- •7.1. Методы минимизации логических функций на основе прямых аналитических преобразований СДНФ
- •7.2. Метод испытания импликант
- •7.3. Визуальные методы минимизации логических функций
- •7.3.2. Метод минимизации частично определенных логических функций с помощью карт Карно
- •7.4. Машинно-ориентированные методы минимизации логических функций
- •7.5. Групповая минимизация системы логических функций
- •8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ
- •9. ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ
- •9.1. Программируемые логические матрицы
- •10. КОНЕЧНЫЕ ФУНКЦИОНАЛЬНЫЕ ПРЕОБРАЗОВАТЕЛИ
- •11. СИНТЕЗ И АНАЛИЗ ТИПОВЫХ КОМБИНАЦИОННЫХ АВТОМАТОВ
- •11.1. Шифратор (coder) и его синтез
- •11.2. Дешифратор и его синтез
- •11.3. Мультиплексор и его синтез
- •11.4. Синтез демультиплексора (распределителя)
- •12. Элементарные автоматы с памятью и их синтез
- •12.1. Понятие функционально полной системы элементарных автоматов
- •12.2. Разновидности триггеров
- •12.3. Обобщённая характеристика триггеров
- •12.4. Синтез однотактного асинхронного RS-триггера
- •12.4.1. Синхронный однотактный RS-триггер
- •12.5. Синхронный однотактный D-триггер
- •12.6.1. Принцип построения двухтактного триггера
- •12.6.2. Однотактный Т-триггер
- •12.6.3. Двухтактные Т-триггеры
- •12.7. Двухтактный JK-триггер
- •12.8. Двухтактные RS-триггеры и D-триггеры
- •Рис. 12.28. Синхронный двухтактный RS-триггер
- •Рис. 12.30. УГО синхронного двухтактного RS-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
циюF(a,b,c) . В частности, если начать испытание импликант
с последней импликанты в (7.3), то полученная тупиковая ДНФ для логической функции F(a,b,c) будет иметь вид:
F Тупиковая ДНФ (a,b,c) = |
|
|
|
|
|
|
|
ab |
+bc |
+ ac |
(7.5) |
||||
2 |
|
|
|
|
|
|
|
7.3. Визуальные методы минимизации логических функций
Данные методы основаны на графическом представлении логических функций и способности человека быстро зрительно отыскивать некоторые геометрические фигуры. Одним из таких способов является метод импликантных матриц.
Импликантная матрица – это таблица, столбцы которой содержат элементарные конъюнкции (минтермы) СДНФ логической функции, а строки – найденные по методу Квайна импликанты.
Проиллюстрируем данный метод на примере рассматриваемой нами ранее логической функцииF(a,b,c) , СДНФ ко-
торой определяется соотношением (7.1):
F СДНФ (a,b,c) = abc + abc + abc + abc + abc + abc
Составим для этой функции импликантную матрицу (табл.7.3), в которой Ki - элементарные конъюнкции из (7.1),
а U j - импликанты из выражения (7.3).
Таблица 7.3
|
|
|
|
|
|
Ki |
abc |
abc |
abc |
abc |
abc |
abc |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
U j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
Χ |
|
Χ |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
ab |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
Χ |
|
|
|
|
|
|
Χ |
|
|
|
|
|
|
|
|||||||||
ac |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Χ |
|
|
|
|
|
Χ |
|
|
|
|
||||||||
|
|
bc |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Χ |
|
|
|
Χ |
|
||||||||||
|
bc |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
ac |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Χ |
|
|
|
Χ |
||||||||
|
ab |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Χ |
Χ |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
100 |
|
|
|
|
|
|
|
|
В импликантной матрице ставим “ Χ” на пересечении тех строк и столбцов матрицы, в которых импликанта может поглотить конъюнкцию. Для получения тупиковой ДНФ необходимо выбрать минимальное число таких импликант U j , ко-
торые в совокупности поглотили бы все элементарные конъюнкции Ki . В результате этих действий получим две тупиковые формы логической функции F(a,b,c) .
F Тупиковая ДНФ (a,b,c) = |
|
|
|
|
|
|
|
|
|
|
|
|||
ac |
+ |
bc + ab |
(7.6) |
|||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F Тупиковая ДНФ (a,b,c) = |
|
|
|
|
|
|
(7.7) |
|||||||
ab +bc + ac |
||||||||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7.3.1. Метод |
минимизации полностью |
определенных |
логических функций с помощью карт Карно
Метод минимизации логических функций с помощью карт Карно заключается в следующем: на карту Карно наносятся единичные и нулевые значения логических функций. Для получения ДНФ логической функции рассматриваются единичные значения функции, а для получения КНФ – нулевые.
Пусть с помощью карты Карно задана логическая функция f (x1,..., xn ) , необходимо найти ее тупиковую ДНФ. Тогда задача минимизации решается следующим образом: среди единичных значений логической функции f (x1,..., xn ),
предварительно нанесенных на карту Карно, отыскиваются
прямоугольники (и/или квадраты) с числом клеток 2k , где k = (n-1),…,0. Задача минимизации состоит в том, чтобы все единичные значения логической функции покрыть минимальным количеством прямоугольников максимальной площади,
величина которых равна 2k . Для формирования тупиковых ДНФ в каждом прямоугольнике находится соответствующая импликанта, которая является одинаковой для всех объеди-
101
ненных клеток карты Карно. Найденные из каждого прямоугольника импликанты соединяются знаком дизъюнкции.
Если необходимо найти тупиковую КНФ логической функции f (x1,..., xn ), то задача минимизации решается сле-
дующим образом: среди нулевых значений логической функции f (x1,..., xn ) , предварительно нанесенных на карту Карно,
отыскиваются прямоугольники (квадраты) с числом клеток 2k , где k=(n-1),…,0. Задача минимизации состоит в том, чтобы все нулевые значения логической функции покрыть минимальным количеством прямоугольников максимальной пло-
щади, величина которых равна2k . Для формирования тупиковых КНФ в каждом прямоугольнике находят элементарные дизъюнкции логических переменных, которые являются общими для всех выделенных клеток карты Карно. Найденные из каждого прямоугольника дизъюнкции соединяются знаком конъюнкции.
При применении метода минимизации логических функций с помощью карт Карно необходимо помнить о том, что карты Карно обладают свойством цилиндричности, т.е. клетки, расположенные по краям карт Карно являются соседними в каждом столбце и каждой строке.
Минимизируем с помощью данного метода логическую функциюF(a,b,c) , СДНФ которой определяется соотношени-
ем (7.1):
F СДНФ (a,b,c) = abc + abc + abc + abc + abc + abc
Построим для функции F(a,b,c) карту Карно (рис. 7.1).
ab |
|
|
|
|
c |
00 |
01 |
11 |
10 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
Рис. 7.1. Карта Карно функцииF (a,b,c)
102
Определим максимальный размер прямоугольника, которым можно покрыть клетки карты. Величина прямоугольников вычисляется как 2k , где k=(n-1),(n-2),…,0, а n – число аргументов, от которых зависит логическая функция. В нашем случае n=3, следовательно максимальный размер прямоугольника равен 23−1 =22 =4. В карте Карно нет прямоугольника (или квадрата), состоящего из четырех единиц, стоящих рядом, поэтому объединять клетки карты можно только по две, например так, как показано на рис. 7.2.
Минтермы функции образуют в карте три группы. Одна группа состоит из двух минтермов abc и abc . Общей у них
является импликанта ab , так как в соответствии с теоремами алгебры логики имеем:
abc + abc = ab(c + c) = ab ,
то есть переменная c из этой группы может быть исключена
[23].
Вторая группа состоит из двух минтермов abc и abc , следовательно
abc + abc = bc , то есть переменная a из этой группы может быть исключена.
Третья группа состоит из двух минтермов abc и abc , следовательно
|
|
|
|
||||
abc + abc = ac , то есть переменная |
b из этой группы мо- |
||||||
жет быть исключена. |
|
|
|
|
|
||
|
|
ab |
|
|
|
|
|
|
|
c |
00 |
01 |
11 |
10 |
|
0 |
1 |
1 |
1 |
0 |
|
||
1 |
1 |
0 |
1 |
1 |
|
Рис. 7.2. Карта Карно функцииF (a,b,c)
103