Определение и задание функций алгебры логики (ФАЛ)

Функцией алгебры логики (ФАЛ) называют функцию «n» переменных f(x₁, x₂, … , x_n), если она, как и ее переменные, может принимать только два значения: 0 или 1. Переменным ФАЛ можно поставить в соответствие дискретные значения сигналов на входах дискретного автомата ДА. Значениям ФАЛ можно поставить в соответствие дискретные значения сигналов на выходах дискретного автомата, рис. 12.

Рис. 12

Следовательно, дискретный автомат реализует ФАЛ f(x₁, x₂, … , x_n) от «n» двоичных переменных путем преобразования значений входных переменных в выходную переменную «у» по закону, задаваемому ФАЛ: у = f(x₁, x₂, … , x_n).

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

Число N возможных комбинаций значений “n” переменных равно: N = 2ⁿ.

Так как каждой комбинации переменных можно поставить в соответствие одно из двух значений ФАЛ, то общее число F различных ФАЛ, которое можно реализовать на множестве “n” переменных, равно: .

Так, например, при n = 1; N = 2¹ = 2; F = 2² = 4;

при n = 2; N = 2² = 4; F = 2⁴ = 16;

при n = 3; N = 2³ = 8; F = 2⁸ = 256.

Способы задания ФАЛ

Существует несколько способов задания ФАЛ. Рассмотрим некоторые из них.

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

X_n∙2^n-1 + X_n-1∙2^n-2 + … + X₂∙2¹ + X₁∙2⁰, где

X_n, X_n-1, … , X₁ – входные переменные, которые играют роль коэффициентов при соответствующих степенях основания 2.

Ниже приведен пример табличного задания двух произвольных функций алгебры логики f₁ и f₂ от трех переменных. С помощью табл. 1 мы задали алгоритм работы двух комбинационных устройств, значения выходных сигналов которых однозначно определяются только значениями входных переменных.

Таблица 1

Таблица, в которой значения ФАЛ приведены для всех возможных значений переменных, называют таблицей истинности. Очевидно, что таблица истинности при “n” переменных должна содержать 2ⁿ наборов (строк), n столбцов по числу переменных и m столбцов по числу задаваемых ФАЛ. В нашем случае число переменных равно 3, число заданных ФАЛ равно 2, следовательно, таблица истинности должна содержать 8(2³) строк и 6 (3 + 2 + 1) столбцов, включая столбец номеров наборов значений переменных.

Графический способ задания ФАЛ. При графическом способе задания ФАЛ каждому набору значений n переменных в n-мерном пространстве соответствует точка, которой приписывается значение функции на этом наборе.

Рис. 13

При одной переменной х, имеющей всего два значения, одномерным пространством является линия (ось х), на которой откладываются две точки с координатами, соответственно, 0 и 1, рис. 13, а. Двум переменным, например, х₁ и х₂ соответствует двухмерное пространство в виде плоскости (системы прямоугольных координат), на которой на каждой из осей откладываются по две точки, соответственно, (00; 01) и (10; 11), рис. 13, б. Трем переменным х₁, х₂ и х₃ соответствует трехмерное объемное пространство в виде куба с восьмью вершинами по числу наборов значений переменных, рис. 13, в. Данный куб называется единичным, так как каждое его ребро соединяет вершины, наборы которых отличаются значением одной переменной. На рисунке (см. рис. 13, в) с помощью единичного куба задана ФАЛ f₁ из табл. 1.из табл. о куба задана ФАЛ (аргументами). редставляется в виде алгебраического выражения, состоящего из логическ

Множеству 2ⁿ наборов соответствует множество вершин n-мерного единичного куба, который строится из двух (n-1)-мерных кубов путем соединения их одноименных вершин ребрами и приписывания 2^n-1 вершинам одного куба нулевого значения, а другого куба единичного значения n-й переменной.

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

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

Так, например, при n = 2 карта Карно должна содержат 2ⁿ = 2² = 4 ячейки, рис. 14, а. При n = 3 карта Карно должна содержать уже 2³ = 8 ячеек, рис. 14, б. При n = 4 – 16 ячеек, рис. 14, в.

Рис. 14

Как видно из приведенного рисунка каждая ячейка находится на пересечении n координат, соответствующих определенному набору значений переменных. При этом значения переменных разделяются на группы так, чтобы наборы соседних клеток различались значением одной переменной. Например, функция f1 трех переменных из табл. 1 может быть представлена с помощью таблица Карно (см. рис. 14, б) следующим образом, рис. 15, а:

Чтобы найти ячейку, в которую следует проставить значение функции для некоторого набора значений переменных, например, для х₁ = 0, х₂ = 1, х₃ = 1, необходимо через выбранные значения этих переменных (координат) провести прямые линии, тогда точка пересечения этих будет находиться в пределах искомой ячейки, рис. 14, б.

Рис. 15

Числовой способ задания ФАЛ. При данном способе функция задается в виде десятичных номеров наборов (комбинаций) значений переменных, на которых функция принимает единичное или нулевое значение. Например, если ФАЛ трех переменных задана в виде следующего перечня номеров наборов f₁(1, 3, 7), то это говорит о том, что при комбинациях значений переменных 1₁₀ = 001₂, 3₁₀ = 011₂ и 7₁₀ = 111₂ функция f принимает значение лог. 1. Следовательно, функцию, заданную картой Карно, приведенной на рис. 15, а, можно аналогично задать числовым способом, так как данная функция имеет единичные значения на трех наборах значений переменных: 001, 011 и 111, номера которых соответственно равны 1, 3 и 7. Учитывая, что на оставшихся пяти наборах значений переменных функция принимает нулевое значение, то функцию можно также задать числовым способом, но уже в виде перечня номеров наборов, на которых ФАЛ принимает значение лог. 0: f₀(0,2, 4, 5, 6).

