3376 ЛОГИЧЕСКИЕ ОСНОВЫ ВС

ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ И СПОСОБЫ ИХ ЗАДАНИЯ

 

Для синтеза схем цифровых устройств используется математическая логика, точнее её основной раздел, называемый алгеброй логики, или алгеброй высказываний, или алгеброй Буля (по имени её основоположника,  ирландского математика Джорджа Буля (1815-1864 гг.)).

Одним из основных понятий алгебры логики является понятие высказывания (суждения). Под высказыванием понимают любое утверждение, предположение,  о котором можно сказать, истинно оно или ложно. Существует бесконечное множество простых высказываний самой разнообразной природы. При этом никакие иные количественные или качественные соотношения не рассматриваются кроме как “да, это истинно” или “нет, это ложно”. Если высказывание – “истина”, то значение его истинности считается равным 1, если высказывание  – “ложь”, то значение его истинности – 0. Иначе говоря, высказывание можно рассматривать как двоичную переменную x, принимающую значения 0 или 1, т.е. используются два цифровых символа, как и в двоичной системе счисления. Это сходство с двоичной системой счисления даёт большое удобство при использовании алгебры логики при анализе и синтезе схем цифровых устройств.

Из простых высказываний с помощью определённых операций можно строить сложные высказывания, т.е. функции алгебры логики. Функция f (x1,x2, ... xn), которая, как и её аргументы, может принимать только два значения, называется переключательной (булевой, двоичной, логической) функцией (ПФ) [1].

Существует несколько способов вполне однозначного задания ПФ [1,2,3]. Основные из них следующие.

1. Заполнение таблицы истинности.

2. Перечисление номеров наборов, на которых ПФ равна 0.

3. Перечисление номеров наборов, на которых ПФ равна 1.

4. Присваивание ПФ её собственного номера.

5. Представление ПФ в аналитическом виде – в виде совершенных форм.

6. Представление ПФ каким-либо геометрическим способом (например, в виде пространственного куба [2,3] или диаграммы Вейча).

Рассмотрим кратко каждый из этих способов.

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

Пусть ПФ зависит от трёх аргументов, т.е. f (x1,x2,x3). Пример табличного задания одной из таких ПФ приведён в табл.1, где перебраны все возможные значения трёх аргументов и на каждом из них задано значение функции. Такие таблицы называются таблицами истинности.

 

Таблица 1

x1

0

0

0

0

1

1

1

1

x2

0

0

1

1

0

0

1

1

x3

0

1

0

1

0

1

0

1

F(3)

1

1

0

1

1

0

1

1

 

Совокупность значений аргументов называется набором. Любой набор можно рассматривать как двоичное число. Каждому набору присваивается номер, равный двоичному числу, образованному значениями аргументов на этом наборе. Принято считать, что старшему разряду этого числа соответствует значение аргумента с меньшим индексом. Так в табл.1 наборы слева направо последовательно имеют номера: нулевой (0,0,0), первый (0,0,1), второй (0,1,0),..., седьмой или единичный (1,1,1). При табличном задании ПФ наборы обычно следуют в порядке их возрастания от нулевого до единичного.

Основное достоинство задания ПФ с помощью таблиц истинности – наглядность. Однако с каждым увеличением числа аргументов на единицу таблица истинности удваивается. Поэтому при большом числе аргументов задание ПФ таким способом становится слишком трудоёмким.

2. ПФ, зависящую от n аргументов, ещё обозначают символом f (n). Если известны наборы, на которых она равна 1, её можно задать перечислением номеров (a1, a2, ... ak) этих наборов. Такое задание ПФ обычно записывается в виде f (n) = Ú(a1, a2, ... ak). ПФ, заданная в табл.1, запишется в виде f (3) = Ú(0,1,3,4,6,7).

3. Если ПФ f (n) равна 0 на наборах с номерами b1, b2, ... bm, то её можно задать перечислением этих наборов f (n) = Ù( b1, b2, ... bm ). ПФ, заданная в табл.1, запишется в виде f (3) = Ù(2,5).

4. Каждая ПФ n аргументов задана на 2n наборах. Поэтому её можно рассматривать как двоичное число, имеющее 2n разрядов. Значит, число ПФ n аргументов равно . Следовательно, любую такую функцию f (n) можно задать с помощью её номера N, равного двоичному числу, образованному значением этой функции на всевозможных наборах. Причём старшему разряду этого числа соответствует значение функции на наборе с меньшим  номером. При таком способе задания ПФ записывается в виде f N(n). Например, ПФ, заданная в табл.1, записывается как f219(3).

Основным достоинством 2-го, 3-го и 4-го способов задания ПФ является компактность.