Пролог - какие предложения нельзя выразить

Мне было интересно, какие предложения нельзя выразить на Прологе? Я изучал логическое программирование в целом и узнал, что логика первого порядка более выразительна по сравнению с логикой определенных предложений (предложение Хорна), на которой основан Пролог. Мне сложно разобраться в этом вопросе.

Так, например, можно выразить следующее предложение:

For all cars, there does not exist at least 1 car without an engine

Если да, то есть ли другие предложения, которые НЕ МОГУТ быть выражены? Если нет, то почему?


logic prolog first-order-logic logic-programming
person user1280446    schedule 11.09.2012    source источник
comment
+1 Приятно знать, что другие считают это сложной темой.   -  person Guy Coder    schedule 11.09.2012

Ответы (4)


arrow_upward
3
arrow_downward

Наиболее проблемными определениями в Прологе являются те, которые являются леворекурсивными. Такие определения, как

g(X) :- g(A), r(A,X).

, скорее всего, потерпят неудачу из-за алгоритма поиска Пролога, который представляет собой простой поиск в глубину и будет работать до бесконечности и далее.

Однако общая проблема с Horn Clauses состоит в том, что они определены как содержащие не более одного положительного элемента. Тем не менее, можно найти пункт, который ограничен этими условиями, например:

A ∨ B

Как следствие, такие факты, как ∀ X: cat(X) ∨ dog(X), не могут быть выражены напрямую. Есть способы обойти их и есть способы разрешить такие утверждения (см. Ниже).

Материал для чтения:

  • Эти слайды (стр. 3) дают пример того, какое предложение вы не можете построить на Прологе.

  • Эта работа (стр. 10) также объясняет Horn Clauses и их значение и представляет метод, позволяющий разрешить «недействительные» Horn Clauses.

person nemo    schedule 11.09.2012

arrow_upward
4
arrow_downward

Вы можете прямо выразить свое предложение с помощью Пролога, используя отрицание (\+).

E.g.:

car(bmw).
car(honda).
...
car(toyota).

engine(bmw, dohv).
engine(toyota, wenkel).

no_car_without_engine:-
  \+(
    car(Car),
    \+(engine(Car, _))
  ).

Процедура no_car_without_engine/0 будет успешной, если у каждой машины есть двигатель, и неудачной в противном случае.

person gusbro    schedule 11.09.2012

arrow_upward
2
arrow_downward

Пролог - это язык программирования, а не интерфейс на естественном языке.

Предложение, которое вы показываете, выражено настолько запутанно, что мне было трудно его понять. По сути, я должен поблагодарить gusbro, который приложил все усилия, чтобы выразить это в понятной форме. Но он полностью замалчил проблемы представления знаний, которые любой язык программирования создает в применении к естественному языку, или даже просто отрицание в логике первого порядка. Эти проблемы настолько актуальны, что выбранный язык часто воспринимается как «неважный».

Что касается программирования, в Prolog отсутствует возможность доступа за O (1) (постоянное время) к любой линейной структуре данных (то есть к массивам). Тогда, например, QuickSort, который требует доступа к элементам массива в O (1), не может быть реализован эффективно.

Но, тем не менее, это полный язык Тьюринга, чего стоит. Тогда есть нет операторов, которые нельзя выразить в Прологе.

person CapelliC    schedule 11.09.2012
comment
W.r.t. QuickSort: стоит отметить, что сортировка с помощью sort/2 с самого начала была довольно эффективной операцией (например, различные сортировки Ричарда О'Кифа), тогда как сортировка на распространенных эффективных языках часто имела проблемы с производительностью - например, STL C ++ появился 10-20 лет назад. - person false; 11.09.2012
comment
вы можете использовать составные термины для моделирования массивов .arg/3 - это доступ O (1). Я думаю. - person Will Ness; 21.09.2012
comment
@Will Ness: да, SWI-Prolog имеет неограниченные сроки арности и множество других практических "приемов", необходимых для работы систем SW. Но это лишние логические особенности. - person CapelliC; 22.09.2012

arrow_upward
0
arrow_downward

Итак, вы ищете предложения, которые нельзя выразить в клаузальной логике, но которые можно выразить в логике первого порядка.

Строго говоря, их много, просто потому, что клаузальная логика является ограничением FOL. Так что это правда по определению. Что вы можете сделать, так это переписать любой набор предложений FOL в логическую программу, которая не эквивалентна, но с хорошими свойствами. Так, например, если вы хотите знать, является ли p следствием вашей теории, вы можете эквивалентным образом использовать преобразованную логическую программу.

Несколько примечаний к другим ответам:

  1. Отрицание в Прологе (\ +) - это отрицание как сбой, а не логическое отрицание первого порядка.
  2. Пролог - это язык программирования, как правильно указано, вместо этого мы должны говорить о клаузальной логике.
  3. Левая рекурсия не проблема. Вы можете легко использовать другое правило выбора или какой-либо другой механизм вывода.
person NotAUser    schedule 21.09.2012