01.1. Основные способы задания двоичных функций. Табличный способ задания
Определение 1.1. Двоичной функцией от N (N ³ 1) переменных называется функция 
, аргументы и значения которой выбираются из множеств 
, т. е.
F: 
,
Где
, 
.
Замечание 1.2. Двоичные функции от N переменных также называют Булевыми (Булевскими) функциями от N переменных или N-местными булевыми функциями.
На множестве 
определим так называемый лексикографический порядок, т. е. для любого двоичного набора 
определим его номер
.
Тогда двоичная функция однозначно может быть задана Табл.1.1 (называемой Таблицей истинности).
Таблица 1.1
|
Номер набора |
X1 … XN-1 Xn |
F(X1, ..., XN) |
|
0 |
0 ... 0 0 |
F(0, ..., 0,0) |
|
1 |
0 ... 0 1 |
F(0, ..., 0,1) |
|
. . . |
. . . |
. . . |
|
2N – 2 |
1 ... 1 0 |
F(1, ..., 1,0) |
|
2N – 1 |
1 ... 1 1 |
F(1, ..., 1,1) |
При указанной договоренности о расположении наборов из функция однозначно определяется набором — столбцом значений. Отсюда непосредственно вытекает справедливость следующего утверждения.
Утверждение 1.3. Число двоичных функций от N переменных равно 
.
Перечислим все двоичные функции от одной и двух переменных. Имеется четыре функции от одной переменной (табл.1.2).
Таблица 1.2
|
X1 \ F |
F0 |
F1 |
F2 |
F3 |
|
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
|
Условное обозначение |
0 |
|
|
1 |
Функции 
и 
не зависят от значения переменной 
и называются Константными (
, 
). Функция 
называется Тождественной функцией, а функция 
называется Отрицанием.
Функций от двух переменных — шестнадцать (табл.1.3).
Таблица 1.3
|
|
F0 |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
|
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
Обозначение |
0 |
X1×X2 |
X1 |
X2 |
X1ÅX2 |
X1ÚX2 |
\ FПродолжение табл.1.3
|
X1, X2\ F |
F8 |
F9 |
F10 |
F11 |
F12 |
F13 |
F14 |
F15 |
|
0 0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
Обозначение |
X1¯X2 |
X1 ~ X2 |
|
|
X1 ® X2 |
X1½X2 |
1 |
Важнейшими из них являются: 
— конъюнкция (X1 X2, X1 & X2, X1
X2), 
— сложение по модулю 2 (X1
X2), 
— дизъюнкция (X1
X2), 
— функция Пирса (X1
X2), 
— импликация (X1
X2), 
— функция Шеффера (X1| X2).
Определение 1.4. Переменная XI, или I-я переменная двоичной функции F(X1, ..., XN) называется Существенной переменной функции F (т. е. функция F Существенно зависит от XI), если существует набор (A1, ..., AI-1, AI+1, ..., AN) Î
, такой, что
F(A1, ..., AI-1, 0, AI+1, ..., AN) ¹ F(A1, ..., AI-1, 1, AI+1, ..., AN).
В противном случае переменная XI называется Несущественной (Фиктивной) переменной функции F.
Так, среди функций от двух переменных имеется ровно десять функций, существенно зависящих от всех своих переменных.
Число двоичных функций от N переменных растет с увеличением N чрезвычайно быстро. В табл.1.4 приведена зависимость функций от своих переменных при N £ 8.
Таблица 1.4
|
N |
Число функций от N переменных |
|
1 |
2 |
|
2 |
16 |
|
3 |
256 |
|
4 |
65536 |
|
5 |
4294967296 |
|
6 |
> 1.8 ×1019 |
|
7 |
> 3.4 ×1038 |
|
8 |
> 1.1 ×1077 |
С табличным заданием функции непосредственно связан такой ее параметр, как вес.
Определение 1.5. Множество двоичных наборов {(A1, ..., AN) Î Î| F(A1, ..., AN) = 1}, на которых функция F принимает значение 1, называется Областью истинности функции F. Мощность области истинности функции F называется Весом функции F и обозначается || F ||.
Очевидно, что 0 £ || F || £ 2N, причем равенства достигаются лишь для функций-констант 0 и 1. Если || F || = 2N-1, то функция F называется Равновероятной.
Для двоичных функций используются и другие способы задания, приспособленного для рассматриваемой в каждом конкретном случае задачи, которые будут рассмотрены далее.
| Следующая > |
|---|
