Поняття алгебри Жегалкіна, лінійні функції.

Алгебра (В,Ù,Å,0,1), що утворена множиною В – {0,1} разом з операціями Ù (кон’юнкції), Å, і константами 0, 1, називається алгеброю Жегалкіна. Будь – яка булева функція може бути зображена через операції кон’юнкції, диз’юнкції, заперечення. Для доведення зображення будь – якої булевої функції формулою алгебри Жегалкіна достатньо виразити диз’юнкцію і заперечення через кон’юнкцію і XOR – операції алгебри Жегалкіна. За видом полінома Жегалкіна визначається така важлива властивість булевих функцій, як лінійність. Булава функція називається лінійною, якщо її поліном Жегалкіна не містить кон’юнкцій змінних.

Поліномом Жегалкінаназив. скінченна сума за модулем 2 попарно різних елементарних кон’юнкцій над множиною змінних (x₁,x₂,…,x_n). К-ть попарно різних ел. функцій назив. довжиною полінома. Булева ф-я назив. лінійною, якщо її поліном не містить кон’юнкцію змінних. Для побудови поліному Жегалкіна функції, що задана деякою формулою алгебри Жегалкіна, необхідно розкрити всі дужки в даній формулі за законом дистрибутивності і виконати всі можливі спрощення. Якщо ф-я задана в ДДНФ або цю форму легко знайти, доцільно замінити диз’юнкції ксором, застосув. операції інверсії та зведення подібних. Метод невизначених коефіцієнтів: для ф-ї f(x₁,x₂,…,x_n) записують найзагальніший вигляд поліному Жегалкіна (Р(x₁,x₂,…,x_n)) з невизначеними коеф., їх буде 2ⁿ . Поліном Жегалкіна 2-х змінних має заг. вигляд P(x,y): a₀Åa₁xÅ a₂yÅa₃xy. Для трьох: P(x,y,z): a₀Åa₁xÅ a₂yÅa₃zÅa₄xyÅ a₅xzÅa₆yzÅa₇xyz. Для кожного двійкового набору (a₁…a_n) записують 2ⁿ рівнянь: f(a₁…a_n) = P(a₁…a_n). Розв’язавши їх, отримують коефіцієнти полінома.