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

В табл. 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) = x1* x2=1 на входном наборе (0,0),то этот факт отражается на карте Карно записью в левую верхнюю ячейку единицы (рис. 6.2, а). Остальные ячейка остаются незаполненными. Карта Карно может заполняться нулями в те ячейки, на входных наборах которых функция равна нулю. На рис. 6.2, б приведен пример заполнения

Рис. 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 карты Карно становятся громоздкими и неудобными для практического применения.

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

84

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

. а) б)

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

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

85