Изменения

# * <tex>x_i \to x_i</tex>;# * <tex>\lnot x \varphi \to 1 - xA_\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>;# <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>\phi</tex> не содержит кванторов, то <tex>|A_\phi| \le C |\phi|</tex> , где <tex>C</tex> {{---}} некоторая константа.

|proof=proofНепосредственно следует из построения.

Введем обозначениеДля арифметизации булевых формул с кванторами добавим еще два правила преобразования: * <tex>A_i\exists x \varphi(x_{i+1}x) = \to \sum\limits_{x_{i+2} x= 0}^{1}A_\ldotsvarphi(x)</tex>;* <tex>\forall x \varphi(x) \to \sumprod\limits_{x_m x= 0}^{1} AA_\varphi(c_1x)</tex>. Будем обозначать через <tex>Q_i</tex> квантор,связывающий переменную <tex>x_i</tex>. Через <tex>R_i</tex> будем обозначать операцию, в которую преобразуется квантор <tex>Q_i</tex> в процессе арифметизации. Заметим, что любую булеву формулу можно привести к виду <tex>Q_1 \ldotsQ_m \phi(x_1, c_i, x_{i+1}, ...\ldots, x_m)</tex>, где <tex>c_1, \ldots, c_iphi</tex> {{---}} некоторые константыформула, не содержащая кванторов. Кроме того, в процессе арифметизации <tex>Q_1 \ldots Q_m \phi(x_1, \ldots, x_m)</tex> переходит в <tex>R_1 \ldots R_m A_\phi(x_1, \ldots, x_m)</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>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>R_1 = \sum</tex>, то <tex>A_0(0) + A_0(1) = ks</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>.

proofДокажем пункты 1.1 и 2.1. Для остальных пунктов доказательство аналогично. 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>. 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>.