Полином Жегалкина - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:36:46Z

rollbackEdits.php mass rollback

185.220.101.2 в 03:57, 1 сентября 2022

2022-09-01T03:57:41Z

176.59.16.251: /* По таблице истинности */

2019-01-07T14:27:25Z

‎По таблице истинности

91.78.213.69: /* По таблице истинности */ знак импликации вводит в заблуждение

2018-10-06T20:10:43Z

‎По таблице истинности: знак импликации вводит в заблуждение

77.234.212.37 в 12:25, 25 сентября 2018

2018-09-25T12:25:23Z

P.vasilyev: Исправлены индексы коэффициентов в построении полинома Жегалкина

2018-05-03T16:07:44Z

Исправлены индексы коэффициентов в построении полинома Жегалкина

188.242.29.236 в 12:20, 28 декабря 2017

2017-12-28T12:20:38Z

188.242.29.236 в 14:48, 27 декабря 2017

2017-12-27T14:48:41Z

Nikitaevg: /* Преобразование Мёбиуса */

2016-01-18T07:49:54Z

‎Преобразование Мёбиуса

Nikitaevg: /* Преобразование дизъюнктивной нормальной формы */ исправлено написание "Де-Морган"

2016-01-18T07:44:51Z

‎Преобразование дизъюнктивной нормальной формы: исправлено написание "Де-Морган"

← Предыдущая		Версия 16:36, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции\|функций булевой логики]]. Полином Жегалкина имеет следующий вид:		'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции\|функций булевой логики]]. Полином Жегалкина имеет следующий вид:

← Предыдущая		Версия 03:57, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции\|функций булевой логики]]. Полином Жегалкина имеет следующий вид:		'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции\|функций булевой логики]]. Полином Жегалкина имеет следующий вид:

@@ Строка 118: / Строка 118: @@
 Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:
-<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1 следовательно a_{1000} = 1</tex>
+<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1,</tex> следовательно <tex>a_{1000} = 1</tex>
-<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0 следовательно a_{0100} = 0</tex>
+<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0,</tex> следовательно <tex>a_{0100} = 0</tex>
-<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0 следовательно a_{0010} = 0</tex>
+<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0,</tex> следовательно <tex> a_{0010} = 0</tex>
-<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0 следовательно a_{0001} = 0</tex>
+<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0,</tex> следовательно <tex> a_{0001} = 0</tex>
-<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1 следовательно a_{1100} = 0</tex>
+<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1,</tex> следовательно <tex> a_{1100} = 0</tex>
-<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{1010} = 0 </tex> следовательно <tex> a_{1010} = 1</tex>
+<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{1010} = 0, </tex> следовательно <tex> a_{1010} = 1</tex>
-<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0001} \oplus a_{1001} = 0 </tex> следовательно <tex> a_{1001} = 1</tex>
+<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0001} \oplus a_{1001} = 0, </tex> следовательно <tex> a_{1001} = 1</tex>
-<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1 </tex> следовательно <tex> a_{0110} = 1</tex>
+<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1, </tex> следовательно <tex> a_{0110} = 1</tex>
-<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0 </tex> следовательно <tex> a_{0101} = 0</tex>
+<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0, </tex> следовательно <tex> a_{0101} = 0</tex>
-<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0 </tex> следовательно <tex> a_{0011} = 0</tex>
+<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0, </tex> следовательно <tex> a_{0011} = 0</tex>
-<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1 </tex> следовательно <tex> a_{1110} = 0</tex>
+<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1, </tex> следовательно <tex> a_{1110} = 0</tex>
-<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0 </tex> следовательно <tex> a_{1101} = 0</tex>
+<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0, </tex> следовательно <tex> a_{1101} = 0</tex>
-<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1 </tex> следовательно <tex> a_{1011} = 0</tex>
+<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1, </tex> следовательно <tex> a_{1011} = 0</tex>
-<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0 </tex> следовательно <tex> a_{0111} = 1</tex>
+<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0, </tex> следовательно <tex> a_{0111} = 1</tex>
-<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0 </tex> следовательно <tex> a_{1111} = 1</tex>
+<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0, </tex> следовательно <tex> a_{1111} = 1</tex>
 Таким образом, полином Жегалкина выглядит так:

@@ Строка 118: / Строка 118: @@
 Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:
