Какова разница между моделью и наименьшей моделью в программировании набора ответов?

Question

Я беру урок искусственного интеллекта, и мы работаем с Программой набора ответов (Clingo, в частности). В данный момент мы говорим в основном о теории, и у меня возникли проблемы с разграничением моделей и моделей с наименьшим количеством моделей. У меня есть следующие определения:

Удовлетворяющие правила, модели, наименьшие модели и наборы ответов определенной программы

1. Программа называется определенной, если она не имеет "не" в теле своих правил.
2. Говорят, что множество S удовлетворяет правилу вида a:- b1, …, bm, а не c1, …, не cn. если его тело удовлетворяется S (т. е. b1... bm находятся в S и ни один из c1 ... cn не находится в S), это означает, что его голова должна быть удовлетворена S (т.е.... a находится в S).
3. Говорят, что множество S удовлетворяет программе, если оно удовлетворяет всем правилам этой программы.
4. Множество S называется набором ответов определенной программы P, если (a) S удовлетворяет P (также называемому S - модель P) и (b) Ни одно строгое подмножество S не удовлетворяет P (то есть S является наименьшая модель П).

С вопросом (вытащил из слайдов лекции, а не домашнее задание):

P is defined as:
a :- b,e.
b. 
c :- d,b.
d.

Which of the following are models and least models?
{}, {b}, {b,d}, {b,d,c}, {b,d,c,e}, {b,d,c,e,a}

Кто-нибудь может дать мне знать, каков ответ на поставленный выше вопрос? Я могу, вероятно, выяснить разницу оттуда, хотя, если бы кто-то мог объяснить разницу в общении (а не в определении из учебника), это было бы замечательно. Я не уверен, на каком форуме размещать этот вопрос - пожалуйста, дайте мне знать, если он должен быть размещен где-то еще.

Спасибо

Answer 1

Прежде всего, обратите внимание, что в этом разделе ваших слайдов говорится о наборе ответов положительной программы P (также называемой определенной программой), хотя в ней также не упоминается. Положительная программа - это простой случай, так как для положительной программы P всегда существует уникальная наименьшая модель LM (P), которая является пересечением всех ее моделей.

Отсутствие правил в органах правил усложняет ситуацию. Тело правила является правой стороной :-,

Ответ на вопрос будет задан набором:

• S = {} не является моделью, так как b и d являются фактами b. d.
• S={b} не является моделью, так как d является фактом d.
• S={b,d} не является моделью, поскольку c подразумевается c :- d,b. и с не в S
• S = {b, d, c} - модель
• S={b,d,c,e} не является моделью, поскольку a подразумевается a :- b,e. и не в S
• S = {b, d, c, e, a} является моделью

Так какая модель меньше всего? Это S={b,c,d}, поскольку ни одно строгое подмножество S не удовлетворяет P.

Мы можем прийти к наименьшей модели положительной программы P двумя способами:

• Перечислите все модели и возьмите их пересечение (здесь {b,c,d}∩{a,b,c,d,e}={b,c,d}).
• Начиная с фактов (здесь b. d.) и итеративное добавление подразумеваемых атомов (здесь c :- b,d.) к S, повторяя до тех пор, пока S не станет моделью и остановившись в этой точке.

Как показывают ваши слайды, определение набора ответов для положительной программы P таково: S - это набор ответов P, если S - наименьшая модель P. Чтобы быть более строгим, это на самом деле тогда и только тогда, когда наименьшая модель LM (P) уникальна.

Как последнее замечание, чтобы вы не смутили их позже, ограничение :- a, b на самом деле просто стенография для x :- not x, a, b, Таким образом, программы, содержащие ограничения, не являются положительными программами; хотя на первый взгляд они могут выглядеть так, как они есть, поскольку тело ограничения, по-видимому, не содержит not.