УП часть 1 теория авт

х1 х2 х3 x4 v х1х2 х3 x4 = х2 х3 x4 , х1 х2 v х1 х2 = х1 .

Правило склеивания для соседних элементарных дизъюнкций:

логическое произведение двух соседних элементарных дизъюнкций ранга r можно заменять одной элементарной дизъюнкцией ранга r - 1, являющейся общей частью исходных дизъюнкций. Это правило является следствием распределительного закона и применяется для упрощения логических выражений. Например:

(х1 v х2 v х3v x4)( х1v х2vх3v x4)= х2v х3v x4,

(х1v х2) (х1v х2)= х1.

Правило поглощения для элементарных конъюнкций:

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

х1 х2 х3 x4 v х1х2 = х1х2, х1v х1х2 = х1.

Кроме того, справедливы выражения:

х1v х1х2 = х1v х2 , х1v х1х2=х1v х2.

Правило поглощения для элементарных дизъюнкций:

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

(x1 v x2 v x3 v x4)(x1 v x2)=x1 v x2, x1(x1 v x2) = x 1 .

В алгебре логики существуют две теоремы разложения:

79

и четыре соотношения, позволяющие упрощать логические функции:

Из соотношений (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.

80

6.4 Формы представления логических функций

На отдельных этапах анализа и синтеза комбинационных автоматов используются различные формы их представления (задания): словесная, табличная, аналитическая, числовая, геометрическая и кубическая. Задать логическую функцию - значит указать значения, которые принимает функция (т.е. 1, или 0, или неопределенное значение) при всех возможных комбинациях входных наборов.

6.4.1 Словесная форма представления логических функций

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

Пример 6.2. Функция f от двух переменных истинна тогда и только тогда, когда обе переменные одновременно ложны.

Пример 6.3. Функция g от трех переменных истинна только тогда, когда одновременно истинны не менее двух аргументов.

Функция g определена (задана) достаточно лаконично, но вместе с тем, не достаточно определенно. Для полной определенности данную функцию нужно было бы задать следующим образом: функция истинна тогда, когда одновременно истинны аргумент первый и второй, или когда истинны аргумент первый и третий, или когда истинны аргумент второй и третий, или когда истинны все три аргумента.

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

Пример 6.3.

"Если не знает, и не знает, что он не знает, тот глуп - избегай его.

Если не знает, и знает, что он не знает, ученик - научи его.

Если знает, и не знает, что он знает, тот спит - разбуди его.

Если знает, и знает, что он знает, мудрец - учись у него."

Эта арабская мудрость может интерпретироваться как логическая функция двух аргументов (знает/не знает, знает/ не знает), которая рекомендует не общаться только с глупцами.

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

6.4.2 Табличная форма представления логических функций

Логическую функцию можно представить в табличной форме (таблицей истинности или картой Карно). Принцип по-

строения таблиц истинности рассмотрен в п.6.3. В таблице 6.1 представлена в табличной форме логическая функция из приме-

ра 6.2.

Т а б л и ц а 6.1 Таблица истинности функции f

В таблице 6.2 задана в табличной форме логическая функция g от трех переменных из примера 6.3.

Таблица 6.2. Таблица истинности функции g

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

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

— с переменной х2 .Следовательно, расположенная слева вверху ячейка соответствует входному набору (0,0) или минтерму (x1 x2), а расположенная справа внизу ячейка — входному набору ( 1 , 1 ) или макстерму (x1 v x2).Такого рода карта называется картой Карно на две переменные (рис. 6.2). Представление логической функции на карте Карно производится в соответствии, с таблицей истинности. Если функция f = x1 x2=1 на входном наборе (0,0),то этот факт отражается на карте Карно записью в левую верхнюю ячейку единицы (рис. 6.2,а ). Остальные ячейка остаются незаполненными. Карта Карно может заполняться нулями

83

в те ячейки, на входных наборах которых функция равна нулю. На рис. 6.2,б приведен пример заполнения карты Карно для тех наборов, на которых функция f = 0,

Рис.6.2. Изображение функции f на карте Карно

Карта Карно (табл.6.1 и рис.6.2), содержит все 2n возможных входных наборов и значения функции, соответствующие каждому из наборов.

В случае трех переменных карта Карно (рис.6.3) содержит восемь ячеек, по одной для каждого входного набора, указанного внутри ячейки. Переменная x1связана с двумя строками карты, а переменные x2 и x3 — с четырьмя столбцами. Таким образом, любые две рядом расположенные ячейки являются соседними и их координаты отличаются только одной переменной. Кроме того, соседними являются ячейки, стоящие в первом и последнем столбцах карты.

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

В случае пяти переменных целесообразно использовать две 16-ячеечные карты (рис. 2.4), а не одну 32-ячеечную

84

(рис. 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. Карта Карно для функции трех переменных

Рис.6.4. Карта Карно для функции четырех переменных

85

Рис. 6.5. Представление функции пяти переменных на двух 16ячеечных картах Карно а- при x5 ; б- при x5

x3x4 x5

000 001 011 010 110 111 101 100

00

01

x1x2

11

10

Рис 6.6.Карта Карно для функции пяти переменных

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

86

6.4.3 Аналитическая форма представления логических функций

Табличные способы задания логических функций становятся весьма громоздкими с увеличением числа аргументов. Так, уже при восьми аргументах количество строк в таблице истинности или количество клеток карты Карно равно 256. Аналитические формы представления логических функций более компактны и наглядны, и позволяют очень просто синтезировать комбинационные автоматы из ограниченного количества логических элементов, реализующих логические операции умножения (конъюнкцию), сложения (дизъюнкцию) и отрицания (инверсию). В то же время, аналитические формы логических функций позволяют выполнять различные их математические преобразования с целью получения более простых соотношений или для каких - либо других целей.

Аналитический способ предусматривает запись логической функции в форме логического выражения, показывающего, какие логические операции над аргументами должны выполняться и в какой последовательности. Сложные функции от многих аргументов могут быть представлены в форме "функций от функций", т.е. выражаться через более простые функции - от меньшего числа аргументов. Так, если z = z(x,y); x = x (a,b); y = y (c,d), то z = z (a,b,c,d). Операция замены аргу-

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

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

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

СДНФ логической функции может быть получена путем многократного применения теоремы разложения (6.25) к некоторой функции n аргументов для каждой ее переменной xi (i=1…n). Применяя теорему разложения, получим

……………………… 2n -1

+ f(1,1,…1 )x1 x2…xn = ∑ fi mi, i=0

где fi - значение логической функции на i -ом входном наборе аргументов;

mi - i -ый минтерм или i -ая элементарная конъюнкция максимального ранга.

Из (6.31) следует, что СДНФ логической функции — это дизъюнкция конституент единицы (минтермов), соответствующих наборам входных переменных, для которых функция равна единице. Совершенная дизъюнктивная нормальная форма записывается для истинного значения логической функции. В то же время относительно логической функции можно сказать, что она истинна тогда, когда не ложна. Такое утверждение можно формализовать следующим образом.

Образуем логическую функцию по ее нулевым значениям на всех входных наборах. Тогда

Применяя к (6.32) правило де Моргана, получим

2n -1

F(x1, x2,… xn) = ∏ (fi + Mi), (6.33) i=0

где fi - значение логической функции на i -ом входном наборе аргументов;

Mi - i -ый макстерм или i -ая элементарная дизъюнкция максимального ранга.

Представление логической функции в виде (6.33) называется совершенной конъюнктивной нормальной формой (СКНФ).

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

Рассмотрим алгоритмы перехода от табличного описания логической функции к ее аналитическому описанию (СДНФ, СКНФ).

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

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

2)по каждому такому набору составить элементарные конъюнкции максимального ранга (минтермы);

3)в минтермы записать не инвертированными переменные, заданные единицей в таблице истинности, а инвертированными - те переменные, которые в таблице истинности заданы нулем;

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

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

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

