- •Воронежский государственный технический университет
- •(Часть 1) Учебное пособие
- •Глава 1. Становление теории автоматов и ее основные задачи
- •Взаимосвязь теории автоматов и других научно-технических направлений
- •Подходы к определению конечного автомата.
- •Сущность метода "черного ящика".
- •Основные задачи теории автоматов
- •Глава 2. Формальная классификация абстрактных автоматов и их математические модели.
- •2.1 Словесные определения автоматов.
- •2.4.3 Модель совмещенного автомата (с-автомата)
- •2.4.4 Модель микропрограммного автомата
- •Глава 3 Структурные модели первого уровня абстрактных автоматов
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3 Структурная модель с - автомата
- •3.4 Структурная модель микропрограммного автомата
- •Глава 4. Способы задания абстрактных и структурных автоматов.
- •Глава 5 Минимизация абстрактных автоматов
- •Глава 6. Математические основы алгебры логики
- •Теоремы алгебры логики
- •6.4.1 Словесная форма представления логических функций
- •6.4.3 Аналитическая форма представления логических функций
- •6.4.4 Геометрическая и кубическая формы представления
- •2.4.3 Модель совмещенного автомата………………25
- •Глава 5 Минимизация абстрактных автоматов……………..58
- •Глава 6. Математические основы алгебры логики……...…70
- •Учебное издание
- •394026 Воронеж, Московский просп.,14
6.4.1 Словесная форма представления логических функций
Любая логическая функция может быть представлена в виде словесного описания.
Пример 6.2. Функция f от двух переменных истинна тогда и только тогда, когда обе переменные одновременно ложны.
Пример 6.3. Функция g от трех переменных истинна только тогда, когда одновременно истинны не менее двух аргументов.
Функция g определена (задана) достаточно лаконично, но вместе с тем, не достаточно определенно. Для полной определенности данную функцию нужно было бы задать следующим образом: функция истинна тогда, когда одновременно истинны аргумент первый и второй, или когда истинны аргумент первый и третий, или когда истинны аргумент второй и третий, или когда истинны все три аргумента.
Таким образом, словесное описание логических функций усложняется по мере увеличения числа аргументов, что может приводить к неоднозначности задания функции. Однако и при небольшом числе аргументов словесное описание логической функции может выглядеть в форме, достаточно трудной для понимания. Рассмотрим в качестве примера следующую арабскую мудрость, которая выражает целесообразность общения между людьми.
Пример 6.3.
"Если не знает, и не знает, что он не знает,
тот глуп - избегай его.
Если не знает, и знает, что он не знает,
ученик - научи его.
Если знает, и не знает, что он знает,
тот спит - разбуди его.
Если знает, и знает, что он знает,
мудрец - учись у него."
Эта арабская мудрость может интерпретироваться как логическая функция двух аргументов (знает/не знает, знает/ не знает), которая рекомендует не общаться только с глупцами.
Словесная форма задания логических функций наиболее часто используется на начальном этапе проектирования комбинационных автоматов.
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.
82
81
Таблица 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
Карта Карно - это прямоугольник, разбитый на квадраты, число которых равно числу входных наборов логической функции, т.е. 2n. Каждая клетка карты соответствует одному входному набору. Клетки размечают так, чтобы наборы, которые соответствуют смежным минтермам (макстермам), располагались бы в соседних ячейках карты Карно. Координатами каждой клетки карты Карно являются комбинации переменных из всех возможных входных наборов логической функции.
Д ля двух переменных карта Карно представляет собой квадрат, разделенный на четыре ячейки, по одной на каждый входной набор. Строки карты связаны с переменной x1, столбцы — с переменной х2 .Следовательно, расположенная слева вверху ячейка соответствует входному набору (0,0) или минтерму (x1 x2), а расположенная справа внизу ячейка — входному набору (1,1) или макстерму (x1 v x2).Такого рода карта называется картой Карно на две переменные (рис. 6.2). Представление логической функции на карте Карно производится в соответствии, с таблицей истинности. Если функция f = x1x2=1 на входном наборе (0,0),то этот факт отражается на карте Карно записью в левую верхнюю ячейку единицы (рис. 6.2,а ). Остальные ячейка остаются незаполненными. Карта Карно может заполняться нулями в те ячейки, на входных наборах которых функция равна нулю. На рис. 6.2,б приведен пример заполнения карты Карно для функции f = 0,
x2 x2
0
1
0
0
1
0
0
0
1
0
1
1
x1 x1
f = 1 f = 0
а) б)
Рис.6.2. Изображение функции f на карте Карно
Карта Карно (табл.6.1 и рис.6.2), содержит все 2n возможных входных наборов и значения функции, соответствующие каждому из наборов.
В
Поскольку для четырех переменных существует 16 входных наборов, карта Карно разделена на 16 ячеек (рис. 6.4). Каждая ячейка пронумерована в соответствии с десятичным номером входного набора. Карта Карно обладает свойством цилиндричности: смежными являются минтермы, расположенные в двух крайних столбцах, и расположенные в двух крайних строках.
84
83
В случае шести переменных потребуется уже четыре 16-ячеечные карты. Каждая карта должна быть связана с одной из четырех возможных комбинаций переменных х5 и x6 . Для логических функций с числом переменных n>6 карты Карно становятся громоздкими и неудобными для практического применения.
x2x3
00
01
11
10
0
000
001
011
010
1
100
101
111
110
x1
Рис.6.3. Карта Карно для функции трех переменных
x3x4
00
01
11
10
00
0
1
3
2
01
4
5
7
6
11
12
13
15
14
10
8
9
11
10
x1x2
Рис.6.4. Карта Карно для функции четырех переменных
x3x4 x3x4
00
01
11
10
00
0
3
7
5
01
9
11
15
13
11
25
27
31
29
10
17
19
23
21
00
01
11
10
00
0
2
6
4
01
8
10
14
12
11
24
26
30
28
10
16
18
22
20
x1x2
x1x2
. а) б)
Р ис. 6.5. Представление функции пяти переменных на двух 16-ячеечных картах Карно а- при x5 ; б- при x5
x3x4 x5
000
001
011
010
110
111
101
100
00
01
11
10
x1x2
Рис 6.6.Карта Карно для функции пяти переменных
К
86
85