33
правки
Изменения
Нет описания правки
Внутри будем проверять используемый набор
<tex>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi{}(x)=0) \label{f1}\vee{}</tex> <tex>(C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)\label{f2}</tex>
Вот когда подставим x1=0 нужно будет использовать(получится более короткая формула) и используем для проверки логическую схему более короткую . Если она выдает 1 то мы опять подставляем либо 0 либо 1 и так далее. Это правильная проверка причем за полином
Если <tex>C</tex> решает <tex>SAT</tex> то все хорошо. Если нет, то зафиксируем формулу <tex>\varphi{}_0</tex>, которую он не решает. Если на этой формуле выдаст 0, а должна выдать 1, то получается что не удовлетворяет первую часть и не будет работать, если наоборот выдаст 1 а на самом деле формула не удавлетворима то обе скобки работать не будут.
Рассмотрим минимальную схему которая неправильна, тогда на той формуле, на которой эта схема неправильна. По предположению, что все более короткие формулы правильны,эта формула распознается схемами с меньшим числом входов. Поэтому эта и эта будут 0 и мы не узнаем набор схем. Можно попробовать развернуть формулу до конца. Видимо это будет выглядеть так
