Обратные функции

При рассмотрении логических функций вполне естественно возникает вопрос: А есть ли у них обратные функции?

Для ответа на этот вопрос рассмотрим таблицу истинности одной из функций двух переменных как таблицу, устанавливающую соответствие.

Напомним определение из теории множеств:

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

Таблица истинности (табл. 7) функции двух переменных f₈= ab устанавливает взаимосвязь между элементами множества двоичных наборов А={00,01,10,11} и множества значений функции В = {0, 1}.

Прямое и обратное соответствия, заданные табл. 7, показаны на рис. 2.

Рисунок 2 – Графики соответствий, заданных табл. 7

Прямое соответствие (рис. 2,а)

– полностью определено (используются все наборы множества А),

– сюръективно (все элементы множества В участвуют в соответствии),

– функционально, так как однозначно.

Обратное соответствие (рис. 2,б)

– полностью определено,

– сюръективно,

– не однозначно, следовательно, не функционально.

Обратное соответствие не однозначно, следовательно, не функционально, а поэтому логическая функция двух переменных f₈= ab не имеет обратной функции в таком понимании, как это было определено в Теории множеств.

Аналогичное заключение можно сделать и для других логических функций, существенно зависящих от двух переменных. Более того, аналогичное заключение можно сделать и для логических функций n переменных при n >2, так как элементов в множестве В только 2, а количество элементов в множестве А равно его мощности |А| = 2ⁿ, поэтому взаимно однозначного соответствия не получится.

Однако понятие обратной функции в булевой алгебре применяется. Обратные функции имеют логические функции, существенно зависящие от одной переменной (подтверждение этого – таблицы истинности функций одной переменной, приведенные в табл. 1). Кроме того, в булевой алгебре можно создать систему логических функций, которые имеют обратные функции. Пример этого – шифратор (CD) и дешифратор (DC), таблицы истинности которых показаны в табл. 11.

Таблица 11

Шифратор – это узел, имеющий m входов и n = выходов, где ]x[ – ближайшее большее целое. Он выполняет преобразование единичных сигналов на отдельных входах в двоичные наборы на выходах. Например, при m = 4, n = 2 (входы y_i, выходы a, b) значения выходов определяются по формулам

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

(Как получить формулу по таблице истинности см. п. 2.3, а как выполнить минимизацию частично определенной функции см. п. 4.4.)

Дешифратор (полный) – это узел, который имеет n входов и 2ⁿ выходов и преобразует каждый входной набор в активный сигнал на одном из выходов (например, на одном выходе 1, а на остальных выходах – 0). Так при n = 2 (входы a, b) значения выходов y_i определяются следующими формулами

Назовем эти функции системой обратных функций.

(Как получить формулу по таблице истинности см. п. 2.3.)

Если рассмотреть работу шифратора и дешифратора с точки зрения теории множеств, то получается следующее.

Шифратор производит преобразование наборов множества в наборы множества А = {00, 01, 10, 11}, при этом каждому набору из Y соответствует один набор из множества A.

Дешифратор выполняет функции, обратные по отношению к функциям, выполняемым шифратором, т. е. преобразовывает множество входных наборов из множества А = {00, 01, 10, 11}, в множество выходных наборов , причем каждому набору множества А соответствует один набор из множества Y.

Таким образом, взаимная связь между наборами множеств Y и A представляет взаимно однозначное соответствие, а это говорит о том, что мы имеем здесь дело с обратными функциями.

Замечание.Формирование системы прямых и системы обратных функций в шифраторе и дешифраторе выполняется с помощью пары функций f₁₄ – f₈, характерной особенностью которых является наличие одного нуля у одной из них и одной единицы у другой в графе функции таблицы истинности. Такими свойствами обладают также пары функций f₇ – f₁, f₁₃ – f₂, f₁₁ – f₄, приведенные в табл. 2, поэтому подобные системы функций можно создать и на этих функциях.