211
правок
Изменения
Новая страница: «Введём понятие арифметизации булевых формул. Пусть нам дана формула <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=
}}
# <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=
}}
