Эквивалентность, допустимость и выполнимость
Прежде чем перейти к изложению подробных сведений об алгоритмах логического вывода, необходимо рассмотреть некоторые дополнительные понятия, касающиеся логического следствия. Как и само понятие следствия, эти понятия относятся ко всем формам логики, но их лучше всего показать на примере какого-то конкретного варианта логики, например пропозициональной логики.
Первым понятием является логическая эквивалентность: два высказывания, а и (3, являются логически эквивалентными, если они истинны в одном и том же множестве моделей. Это утверждение записывается как ос <=> (3. Например, можно легко показать (с помощью истинностных таблиц), что высказывания Р л Q и Q л Р логически эквивалентны; другие эквивалентности приведены в листинге 7.4. Они играют в логике практически такую же роль, какую арифметические равенства играют в обычной математике. Альтернативное определение эквивалентности является следующим: для любых двух высказываний а и (3
а = Р тогда и только тогда, когда а И (3 и (3 И а
(Еще раз напоминаем, что \= означает логическое следствие.)
Вторым понятием, которое нам потребуется, является допустимость. Высказывание допустимо, если оно истинно во всех моделях. Например, высказывание Р v -iP является допустимым. Допустимые высказывания известны также под названием тавтологий — они обязательно истинны и поэтому избыточны. Поскольку высказывание True является истинным во всех моделях, то любое допустимое высказывание логически эквивалентно True.
Для чего могут применяться допустимые высказывания? Из определения логического следствия можно вывести теорему дедукции, которая была известна еще в древней Греции:
сЖ* Для любых высказываний а и (3, а N (3, если и только если высказывание (а=>$) является допустимым.
(В упр. 7.4 предлагается доказать эту теорему.) Алгоритм логического вывода, приведенный в листинге 7.3, может рассматриваться как проверка допустимости высказывания (KB => а). И наоборот, каждое допустимое высказывание в форме импликации описывает приемлемый вариант логического вывода.
Последним понятием, которое нам потребуется, является выполнимость. Некоторое высказывание выполнимо тогда и только тогда, когда оно истинно в некоторой модели. Например, приведенная выше база знаний, {R± л R2 л R3 л RA л я5), выполнима, поскольку существует даже не одна, а три модели, в которых она истинна (см. табл. 7.2). Если некоторое высказывание а является истинным в модели л2, то для обозначения этого применяется выражение, что "т "JSk выполняет а", или что "л? является моделью а". Выполнимость можно проверить, перебирая все возможные модели до тех пор, пока не будет найдена хотя бы одна из них, которая выполняет данное высказывание. Первой задачей в пропозициональной логике, для которой было доказано, что она является NP-полной, была задача определения выполнимости высказываний.
Многие задачи в компьютерных науках в действительно представляют собой задачи определения выполнимости. Например, во всех задачах удовлетворения ограничений, приведенных в главе 5, по сути требовалось найти ответ на вопрос о том, выполнимы ли данные ограничения при некотором присваивании. Кроме того, с помощью соответствующих преобразований по методу проверки выполнимости можно решать и задачи поиска. Безусловно, что понятия допустимости и выполнимости связаны друг с другом: высказывание а является допустимым тогда и только тогда, когда высказывание -.а невыполнимо, и наоборот, высказывание а является выполнимым тогда и только тогда, когда высказывание -пос недопустимо. На этом основании может быть также получен следующий полезный результат:
& Высказывание а N Р истинно, если и только если высказывание (а л -. $) невыполнимо.
Доказательство истинности высказывания (3 на основании истинности высказывания а путем проверки невыполнимости выражения (а л -п(3) точно соответствует стандартному математическому методу доказательства путем приведения к абсурду (буквально, "доведение до абсурда" — reductio ad absurdum). Его также называют доказательством путем опровержения, или доказательством с помощью выявления противоречия. В этом методе доказательства принимается предположение, что высказывание (3 ложно, и демонстрируется, что такое предположение приводит к противоречию с известными аксиомами а. Подобное противоречие точно соответствует тому, что подразумевается под утверждением, что выражение (а л -!(3) невыполнимо.