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

Логическая функция (функция алгебры высказываний) f(X₁, X₂, …, X_n) РѕС‚ n переменных – n-арная операция РЅР° множестве [0; 1]. Р’ этой функции логические переменные X₁, X₂, …, X_n представляют СЃРѕР±РѕР№ высказывания Рё принимают значения 0 или 1.

Существует различных логических функций от n переменных.

Логические операции, рассмотренные в предыдущем разделе, можно рассматривать как логические функции от двух переменных.

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

1) булевый базис, состоящий из конъюнкции, дизъюнкции и отрицания;

2) базис NOR, состоящий из стрелки Пирса;

3) базис NAND, включающий штрих Шеффера.

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

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

Табличный. Функция задается РІ РІРёРґРµ таблицы истинности (соответствия), которая содержит 2ⁿ строк (РїРѕ числу наборов аргументов), n столбцов РїРѕ числу переменных Рё РѕРґРёРЅ столбец значений функции. Р’ такой таблице каждому набору аргументов соответствует значение функции.

Числовой. Функция задается в виде десятичных (восьмеричных, шестнадцатеричных) эквивалентов номеров тех наборов аргументов, на которых функция принимает значение 1. Нумерация наборов начинается с нуля. Аналогичным образом логическая функция может быть задана по нулевым значениям.

Пример 6.1. Функция задана аналитически:

f(X, Y, Z) = + .

Записать функцию в табличном и числовом представлениях.

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

Опустим отрицание до переменных по законам де Моргана (6.8)-(6.9):

f(X, Y, Z) = + = Z + X + Y + Z.

Сократим одинаковые слагаемые по формуле (6.10) и перегруппируем их:

f(X, Y, Z) = Z + X + Y + Z = X + Y + Z.

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

Таблица 6.2. Таблица истинности
функции f(X, Y, Z) = X + Y + Z

Номер набора	X	Y	Z	f(X, Y, Z) = X + Y + Z

Чтобы представить функцию в числовом представлении, выпишем номера наборов, на которых функция принимает значение 1: 1, 2, 4, 5, 6, 7 и номера наборов, на которых функция принимает значение 0: 0, 3.

Тогда функция f(X, Y, Z) = X + Y + Z имеет два числовых представления. В первом случае перечисляются все наборы, на которых функция равна 1:

f(1, 2, 4, 5, 6, 7) = 1.

Во втором случае перечисляются все наборы, на которых функция равна 0:

f(0, 3) = 0.

Р’СЃРµ эти представления эквивалентны Рё описывают РѕРґРЅСѓ функцию. □

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

Пример 6.2. Функция задана таблично (табл. 6.3).

Таблица 6.3. Таблица истинности некоторой функции

Записать функцию в аналитическом представлении ДНФ и числовом представлении.

Решение. Выпишем те наборы переменных, на которых функция принимает значение 1, и запишем их в виде конъюнкции переменных:

набор 3: X = 0, Y = 1, Z = 1 ® YZ;

набор 6: X = 1, Y = 1, Z = 0 ® XY ;

набор 7: X = 1, Y = 1, Z = 1 ® XYZ.

Соединим полученные конъюнкции переменных дизъюнкцией и получим аналитическое представление функции:

f(X, Y, Z) = YZ + XY + XYZ.

Функция принимает значение 1 на наборах 3, 6, 7 и значение 0 на наборах 0, 1, 2, 4, 5, поэтому в числовом представлении функция будет иметь вид

f(3, 6, 7) = 1.

f(0, 1, 2, 4, 5) = 0. □

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

Пример 6.3. Функцию, заданную таблично в примере 6.2, записать в аналитическом представлении КНФ.

Решение. Выпишем наборы, на которых функция принимает значение 0 и преобразуем их в дизъюнкции переменных:

набор 0: X = 0, Y = 0, Z = 0 ® X + Y + Z;

набор 1: X = 0, Y = 0, Z = 1 ® X + Y + ;

набор 2: X = 0, Y = 1, Z = 0 ® X + + Z;

набор 4: X = 1, Y = 0, Z = 0 ® + Y + Z;

