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

⇐ ПредыдущаяСтр 6 из 25Следующая ⇒

Логическая функция (функция алгебры высказываний) 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. Таблица истинности некоторой функции

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

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

Решение. Выпишем те наборы переменных, на которых функция принимает значение 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= = ;