Оксана Джосан: "Задачи со второй пересдачи матем.логики" (17 февраля 2005 года)

пролог: два натуральных числа называются взаимно простыми, если они имеют в точности один общий делитель. Пара натуральных чисел (х,у) задается списком (х.у.nil). Две пары чисел, отличающиеся лишь порядком следования чисел, считаются одинаковыми. Составить логическую программу, которая для заданного натурального числа N вычисляет список Х всех неодинаковых пар взаимно простых чисел, не превосходящих N. Запрос G(N,X)

1. «Никакой белый шар, лежащий над всеми черными пирамидами, не лежит слева от черного куба, под которым лежит черная сфера»

предикаты :

S(x) – х – шар

P(x) – х – пирамида

C(x) – х – куб

W(x) – х – белый объект

B(x) – х – черный объект

U(x,y) – х лежит над у

D(x,y) – х лежит под у

L(x,y) – х лежит слева от у

R(x,y) – х лежит справа от у

2. Метод семантических таблиц

exist x all y exist z (P(x,y) -> P(y,z))

3. Любым методом проверить общезначимость

 all x (A(x) -> all y (Q(y) -> R(x,y))) & ~ all x (A(x) -> all y (B(y) -> R(x,y))) -> ~ all x (B(x) -> Q(x))

4. ? <- A(x),B(x);
   A(f(x)) <- P(x);
   A(x) <- B(y), not (P(y)), !;
   A(c) <- ;
   B(x) <- R(x);
   P(c) <- R(x), !, B(x);
   P(x) <- B(x), A(y), !;
   R(b) <- ;
5. Дать определение «равносильные формулы»
6. Что такое НОУ для двух атомов А1 и А2?Дать какой-нибудь алгоритм построения НОУ для двух атомов.
7. Что такое множество успехов для ЛП П? Как оно связано с оператором непосредственного следования?
8. Какая стратегия вычисления называется полной? Привести пример полной стратегии.