-<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1 \Rightarrow a_{1000} = 1</tex>
+<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1 следовательно a_{1000} = 1</tex>
-<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0 \Rightarrow a_{0100} = 0</tex>
+<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0 следовательно a_{0100} = 0</tex>
-<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0 \Rightarrow a_{0010} = 0</tex>
+<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0 следовательно a_{0010} = 0</tex>
-<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0 \Rightarrow a_{0001} = 0</tex>
+<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0 следовательно a_{0001} = 0</tex>
-<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1 \Rightarrow a_{1100} = 0</tex>
+<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1 следовательно a_{1100} = 0</tex>
-<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{1010} = 0 \Rightarrow a_{1010} = 1</tex>
+<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{1010} = 0 </tex> следовательно <tex> a_{1010} = 1</tex>
-<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0001} \oplus a_{1001} = 0 \Rightarrow a_{1001} = 1</tex>
+<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0001} \oplus a_{1001} = 0 </tex> следовательно <tex> a_{1001} = 1</tex>
-<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1 \Rightarrow a_{0110} = 1</tex>
+<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1 </tex> следовательно <tex> a_{0110} = 1</tex>
-<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0 \Rightarrow a_{0101} = 0</tex>
+<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0 </tex> следовательно <tex> a_{0101} = 0</tex>
-<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0 \Rightarrow a_{0011} = 0</tex>
+<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0 </tex> следовательно <tex> a_{0011} = 0</tex>
-<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1 \Rightarrow a_{1110} = 0</tex>
+<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1 </tex> следовательно <tex> a_{1110} = 0</tex>
-<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0 \Rightarrow a_{1101} = 0</tex>
+<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0 </tex> следовательно <tex> a_{1101} = 0</tex>
-<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1 \Rightarrow a_{1011} = 0</tex>
+<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1 </tex> следовательно <tex> a_{1011} = 0</tex>
-<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0 \Rightarrow a_{0111} = 1</tex>
+<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0 </tex> следовательно <tex> a_{0111} = 1</tex>
-<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0 \Rightarrow a_{1111} = 1</tex>
+<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0 </tex> следовательно <tex> a_{1111} = 1</tex>
 Таким образом, полином Жегалкина выглядит так:

@@ Строка 222: / Строка 222: @@
 в четвёртом —
-<tex> a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1)  \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1), </tex>
+<tex> a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1)  \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,0,1) \oplus P(0,1,1), </tex>
 и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.

@@ Строка 1: / Строка 1: @@
 '''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
-<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0}  x_2 \oplus \ldots \oplus a_{00\ldots01}  x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11..1} x_1 x_2 \ldots x_n  </tex>
+<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0}  x_2 \oplus \ldots \oplus a_{00\ldots01}  x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11\ldots1} x_1 x_2 \ldots x_n  </tex>
 == Полнота ==
@@ Строка 17: / Строка 17: @@
 {| class="wikitable"  style="width:8cm" border="1"
 |-align="center" bgcolor=#EEEEFF
-  !<tex>x_0</tex>||<tex>x_1</tex>||<tex>\dots</tex>||<tex>x_n</tex>
+  !<tex>x_0</tex>||<tex>x_1</tex>||<tex>\ldots</tex>||<tex>x_n</tex>
 |<tex>1</tex>||<tex>\land</tex>||<tex>\oplus</tex>
 |-align="center"
-  !<tex>0</tex>||<tex>0</tex>||<tex>\dots</tex>||<tex>0</tex>
+  !<tex>0</tex>||<tex>0</tex>||<tex>\ldots</tex>||<tex>0</tex>
 |<tex>1</tex>||<tex>0</tex>||<tex>0</tex>
 |-align="center"
-  !<tex>1</tex>||<tex>0</tex>||<tex>\dots</tex>||<tex>0</tex>
+  !<tex>1</tex>||<tex>0</tex>||<tex>\ldots</tex>||<tex>0</tex>
 |<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
 |-align="center"
@@ Строка 29: / Строка 29: @@
 |<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
 |-align="center"
-  !<tex>1</tex>||<tex>1</tex>||<tex>\dots</tex>||<tex>1</tex>
+  !<tex>1</tex>||<tex>1</tex>||<tex>\ldots</tex>||<tex>1</tex>
 |<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
 |-align="center"
@@ Строка 66: / Строка 66: @@
 === По таблице истинности ===
-Пусть для функции <tex>f(x_1,x_2,\dots,x_n)</tex>  задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.
+Пусть для функции <tex>f(x_1,x_2,\ldots,x_n)</tex>  задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.
 '''Пример:'''
@@ Строка 199: / Строка 199: @@
 === Метод треугольника === <!-- Да, копипаста с википедии, и что? Метод же прост и удобен -->
 Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
-# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000\dots00</tex> до <tex>111\dots11</tex>.
+# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000\ldots00</tex> до <tex>111\ldots11</tex>.
 # Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
 # Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
@@ Строка 230: / Строка 230: @@
 Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
-Пусть <tex> i = (i_1, i_2, .. i_n), \;\; i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i_k} \sim \left\{\begin{matrix} x, \;\; i_k=1
+Пусть <tex> i = (i_1, i_2, \ldots i_n), \;\; i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i_k} \sim \left\{\begin{matrix} x, \;\; i_k=1
 \\ 1, \;\; i_k=0
 \end{matrix}\right. </tex>
 Тогда полином Жегалкина можно записать как:
-<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot</tex><tex>\dots</tex><tex>\cdot x_n^{i_n}</tex>, где   <tex>\alpha_i \in  \{ 0; 1 \}</tex>.
+<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot</tex> <tex>\ldots</tex> <tex>\cdot x_n^{i_n}</tex>, где   <tex>\alpha_i \in  \{ 0; 1 \}</tex>.
-Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, \dots i_n)</tex>, то есть <tex>\alpha: i \mapsto \alpha_i</tex>.
+Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, \ldots i_n)</tex>, то есть <tex>\alpha: i \mapsto \alpha_i</tex>.
-Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; </tex> если <tex> \;\; i_1] \cdot [x_2 , \; </tex> если <tex> \;\; i_2] \cdot</tex><tex>\dots</tex><tex>\cdot [x_n , \; </tex> если <tex> \;\; i_n]</tex>.
+Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; </tex> если <tex> \;\; i_1] \cdot [x_2 , \; </tex> если <tex> \;\; i_2] \cdot</tex> <tex>\ldots</tex> <tex>\cdot [x_n , \; </tex> если <tex> \;\; i_n]</tex>.
 Тут запись <tex>[x_k , \; </tex> если <tex> \; i_k]</tex> означает, что элелемент <tex> x_k </tex> присутствует в соответствующем члене полинома только если <tex> i_k = 1 </tex>.
-Тогда если для какого-то <tex>x</tex>, <tex>i \succ x</tex>* ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.
+Тогда если для какого-то <tex>x</tex>, <tex>i \succ x*</tex> ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.
 Отсюда ясно, что <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i </tex>&nbsp; <tex> (2) </tex>
 Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).
@@ Строка 250: / Строка 250: @@
 {{Теорема
 |statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_x </tex> можно найти по формуле: <tex>\alpha_x = \bigoplus \limits_{j\preceq  x} f(j)</tex> &nbsp; &nbsp; <tex> (3) </tex>.
-||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+</tex><tex>\dots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.
+||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+</tex><tex>\ldots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.
 '''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha_0 </tex>

