Писмен изпит - задачи

1 част

Задача 1

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

  1. $\forall x \exists y (p(x,y) \And \lnot p(x,y) \And p(y,y))$
  2. $\lnot \forall x \forall y \forall z (p(x,z) \Longrightarrow p(x,y) & p(y,z))$

Задача 2

Да се дефинира на Пролог предикат $p(X, Y)$, който по даден списък от цели числа $X$ намира списък $Y$, съдържащ всички числа, които са от $X$ и чиито квадрати не са от $X$.

% elem(E, XS) - E is element of XS
elem(E, [H|T]) :- E = H; elem(E, T).

% filterx(X, T, GT) - GT has all elements from T, which squares are not in X
filterx(_, [], []).
filterx(X, [H|T], [H|GT]) :- filterx(X, T, GT), H2 is H * H, not(elem(H2, X)). % not should be \+ in gprolog
filterx(X, [H|T], GT) :- filterx(X, T, GT), H2 is H * H, elem(H2, X).

% filter(X, Y) - Y has all elements from X, which squares are not in X
filter(X, Y) :- filterx(X, X, Y).

% p(X, Y) - the given task
p(X, Y) :- filter(X, Y).

Задача 3

Да се дефинира на Пролог предикат $p(X, Y)$, който по даден списък от числа $X$ генерира в $Y$ всички възможни произведения на нечетен брой елементи на $X$.

% subset(T, GT) - generate all subsets of T in GT
subset([], []).
subset([H|T], [H|GT]) :- subset(T, GT).
subset([_|T], GT) :- subset(T, GT).

% oddlen(T) - T has odd len
oddlen([_]).
oddlen([_|[_|X]]) :- oddlen(X).

% prod(T, P) - P is the product of the elements in T
prod([], 1).
prod([X|T], N) :- prod(T, N1), N is N1 * X.

% gen_odd_subs_prod(X, P) - generates in P all products of odd-length subsets of X
gen_odd_subs_prod(X, P) :- subset(X, XS), oddlen(XS), prod(XS, P).

% p(X, Y) - the given task
p(X, Y) :- gen_odd_subs_prod(X, Y).

Задача 4

Нека $L$ е предикатен език без формално равенство, имащ само 2 триместни предиката $p$ и $q$. Нека $A$ е структура за $L$ с универсум реалните числа, такава че за произволна тройка от реални числа $a,b$ и $c$:

  1. $<a,b> \in p^{\mathcal{A}} \Leftrightarrow a+b=c$
  2. $<a,b> \in q^{\mathcal{A}} \Leftrightarrow ab=c$

Да се докаже, че в $\mathcal{A}$ са определими следните множества:
$\{0\}, \{-2\}, \{x \in \mathbb{R} | x > 0\}, \{x \in \mathbb{R} | |x+1| < 2\}$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License