Логическо програмиране - писмен изпит

2 част

Тест

  1. Дадена е структура $\mathcal{A}$ с универсум $\mathbb{R}$, в която $\langle a, b \rangle \in r^{\mathcal{A}} \leftrightarrow a < b$. Вярна ли е формулата $\forall x(\exists y r(x, y) \And \lnot \forall y r(x, y))$.1
  2. Нека $\Delta$ и $\Gamma$ са множества от формули и $\Delta \subseteq \Gamma$. Вярно ли е, че ако $\Delta \nvDash \varphi$, то $\Gamma \nvDash \varphi$?2
  3. Правилно построена формула ли е следният израз, и ако да, то затворена формула ли е: $\forall x(r(x) \Rightarrow (p(f(x, y)) \lor \exists y q(p(x,y))))$.3
  4. Вярно ли е, че всяко неизпълнимо множество от формули има изпълнимо подмножество?4
  5. Вярно ли е, че $\lnot \exists x\exists y(p(x) \And p(y)) |=| \lnot \exists x p(x) \lor \lnot \exists y p(y)$.5
  6. Вярно ли е, че следната формула е в скулемова нормална форма: $\exists x \exists y \exists z p(x, y, z) \And q(x, y, z)$.6
  7. Вярно ли е, че ако $\nvDash \varphi$, то $\models \lnot \varphi$.7
  8. Предикатна тавтология ли е формулата $(\forall x p(x) \lor \exists x p(x))$.8
  9. Дадена е структурата $\mathcal{A}$ с универсум $\mathbb{R}$, в която $\langle a, b \rangle \in r^\mathcal{A} \leftrightarrow a < b$. Вярна ли е формулата $\exists x \forall y \forall z(r(y, z) \Rightarrow r(x, z))$.9
  10. Дадени са съждителните дизюнкти $\{ \lnot p, q, r \}$ и $\{ p, \lnot q, r \}$. Вярно ли е, че $\{ r \}$ е тяхна резолвента.10
  11. Вярно ли е, че $\exists x \lnot \exists y(p(x) \And p(y)) |=| \exists x \lnot p(x) \lor \lnot \exists y p(y)$.11
  12. Дадена е структура $\mathcal{A}$ с универсум $\{ x : x \in \mathbb{R} \mbox{and} x > 0 \}$ и единствен предикатен символ $p, \langle a, b, c \rangle \in p^\mathcal{A} \leftrightarrow ab = c$. Вярно ли е, че изображението $h(x) = 1 / x$ е автоморфизъм?12
  13. Дадена е структура $\mathcal{A}$ с универсум $\{ x : x \in \mathbb{R} \mbox{and} x \ne 0 \}$ и единствен предикатен символ $p, \langle a, b, c \rangle \in p^\mathcal{A} \leftrightarrow ab = c$. Вярно ли е, че изображението $h(x) = x^2$ е автоморфизъм?13
  14. Предикатна тавтология ли е формулата $\forall(x)(\lnot p(x) \Rightarrow p(x)) \Rightarrow \forall x p(x)$?14
  15. Вярно ли е, че $\lnot \exists x \exists y(p(x) \And p(y)) |=| \lnot \exists xp(x) \And \exists y p(y)$.15
  16. Има ли ербранов модел формулата $\forall x(p(x) \lor p(c))$, в която $c$ е индивидна константа?16
  17. Възможно ли е $\varphi$ и $\varphi \Rightarrow \psi$ да са изпълними, а $\psi$ да не е изпълнима? Ако да, посочете пример.17
  18. Дадена е структурата $\mathcal{A}$ с универсум $\mathbb{R}$, $p, r$ са съответно едно- и триместен предикатен символ, $\langle a, b, c \rangle \in r^\mathcal{A} \leftrightarrow a + b = c$ и $a \in p^\mathcal{A} \leftrightarrow a = 1$. Вярно ли е, че $r(p(x), p(x), x)$ определя $\{ 2 \}$?18
  19. Вярно ли е, че ако $\models \lnot \varphi$, то $\nvDash \varphi$?19
  20. Дадена е структурата $\mathcal{A}$ с универсум $\mathbb{R}$, $p, r$ са съответно едно- и триместен предикатен символ, $\langle a, b, c \rangle \in r^\mathcal{A} \leftrightarrow a + b = c$ и $a \in p^\mathcal{A} \leftrightarrow a = 1$. Вярно ли е, че $\forall x r(x, y, x)$ определя $\{ 0 \}$.20
  21. Дадени са дизюнктите $\{ \lnot r(f(y), x), r(f(x), y) \}$, и $\{ \lnot r(x, f(x)) \}$. Имат ли те либерална резолвента? Напишете някоя, ако има такава.21

Алгоритъм за решаване на теста:

Имаме няколко типа задачи, които се срещат на теста
0.<тип задача>:<алгоритъм за решаване>
1. Вярна ли е формулата: проверяваме дали формулата е правилно построена, превеждаме си формулата на 'човешки език', мислим дали е вярна.
2. Правилно построена ли е формулата: има ли повтарящи се имена на предикати с различна арност(тоест p(a,b) и p(a,v,g)), правилни ли са аргументите на предикатите,…
3. Вярно ли е <формула> |=| <формула> : разписваме формулите.
4. Вярно ли е, че <формлула> определя <множество>: правилно построена ли е формулата, има ли свободни променливи формулата, определят ли свободните променливи множеството
5. В СНФ форма ли е <формула>: ясно..
6. Предикатна тавтология ли е формулата: правилно построена ли е формулата, разписваме формулата
7. Хомоморфизъм/автоморфизъм ли е нещо: проверяваме с дефиницията и внимателно за случаите x=1, x=0.

Задача 1

Посредством метода на резолюцията да се покаже, че

(1)
\begin{align} ((\lnot \forall x p(x) \And \forall y q(x, y)) \lor \lnot \exists y \lnot (p(y) \lor \forall x q(x, y))) \And \forall x p(x) \models \exists x \forall y (p(x) \lor q(x, y)) \end{align}

Задача 2

Да се докаже, че множеството, съдържащо следните дизюнкти е неизпълнимо:

(2)
\begin{align} \{ p(a, y), p(b, y) \}, \{ \lnot p(c, f(z)) \}, \{ q(f(y), t), \lnot p(y, t) \}, \{ \lnot p(a, h(y)), p(c, y) \}, \{ \lnot q(y, h(y)), p(c, y) \}. \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License