Аналогичным образом в карте Карно можно проставлять только единичные или нулевые значения функции. При этом вместо числовых значений координат можно использовать обозначения выходных сигналов логических элементов, которые формируют входные сигналы дискретного устройства, реализующего заданную ФАЛ. Действительно, под значениями переменных заданных таблицей истинности следует понимать состояния логических элементов, формирующих входные сигналы. Каждый логический элемент Х имеет условно два выхода: прямой – х, сигнал которого повторяет значение состояния элемента, и инверсный - , сигнал которого противоположен по своему значению состоянию логического элемента. При проставлении только единиц в ячейках карты Карно следует вместо числовых координат (состояний соответствующих логических элементов) проставлять обозначения таких выходов логического элемента, которые в данном состоянии логического элемента принимают единичное значение, рис. 16, а. И, наоборот, при проставлении только нулей в ячейках карты Карно следует вместо числовых координат проставлять обозначения таких выходов логического элемента, которые в данном состоянии логического элемента принимают нулевое значение, рис. 16, б.

Рис. 16

Аналитический способ задания ФАЛ. При аналитическом способе задания функция представляется в виде алгебраического выражения, состоящего из логических операций над переменными (аргументами). Например, ФАЛ f₂ из табл. 1 может быть задана аналитически двумя способами:

f₂(x₃, x₂, x₁) = - в виде логической суммы логических произведений переменных, или в виде логического произведения логических сумм переменных:

f₂(x₃, x₂, x₁) = .

Оба выражения для ФАЛ являются равносильными, так как на одних и тех же наборах значений переменных принимают одни и те же значения. Так, например, на наборе значений (000) функция, заданная первым и вторым выражениями, принимает значение, равное лог. 1:

f₂(x₃, x₂, x₁) = 1∙1∙1 + 0∙1∙1 + 0∙0∙1 + 0∙0∙0 = 1 + 0 + 0 + 0 = 1.

f₂(x₃, x₂, x₁) = (0 + 0 + 1) ∙ (0 + 1 + 0) ∙ (0 + 1 + 1) ∙ (1 + 0 + 1) = 1∙1∙1∙1 = 1.

ФАЛ f₁, заданную картой Карно (см. рис. 16), можно также представить в аналитическом виде. Для функции, заданной картой Карно (см. рис. 16, а), аналитическое выражение представляет собой логическую сумму логических произведений координат ячеек, в которых проставлены 1:

f₁(x₃, x₂, x₁) = .

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

f₁(x₃, x₂, x₁) = .

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

.

Проинвертировав все переменные в данном выражении, получим аналитическое выражение для f1, аналогично полученному ранее с использованием карты Карно (см. рис. 16, а):

f₁(x₃, x₂, x₁) = .

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

Если ФАЛ не определена на каком либо наборе значений переменных, то в таблице значений функции или в карте Карно на соответствующем месте (в ячейке) проставляется обычно знак тильды (~). При числовом способе задания ФАЛ номера неиспользуемых наборов заключают в скобки. Например, для функции трех переменных у(x₃, x₂, x₁) запись: у(x₃, x₂, x₁) = f₁[0, 5, 6, (2, 4)], говорит о том, что на наборах значений переменных (0, 5, 6) функция принимает единичное значение, на наборах (1, 3, 7) – нулевое, а на наборах (2, 4) – значение функции не определено.

Задачи для самостоятельного решения

1. Дискретное устройство состоит из трех одновременно работающих логических блоков и контрольного блока, который контролирует работоспособное состояние логических блоков. При неисправности одного и более логических блоков контрольный блок формирует на одном из выходов у₁ сигнал логической единицы, который включает сигнализацию о наличии неисправных логических блоков в дискретном устройстве. Требуется составить таблицу истинности для ФАЛ у₁, реализуемой контрольным блоком. Работоспособное состояние логического блока соответствует лог. 1, а неисправное – лог. 0. Ответ:

2. Составить карту Карно для ФАЛ у₁, реализуемой контрольным блоком из задачи 1. Ответ:

3. Составить аналитическое выражение для ФАЛ у₁, используя карту Карно из задачи 2. Ответ: у₁ = .

4. На втором выходе у₂ контрольного устройства из задачи 1 формируется сигнал лог. 0 в том случае, если в дискретном устройстве вышло из строя два и более логических блоков. Сигнал лог. 0 на втором выходе контрольного блока блокирует работу дискретного устройства. Требуется составить таблицу истинности для ФАЛ у₂, реализуемой контрольным блоком. Работоспособное состояние логического блока соответствует лог. 1, а неисправное – лог. 0. Ответ:

5. Составить карту Карно для ФАЛ у₂, реализуемой контрольным блоком из задачи 4. Ответ:

6. Составить аналитическое выражение для ФАЛ у₂, используя карту Карно из задачи 5. Ответ: у₂ = .

7. Записать функцию у₂ из задачи 4 числовым способом по единичным значениям функции. Ответ: у₂ = f₁(3, 5, 6, 7).

8. Записать функцию у₂ из задачи 4 числовым способом по нулевым значениям функции. Ответ: у₂ = f₀(0, 1, 2, 4).

9. Решить задачу 7 при условии, что на нулевом наборе значение функции у₂ не определено. Ответ: у₂ = f₁[3, 5, 6, 7, (0)].