задачи2004 (Экзаменационные варианты)

Математическая Логика.

Задачи с экзамена.

2004 г.

Тип 0 (составление логической программы)

День 1:

Слово – конечный непустой список букв фиксированного конечного алфавита. Текст – конечный непустой список слов. Построить логическую программу, которая …

1. … для заданного текста L вычисляет одно из слов X, имеющее максимальную длинну среди всех тех слов текста L, которые встречаются в нем наиболее часто. Запрос к программе должен иметь вид ?C(L, X).

1. … для заданных текстов L1 и L2 вычисляет одно из слов X, содержащееся в тексте L1 и имееющее своим префиксом одно из слов максимальной длинны из текста L2. Запрос к программе должен иметь вид ?D(L1, L2, X).

1. … для заданных текстов L1 и L2 вычисляет суммарное количество X вхождений в текст L1 всех наиболее часто встречающихся слов из текста L2. Запрос к программе должен иметь вид ?E(L1, L2, X).

1. … для заданных текстов L1 и L2 вычисляет одно из слов, содержащееся в тексте L2 такое, что частота его вхождения L2 больше частоты его вхождения в L1. Запрос к программе должен иметь вид ?E(L1, L2, X).

День 2:

Построить логическую программу, которая …

1. … для двух заданных конечных последовательностей натуральных чисел, представленных списками L1 и L2, вычисляет наименьшее из чисел X, которые являются элементами L1 и превосходят любой элемент последовательности L2. Запрос к программе должен должен иметь вид ?G(L1,L2,X).

1. … для заданной конечной последовательности натуральных чисел L вычисляет сумму X всех тех элементов L, квадрат которых превосходит среднее арифметическое всех элементов последовательности L. Запрос к программе должен должен иметь вид ?G(L,X).

1. …для двух заданных конечных последовательностей натуральных чисел, представленных списками L1 и L2, вычисляет бесповторный список L3 из всех элементов последовательности L1, которые не превосходят наименьшего элемента последовательности L2. Запрос к программе должен иметь вид ?G(L1, L2, L3).

День 3:

Гибрид двух слов - это слово, составленное конкатенацией любого непустого префикса одного слова и непустого суффикса другого Построить логическую программу, которая …

1. …для заданного непустого текста L, строит число слов Х из списка L, являющихся гибридами двух других слов из этого списка. Запрос к программе должен иметь вид ?G(L, X).

1. …для заданных текстов L1, L2 строит список L3 тех слов, которые являются гибридами слов из списка L1 и не содержатся в списке L2. Запрос к программе должен иметь вид ?G(L1, L2, L3).

Тип 1 (построение предиката по утверждению)

Используя константные, функциональные и предикатные символы алфавита (указан в приложении), построить замкнутую формулу логики предикатов, соответствующую следующему утверждению:

1. “Какова бы ни была последовательность действительных чисел и отрезок [a,b] действительных чисел, если бесконечно много элементов этой последовательности содержиться в данном отрезке, то хотя бы одна предельная точка данной последовательности также сожержится в этом отрезке”.

1. “Какова бы ни была последовательность действительных чисел, найдется отрезок, содержащий все ее предельные точки”.

1. “Каков бы ни был отрезок [a,b] действительных чисел, если почти все элементы произвольной последовательности действительных чисел лежат вне этого отрезка, то и все предельные точки этой последовательности лежат вне этого отрезка”.

1. “Какова бы ни была последовательность действительных чисел, если эта последовательность содержит отрицательный элемент, то найдется хотя бы одна неположительная предельная точка этой последовательности.“

1. “Каковы бы ни были две последовательности действительных чисел такие, что первая одна из них → 0, а другая ограничена, тогда из произведение тоже → 0”.

1. “Нет такой сходящейся последовательности, что ее нельзя было бы представить как сумму двух сходящихся последовательностей”.

Приложение:

* почти все = все, кроме конечного числа;

Доступные предикаты:

R(x) - вещественное число;

N(x) - натуральное число;

S(y) - y - последовательность действительных чисел;

E(x,n,y) - x - элемент y с номером n;

A(p,y) - p - предельная точка последовательности y;

M(x, y) – x – предел последовательности y;

x < y, x = y – сравнение и равенство.

Тип 2 (метод семантических таблиц)

С помощью метода семантических таблиц установить, общезначима ли формула:

1. x y (P(x) → R(y)) → ( y P(y) → x  R(x)).

1. ( y P(y) → x R(x)) → x y (P(x) → R(y)).

1. x y (P(x) → R(y)) → ( y P(y) → x R(x)).

1. ( y P(y) x R(x)) → x (P(x) → R(x)).

1. ( y Q(y) → x P(x)) → x (P(x) Q(x)).

1. ( x R(x) & y (P(y) → R(y))) → x  P(x)).

1. ( y Q(y) x P(x)) → x (P(x) Q(x)).

1. ( y P(y) → x R(x)) → x y (P(x) → R(y)).

1. ( y P(y) → x R(x)) → x y (P(x) R(y)).

Тип 3 (метод резолюций)

С помощью метода резолюций исследовать на противоречивость систему дизъюнктов S.

1. S = { P(y, z) R(x, b);

Q(b, x) P(z, y);

R(c, x) P(x, g(y));

Q(y, y) P(x, g(y));

P(x, y) Q(f(x), y)

}.

2. S= { A(v, c) B(u, w);

B(u, w) E(c ,v);

A(b, v) B(v, f(u));

E(u, u) B(v, f(u));

B(v, u) E(h(v), u)

}.

3. S= { P(x, y) Q(g(x), y);

Q(y, y) P(x, f(y));

R(a, x) P(x, f(y));

Q(c, x) P(z, y);

P(y, z) R(x, c)

}.

4. S= { Q(x, x);

R(x, y) R(z, f(z)) Q(z, a);

R(c, x);

R(y, z) Q(y, f(a));

Q(x, f(x)) }.

5. S= { A(v, v);

B(u,v) A(w, c1) B(w, f(w));

A(u, f(u));

A(v, f(c)) B(v, w);

B(c2, u)

}

6. S= { B(v, f(c)) A(v, w);

B(u, f(u));

A(u, v) B(w, c) A(w, f(w));

A(b, u);

B(v, v)

}

7. S= { Q(v,v);

Q(v, u) P(u, v);

Q(u, v) P(a, u) R(v, v);

R(a, u) Q(v, u);

P(v, f(u))

}

8. S= {

E(w,v) T(v,v) B(c,w);

E(w,v) B(v,w);

B(v, f(w));

E(w,w);

T(b, w) E(v,w)

}

Тип 4 (дерево вычисления запроса к лог. программе)

Дана программа P и запрос G к ней. Изобразить дерево SLD-вычислений (при использовании стандартной стратегии) и найти все вычислимые ответы:

1. G: ?Q(x, y)

P: Q(a, x) ← P(x), R(a);

Q(y, b) ← not(R(c)), !, P(y);

P(f(x)) ← R(x), !;

P(c) ← ;

R(x) ← P(b);

R(c) ← not(P(a));

2. G: ?P1(x, y)

P: P1(a, x) ← P2(x), P3(a);

 P1(y, b) ← not(P3(c)), !, P2(y), P1(y, b);

P2(f(x)) ← P3(x), !;

P2(c) ← ;

P3(x) ← P2(b);

P3(c) ← not(P2(a));

P3(a) ← ;

  

3. G: ?R(x, y), P(x)

P: R(c, x) ← P(x), Q(a);

R(y, b) ← not(Q(c)), !, P(y);

P(f(x)) ← Q(x), !;

Q(x) ← P(b);

Q(c) ← not(P(a));

P(c) ← ;

Q(a) ← ;

4. G: ?Q(x, y)

P: Q(a, x) ← P(x), R(a);

Q(y, b) ← not(R(c)), !;

P(c) ← ;

R(x) ← P(b);

R(c) ← not(P(a));

R(a) ← ;

5. G: ?P(x), R(x)

P: P(b) ← ;

P(x) ← R(f(x));

P(f(b)) ← R(b), !;

P(c) ← ;

R(f(x)) ← P(x), !;

R(c) ← P(c);

R(x) ← P(x);

6. G: ?P(z), B(z)

P: P(b) ← ;

B(f(x)) ← P(x), !;

B(d) ← P(d);

P(z) ← B(f(z));

P(f(b)) ← B(b);

P(d) ← ;

B(x) ← P(x);

7. G: ?Q(y), A(y)

P: Q(a) ← ;

A(g(z)) ← Q(z);

Q(b) ← not(A(a)), !;

Q(g(a)) ← R(a), !;

A(c) ← Q(c);

A(a) ← Q(a);

A(a) ← ;

Q(c) ← ;

8. G: ?

P: A(b) ← ;

A(a) ← not(B(b)), !;

A(f(b)) ← B(b);

A(c) ← not(B(c)), !, A(b);

B(f(x)) ← A(x);

B(c) ← A(a), !, B(b);

B(b) ← A(b);

B(b) ← ;

6