Общезначимость и выполнимость формул.

Определение 1. Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула А принимает истинные значения.

Определение 2. Формула А называется выполнимой, если существует область, на которой эта формула выполнима.

Из определения 2 следует, что, если формула выполнима, то это еще не означает, что она выполнима в любой области.

Определение 3. Формула А называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Определение 4. Формула А называется общезначимой, если она тождественно истинная на всякой области.

Определение 5. Формула А называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Из приведенных определений следует:

1. Если формула А общезначима, то она и выполнима на всякой области.

2. Если формула А тождественно истинная в области М, то она и выполнима в этой области.

3. Если формула А тождественно ложная в области М, то она не выполнима в этой области.

4. Если формула А не выполнима, то она тождественно ложна на всякой области.

В связи с данными определениями естественно выделить два класса формул логики предикатов: выполнимых и не выполнимых формул.

Общезначимую формулу называют логическим законом.

Рассмотрим пример:

Пример: Формула хуР(х,у) выполнима. Действительно. если Р(х,у) - предикат « х < y». определенный в области М = Е  Е. где Е = {0,1.2,....n,....} , то формула хуР(х,у) тождественно истинная в области М, и, следовательно, выполнима в этой области. Однако, если предикат «х < у». рассматривается в конечной области М₁ = Е₁Е₁, где Е₁ = {0,1.2.....k}. то формула хуР(х, y) будет тождественно ложной в области М₁ и, следовательно. не выполнима в области М₁ . При этом ясно. что формула хуР(х,y) не общезначима.

Пример 3. Формула x[P(x)Р(х)] тождественно истинная в любой области М. Значит, она является общезначимой, то есть является логическим законом (закон исключенного третьего). Аналогично, x[P(x)Р(х)] тождественно ложная в любой области М. и поэтому она не выполнима.

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

Теорема 1. Для того, чтобы формула А была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

Теорема 2. Для того, чтобы формула А была выполнимой, необходимо и достаточно, чтобы формула А была не общезначима.

Проблема разрешимости для общезначимости и выполнимости, неразрешимость ее в общем случае (без доказательства)

Проблема разрешимости в логике предикатов ставится так же, как и в алгебре логики: существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому классу она относится, то есть является ли она или общезначимой, или выполнимой, или тождественно ложной. Если бы такой алгоритм существовал, то, как и в алгебре высказываний, он сводился бы к критерию тождественной истинности любой формулы логики предикатов.

В отличие от алгебры логики, в логике предикатов не применим метод перебора всех вариантов

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

В 1936 году американский математик А.Черч доказал, что проблема разрешимость логики предикатов в общем виде алгоритмически не разрешима, то есть не существует алгоритма, который бы позволил установить, к какому классу формул относится любая формула логики предикатов.