Вопрос 2. Класс линейных функций

ЛИНЕЙНЫЕ БУЛЕВЫ ФУНКЦИИ

1.Полиномы Жегалкина.

2.Класс линейных функций.

Вопрос 1. Полиномы Жегалкина

Рассмотрим кольцевую сумму (операцию сложения по модулю 2 или сумму Жегалкина), которая обозначается хÅу и задается таблицей истинности:

Данная операция используется в логических функциях, называемых полиномами (многочленами) Жегалкина.

О.1.1.Полиномом (многочленом) Жегалкинаназывается многочлен, являющийся суммой константы (0 или 1) и различных одночленов, в которых все переменные входят не выше, чем в первой степени:

(1)

причем на каждом наборе (i₁,i₂,…,i_k) все i_j (j = 1,2,…,k) различны, а

Пример 1.

1.Полином Жегалкина константы равен самой этой константе.

2.Полином Жегалкина булевой функции одной переменной f(х) имеет вид

f(х) = а₀Åа₁х.

3.Полином Жегалкина булевой функции двух переменных f(х₁,х₂) имеет вид

f(х₁,х₂) = а₀Åа₁х₁Åа₂х₂Åа₁₂х₁х₂.

4.Полином Жегалкина булевой функции трех переменных f(х₁,х₂,х₃) имеет вид

f(х₁,х₂,х₃) = а₀Åа₁х₁Åа₂х₂Åа₃х₃Åа₁₂х₁х₂Åа₁₃х₁х₃Åа₂₃х₂х₃Åа₁₂₃х₁х₂х₃.

Во всех приведенных формулах коэффициенты и свободный член а₀ принимают значения 0 или 1; число слагаемых в формуле равно 2ⁿ (где n – число переменных).

Можно показать, что число полиномов Жегалкина от n переменных х₁,х₂,…,х_n, т.е. число выражений вида (1), равно Так как число булевых функций от n переменных так же равно то каждая булева функция может быть представлена полиномом Жегалкина.

T.1.1. (теорема Жегалкина)

Каждая булева функция f(х₁,х₂,…,х_n) может быть представлена в виде полинома Жегалкина и притом единственным образом (с точностью до порядка слагаемых).

Пример 2. С помощью таблицы истинности найдем полином Жегалкина для функции ͞х.

Þ ͞х = х Å 1.

Алгоритмы построения полинома Жегалкина

Известно, что любую булеву функцию, отличную от константы 0, можно представить в виде СДНФ. Сравним таблицы истинности дизъюнкции и кольцевой суммы:

Мы видим, что они отличаются только последней строкой, т.е. на наборе (11). Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю 2. Кроме того, ͞х = х Å 1. На этом основан следующий алгоритм построения полинома Жегалкина.

Первый алгоритм построения полинома Жегалкина (на основе СДНФ)

1.Находим множество тех двоичных наборов, на которых функция принимает значение 1.

2.Составляем СДНФ.

3.В СДНФ каждый знак дизъюнкции заменяем знаком суммы Жегалкина.

4.Упрощаем, если можно, полученное выражение, используя тождество

5.В полученной формуле каждое отрицание заменяем на х_i Å 1.

6.Раскрываем скобки в полученной формуле, содержащей только функции Ù, Å и константу 1.

7.Приводим подобные члены, используя тождество х_i Å х_i = 0.

Пример 3. На основе СДНФ построить полином Жегалкина для функции

Решение

Данная функция представлена в форме СДНФ.

Таким образом, имеет место представление

Второй алгоритм построения полинома Жегалкина

(с помощью метода неопределенных коэффициентов)

1.Запишем предполагаемый результат в виде выражения общего вида с неопределенными коэффициентами.

2.Составляем систему линейных уравнений относительно 2ⁿ неизвестных коэффициентов, содержащую 2ⁿ уравнений, решением которой являются коэффициенты полинома Жегалкина.

Пример 4. С помощью метода неопределенных коэффициентов построить полином Жегалкина для функции

Решение

Запишем предполагаемый результат в виде выражения общего вида с неопределёнными коэффициентами:

Для определения значений коэффициентов вычислим левую и правую части для четырех возможных наборов значений входных переменных:

f(0,0) = 1 = a Å 0 Å 0 Å 0 = a Þ a = 1.

f(0,1) = 0 = 1 Å 0 Å c Å 0 Þ 1 Å c = 0 Þ c = 1.

f(1,0) = 0 = 1 Å b Å 0 Å 0 Þ 1 Å b = 0 Þ b = 1.

f(1,1) = 1 = 1 Å 1 Å 1 Å d Þ 1 Å d = 1 Þ d = 0.

Таким образом, имеет место представление f(x₁,x₂) = 1 Å x₁ Å x₂.

Вопрос 2. Класс линейных функций

О.2.1. Полином Жегалкина называется линейным(нелинейным), если он не содержит (содержит) конъюнкции переменных.

О.2.2. Булева функция f(х₁,х₂,…,х_n) называется линейной (нелинейной), если ее полином Жегалкина является линейным (нелинейным).

Полином Жегалкина линейной функции f(х₁,х₂,…,х_n) имеет вид

a₀ Å a₁x₁ Å a₂x₂ Å …. Å a_nx_n.

Из определения полинома Жегалкина следует, что для любой булевой функции коэффициенты при переменных х₁,х₂,…,х_n и свободный член выражаются по формулам:

а₀ = f(0,0,…,0), а₁ = а₀ Å f(1,0,…,0), а₂ = а₀ Å f(0,1,…,0), …, а_n = а₀ Å f(0,0,…,1).

На этом основан алгоритм определения линейности (или нелинейности) булевой функции.

Не нашли, что искали? Воспользуйтесь поиском по сайту: