Сложность булевых функций. Аффинные и неаффинные операторы

Булевой функцией от n переменных называется функция из множества Z/ 2ⁿ Z во множество {0,1}. Для булевой формулы в базисе булевых функций B = {g₁,g₂,...} от n переменных дадим индуктивное определение:

а) каждая переменная x _i есть формула;

б) если g(x₁,...,x_n)ÎB и F₁,...,F_r суть формулы, то g(F₁,...,F_r) есть формула.

Булевы формулы дают аналитический способ задания булевых функций. Ясно, что одна и та же функция может быть записана с помощью различных фор­мул. Обычно булевы функции представляются формулами в системе операций И, ИЛИ, НЕ.

Сложностные характеристики булевых формул определяются с помощью не­скольких характеристик. Наиболее распространенными являются следующие:

L (F) - число вхождений символов переменных и констант в формулу F в не­котором базисе функций. Частным случаем L (F) является число конъюнкций в дизъюнктивной нормальной форме L (D).

L_ф(F) - число функциональных элементов в схеме, моделирующей F, с помо­щью замыкающих и размыкающих контактов.

Сложностью булевой функции f в классе формул (L (f)) называется слож­ность минимальной формулы, реализующей f. Введем понятие функции Шеннона

L (n) = max L (f)

f: Z/ 2ⁿ Z ® {0,1},

как сложности самой сложной функции, отображающей вход длиной n бит в выход длиной 1 бит.

Любой набор булевых формул можно представить в виде

у = а ₀ + а _iХ_i + а _ijХ_iХ_j + а _ijkХ_iХ_jХ_k +...+ а _12...nХ₁Х₂...Х_n ,

где х = (Х₁,Х₂,...Х_n); сложение выполняется по модулю 2. Здесь вектор а ₀ называет­ся вектором сдвига, векторы а _i задают линейную часть преобразования, а векторы а ₁₂,... а _12...n - нелинейную часть.

Наиболее простым является случай, когда нелинейные слагаемые отсутству­ют. Тогда преобразование описывается матричным уравнением, где L - невырож­денная квадратная (0,1)-матрица, у = L x + a (знак транспонирования вектора опус­кается) и называется аффинным преобразованием. Множество взаимно однознач­ных аффинных преобразований образует группу по умножению. Пусть у = L x + a, u = M у + b. Тогда u = ML x + M a + b = L’ x + a ’. Единичным элементом группы явля­ется преобразование х = Е х + 0, где Е - единичная матрица (содержит единицы на главной диагонали, остальные элементы - нулевые), 0 - нулевой вектор. К каждому взаимно однозначному аффинному преобразованию есть обратное аффинное. Если у = L x + a, то, умножая слева на L^-1, получим L^‑1 у = L^-1L x + L^-1 a. Поэтому х = L^-1 у + L^-1 a = L’ у + а ’. Заметим, что группа аффинных преобразований некоммутативна: МL ¹ LM.

Если вектор сдвига нулевой, то преобразование называется линейным. Ли­нейные и аффинные преобразования образуют подгруппы в группе всевозможных обратимых преобразований (подстановок).

Дата добавления: 2015-12-01