2013_2Лекціі 4, 5, 6 таблиці

4.1 Визначення та основні властивості булевих функцій

Булеве відображення над −.

Булева функція − булеве відображення виду .

Булеве відображення в координатному виді − вектор-функція , де- так звані, координатні булеві функції.

Представлення функції у вигляді т.зв. полінома Жегалкіна (АНФ) −

Значення називається степенем нелінійності функції.

Таблиця булевої фінкції складається з рядків виду. Останній правий стовбчик таблиці називається вектором значень функції. Він міститьєлементів.

Приклад: .

Кількість булевих функцій від аргументів.

Вагою булевої функціїназивається кількість одиниць у векторі значень.

При рівноімовірному і незалежному виборі аргументів булевої функції , імовірності її значень, відповідно рівні.

Відстанью Хемінга між булевими функціями іназивається кількість покоординатних неспівпадінь у векторах їхніх значень:.

Відстанню Хемінга від функції до заданої множини функційназивається значення.

У послідовності -вимирних аргументів рядки підтаблиці, що складається здовільних фіксованих стовбчиків, розбиваються наблоків, кожний з яких містить всі-вимірні двійкові комбінації.

Таблиця 1

						№ блока	:
0	0	0	1	0	1	1	0	0
0	0	1	1	1	0	1	0	1
0	1	0	0	0	0	2	0	0
0	1	1	1	0	1	2	0	1
1	0	0	0	1	1	1	1	0
1	0	1	1	0	1	1	1	1
1	1	0	0	1	1	2	1	0
1	1	1	1	1	0	2	1	1

; ,.

Рівноймовірність (збалансованість, урівноваженість) булевих відображень − .

Властивістю рівноймовірності володіють так звані лінійні функції виду , де- вектор коефіцієнтів,. Так само рівноймовірними є всі функції виду, де, які називаються афінними.

Множина афінних булевих функцій від змінних позначається через.

4.2 Нелінійність булевої функції

Нелінійність булевої функції відзмінних −,.

Нелінійність булевого відображення , визначається виходячи з властивостей нетрівіальних лінійних комбінацій виду−,,.

4.2 Перетвореняя Уоша-Адамара

Функція назівається псевдобулевою.

Перетворення Уолша-Адамара діє на булевих функціях.

Результатом перетворення булевої функції є цілочислена псевдобулева функція ,,що пов’язана з векторами значень всіх функцій виду . У кожному подібному векторі одиниці відповідають місцям неспівпадінь правої частини з правою частиною лінійної функції .

Вектор можна розглядаєти як запис деякого числа у двійковій системі счислення. У цьому контексті значення часто називається коефіціентом Уолша-Адамара функції з номером.

З урахуванням цього, . Цей вектор зазвичай записують у рядок.

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

Співставимо вектору значень булевої функції вектор цілочисленої функції, в якому , тобто нулізамінимо на, а одиниці – на. Функція часто позначається якexp.

Це дає інший запис: , який є звичайним скалярний добуток векторів і , тому .

Оскильки , то . До того ж, це число є парним.

Далі ми покажемо, що дозволяє обчислити , дета отримати суттєву інформацію про властивості параметра.

Оскільки функція - фіксована, то можна вважати, що аргументом є лінійна функція , яка задається вектором коефіціентівта уявляти значення , як деяку характеристику зв’язку між функціями і .

Таблиця 2 Функції ,, і .

0000	0	0	1
0001	0	0	0
0010	0	0	0
0011	0	0	1
0100	1	1	0
0101	1	1	1
0110	1	1	1
0111	1	1	0
1000	0	1	1
1001	0	1	1
1010	0	1	0
1011	0	1	0
1100	1	0	0
1101	1	0	0
1110	1	0	0
1111	1	0	1