Выполнимость в логике предикатов

[bonika]

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

[mkot]

Можно заметить, что в случае конечного носителя $A=\{a_1, \ldots, a_n\}$
$\exists x \varphi(x)$ это "тоже самое", что и $\varphi(a_1) \vee \ldots \vee \varphi(a_n)$,
а $\forall x \varphi(x)$ -- $\varphi(a_1) \wedge \ldots \wedge \varphi(a_n)$.

И индукцию по построению формулы применить.

(В некотором смысле выполнима элиминация кванторов.)

[bonika]

Спасибо за ответ, завтра попробую доказать, вроде должно получиться...еще раз спасибо!

[bonika]

Хотела уточнить правильно ли я поняла...
мне нужно рассмотреть два случая
1.$\varphi(a_1) \vee \ldots \vee \varphi(a_n)$
2.$\varphi(a_1) \wedge \ldots \wedge \varphi(a_n)$
так как формулы логики предикатов рассматриваются на конечном множестве, то вместо ее предкатных переменных могут подставляться конкретные предикаты, определенные на этом множестве. Ввиду этого операции квантификации на конечном множестве сводятся к конъюнкции и дизъюнкции

в каждом из случаев, я предполагаю что
$\varphi(a_1) $ выполнима,
1. затем, что $\varphi(a_1) \vee \varphi(a_2)$ тоже выполнима...тогда $\varphi(a_1) \vee \ldots \vee \varphi(a_n)$ так как выполнимая или какая то еще будет выполнимая
2. а во втором случае она будет выполнима разве?

[mkot]

Давайте точно сформулируем задачу.
Пусть $\sigma$ -- некоторая сигнатура.
$\mathcal{A}$ -- некоторая конечна алгебраическая система этой сигнатуры.
Пусть $\Phi(y_1, \ldots, y_n)$ -- формула сигнатуры $\sigma$ от свободных переменных $y_1, \ldots, y_n$.

Необходимо придумать алгоритм, который за конечное число шагов установит,
является ли формула $\Phi$ выполнимой или нет.

Формула называется выполнимой, если найдутся такие знаения $a_1, \ldots, a_n$ из носителя алгебраической системы, что $\Phi(y_1, \ldots, y_n)$ является истинной.

Как предлагается построить такой алгоритм? Формула определяется индуктивным определением. Им и воспользуется.

Так как алгебраическая система конечна, то выполнимость атомарных формул
устанавливается полным перебором всех наборов переменных. Правильно?
Ну то есть пусть $f(x) = y^2$, запомним все наборы $(x, y)$ на которых эта формула истинна.

Далее, рассмотрим конъюнкцию, дизъюнкцию и отрицание.
Пусть $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \vee \psi(y_1, \ldots, y_n)$. Мы уже умеем находить множества выполнимости для слагаемых, тогда множество выполнимости формулы $\Phi$ -- это пересечение этих двух множеств.
Остальные случаи разберите самостоятельно.

Пусть теперь формула $\Phi$ имеет вид $\exists x \varphi (x, y_1, \ldots, y_n)$.
Здесь во множество выполнимости войдут, только те наборы $(y_1, \ldots, y_n)$, что во множестве истинности $\varphi (x, y_1, \ldots, y_n)$ найдётся хотя бы один набор $(x, y_1, \ldots, y_n)$, понятно, что это можно установить за конечное число шагов.
Что делать с квантором всеобщности придумайте сами.

Ну а формула тоже когда-нибудь закончится, так что алгоритм за конечное число шагов найдёт множество выполнимости, достаточно для ответа проверить его на пустоту.

Правда ещё есть проблема, если формула имела вид типа $\exists x f(x) = g(x)$. То есть без свободных переменных, но введением набора нулевой длины, она решается.

В общем идея такая, введите обознаение для множества выполнимости формулы только.

И главное найдите в этом алгоритме все случаи, где существенно используется конечность носителя.

Не отрицаю, что возможно проще или как-то по другому. Но рассуждения использующие индуктивное определение формулы встречаются настолько часто, так что подобные рассуждения нужно проводить не задумываясь.

[bonika]

mkot в сообщении #430428 писал(а):

Пусть $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \vee \psi(y_1, \ldots, y_n)$. Мы уже умеем находить множества выполнимости для слагаемых, тогда множество выполнимости формулы $\Phi$ -- это пересечение этих двух множеств.

А точно это будет пересечение, я почему то думала, что будет объединение, если $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \vee \psi(y_1, \ldots, y_n)$ и пересечение, если $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \wedge \psi(y_1, \ldots, y_n)$.
И по поводу отрицание получится пусто?

[mkot]

bonika в сообщении #433435 писал(а):

mkot в сообщении #430428 писал(а):

Пусть $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \vee \psi(y_1, \ldots, y_n)$. Мы уже умеем находить множества выполнимости для слагаемых, тогда множество выполнимости формулы $\Phi$ -- это пересечение этих двух множеств.

А точно это будет пересечение, я почему то думала, что будет объединение, если $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \vee \psi(y_1, \ldots, y_n)$ и пересечение, если $\Phi(y_1, \ldots, y_n) = \varphi(y_1, \ldots, y_n) \wedge \psi(y_1, \ldots, y_n)$.

Вы правильно думали, это я опечатался.

Цитата:

И по поводу отрицание получится пусто?

Не уловил смысл фразы.

[bonika]

mkot, спасибо огромное за помощь, если бы не вы, я бы не разобралась.