Линейная функция дискретная математика

Линейная функция дискретная математика

Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен.

Примеры. Мажоритарная функция не является линейной: степень ее полинома Жегалкина (xy xz yz) равна 2. Из элементарных булевых функций линейными являются, например, инверсия и эквивалентность. Не являются линейными, например, штрих Шеффера и стрелка Пирса. •

Утверждение о числе булевых функций класса L. Число различных линейных булевых функций, зависящих от n переменных, равно 2 n+1 .

Доказательство. Полином Жегалкина линейной функции f(x1, …, xn) имеет вид:

где a, …, an – булевы константы. Таким образом, каждый линейный полином определяется булевым вектором a… an длины n+1, и наоборот, каждый булев вектор длины n+1 задает линейный полином Жегалкина некоторой функции n аргументов. Следовательно, число линейных полиномов (а значит, и число различных линейных функций n аргументов) равно числу булевых векторов длины n+1, то есть равно 2 n+1 . •

Пример. Из всех 16 булевых функций двух аргументов x1, x2 8 функций (2 2+1 ) принадлежат классу L: 0, 1, , , тождественные функции x1 и x2 и их инверсии x 1 и x 2. •

Теорема о замкнутости класса L. Множество всех линейных булевых функций является замкнутым классом.

Доказательство. Рассмотрим суперпозицию любых булевых функций из L, то есть функцию

и покажем, что она является линейной. Представим каждую из функций, образующих суперпозицию, полиномом Жегалкина:

Подставив эти полиномы в суперпозицию, получим:

Поскольку в последней формуле каждая скобка есть булева константа, то получен линейный полином Жегалкина. Значит, функция f(x1, …, xn) линейная, и класс L замкнут. •

Лемма о нелинейной булевой функции. Если булева функция нелинейная, то из нее подстановкой вместо аргументов констант, переменных x, y, их инверсий x , y и, возможно, инверсией самой функции можно получить конъюнкцию xy.

Доказательство. Рассмотрим полином Жегалкина нелинейной функции f(x1, …, xn). Выберем в нем конъюнкцию K ранга больше единицы (такая конъюнкция существует, так как функция нелинейна). Не умаляя общности, можно считать, что K содержит переменные x1 x2 . Разобьем множество конъюнкций полинома на четыре группы: – первую образуем из конъюнкций, содержащих x1 и x2, – вторую – из конъюнкций, содержащих x1 и не содержащих x2, – третью – из конъюнкций, содержащих x2 и не содержащих x1 – остальные конъюнкции отнесем к четвертой группе.

Читайте также:  Ошибка boot bcd 0xc0000098

В первых трех группах вынесем за скобки соответственно x1x2, x1 и x2 :

Первая группа не пуста, так как есть по крайней мере одна конъюнкция K, содержащая x1 и x2 . Значит, найдется набор a3 … an такой, что p(a3, …, an) = 1. Подставим его в функцию f(x1, …, xn) (подстановка констант допустима по условию теоремы):

где a, b, c – булевы константы.

Если a=b=c=0, конъюнкция получена. Иначе положим в последней формуле x1= x b, и x2 = y a (подстановка переменных x, y и их инверсий x 1, y 1 допустима по условию теоремы), раскроем скобки и удалим пары одинаковых конъюнкций:

Если булева константа d=0, конъюнкция xy получена. Иначе функция g(x,y)= x y. Тогда, инвертировав исходную функцию (что допустимо по условию теоремы), получим конъюнкцию xy. •

Пример. Рассмотрим нелинейную булеву функцию, заданную полиномом Жегалкина.

[ выберем первую конъюнкцию x1x2 x3x4, в ней выберем переменные x1, x2 и сгруппируем конъюнкции ]

[ p(x3,x4)=1 при x3=1, x4=0, подставим эти значения переменных в формулу ]

[ положим x1=x b = x, x2 =y a=y 1 ]

Инвертировав исходную функцию, получим конъюнкцию xy. •

