Полином на Жегалкин
Полином на Жегалкин.
Представяне на булеви функции като полиноми
Как логическите функции се превеждат на езика на алгебрата чрез събиране по модул \(2\)
Полиномът на Жегалкин е едно от най-елегантните представяния на булевите функции. Вместо да описваме логическа функция чрез дизюнкция, конюнкция, отрицание, импликация и еквивалентност, я записваме като специален полином, в който участват само променливите, произведения от тях и събиране по модул \(2\). Резултатът е компактен и алгебрично удобен запис.
Темата е кръстена на руския математик Иван Иванович Жегалкин, който в началото на XX век развива алгебричен подход към логическите функции. Идеята е дълбока: логиката не е само въпрос на таблици за истинност, тя може да се изучава и чрез алгебрични структури. Освен теоретичния интерес, полиномът на Жегалкин има и пряко приложение в програмирането — операциите XOR и AND са точно събирането по модул \(2\) и умножението в тези полиноми. В криптографията линейността на полинома на Жегалкин е ключов критерий за устойчивост на криптографските функции.
\(0+0=0\), \(0+1=1\), \(1+0=1\), \(1+1=0\).
Знакът „\(+\)" в полинома на Жегалкин означава изключващо или (XOR), не обикновено събиране. От тази дефиниция следват три фундаментални правила, които се използват при всяко опростяване: \[x+x=0,\qquad 1+1=0,\qquad x\cdot x=x.\] Последното следва директно от таблицата за умножение: \(0\cdot0=0\) и \(1\cdot1=1\).
\[\overline{x}=1+x;\] \[x_1\lor x_2=x_1+x_2+x_1x_2;\] \[x_1\to x_2=1+x_1+x_1x_2;\] \[x_1\equiv x_2=1+x_1+x_2;\] \[x_1\oplus x_2\ \text{(изключващо или)}=x_1+x_2.\]
Тези формули позволяват директно да превеждаме логическите изрази на езика на полиномите. След превода полученият израз се опростява с правилата \(x+x=0\), \(1+1=0\), \(xx=x\).
Кликнете върху задача, за да видите решението.
От ред \((0,0)\): \(a_0=1\).
От ред \((0,1)\): \(a_0+a_2=1\Rightarrow 1+a_2=1\Rightarrow a_2=0\).
От ред \((1,0)\): \(a_0+a_1=0\Rightarrow 1+a_1=0\Rightarrow a_1=1\).
От ред \((1,1)\): \(a_0+a_1+a_2+a_{12}=1\Rightarrow 1+1+0+a_{12}=1\Rightarrow a_{12}=1\).
Следователно \(\boxed{f(x_1,x_2)=1+x_1+x_1x_2}\). \(\blacksquare\)
От ред \((0,0,0)\): \(a_0=0\).
От ред \((0,0,1)\): \(a_0+a_3=1\Rightarrow a_3=1\).
От ред \((0,1,0)\): \(a_0+a_2=0\Rightarrow a_2=0\).
От ред \((0,1,1)\): \(a_0+a_2+a_3+a_{23}=1\Rightarrow 0+0+1+a_{23}=1\Rightarrow a_{23}=0\).
От ред \((1,0,0)\): \(a_0+a_1=0\Rightarrow a_1=0\).
От ред \((1,0,1)\): \(a_0+a_1+a_3+a_{13}=1\Rightarrow 0+0+1+a_{13}=1\Rightarrow a_{13}=0\).
От ред \((1,1,0)\): \(a_0+a_1+a_2+a_{12}=1\Rightarrow 0+0+0+a_{12}=1\Rightarrow a_{12}=1\).
От ред \((1,1,1)\): \(a_0+a_1+a_2+a_3+a_{12}+a_{13}+a_{23}+a_{123}=0\Rightarrow 0+0+0+1+1+0+0+a_{123}=0\Rightarrow a_{123}=0\).
Следователно \(\boxed{f(x_1,x_2,x_3)=x_3+x_1x_2}\). \(\blacksquare\)
Нека \(c=x_2x_3\). Тогава: \[(a\lor b)\lor c=(x_1x_2+x_1x_3+x_1x_2x_3)\lor x_2x_3.\] Прилагаме отново \(p\lor q=p+q+pq\): \[f=x_1x_2+x_1x_3+x_1x_2x_3+x_2x_3+(x_1x_2+x_1x_3+x_1x_2x_3)x_2x_3.\] Разкриваме последния член: \[x_1x_2\cdot x_2x_3+x_1x_3\cdot x_2x_3+x_1x_2x_3\cdot x_2x_3=x_1x_2x_3+x_1x_2x_3+x_1x_2x_3.\] Три еднакви члена по модул \(2\): \(x_1x_2x_3+x_1x_2x_3+x_1x_2x_3=x_1x_2x_3\). Събираме всичко: \[f=x_1x_2+x_1x_3+x_2x_3+x_1x_2x_3+x_1x_2x_3=x_1x_2+x_1x_3+x_2x_3.\] (последните два члена се съкращават: \(x_1x_2x_3+x_1x_2x_3=0\))
Следователно \(\boxed{f(x_1,x_2,x_3)=x_1x_2+x_1x_3+x_2x_3}\). \(\blacksquare\)
Първо: \(x_1\lor x_2=x_1+x_2+x_1x_2\).
Сега \((x_1\lor x_2)\lor x_3\). При \(a=x_1+x_2+x_1x_2\), \(b=x_3\): \[f=a+b+ab=x_1+x_2+x_1x_2+x_3+(x_1+x_2+x_1x_2)x_3.\] Разкриваме: \[f=x_1+x_2+x_3+x_1x_2+x_1x_3+x_2x_3+x_1x_2x_3.\] Следователно \(\boxed{f=x_1+x_2+x_3+x_1x_2+x_1x_3+x_2x_3+x_1x_2x_3}\). \(\blacksquare\)
Едно от най-естествените приложения на полинома на Жегалкин е работата с битови операции. В повечето езици за програмиране операторите XOR и AND отговарят директно на събирането по модул \(2\) и умножението в полинома. Затова, когато една булева функция е записана в тази форма, тя може да бъде реализирана директно в код или цифрова схема.
f = (x1 AND x2) XOR (x1 AND x3) XOR (x2 AND x3)Само три AND и два XOR — без разклонения, без таблици за истинност.
В криптографията линейността на полинома на Жегалкин е ключов критерий: функция, чийто полином съдържа само линейни членове (от вида \(a_i x_i\)), е линейна и уязвима. Нелинейните членове (произведения на две или повече променливи) правят функцията устойчива срещу линейни атаки. Паритетната проверка при предаване на данни е друг пряк пример: \(p=x_1+x_2+\cdots+x_n\) проверява нечетния брой единици точно чрез полинома на Жегалкин.
Опитайте сами преди да погледнете краткия отговор.
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Софийски университет „Св. Климент Охридски“
- ›УАСГ – Университет по архитектура, строителство и геодезия
- ›Технически университет – София и др.
- ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти по всички математически дисциплини:
Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар