14
правок
Изменения
→Доказательство принадлежности классу NPH
Итак, опишем действия функции <tex>f</tex>.
# На первом этапевсе отрицания <tex> \neg </tex> спускаются вниз по дереву выражения, так что в формуле остаются только отрицания переменных. Булева формула превращается в логические '''И''' и '''ИЛИ''' литералов. Это преобразование дает формулу, эквивалентную исходной, и занимает время, как максимум, квадратичное относительно длины этой формулы. Для этого используются ''законы Де Моргана'' и ''закон двойного отрицания''.* <tex> \neg(x \wedge y) = \neg x \vee \neg y </tex>* <tex> \neg(x \vee y) = \neg x \wedge \neg y </tex>* <tex> \neg(\neg x) = x </tex>
