1.3. Переключательные функции

Любое логическое выражение, составленное из переменных с помощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию переменных. В соответствии с аксиомами (1.1) - (1.5) функция может принимать в зависимости от значений переменных или 1 только два значения: 0 и 1. Такие функции являются весьма удобным инструментом для описания, анализа и синтеза переключательных схем, выходные сигналы которых характеризуются лишь двумя уровнями напряжения: высоким (1) и низким (0). В связи с этим такие функции называются переключательными (термин "переключательная" обычно будем опускать, так как никакие другие функции рассматриваться не будут).

Для функций переменных будем использовать общее обозначение где т. е. совокупность переменных можно рассматривать как -мерный вектор. Каждая переменная может принимать только два значения: 0 и 1. Поэтому число всех возможных комбинаций значений конечно. В общем виде конкретное значение переменной (0 или 1) будем обозначать через

Для обозначения произвольных десятичных чисел будем использовать символы п., а двоичные числа будем записывать в виде где или 1. Равенства для десятичных и двоичных чисел будем записывать, опуская индекс, указывающий основание системы счисления: Значения и 1 являются элементами алгебры логики (булевой алгебры), если они используются в качестве значений переменных Для этих элементов не существует соотношений больше и меньше. В записи же двоичного числа значения и 1 считаются элементами кольца целых чисел Какими элементами являются символы 0 и 1, всегда ясно из контекста или используемых в выражениях операций. На основании этого, например, можно записать, что (в левой части используется логическая операция отрицания, а в правой — арифметическая операция вычитания).

Областью определения функции переменных является совокупность точек n-мерного пространства, причем каждая из точек задается определенной комбинацией значений этих переменных:

где или Точки, задающие область определения функции будем обозначать через

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

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

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

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

дизъюнкция (ИЛИ),

— конъюнкция И),

- функция И-НЕ,

— функция ИЛИ-НЕ,

- сумма по модулю два.

Область определения этих функций состоит из четырех точек:

поскольку

Так как область определения любой функции переменных конечна точек), она может быть задана таблицей значений или 1, которые она принимает в точках где Такие таблицы называются таблицами истинности. Табл. 1.3, которая составлена в соответствии с аксиомами (1.2) - (1.5) для указанных выше функций двух переменных, представляет собой таблицу истинности, задающую эти функции. В предпоследнем столбце помещена функция, заданная в общем виде коэффициентами где а в последнем столбце — инверсная функция, заданная коэффициентами Подставляя различные значения или 1, можно задать все 16 функций двух переменных В частности, можно получить вырожденные функции:

называемые инверсиями переменных (в табл. 1.3 показаны вырожденные функции константа нуль и константа единица).

Таблица 1.3. (см. скан) Функции двух переменных

Функции двух переменных исключительно важны в силу того, что любая функция переменных может быть получена из них методом суперпозиции [7] — подстановкой этих функций вместо переменных в другие функции. Такая подстановка возможна на основании того, что области значений функций и переменных совпадают (0 и 1).

Функция переменных называется полностью определенной, если ее значения или 1 заданы во всех точках области определения. Если же значение функции не задано хотя бы в одной точке то она называется неполностью определенной. Не определенное в точке значение функции будем задавать произвольным коэффициентом совмещенные символы 0 и 1, что указывает на неопределенность значения т.е., если в точке значение функции не

задано, то

Неполностью определенные функции можно доопределять произвольным способом, полагая или 1. Если значения функции не заданы в точках, то функцию можно доопределить способами, так как имеется различных -разрядных двоичных чисел, соответствующих различным способам доопределения функции в точках. Таким образом, не определенной в точках функции соответствует класс из полностью определенных функций. Если значения функции а, не заданы ни в одной точке то она называется полностью неопределенной и обозначается через h [10].

Теории переключательных функций посвящено много работ, среди которых следует выделить [5, 7, 8] как наиболее фундаментальные.