Арифметизация булевых формул с кванторами - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:13:03Z

rollbackEdits.php mass rollback

94.16.121.91 в 05:55, 1 сентября 2022

2022-09-01T05:55:25Z

Kirelagin в 09:33, 4 июня 2012

2012-06-04T09:33:16Z

AndrewD в 01:43, 4 июня 2012

2012-06-04T01:43:59Z

Байдаров Андрей в 20:41, 2 июня 2012

2012-06-02T20:41:52Z

AndrewD в 20:36, 2 июня 2012

2012-06-02T20:36:00Z

AndrewD в 20:36, 1 июня 2012

2012-06-01T20:36:44Z

AndrewD в 15:58, 1 июня 2012

2012-06-01T15:58:07Z

AndrewD в 14:41, 1 июня 2012

2012-06-01T14:41:54Z

Байдаров Андрей: Новая страница: «Введём понятие арифметизации булевых формул. Пусть нам дана формула \phi(x_1 \ldots x_m). С...»

2012-06-01T14:00:21Z

Новая страница: «Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. С...»

Новая страница

Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:
# <tex> x_i \to x_i</tex>;
# <tex> \lnot x \to 1 - x</tex>;
# <tex>\Phi \land \Psi \to A_\Phi \cdot A_\Psi</tex>;
# <tex>\Phi \lor \Psi \to 1 - (1 - A_\Phi) \cdot (1 - A_\Psi)</tex>.
Заметим, что длина формулы при этом возрастёт не более, чем в константу раз.

{{Лемма
|about=1
|statement=<tex>\phi(x_1 \ldots x_m) = A_\phi(x_1, \ldots, x_m)</tex>.
|proof=
}}

← Предыдущая		Версия 16:13, 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 Майкл Наки].
−	\|}
−
	Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:		Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:
	* <tex>x_i \to x_i</tex>;		* <tex>x_i \to x_i</tex>;

← Предыдущая		Версия 05:55, 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 Майкл Наки].
		+	\|}
		+
	Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:		Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:
	* <tex>x_i \to x_i</tex>;		* <tex>x_i \to x_i</tex>;

@@ Строка 1: / Строка 1: @@
 Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:
 * <tex>x_i \to x_i</tex>;
-* <tex>\lnot x \to 1 - x</tex>;
+* <tex>\lnot \varphi \to 1 - A_\varphi</tex>;
 * <tex>\varphi \land \psi \to A_\varphi \cdot A_\psi</tex>;
 * <tex>\varphi \lor \psi \to 1 - (1 - A_\varphi) \cdot (1 - A_\psi)</tex>;

← Предыдущая		Версия 01:43, 4 июня 2012
Строка 41:		Строка 41:

	2.1. <tex>A_{i-1}(c_i)=\sum\limits_{x_{i+1} = 0}^{1}R_{i+2}\ldots R_m</tex><tex>(c_1, \ldots, c_{i-1}, c_i, x_{i+1}, \ldots x_m)=R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 0, x_{i+2}, \ldots, x_m) + R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 1, x_{i+2}, \ldots, x_m)=A_i(0) + A_i(1)</tex>.		2.1. <tex>A_{i-1}(c_i)=\sum\limits_{x_{i+1} = 0}^{1}R_{i+2}\ldots R_m</tex><tex>(c_1, \ldots, c_{i-1}, c_i, x_{i+1}, \ldots x_m)=R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 0, x_{i+2}, \ldots, x_m) + R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 1, x_{i+2}, \ldots, x_m)=A_i(0) + A_i(1)</tex>.
		+	}}
		+	{{Определение
		+	\|definition=
		+	Оператором линеаризации будем называть оператор <tex>L_{i}A(x_i)=(1-x_i) \cdot A</tex><tex>(0)+x_i \cdot A(1)</tex>.
		+	}}
		+	Заметим, что оператор линеаризации уменьшает степень <tex>x_i</tex> до единицы, при этом полученная формула эквивалентна исходной. Кроме того, если дано выражение <tex>R_1 \ldots R_m A_\phi(x_1, \ldots, x_m)</tex>, то <tex>L_{i}</tex> можно вставить в список <tex>R_1,\ldots,R_m</tex> в любое место, после операции <tex>R_i</tex> (для того, чтобы выражение, на которое действует оператор, было функцией от <tex>x_i</tex>). При этом значение выражения не изменится. Операторы <tex>L_i</tex> и <tex>L_j</tex> можно вставлять в выражение независимо друг от друга для любых <tex>1 \le i, j \le m</tex>. Для оператора линеаризации можно сформулировать лемму, аналогичную лемме (2).
		+	{{Лемма
		+	\|about=3
		+	\|statement=
		+	Пусть <tex>Q_1 \ldots Q_m \phi(x_1, \ldots, x_m)</tex> {{---}} булева формула с кванторами, переходящая в процессе арифметизации в <tex>s = R_1 \ldots R_m A_\phi(x_1, \ldots, x_m)=R_1 \ldots R_{i+1} L_j R_{i+2}\ldots R_m A_\phi(x_1, \ldots, x_m)</tex>, <tex>j < i + 2</tex>.
		+
		+	<tex>c_1, \ldots, c_m</tex> {{---}} двоичные константы.
		+
		+	<tex>A_{i}'(x_1,\ldots,x_{i+1}) = L_j R_{i+2} \ldots R_m A_\phi(x_1, \ldots, x_m)</tex>
		+
		+	<tex>A_{i}(x_1,\ldots,x_{i+1}) = R_{i+2} \ldots R_m A_\phi(x_1, \ldots, x_m)</tex>
		+
		+	Тогда
		+
		+	<tex>A_i'(c_1,\ldots,c_{i+1}) = (1-c_j) \cdot A_i</tex><tex>(c_1,\ldots,c_{j-1},0,c_{j+1},\ldots,c_{i+1}) + c_j \cdot A_i(c_1,\ldots,c_{j-1},1,c_{j+1},\ldots,c_{i+1})</tex>.
	}}		}}

