Из того факта, что задача логического вывода в пропозициональной логике является NP-полной, следует, что в наихудшем случае поиск доказательств может оказаться не более эффективным по сравнению с перебором моделей. Однако во многих практических случаях поиск доказательства может быть чрезвычайно эффективным просто потому, что в нем могут игнорироваться не относящиеся к делу (нерелевантные) высказывания, независимо от того, насколько велико их количество. Например, в приведенном выше доказательстве, ведущем к высказыванию , не упоминались высказыванияили. Их можно было не рассматривать, поскольку целевое высказывание,присутствует только в высказывании; остальные высказывания из составаприсутствуют только в ипоэтомуне имеют никакого отношения к доказательству. Те же рассуждения останутся справедливыми, если в базу знаний будет введено на миллион больше высказываний; с другой стороны, в этом случае простой алгоритм перебора строк в истинностной таблице был бы буквально подавлен из-за экспоненциального взрыва, вызванного стремительным увеличением количества моделей.

Это свойство логических систем фактически вытекает из гораздо более фундаментального свойства, называемого монотонностью. Согласно этому свойству, множество высказываний, которые могут быть получены путем логического вывода, возрастает лишь по мере добавления к базе знаний новой информации. Для любых высказываний α и β справедливо следующее:

Например, предположим, что база знаний содержит дополнительное утверждение β, согласно которому в этом экземпляре мира вампуса имеется точно восемь ям. Эти знания могут помочь агенту прийти к дополнительным заключениям, но не способны поставить под сомнение какое-либо уже сделанное заключение а, в частности вывод о том, что в квадрате [1,2] нет ямы. Монотонность означает, что правила логического вывода могут применяться каждый раз, когда в базе знаний обнаруживаются подходящие предпосылки, — полученное заключение будет следствием из данного правила, независимо от того, что еще находится в базе знаний.