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

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

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

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

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

Если две равносильные формулы логики предикатов соединить знаком эквиваленции , то полученная формула будет принимать значение И для любого набора переменных в любой области, т.е. будет общезначимой.

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

Общезначимость формулы логики предикатов, например, F обозначается ├F. Все общезначимые формулы могут быть источниками новых ├ формул. Например, подставляя в закон исключенного третьего – вместо х предикат Р(х₁,…,х_n), получаем общезначимую формулу Р(х₁,…,х_n) (х₁,…,х_n). При n=1 имеем общезначимую формулу , и, таким образом, - общезначимая формула логики предикатов.

Из тождественно истинной формулы логики высказываний подстановкой вместо х предиката Р(х, y), а вместо y- предиката Q(x,y) получаем общезначимую формулу и т. д.

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

Определение 13. Формула А логики предикатов называется тождественно ложной (невыполнимой), если она тождественно ложна на всякой области (на всякой модели).

Например, формула является тождественно ложной (невыполнимой) формулой логики предикатов.

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

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

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

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

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

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

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

Пример 1.Доказать равносильность (логическое тождество):

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

А= ,

В= или обозначив первую и вторую предметные переменные через n1 и n2, соответственно:

А= В=

В этих обозначениях заданное для рассмотрения тождество будет выглядеть так: .

Произведя равносильные преобразования, можем убедиться в справедливости этого тождества:

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

Пример 2.Определить тип формулы .

Пусть Р(х) : “ Число х - четно –” предикат, определенный в М=N².

Таким образом, рассматриваемая формула на данной модели представляет собой следующее утверждение: “ Среди натуральных чисел существуют как четные, так и нечетные ”. Очевидно, что это высказывание истинно и, таким образом, на данной модели формула F тождественно истинна.

Однако, если этот же предикат задать на множестве M=NхN,где N – множество четных чисел, то формула F на такой модели окажется тождественно ложной.

Учитывая изложенное, заключаем, что рассматриваемая формула F выполнима (но не общезначима).

Пример 3.Для формулы подобрать модель, на которой она является тождественно истинной (и, таким образом, в целом выполнимой).

Пусть Р(x, x, y): “x·x=y”, или иначе “x²=y” – предикат, определенный на множестве натуральных чисел, т.е. М=N. Тогда рассматриваемая формула выражает утверждение о существовании натурального квадрата натурального числа, что, очевидно, является истиной, т.е. на данной модели формула тождественно истинна, что и требовалось доказать.

Пример 4.Рассмотрим формулу . Это выполнимая формула. Действительно, если Р(х, y, x): “x+y=x” – предикат суммы, то на M=N существует подстановка вместо y соответствующего значения, дающего значение истинности данной формуле. Очевидно, это y=0, поскольку в этом случае получаем “х=х”.

Если же P(x, y, x): “xy=x” – предикат произведения, то таким значением y является y=1, так как при нем получаем истинное высказывание .

Но это единственные подстановки, приводящие к верным утверждениям, что и говорит именно о выполнимости данной формулы (но не об ее общезначимости).

Пример 5.Является ли общезначимой формула: ?

Пусть P(x, y) – предикат порядка (бинарного отношения ) “ ”, определенный на конечном множестве натуральных чисел M₁. Тогда при подстановке в формулу вместо свободной переменной y величины мы получим истинное утверждение, а при подстановке любой другой константы из множества М₁ – ложное. Таким образом, рассматриваемая формула не является общезначимой.

Пример 6.Рассмотрим формулу . Покажем, что она невыполнима.

Допустим противное, т.е. что она выполнима. Это означает, что существует такое множество М и такой конкретный предикат в нем, что когда , то данная формула превращается в такой конкретный предикат , который, в свою очередь, превращается в истинное высказывание при всякой подстановке вместо y элементов из множества М. Возьмем любое . Тогда высказывание истинно, как мы только что установили. Следовательно, истинны высказывания и .

Из истинности второго высказывания заключаем, что высказывание истинно (поскольку “для всех предметных переменных”, как бы они ни обозначались). Но это противоречит истинности первого высказывания .

Таким образом, наше предположение о выполнимости формулы неверно.

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

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