- •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-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
|
|
|
|
|
|
|
|
|
x1 |
V f(x1, x1,x2 , x3,...,xn)= x1Vf(1,0,x2 , x3,...,xn), |
(6.29) |
||||||
|
|
,x2 , x3,...,xn)= x1Vf(0,1,x2 , x3,...,xn). |
(6.30) |
|||||
x1V f(x1,x1 |
Из соотношений (6.27) и (6.29) следует, что в функции f все переменные х1 следует заменить на единицу, а х1 — на нуль. В соотношениях (6.28) и (6.30), наоборот, все переменные х1 нужно заменить на нуль, а переменные х1— на единицу. Рассмотрим примеры использования некоторых соотношений.
Пример 6.1. Упростить логическое выражение
Y= x 1 (х1х2 v х1х3 v х2х3).
Р е ш е н и е. Воспользовавшись соотношением (6.27), получим
Y=x 1 (x1х2 v х1х3 v х2х3) = x1 (1·х2 v 0·х3 v х2х3)=
= x 1 (х2 v х2х3)=x1 х2.
Пример 6.2. Упростить логическое выражение
Y= x 1 (х1х2 v х1х3 v х2х3).
Р е ш е н и е. Воспользовавшись соотношением (6.28), получим
Y= x 1 (x1х2 v х1х3 v х2х3)= x1 (0·х2 v 1·х3 v х2х3)= = x 1 (х3 v х2х3)=x1 х3.
6.4. Формы представления логических функций
На отдельных этапах анализа и синтеза комбинационных автоматов используютсяразличные формы ихпредставления (задания): словесная, табличная, аналитическая, числовая, геометрическая и кубическая. Задать логическую функциюзна- чит указать значения, которые принимает функция (т.е. 1, или 0, или неопределенное значение) при всех возможных комбинациях входных наборов.
80
6.4.1. Словесная форма представления логических функций
Любая логическая функция может быть представлена в виде словесного описания.
Пример 6.2. Функция f от двух переменных истинна тогда и только тогда, когда обе переменные одновременно ложны.
Пример 6.3. Функция g от трех переменных истинна только тогда, когда одновременно истинны не менее двух аргументов.
Функция g определена (задана) достаточно лаконично, но вместе с тем, не достаточно определенно. Для полной определенности данную функцию нужно было бы задать следующим образом: функция истинна тогда, когда одновременно истинны аргумент первый и второй, или когда истинны аргумент первый и третий, или когда истинны аргумент второй и третий, или когда истинны все три аргумента.
Таким образом, словесное описание логических функций усложняется по мере увеличения числа аргументов, что может приводить к неоднозначности задания функции. Однако и при небольшом числе аргументов словесное описание логической функции может выглядеть в форме, достаточно трудной для понимания. Рассмотрим в качестве примера следующую арабскую мудрость, которая выражает целесообразность общения между людьми.
Пример 6.3.
"Если не знает, и не знает, что он не знает, тот глуп - избегай его.
Если не знает, и знает, что он не знает, ученик - научи его.
Если знает, и не знает, что он знает, тот спит - разбуди его.
Если знает, и знает, что он знает, мудрец - учись у него."
81
Эта арабская мудрость может интерпретироваться как логическая функция двух аргументов (знает/не знает, знает/не знает), которая рекомендует не общаться только с глупцами.
Словесная форма задания логических функций наиболее часто используется на начальном этапе проектирования комбинационных автоматов.
6.4.2. Табличная форма представления логических функций
Логическую функцию можно представить в табличной форме (таблицей истинности или картой Карно). Принцип по-
строения таблиц истинности рассмотрен в п.6.3. В табл. 6.1 представлена в табличной форме логическая функция из приме-
ра 6.2.
Таблица6.1
Таблица истинности функции f
х2 |
х1 |
f |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
В табл. 6.2 задана в табличной форме логическая функция g от трех переменных из примера 6.3.
Таблица 6.2
Таблица истинности функции g
х2 |
х1 |
х0 |
g |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
82 |
|
Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу входных наборов логической функции, т.е. 2n. Каждая клетка карты соответствует одному входному набору. Клетки размечают так, чтобы наборы, которые соответствуют смежным минтермам (макстермам), располагались бы в соседних ячейках карты Карно. Координатами каждой клетки карты Карно являются комбинации переменных из всех возможных входных наборов логической функции.
Для двух переменных карта Карно представляет собой квадрат, разделенный на четыре ячейки, по одной на каждый входной набор. Строки карты связаны спеременной x1, столбцы
— с переменной х2. Следовательно, расположенная слева вверху ячейка соответствует входному набору (0,0) или минтерму
( x1 x2 ), а расположенная справа внизу ячейка — входному на-
бору (1 , 1 ) или макстерму(x1 v x2). Такого рода карта называется картой Карно на две переменные (рис. 6.2). Представление логической функции на карте Карно производится в соответствии, с таблицей истинности. Если функция F(x1, x2) = x1* x2=1 на входном наборе (0,0),то этот факт отражается на карте Карно записью в левую верхнюю ячейку единицы (рис. 6.2, а). Остальные ячейка остаются незаполненными. Карта Карно может заполняться нулями в те ячейки, на входных наборах которых функция равна нулю. На рис. 6.2, б приведен пример заполнения
картыКарно для функции f = x1 v x2, |
|
|
|
|
||||||||||
|
|
|
x2 |
|
|
|
x2 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
|
|
|
0 |
1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
0 |
1 |
|
|
|
|
|
|
x1 |
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
|
|
|
|
|
|
|
1 |
0 |
|
0 |
|
||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
f = |
|
|
|
=1 |
|
|
|
|
||||
|
|
x1 |
x2 |
|
|
|
f = x1 v x2 |
|||||||
|
|
а) |
|
|
|
|
|
|
|
|
|
б) |
Рис. 6.2. Изображение функции f на карте Карно
83
Карта Карно (табл. 6.1 и рис. 6.2), содержит все 2n возможных входных наборов и значения функции, соответствующие каждому из наборов.
В случае трех переменных карта Карно (рис. 6.3) содержит восемь ячеек, по одной для каждого входного набора, указанного внутри ячейки. Переменная x1связана с двумя строками карты, а переменные x2 и x3 — с четырьмя столбцами. Таким образом, любые две рядом расположенные ячейки являются соседними и их координаты отличаются только одной переменной. Кроме того, соседними являются ячейки, стоящие в первом и последнем столбцах карты.
Поскольку для четырех переменных существует 16 входных наборов, карта Карно разделена на 16 ячеек (рис. 6.4). Каждая ячейка пронумерована в соответствии с десятичным номером входного набора. Карта Карно обладает свойством цилиндричности: смежными являются минтермы, расположенные в двух крайних столбцах, и расположенные в двух крайних строках.
В случае пяти переменных целесообразно использовать две 16-ячеечные карты (рис. 2.4), а не одну 32 -ячеечную (рис. 2.5). Каждая из указанных на рис. 2.4 карт связана с одним из значений переменкойx5.
В случае шести переменных потребуется уже четыре 16ячеечные карты. Каждая карта должна быть связана с одной из четырех возможных комбинаций переменных х5 и x6 . Для логических функций с числом переменных n>6 карты Карно становятся громоздкими и неудобными для практического применения.
|
|
|
x2x3 |
|
|
|
|
|
|
|
|
|
|
00 |
01 |
11 |
10 |
x1 |
|
|
|
|
|
0 |
000 |
001 |
011 |
010 |
|
|
|
|
|
|
|
|
1 |
100 |
101 |
111 |
110 |
|
|
|
|
|
|
Рис. 6.3. Карта Карно для функции трех переменных
84
|
|
|
x3x4 |
|
|
|
|
|
|
|
|
|
|
00 |
01 |
11 |
10 |
|
|
|
|
|
|
|
00 |
0 |
1 |
3 |
2 |
|
|
|
|
|
|
x1x2 |
01 |
4 |
5 |
7 |
6 |
|
11 |
12 |
13 |
15 |
14 |
|
|
|
|
|
|
|
10 |
8 |
9 |
11 |
10 |
Рис. 6.4. Карта Карно для функции четырех переменных
|
|
|
|
x3x4 |
|
|
|
|
|
x3x4 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
00 |
01 |
11 |
10 |
|
|
00 |
01 |
11 |
10 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
00 |
0 |
3 |
|
7 |
5 |
|
00 |
0 |
2 |
|
6 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
01 |
9 |
11 |
|
15 |
13 |
|
01 |
8 |
10 |
|
14 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1x2 |
11 |
25 |
27 |
|
31 |
29 |
x1x2 |
11 |
24 |
26 |
|
30 |
28 |
|
10 |
17 |
19 |
|
23 |
21 |
|
10 |
16 |
18 |
|
22 |
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. а) б)
Рис. 6.5. Представление функции пяти переменных на двух 16ячеечных картах Карно а- при x5 ; б- при x5
Карты Карно наиболее эффективны не для первичного задания логических функций, а для упрощения (минимизации) аналитических выражений, задающих логические функции. Методы минимизации логических функций будут рассмотрены в отдельном разделе данного пособия.
85