@@ Строка 10: / Строка 10: @@
 |about=1
 |statement=<tex>\phi(x_1 \ldots x_m) = A_\phi(x_1, \ldots, x_m)</tex>.
-|proof=
+|proof=Непосредственно следует из построения.
 }}
@@ Строка 39: / Строка 38: @@
 Докажем пункты 1.1 и 2.1. Для остальных пунктов доказательство аналогично.
-.1. <tex>s=\sum\limits_{x_1 = 0}^{1}R_2\ldots R_m(x_1, x_2, \ldots, x_m)=R_2 \ldots R_m</tex><tex>(0, x_2, \ldots, x_m) + R_2 \ldots R_m(1, x_2, \ldots, x_m)=A_0(0) + A_0(1)</tex>
+.1. <tex>s=\sum\limits_{x_1 = 0}^{1}R_2\ldots R_m(x_1, x_2, \ldots, x_m)=R_2 \ldots R_m</tex><tex>(0, x_2, \ldots, x_m) + R_2 \ldots R_m(1, x_2, \ldots, x_m)=A_0(0) + A_0(1)</tex>.
-.1. <tex>A_{i-1}(c_i)=\sum\limits_{x_{i+1} = 0}^{1}R_{i+2}\ldots R_m</tex><tex>(c_1, \ldots, c_{i-1}, c_i, x_{i+1}, \ldots x_m)=R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 0, x_{i+2}, \ldots, x_m) + R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 1, x_{i+2}, \ldots, x_m)=A_i(0) + A_i(1)</tex>
+.1. <tex>A_{i-1}(c_i)=\sum\limits_{x_{i+1} = 0}^{1}R_{i+2}\ldots R_m</tex><tex>(c_1, \ldots, c_{i-1}, c_i, x_{i+1}, \ldots x_m)=R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 0, x_{i+2}, \ldots, x_m) + R_{i+2} \ldots R_m</tex><tex>(c_1, \ldots, c_i, 1, x_{i+2}, \ldots, x_m)=A_i(0) + A_i(1)</tex>.
 }}

@@ Строка 25: / Строка 25: @@
 |about=2
 |statement=
-Пусть <tex>Q_1 \ldots Q_m \phi(x_1, \ldots, x_m)</tex> {{---}} булева формула с кванторами, переходящая в процессе арифметизации в <tex>s = R_1 \ldots R_m A_\phi(x_1, \ldots, x_m)</tex>. <tex>c_1, \ldots, c_m</tex> {{---}} двоичные константы. Обозначим через <tex>A_i(x_{i+1}) = R_{i+2} \ldots R_m A_\phi(c_1, \ldots, c_i, x_{i+1}, \ldots, x_m)</tex>, где <tex>0 \le i \le m - 1</tex>. Тогда:
+Пусть <tex>Q_1 \ldots Q_m \phi(x_1, \ldots, x_m)</tex> {{---}} булева формула с кванторами, переходящая в процессе арифметизации в <tex>s = R_1 \ldots R_m A_\phi(x_1, \ldots, x_m)</tex>.
-# Если <tex>R_1 = \sum</tex>, то <tex>A_0(0) + A_0(1) = s</tex>, если <tex>R_1 = \prod</tex>, то <tex>A_0(0) \cdot A_0(1) = s</tex>.
-# <tex>\forall i : 1 \le i \le m - 1</tex> если <tex>R_{i+1} = \sum</tex>, то <tex> A_i(0) + A_i(1) = A_{i-1}(c_i)</tex>, если <tex>R_{i+1} = \prod</tex>, то <tex>A_i(0) \cdot A_i(1) = A_{i-1}(c_i)</tex>.
+<tex>c_1, \ldots, c_m</tex> {{---}} двоичные константы.
 |proof=