набор 5: X = 1, Y = 0, Z = 1 ® + Y + .

Запишем функцию в виде КНФ (произведения сумм):

f(X, Y, Z) = (X + Y + Z)(X + Y + )(X + + Z) ´

´ ( + Y + Z)( + Y + ). □

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

Рассмотрим способы перевода функции из одного базиса в другие.

Правило 6.4. (переход от булевого базиса к базису NOR) Алгоритм перехода включает следующие этапы.

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

X+Y+Z=(X+Y+Z)(X+Y+Z)=((X+Y)(X+Y)+Z)((X+Y)(X+Y)+Z)=

= ;

XYZ=(XY+XY)Z= =

= .

2. Преобразовать конъюнкции по формуле (6.24):

X×Y= .

3. Преобразовать отрицание над переменными по формуле (6.25):

= .

4. Заменить полученные операции стрелкой Пирса по формуле (6.26):

=X¯Y.

Пример 6.4. Привести упрощенную функцию из примера 6.1 к базису NOR.

Решение. Приведем формулу к произведению сумм и т. д. по формуле (6.7):

f(X, Y, Z) = X + Y + Z = (X + Y + )(X + Y + Z) =

= ((X + Y)(X + ) + )((X + Y)(X + ) + Z).

Преобразуем конъюнкции:

((X + Y)(X + ) + )((X + Y)(X + ) + Z) =

= .

Преобразуем отрицания над переменными:

=

= .

Заменим операции стрелкой Пирса:

=

= ((X ¯ Y)(X ¯ (Z ¯ Z)) ¯ (Y ¯ Y)) ¯ ((X ¯ Y)(X ¯ (Z ¯ Z)) ¯ Z).

Формула приведена Рє базису NOR. □

Правило 6.5. (переход от булевого базиса к базису NAND) Алгоритм перехода включает следующие этапы.

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

X+Y+Z=(X+Y)(X+Y)+Z= = ;

XYZ=XYZ+XYZ=(XY+XY)Z+(XY+XY)Z=

= .

2. Преобразовать дизъюнкции формуле

X+Y= . (6.27)

3. Преобразовать отрицание над переменными по формуле:

= . (6.28)

4. Заменить полученные операции штрихом Шеффера по формуле:

=X½Y. (6.29)

Пример 6.5. Привести функцию из примера 6.2 к базису NAND.

Решение. Упростим выражение и приведем к виду суммы произведений и т. д.:

f(X, Y, Z) = YZ + XY + XYZ = Y( Z + X + XZ) =

= Y( Z + X( + Z)) = Y( Z + X) = Y(Z + X) = YZ + YX.

Преобразуем дизъюнкции:

YZ + YX = .

Отрицания над переменными отсутствуют, поэтому приведем операции к штриху Шеффера:

= (Y ½ Z) ½ (Y ½ X).

Формула приведена Рє базису NAND. □

Минимизация логических функций

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

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

Правило 6.6. (метод Блейка) Алгоритм метода состоит из трех этапов:

1) привести формулу к ДНФ;

2) для всевозможных пар слагаемых, если это возможно, применить операцию склеивания:

Y + XZ = Y + XZ + YZ;

3) к исходным и полученным слагаемым применить операцию поглощения:

X + XY = X.

Пример 6.6. Минимизировать функцию из примера 6.2.

Решение. Исходная функция имеет вид:

f(X, Y, Z) = YZ + XY + XYZ.

Выполним последовательно этапы метода Блейка. Применим операцию склеивания для всевозможных пар слагаемых:

YZ + XY = YZ + XY + YZY = YZ + XY + 0;

YZ + XYZ = YZ + XYZ + YZ;

YZ + XY = YZ + XY + XY;

XY + YZ = XY + YZ + YZ.

В результате выполнения второго этапа получено следующее выражение:

f(X, Y, Z) = YZ + XY + XYZ + YZ + XY.

Применим операцию поглощения:

f(X, Y, Z) = YZ + XY.

Таким образом, функция минимизирована. Сравните полученный результат СЃ упрощением функции РІ примере 6.5, то есть минимизация может быть достигнута преобразованиями над функцией. □