Операции над функциями выбора

В теории принятия решений введены следующие операции над функциями выбора: объединение, пересечение и дополнение.

Объединение функций выбора С ₁ и С ₂ – функция С, определяемая формулой

С (X)= C ₁(X)È C ₂(X).

Пересечение функций выбора С ₁ и С ₂ – функция С, определяемая формулой

С (X)= C ₁(X)Ç C ₂(X).

Дополнение функции выбора С ₁ – функция , определяемая формулой

(X)= X \ Ç C ₁(X).

Декомпозиция функций выбора

Общие и частные декомпозиции.

Общие декомпозиции.

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

Нормальная функция выбора C (X) - это функция выбора, порожденная бинарным отношением R ÍW²

Декомпозиция 1. Пусть R ₁,..., R_k - бинарные отношения на W; y(g₁, …, g_k) – булева функция (функция аргументами которой являются 0 и 1). Определим функцию выбора C = C (R _l,..., R_k; y) на W:

xÎC(X) Û y(g1, …, gk) = 1

(2.3)

где

(2.4)

Функцию выбора C = C (R ₁,..., R_k; y), определенную формулами (2.3) и (2.4), назовем y - композицией нормальных функций выбора, порожденных бинарными отношениями R ₁,..., R_k).

Декомпозиция 2. Функцию выбора С, определяемую соотношением

 

(2.5)

назовем функцией разрешения и обозначим через С ⁺. Функцию С:

(2.6)

назовем функцией запрета и обозначим через С ^-.

Смысл функций разрешений и запретов очевиден. Именно, при функции разрешения элемент х_i выбирается из X тогда и только тогда, когда в X входит и элемент х_j, при функции запрета элемент х_i выбирается из X тогда и только тогда, когда x_j не входит в X.

Частные декомпозиции.

Декомпозиция 3. Введем следующие понятия. Булева функция

y_м(g₁, …, g_k) = Ú g₁, …, g_k,

где дизъюнкция берется по всем наборам, называется мажоритарной или функцией голосования. Название объясняется тем, что Y_М = 1 тогда я только тогда, когда больше половины переменных равны 1 (правило большинства).

Функция выбора вида C (R ₁,..., R_k; y _м) называется мажоритарно-нормальной (МНФ). Таким образом, класс МНФ составляют все те функции выбора, которые получаются правилом выбора большинства из нормальных. Элемент х выбирается из X тогда и только тогда, когда он выбирается более чем половиной из функций выбора, порожденных бинарными отношениями R₁,..., R_k.

Декомпозиция 4. Пусть снова R ₁,..., R_k - бинарные отношения на W. Положим

ys(g1, …, gk) = g1 Ú… Ú gk,

(2.7)

Функцию вида C (R ₁,..., R_k; y _s) называется - суммарно-нормальной функцией (СНФ).

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

C = Ck (Ck -1(… C 2(C 1)))

(2.8)

Множество таких функций выбора образует класс конечно-нормальных функций (КНФ).

Декомпозиция 6. Из формул (2.3), (2.4) и (2.5) непосредственно следует, что

 

Тем самым приходим к понятию декомпозиции функции выбора в виде объединения нормальных.