2)по каждому такому набору составить элементарные дизъюнкции максимального ранга (макстермы);

3)в макстермы записать не инвертированными переменные, заданные нулем в таблице истинности, а инвертированными -

89

те переменные, которые в таблице истинности заданы единицей; 4) полученные макстермы соединить между собой знаками конъ-

юнкции.

Помимо двух основных (СДНФ и СКНФ) аналитических форм представления функций в алгебре логики существуют дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ), а также минимальные дизъюнктивные и конъюнктивные нормальные формы (МДНФ и МКНФ).

ДНФ/КНФ – это дизъюнкция/конъюнкция элементарных конъюнкций /дизъюнкций, ранг хотя бы одной из которых отличается от максимального ранга. ДНФ/КНФ называется минимальной, если она содержит наименьшее число букв по сравнению со всеми ДНФ/КНФ, существующими для данной функции. При помощи правил развертывания элементарных конъюнкций и дизъюнкций, ДНФ и КНФ могут быть преобразованы в СДНФ и СКНФ.

В общем виде СДНФ и СКНФ записываются выражениями (6.32) и (6.33), которые могут быть слишком громоздкими. Для их упрощения используется более компактная чи- словая форма записи, предусматривающая только перечисление десятичных эквивалентов двоичных наборов, на которых функция принимает значение единицы (для СДНФ) или нуля (для СКНФ), соединив их знаками дизъюнкции (для СДНФ) и конъюнкции (для СКНФ).

