Мат. Логика и Теория Алгоритмов (нужна помощь с задачами)

[int13]

Здраствуйте. Имеется несколько задач по теме, которые мне нужно решить в довольно сжатые сроки. Почитал литературу, но все равно осталось очень много разных неясностей и вопросов. Примеров решения практических заданий я нигде не нашел. Ориентируюсь в этом неважно, поэтому осталось одна надежда. Кое-чего я уже пробовал разобрать, но сомневаюсь абсолютно в каждом шаге, может быть кто-нибудь сможет мне в этом помочь.

1. В структуре (N, +, *, =, 1) выразить предикат p(x): x - непростое число.

На данный момент решение такое:

$P(x) = \neg \left[ \forall y \exists r \left[ (x*r = y) \wedge \neg (r=x) \wedge \neg (r=1) \wedge \exists z (z*r=x)) \right] \right]$

Выглядит вроде логично, но убедиться лишний раз в этом не помешает. Может ли данное выражение считаться правильным и служить ответом к задаче?

2. Найти долю выполнимости предложения

$\exists x \forall y \left[ S(x) \to \neg R(y,x) \right]$

Доля выполнимости предложения - отношение числа структур сигнатур, в которых истинно предложение, к числу всех сигнатур на универсе. R - двухместный предикатный символ. S - одноместный предикатный символ.

Не совсем ясно что здесь универс. x и y могут принимать любые значения?
Первым шагом, насколько я понял - нужно найти количество интерпретаций.

$k_{i} = 2^{n+n^{2}}$

Это число показывает сколько наборов данных может входить в это предложение? И что с этим делать дальше?
(сейчас допишу остальные вопросы)

[cyb12]

По первой задаче: объясните, зачем нужна подформула $x*r=y$?
По второй задаче: сигнатура состоит из предикатных символов ($S,$ $P$) , символов констант и символов функций. В данной формуле только предикаты. Интерпретация состоит из универсума $D$, и оценок предикатных, константных и функциональных символов. Пусть $|D|=n,$ тогда оценок одноместного предиката $S$ может быть $2^n,$ оценок предиката $P$ -- $2^{n^2}.$ То есть ваше $k_i$ показывает число всех интерпретаций заданного универсума (при фиксированных оценках констант и функций, которых тут нет). Далее нужно посчитать, а сколько оценок предикатов, т.е. сколько способов определения $S$ и $P$, определяют их так, что формула верна. Тут, как мне кажется, проще взять отрицание формулы: $\forall x\exists y (S(x)\& R(y,x)).$