Логические функции

Функция f(x₁, х₂, ..., x_n), принимающая логическое значение (1 или 0)иза­висящая от логических переменных, называется логической функцией. Логическую функцию можно представить в виде отображения f: Eⁿ ® E,где множество Eⁿ = E ´ E ´ … ´ Eестьдекартово произ­ведениевсех упорядоченных наборов (x₁, х₂, ..., x_n)таких, что
x_i ÎE, i = 1,2,…, n.

Таким образом, область определения логической функции – сово­купность всевозможных n-мерных наборов из нулей и единиц, а для её задания достаточно указать, какие значения функции соответст­вуют каждому из наборов (табл. 2.3).

На­боры в таблице будем располагать в порядке возрастания их номера N. Такой порядок расположения наборов называ­ется стандартным или естественным.

При таком порядке каждому набору α = (α₁, …, α_n), где α_i есть 0 или 1, ставится в соответствие целое число

N = α₁2^n-1+ … + α_n-12¹+ α_n.

Наборам (0, 0, ...,0, 0), (0, 0, ..., 0, 1), ..., (1, 1, ..., 1, 1)соот­вет­ствуют числа N = 0, 1,..., 2ⁿ-1. Количество входных наборов для функции n переменных равно k = 2ⁿ.

Таблица 2.3. Задание логической функции

Все множество наборов переменных по значениям функции на них можно разбить на 2 подмножества:

[1] – единичное множество наборов, на которых f = 1;

[0] – нулевое множество наборов, на которых f = 0.

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

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

Далее рассмотрим логические функции одной и двух переменных, которые определяют также и операции, используемые при записи логических формул. Их можно считать «элементарными» функциями (табл. 2.4, 2.5).

Таблица 2.4. Функции g(x)

Таблица 2.5. Функции двух переменных f(х₁, х₂)