Пример 6.4. Пусть логическая функция P(x,y,z) задана следующей таблицей истинности (табл. 6.3). Требуется представить ее в виде СДНФ и СКНФ.

Решение. По таблице истинности находим, что функция P(x,y,z) принимает единичные значения на четырех входных наборах аргументов. Данным наборам аргументов соответствуют следующие четыре минтерма: x y z, x y z, x y z, x y z.

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

90

Pсднф(x,y,z) = x y z + x y z + x y z + x y z.

Таблица 6.3

По аналогии, представим данную логическую функцию в виде СКНФ. В итоге получим:

Pскнф(x,y,z) = (x +y+ z ) (x +y+ z) (x+ y+ z) (x+ y+ z).

6.4.4 Геометрическая и кубическая формы представления логических функций

В геометрическом смысле каждый двоичный набор (a1 a2.... an) переменных логической функции можно рассматривать как n-мерный вектор, определяющий точку n-мерного пространства. Исходя из этого, всe множество наборов, на которых определена функция n переменных, представляется в видe вершин n-мерного куба. Отмечая точками вершины, в которых функция имеет единичные значения, получают ее геометрическое представление, например так, как показано на рис. 6.6, а.

91

а) б ) в)

Рис. 6.6. Геометрическое и кубическое представление функции

Y= (3,4,5,6,7): a — 0-кубы; б — 1-кубы; в — 2-куб

На основе геометрических представлений строятся кубические представления логических функций, в которых используются элементы n-мерных кубов. Геометрически каждому набору (a1 a2.... an) соответствует вершина n-мерного куба с данными координатами. Каждую вершину, на которой функция принимает единичное значение, принято называть 0-кубом (нулевым кубом). Множество 0-кубов образует нуле-

вой кубический комплекс Ко. Например, для функции Y = V(3, 4, 5, 6, 7) нулевой кубический комплекс имеет вид Ко = (011, 100 101, 110, 111) и в данном случае состоит из пяти 0-кубов, каждый из которых соответствует определенной вершине трехмерного куба (рис. 6.6, а).

Если два 0-куба из комплекса К0 различаются только по одной координате, то они образуют один 1-куб (единичный куб). Он представляется общими элементами 0-кубoв, а на месте координаты, по которой различаются 0-кубы, указывается символ «-», обозначающий независимую координату. Например, два 0-куба: 100, 101 различаются только по третьей координате и, следовательно, образуют единичный куб 10-, которому соответствует ребро трехмерного куба. Все множество единичных кубов функции образует единичный кубический

92

4.2.1Таблицы переходов и выходов………….….…41

4.2.2Матрицы переходов и выходов………………..43

4.2.3Граф автомата…………………………………..44

4.3Язык алгебры логики (булевой алгебры)…………..46

4.4Язык временных диаграмм………………………….48

ГЛАВА 5 Минимизация абстрактных автоматов……………..58 ГЛАВА 6. Математические основы алгебры логики……...…70

6.1Формальное определение алгебры логики………..70

6.2Аксиомы, теоремы и законы алгебры логики……..71

6.2.1Аксиомы алгебры логики……………………..72

6.2.2Теоремы алгебры логики………………………73

6.2.3Законы алгебры логики………………………...73

6.3Основные понятия и определения………….…..75

6.4Формы представления логических функций……...81

6.4.1Словесная форма представления логических функций…………………………………………81

6.4.2Табличная форма представления логических функций…………………………………………82

6.4.3Аналитическая форма представления логических функций…………………………………………87

6.4.4Геометрическая и кубическая формы представле-

ния логических функций……………………91

БИБЛИОГРАФИЧЕСКИЙ СПИСОК …………………………..94

Учебное издание

Тюрин Сергей Владимирович

ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ

(Часть 1)

Компьютерный набор С.В. Тюрина

ЛР № 066815 от 25.08.99. Подписано к изданию 25.12.2002. Уч-изд.л. 6,1.

Воронежский государственный технический университет 394026 Воронеж, Московский просп.,14