Табличный способ задания

Основные способы задания двоичных функций

Определение 1.1. Двоичной функцией от n (n ³ 1) переменных называется функция , аргументы и значения которой выбираются из множеств , т.е.

f: ,

где

, .

Замечание 1.2. Двоичные функции от n переменных также называют булевыми (булевскими) функциями от n переменных или n-местными булевыми функциями.

На множестве определим так называемый лексикографический порядок, т.е. для любого двоичного набора определим его номер

.

Тогда двоичная функция однозначно может быть задана табл.1.1 (называемой таблицей истинности).

Таблица 1.1

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

Утверждение 1.3. Число двоичных функций от n переменных равно .

Перечислим все двоичные функции от одной и двух переменных. Имеется четыре функции от одной переменной (табл.1.2).

Таблица 1.2

x1 \ f	f0	f1	f2	f3
Условное обозначение

Функции и не зависят от значения переменной и называются константными ( , ). Функция называется тождественной функцией, а функция называется отрицанием.

Функций от двух переменных — шестнадцать (табл.1.3).

Таблица 1.3

, \ f	f0	f1	f2	f3	f4	f5	f6	f7
0 0
0 1
1 0
1 1
Обозначение		x1×x2		x1		x2	x1Åx2	x1Úx2

Продолжение табл.1.3

x1, x2\ f	f8	f9	f10	f11	f12	f13	f14	f15
0 0
0 1
1 0
1 1
Обозначение	x1¯x2	x1 ~ x2				x1 ® x2	x1½x2

Важнейшими из них являются: — конъюнкция (x₁ x₂, x₁ & x₂, x₁ x₂), — сложение по модулю 2 (x₁ x₂), — дизъюнкция (x₁ x₂), — функция Пирса (x₁ x₂), — импликация (x₁ x₂), — функция Шеффера (x₁| x₂).

Определение 1.4.Переменная x_i, или i-я переменная двоичной функции f(x₁, ..., x_n) называется существенной переменной функции f (т.е. функция f существенно зависит от x_i), если существует набор (a₁, ..., a_i-1, a_i+1, ..., a_n) Î , такой, что

f(a₁, ..., a_i-1, 0, a_i+1, ..., a_n) ¹ f(a₁, ..., a_i-1, 1, a_i+1, ..., a_n).

В противном случае переменная x_i называется несущественной (фиктивной) переменной функции f.

Так, среди функций от двух переменных имеется ровно десять функций, существенно зависящих от всех своих переменных.

Число двоичных функций от n переменных растет с увеличением n чрезвычайно быстро. В табл.1.4 приведена зависимость функций от своих переменных при n £ 8.

Таблица 1.4

С табличным заданием функции непосредственно связан такой ее параметр, как вес.

Определение 1.5. Множество двоичных наборов {(a₁, ..., a_n) Î Î | f(a₁, ..., a_n) = 1}, на которых функция f принимает значение 1, называется областью истинности функции f. Мощность области истинности функции f называется весом функции f и обозначается || f ||.

Очевидно, что 0 £ || f || £ 2ⁿ, причем равенства достигаются лишь для функций-констант 0 и 1. Если || f || = 2^n-1, то функция f называется равновероятной.

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