-proof
+Докажем пункты 1.1 и 2.1. Для остальных пунктов доказательство аналогично.
 }}

@@ Строка 1: / Строка 1: @@
 Введём понятие арифметизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_m)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_m)</tex>:
-# <tex>x_i \to x_i</tex>;
+* <tex>x_i \to x_i</tex>;
-# <tex>\lnot x \to 1 - x</tex>;
+* <tex>\lnot x \to 1 - x</tex>;
-# <tex>\varphi \land \psi \to A_\varphi \cdot A_\psi</tex>;
+* <tex>\varphi \land \psi \to A_\varphi \cdot A_\psi</tex>;
-# <tex>\varphi \lor \psi \to 1 - (1 - A_\varphi) \cdot (1 - A_\psi)</tex>;
+* <tex>\varphi \lor \psi \to 1 - (1 - A_\varphi) \cdot (1 - A_\psi)</tex>;
-# <tex>\exists x \varphi(x) \to \sum\limits_{x=0}^{1} A_\varphi(x)</tex>;
-# <tex>\forall x \varphi(x) \to \prod\limits_{x=0}^{1} A_\varphi(x)</tex>.
+Заметим, что <tex>|A_\phi| \le C |\phi|</tex> , где <tex>C</tex> {{---}} некоторая константа.
 {{Лемма
@@ Строка 15: / Строка 14: @@
 }}
-Введем обозначения:
+Для арифметизации булевых формул с кванторами добавим еще два правила преобразования:
-* <tex>Q_i = \sum\limits_{x_i = 0}^{1}</tex> или <tex>Q_i = \prod\limits_{x_i = 0}^{1}</tex>
+* <tex>\exists x \varphi(x) \to \sum\limits_{x=0}^{1} A_\varphi(x)</tex>;
-* <tex>s = Q_1 \ldots Q_m A(x_1, \ldots, x_m)</tex>
+* <tex>\forall x \varphi(x) \to \prod\limits_{x=0}^{1} A_\varphi(x)</tex>.
-* <tex>A_i(x_{i+1}) = Q_{i + 2} \ldots Q_m A(c_1,\ldots, c_i, x_{i+1}, ..., x_m)</tex>, где <tex>c_1, \ldots, c_i</tex> {{---}} двоичные константы.
 {{Лемма
 |about=2
 |statement=
-При введенных выше обозначениях выполняются:
+Пусть <tex>Q_1 \ldots Q_m \phi(x_1, \ldots, x_m)</tex> {{---}} булева формула с кванторами, переходящая в процессе арифметизации в <tex>s = R_1 \ldots R_m A_\phi(x_1, \ldots, x_m)</tex>. <tex>c_1, \ldots, c_m</tex> {{---}} двоичные константы. Обозначим через <tex>A_i(x_{i+1}) = R_{i+2} \ldots R_m A_\phi(c_1, \ldots, c_i, x_{i+1}, \ldots, x_m)</tex>, где <tex>0 \le i \le m - 1</tex>. Тогда:
-# Если <tex>Q_1 = \sum\limits_{x_1 = 0}^{1}</tex>, то <tex>A_0(0) + A_0(1) = s</tex>, если <tex>Q_1 = \prod\limits_{x_1 = 0}^{1}</tex>, то <tex>A_0(0) \cdot A_0(1) = s</tex>
+# Если <tex>R_1 = \sum</tex>, то <tex>A_0(0) + A_0(1) = s</tex>, если <tex>R_1 = \prod</tex>, то <tex>A_0(0) \cdot A_0(1) = s</tex>.
-# Если <tex>Q_i = \sum\limits_{x_i = 0}^{1}</tex>, то <tex> A_i(0) + A_i(1) = A_{i-1}(c_i)</tex>
+# <tex>\forall i : 1 \le i \le m - 1</tex> если <tex>R_{i+1} = \sum</tex>, то <tex> A_i(0) + A_i(1) = A_{i-1}(c_i)</tex>, если <tex>R_{i+1} = \prod</tex>, то <tex>A_i(0) \cdot A_i(1) = A_{i-1}(c_i)</tex>.
 |proof=
 proof
 }}