@@ Строка 1: / Строка 1: @@
 '''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
-<tex>P = a_{000...000} \oplus a_{100...0} x_1 \oplus a_{010...0}  x_2 \oplus ... \oplus a_{00...01}  x_n \oplus a_{110...0} x_1 x_2 \oplus ... \oplus a_{00...011} x_{n-1} x_n \oplus ... \oplus a_{11..1} x_1 x_2 ... x_n  </tex>
+<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0}  x_2 \oplus \ldots \oplus a_{00\ldots01}  x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11..1} x_1 x_2 \ldots x_n  </tex>
 == Полнота ==
@@ Строка 32: / Строка 32: @@
 |<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
 |-align="center"
-  !colspan="4"|Сохраняет 0
+  !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 0]]
 |<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
 |-align="center"
-  !colspan="4"|Сохраняет 1
+  !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 1]]
 |<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
 |-align="center"
-  !colspan="4"|Самодвойственная
+  !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Самодвойственная]]
 |<tex>0</tex>||<tex>0</tex>||<tex>0</tex>
 |-align="center"
-  !colspan="4"|Монотонная
+  !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Монотонная]]
 |<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
 |-align="center"
-  !colspan="4"|Линейная
+  !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Линейная]]
 |<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
 |}
@@ Строка 264: / Строка 264: @@
 Видно, что <tex> (2) </tex> и <tex> (3) </tex> — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
 == Источники информации ==

@@ Строка 256: / Строка 256: @@
 '''2)''' Пускай теорема справедлива для всех сумм <tex>wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>wt(x) = k</tex>. По <tex> (2) </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i = \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ] \oplus \alpha_x</tex> .
-Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ]  </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \prec x </tex>, и для фиксированных <tex> j</tex> и <tex> x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \prec i \prec x</tex>. Несложно увидеть, что таких <tex> i </tex> существует ровно <tex> 2^{wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ] =  \bigoplus \limits_{j\prec  x} f(j) </tex>.
+Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ]  </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \prec x </tex>, и для фиксированных <tex> j</tex> и <tex> x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \preceq i \prec x</tex>. Несложно увидеть, что таких <tex> i </tex> существует ровно <tex> 2^{wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq  i} f(j) \right ] =  \bigoplus \limits_{j\prec  x} f(j) </tex>.
 Но тогда <tex> f(x) = \left [ \bigoplus \limits_{j\prec  x} f(j) \right ] \oplus \alpha_x \Leftrightarrow f(x) \oplus \bigoplus \limits_{j\prec  x} f(j) = \alpha_x \Leftrightarrow \alpha_x = \bigoplus \limits_{j\preceq  x} f(j)</tex>.
 То есть при <tex>wt(x) = k</tex> формула также выполняется, значит при любых <tex> x </tex>  выполняется <tex>\alpha_x = \bigoplus \limits_{j\preceq  x} f(j)</tex>.

@@ Строка 153: / Строка 153: @@
 === Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]] ===
-Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
+Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило де Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
 <tex> A \lor B = AB \oplus A \oplus B </tex> &nbsp; <tex> (1) </tex>.