<tex>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi(x)=0) (C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)</tex>
Если C решает SAT то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первое не удолветворяет, если наоборот то обе не удовлетворяет.
для любого fi Если <tex>C</tex> решает <tex>SAT</tex> то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первую не удолветворяет, если наоборот то обе не удовлетворяет. <tex> \forall{\varphi{}}: |fi\varphi{}|=m для любого \forall{x_1}...любого \forall{x_m } если C_m(fi\varphi{})=0 => fi\Rightarrow \varphi{(x_1)}=0 иначе C_m-1(fi\varphi|_x_1_{x_1=0})=0 => fi\Rightarrow \varphi|_x1_{x_1=0}(x2)=0</tex>
C_m-1(fi|_x1=1)=0 =>fi|_x1=0(x2)=0
C_m-1(fi|x1=0) галочка C_m-1(fi|x1=1)
