- •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-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
конъюнкцией, то эта конъюнкция должна быть включена в полученную в результате минимизации сокращенную ДНФ.
7.2. Метод испытания импликант
После получения сокращенной ДНФ, к ней может быть многократно применен метод Квайна, в результате чего будет получена некоторая тупиковая форма, тождественная исходной ДНФ. Более часто применяют другой метод: метод испытания импликант в сокращенной ДНФ логической функции.
Существо метода состоит в следующем: из формулы, являющейся сокращенной ДНФ, выбирается испытуемая импликанта (можно произвольным образом). Выбранная импликанта приравнивается к 1. Далее определяются значения логических переменных, обращающих в 1 испытуемую импликанту. Из сокращенной ДНФ удаляется испытуемая импликанта, а в оставшуюся часть сокращенной ДНФ подставляются найденные значения логических переменных, обращающих в 1 испытуемую импликанту. Если в результате такой подстановки значение логической функции равно единичному значению, то испытуемая импликанта является лишней (избыточной) и может быть удалена из сокращенной ДНФ логической функции. После удаления лишней импликанты также испытываются все импликанты, входящие в сокращенную ДНФ.
Рассмотрим метод испытания импликант на примере. Пусть логическая функция F(a,b,c) , представлена в
виде сокращенной ДНФ, полученной по методу Квайна (7.3):
F Сокр. ДНФ (a,b,c) = |
|
|
|
|
|
|
|
|
|
|
|
|
(7.3) |
ab + ac +bc +bc + ac + ab |
Испытаем импликанты в (7.3). Первой будем испытывать импликанту ab .
Импликанта ab обращается в 1 при следующих значениях логических переменных:
98
1. ab =1, при a =0, b =0. Подставляя найденные значения в (7.3), предварительно исключив из формулы испытуемую импликанту, получим:
1 c +1 c +0 c +0 c +0 0 =1 импликанта ab является
лишней и должна быть удалена из формулы.
Таким же образом испытаем оставшиеся в формуле импликанты.
|
|
|
|
|
|
|
|
|
|
|
c =0. |
|
|
|
|
|
|
|
|
|
|
2. |
|
ac =1, при a =0, |
|
|
|
|
|
|
|
||||||||
|
b |
|
|
0 +b 1+ 0 0 + 0 b = b |
импликанта |
ac |
|
не является |
|||||||||||
лишней. Оставляем ее в формуле. |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
c =1. |
|
|
|
|
|
|
|
||
3. |
bc =1, при b =0, |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
0 + 0 0 +1 c + a 0 = c |
|
импликанта |
|
|
|
|
не является |
||||||||
|
|
a |
bc |
|
|||||||||||||||
лишней. Оставляем ее в формуле. |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
=1, при b =1, |
c =0. |
|
|
|
|
|
|
|
|||||
4. |
|
bc |
|
|
|
|
|
|
|
||||||||||
|
|
1+ 0 0 + a 0 + a 1 =1 |
|
импликанта |
|
|
|
|
|
|
|
||||||||
|
a |
|
|
|
|
bc |
является |
||||||||||||
лишней и должна быть удалена из формулы. |
|
|
|
|
|
|
|
||||||||||||
5. |
ac =1, при a =1, |
c =1. |
|
|
|
|
|
|
|
0 0 +b 1+1 b =1 импликанта ac является лишней и должна быть удалена из формулы.
6.ab =1, при a =1, b =1.
0 c + 0 c = 0 импликанта ab не является лишней.
Оставляем ее в формуле.
После испытания импликант получаем одну из тупиковых ДНФ логической функции F(a,b,c) :
F Тупиковая ДНФ (a,b,c) = |
|
|
|
|
|
|
|
ac +bc + ab |
(7.4) |
||||||
1 |
|
|
|
|
|
|
|
Если начать испытание импликант в (7.3) не с первой импликанты, а с какой-либо другой, выбранной произвольным образом, то можно получить некоторое количество тождественных сокращенных и тупиковых ДНФ, реализующих функ-
99