Изменения

:*# Присутствуют одиночно стоящие переменные.:*#::Присвоим всем таким переменным значение <tex> 1 </tex>, если переменная входит без отрицания и <tex>0</tex> иначе, так как в конъюнкции они должны дать <tex>1</tex>. Заметим, что если какая-либо скобка после этого обратилась в <tex> 0 </tex>, то решения не существует. :*# Если Отсутствуют одиночно стоящих переменных в данном выражении нетстоящие переменные.:*#::Всем переменным надо присвоить значение <tex> 0 </tex> и булева формула разрешится. Это следует из того, что в каждом дизъюнкте есть хотя бы одна переменная с отрицанием, подставив в нее значение <tex>0</tex> мы получим <tex> 1</tex> в результате дизъюнкции. В итоге мы получим выражение вида: <tex>1\wedge 1 \wedge ... \wedge 1</tex>, что в результате даст нам <tex> 1</tex>. В таком случае дальнейшие шаги выполнять не нужно.

*: Идем по скобкам и выписываем все встречающиеся нам переменные, кроме тех, с которыми мы работали на предыдущем шаге. Если переменная всегда входит без отрицаний, присваиваем ей значение <tex>1</tex>, если переменная всегда входит с отрицаниями, присваиваем <tex>0</tex>. На данном шаге никакая скобка не может обратиться в <tex>0</tex>.

*:Опустим одиночно стоящие переменные и скобки, в которых значение стало равным <tex>1</tex>. Перейдём к <tex>1</tex> шагу алгоритма. По определению формы Хорна, в каждой из скобок, где мы опустили переменную не больше <tex>1</tex> переменной без отрицания. Либо какая-то из переменных внутри скобки будет иметь отрицание, т.е. при подстановке <tex>0</tex> станет равна <tex>1</tex>, либо мы рассмотрим переменную без отрицания как отдельно стоящую переменную. Значит <tex>1</tex> шаг алгоритма выполнится верно. Проделаем с полученным выражением Будем проделывать алгоритм, начиная с <tex>1</tex> шагасначала, пока <tex>1</tex> шаг не найдёт ответ.

Будем считать, что длиной формулы является количество переменных, входящих в нее и обозначим ее за <tex> n N </tex>.В каждом шаге алгоритма мы обрабатываем очередную одиночную переменную Разберём время выполнения каждого из шагов. *Первый шаг выполняется за время<tex>O(N)</tex>, равное оставшемуся количеству переменныхтак как найти одиночно стоящие переменные можно за линейный проход. А *Второй шаг выполняется за <tex>O(N)</tex>, так же чтобы как выписать, присвоить значения, можно за линейное время.*Третий шаг выполняется за <tex>O(N)</tex>, записать переменные, которые мы ещё не использовали тратится ещё столько же времениформулу для <tex>1</tex> шага можно за линейное время. Отсюда следуетВ итоге, что так как каждый из шагов выполняется за время работы квадратичное<tex>O(N)</tex>, относительно количества входящих переменныха упрощений формулы может быть не больше <tex>N</tex> раз, получается сложность <tex>O(N^2)</tex>.