x1 x2 x3 f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Такое решение:
Если выполняется условие:
f2 = АЛЬФА0 + АЛЬФА1*x1+АЛЬФА2*x2+.АЛЬФАn*xn
то функция линейная
В моем случае
АЛЬФА0 = 1
АЛЬФА1 = 1
АЛЬФА2 = 1
АЛЬФА3 = 0
f2 = 1+x1+x2(выполняется, значит линейная)

Я не пойму, что такое АЛЬФА1,АЛЬФА2, как ее находить?

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

f(000) = 1 → a₀ = 1
f(001) = 1 → a₀ + a₃ = 1 → 1 + a₃ = 1 → a₃ = 0
f(010) = 0 → a₀ + a₂ = 0 → 1 + a₂ = 0 → a₂ = 1
f(011) = 0 → a₀ + a₂ + a₃ + a₂₃ = 0 → 1 + 1 + 0 + a₂₃ = 0 → a₂₃ = 0
f(100) = 0 → a₀ + a₁ = 0 → 1 + a₁ = 0 → a₁ = 1
f(101) = 0 → a₀ + a₁ + a₃ + a₁₃ = 0 → 1 + 1 + 0 + a₁₃ = 0 → a₁₃ = 0
f(110) = 1 → a₀ + a₁ + a₂ + a₁₂ = 1 → 1 + 1 + 1 + a₁₂ = 1 → a₁₂ = 0
f(111) = 1 → a₀ + a₁ + a₂ + a₃ + a₁₂ + a₁₃ + a₂₃ + a₁₂₃ = 1 → 1 + 1 + 1 + 0 + 0 + 0 + 0 + a₁₂₃ = 1 → a₁₂₃ = 0

Читайте также:  Большая голова и маленькое тело

1) ПЖ линейной ф-ции: A0+A1x+A2y+A3z+A4j+A5k
2) ПЖ нелинейной ф-ции: A0+A1x+A2y+A3z+A4xy+A5yz+A6xz

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе все аij (j = 1, …, k) различны, aj Î <0, 1>.

Теорема. Всякую булеву функцию можно представить единственным полиномом Жегалкина.

Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.

Построить многочлен Жегалкина для функции f=10011110.

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

Шаг 1. Строим таблицу (табл. 57). Первый столбец содержит возможные слагаемые полинома Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.

Таблица 57

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 1
x3 1
x2 1
x2x3 1 1 1
x1 1 1
x1 x3 1 1 1
x1 x2 1 1 1
x1 x2 x3 1 1 1

Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g (табл. 58).

Таблица 58

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 1 1 f = 1 0 0 1 1 1 1 0
x3 1 1 1 0 1 0 0 0 1
x2 1 1 1 1 1 0 0 1
x2x3 1 1 1 0 0 1 0 1
x1 1 1 0 1 1 1
x1 x3 1 1 1 1 1 0 0
x1 x2 1 1 1 1 1 0
x1 x2 x3 1 1 1 1 1

Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.

Читайте также:  Пожар который практически невозможно потушить

Для данной функции многочлен Жегалкина имеет вид:

f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.

Определение. Функция f(x1, x2, …, xn) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x1, x2, …, xn) = a1x1 + … + anxn + an+1, где каждое ai равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = > линейных функций замкнут относительно суперпозиций.

Ссылка на основную публикацию
Кофейня форум газеты яблоко
Да, насчет цвета - я так понимаю, что у меня "двойка", т.е. светло-светло-бежевый. На самом деле он очень легко "подстраивается"...
Кодирование в различных системах счисления
Код - это набор условных сигналов для записи или передачи некоторых заранее определенных понятий. Рис. 1. Примеры систем кодирования. Любой...
Код ошибки 42 тойота
Предохранителем под капотом не получается сбросить. Подскажите кто сталкивался?yadi.sk/i/rc3fkFWcqXFzZAскан мурзилки Расшифровка кодовwww.ardio.ru/dtclib.phpИстория повторяется:На windom MCV21-2MZ неожиданно отключился спидометр, на панели...
Кофемашина для дома какую выбрать обзор
В марте 2020 лучшая по цене/качеству — Philips EP1220 Здесь я обрисую характерные особенности кофемашин начального класса популярных брендов. Замечу,...
Adblock detector