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

Табличное задание

Множество If строк таблицы, где б.ф. / = 1, называется множеством истинности б.ф./. Порядок множества /называется весом б.ф./(обозначается !/(*!,…, лг")||, кратко ||/||), т. е. О <f (x_v*")|| = S Да,…а") <

• («1…»пУ&п
• 2^п. < Если |/(x_t,…,х_п) =2″^-1, то f (x_v…, х_п) —равновероятная, или сбалансированная б.ф.

Для любых б.ф. / и g выполнено: Ij = V_n If, L_g = If n /"; /^ = /у u / ;

||7|| - 2″ -14 VM- - 1И1+И -¼ ll/®*ll — l/ll+И — Ы

Из теоремы 6.1 следует, что.

так как множества истинности слагаемых в (6.1) попарно не пересекаются.

Таблица б.ф. есть вектор длины 2″, поэтому одной из мер близости б.ф./ и#с одинаковым множеством переменных является расстояние Хэмминга: dist (/, g) = ||/0gj.

Другая мера олизости б.ф. связана с корреляцией. Функцией взаимной корреляции б.ф. / и |/ называют целочисленную функцию Aj^(u): V_n —> Z: Ay_v(w) ⁼ Z Б.ф. / и V|/ называют совершенно некоррели-

xev_n

рованными (некоррелированными степени k), если Ay_v(w) = 0 (А^(и) = О для всех векторов и веса не более k. Функцией автокорреляции б.ф. / называют целочисленную функцию АД w): V_n —> Z: AXu) =? (-1)/(*)^ф/(*^фм).

^xeKi

Для/, |/ е Р₂(и) ^{и и е} Кг выполнено: Af^{u) = j (u) и Ajj/u) = Af{u).

В некоторых приложениях значения б.ф. известны не на всей таблице. Функцию g: V —> {0, 1}, где V с V_n, называют частичной (частично определенной) б.ф. Доопределением частичной б.ф. g называется всякая б.ф. /, ограничение которой на V совпадает с g.