В данном примере есть только один ответ, включающий b и c. Рассмотрим пример, в котором транспортное средство может быть с мо-
тором, а может быть без мотора. При этом рассматриваем как факт, что велосипед не использует мотор.
motor(X) :- vehicle(X), not neg_motor(X). neg_motor(X) :- vehicle(X), not motor(X).
neg_motor(X) :- bike(X).
При этом заранее известна американская фирма sram, производящая велосипеды, и как новую продукцию – некое транспортное средство mulsane, производимое bentley.
vehicle(sram). bike(sram).
vehicle(mulsane). bentley(mulsane).
В результате работы граундера gringo переменным присваиваются все возможные значения, в нашем случае X присваиваются значения sram и mulsane. Получаются следующие правила.
motor(sram) :- vehicle(sram), not neg_motor(sram). motor(mulsane) :- vehicle(mulsane), not
neg_motor(mulsane).
neg_motor(sram) :- vehicle(sram), not motor(sram). neg_motor(mulsane) :- vehicle(mulsane), not
motor(mulsane).
neg_motor(sram) :- bike(sram).
neg_motor(mulsane) :- bike(mulsane).
Учитывая факты программы получаем.
motor(mulsane) :- not neg_motor(mulsane). neg_motor(mulsane) :- not motor(mulsane).
neg_motor(sram) :- bike(sram).
Таким образом, mulsane может быть как моторным, так и не моторным транспортным средством. Поэтому есть два набора ответов.
Answer: 1 vehicle(mulsane) vehicle(sram) neg_motor(sram) bike(sram) bentley(mulsane)
neg_motor(mulsane)
Answer: 2 vehicle(mulsane) vehicle(sram) neg_motor(sram) bike(sram) bentley(mulsane)
motor(mulsane)
6
В дальнейших примерах очевидные ответы будем заменять многоточи-
ем.
1.3. Использование дизъюнкции и задание альтернатив
Дизъюнкция в ASP обозначается с использованием символа «;» в голове правил и фактов.
Факт: A1; …; Am.
Правило: A1; …; Am :- L1, …, Ln.
Дизъюнкция обеспечивает, чтобы хотя бы один из атомов Ai (1 ≤ i ≤ m) был истинен. Рассмотрим программу.
a; b.
В ней будет два набора ответов: a или b. При этом решатель clasp ищет минимальную комбинацию, поэтому третий набор ответов, включающий a и b, появится только при наличии дополнительных условий.
a:- b.
b:- a.
a; b.
В указанной программе будет один набор ответов: a b.
Символ «;» может использоваться для задания альтернатив. Например, для задачи с транспортными средствами альтернативы могут быть заданы следующим образом.
vehicle((sram; mulsane)).
В данном примере дополнительные внутренние скобки могут быть опу-
щены. И результатом будет: vehicle(sram) vehicle(mulsane).
Другой пример альтернатив, в котором дополнительные скобки убирать нельзя.
values(X) :- X = (1;2;3).
Результат: values(3) values(2) values(1)
Целочисленные интервалы могут задаваться через символы «..».
values(X) :- X = 1..4.
Результат: values(1) values(2) values(3) values(4)
7
1.4. Логические константы и арифметика
Логические константы #true и #false принимают значения «истина» и «ложь». Пример их использования в программе:
#true.
not #false. not not #true. :- #false.
:- not #true.
:- not not #false.
Результат данной программы SATISFIABLE, значит все факты и ограничения целостности удовлетворены.
ASP поддерживает следующие арифметические операции: сложение «+», вычитание и унарный минус «–», умножение «*», деление «/», остаток от деления «\», модуль «|», возведение в степень «**», побитовое И «&», побитовое ИЛИ «?», побитовое исключающее ИЛИ «^», побитовое отрицание «~». Пример их использования в программе:
l(5).
r(3).
plus(L + R) :- l(L), r(R). min(L - R) :- l(L), r(R). mod(L \ R) :- l(L), r(R). abs(|-R|) :- r(R).
pow(L ** R) :- l(L), r(R).
Результат выполнения данной программы.
r(3) l(5) plus(8) min(2) mod(2) abs(3) pow(125)
ASP поддерживает операции сравнения: равно «=», неравно «!=», меньше «<», меньше либо равно «<=», больше «>», больше либо равно «>=».
1.5. Условия и условные литералы
Формат условного литерала: L0 : L1, …, Ln.
Здесь каждый Lj (0 ≤ j ≤ n) – литерал, при этом L1, …, Ln называются условием. Если n = 0 получается обычный литерал. Литерал L0 истинный, если истинны все литералы L1, …, Ln:
a :- b : c.
8
В данном примере a истинно только если либо оба b и c ложны, либо оба истинны:
r(a). r(b). r(c).
p :- q(X) : r(X).
В данном случае будет доказываться p :- q(a), q(b), q(c). Обычно условные литералы используются для объединения значений
нескольких переменных:
c(1). d(2). b(1, 2).
a :- b(X, Y) : c(X), d(Y).
В результате будет получено: c(1) d(2) b(1,2) a.
При этом условные операторы могут встречаться как в теле правила, так и в голове правила:
person(jane). person(john).
day(mon). day(tue). day(wed). day(thu). day(fri). available(jane) :- not on(fri).
available(john) :- not on(mon), not on(wed). meet :- available(X) : person(X).
on(X) : day(X) :- meet.
В данной программе два человека jane и john пытаются назначить встречу на рабочей неделе: mon, tue, wed, thu, fri. При этом jane не может встретиться в fri, а john не может в mon и wed. Встреча возможна (available), если оба в этот день могут встретиться (meet). Граундер преобразует последние два правила следующим образом:
meet:-available(jane),available(john).
on(mon);on(tue);on(wed);on(thu);on(fri):-meet.
В результате получаем два ответа (многоточием заменены очевидные факты, такие как person(jane), person(john), day(mon)…):
Answer: 1 ... on(thu)
Answer: 2 ... on(tue)
Рассмотрим программу:
person(tom; bob; alex; liza).
parent(tom, bob). parent(tom, alex). parent(bob, liza).
havechild(X) :- person(X), parent(X, _). havenotchild(X) :- person(X), #false : havechild(X).
9
Первая строка – все участники генеалогического дерева. Вторая строка – указание на родственные связи. Третья строка – правило вычисления тех, у кого есть ребенок. Четвертая строка – правило вычисления тех, у кого нет ребёнка. Условный оператор ложен (#false), если выполнилось условие havechild(X). В результате – один набор ответов.
Answer: 1 ... havechild(tom) havechild(bob)
havenotchild(alex) havenotchild(liza)
В данном случае четвертая строка может быть записана без использования условного литерала.
havenotchild(X) :- person(X), not havechild(X).
Если после условного литера следуют безусловные, то в качестве разделителя используется символ «;»:
d(1..5).
next(X,Z) :- d(X), #false : X < Y, d(Y), Y < Z;
d(Z), X < Z.
В данном примере условный литерал ложен, если между X и Z существует Y. Результат:
Answer: 1 d(1) d(2) d(3) d(4) d(5) next(1,2)
next(2,3) next(3,4) next(4,5)
Ограничения условного литерала:
1)ни одна переменная, унифицированная внутри условного литерала, не может быть использована за его пределами;
2)в первую очередь выполняется унификация переменных за пределами условного литерала, после чего унифицируются переменные условного литерала;
3)в условных литералах могут использоваться только встроенные в ASP
идоменные предикаты. К доменным предикатам относят не содержащие от-
рицаний (не содержат not) и не являющиеся агрегаторами (раздел 1.6).
1.6. Агрегаторы
Общий вид агрегатора
Агрегаторы – конструкции, которые позволяют формировать ответы из групп атомов. При этом за счёт добавления сравнений агрегаторы могут ограничивать количество полученных атомов.
Агрегатор: s1 <1 Func{ t1: L1; ...; tn: Ln } <2 s2.
10