Определение.Формула A выполнима в данной интерпретации, если существует такой набор <a1, a2,…, an>, aiÎM, значений свободных переменных x1, x2, …, xn формулы A, что A|<a1, a2,…, an> = И.
Формула A истинна в данной интерпретации, если она принимает значение И на любом наборе значений своих свободных переменных.
Формула A называется ложной в данной интерпретации, если она не является выполнимой ни на одном наборе значений своих свободных переменных.
Формула A общезначима (в логике предикатов), если она истинна в любой интерпретации.
Формула A выполнима (в логике предикатов), если существует интерпретация, в которой она выполнима.
Формула A называется противоречием (в логике предикатов), если она ложна в любой интерпретации.
Данная интерпретация называется моделью для данного множества формул S, если каждая формула из S истинна в данной интерпретации.
Приведенные ниже утверждения являются просто простыми следствиями определений.
Формула A является ложной в данной интерпретации тогда и только тогда, когда ØA истинно в той же интерпретации, и A истинно тогда и только тогда, когда ØA ложно.
Никакая формула не может быть одновременно истинной и ложной в одной и той же интерпретации.
Если в данной интерпретации истинны A и AÉB, то истинно и B.
Формула AÉB является ложной в данной интерпретации тогда и только тогда, когда A в этой интерпретации истинно, а B ложно.
Формула A общезначима тогда и только тогда, когда формула ØA не является выполнимой, а формула A выполнима тогда и только тогда, когда формула ØA не является общезначимой.
Теорема 4.1. Формула "x A(x)ÉA(y), где y не входит в формулу A(x), общезначима.
Доказательство. Пусть {x, x1, x2,..., xn} - множество всех свободных переменных формулы A. Тогда, очевидно, {y, x1, x2,..., xn} будет множеством всех свободных переменных формулы "x A(x)ÉA(y). Возьмем произвольную интерпретацию этой формулы на произвольном непустом множестве M и пусть <b, a1, a2,..., an> произвольный набор значений переменных {y, x1, x2,..., xn} на множестве M. Требуется доказать, что значение формулы "xA(x)ÉA(y) на наборе <b, a1, a2,..., an> есть истина.
Рассмотрим два случая.
1. Значение формулы A(x) на наборе <b, a1, a2,..., an> есть истина для любого bÎM. Тогда формула "xA(x) имеет истинное значение на наборе <a1,a2,...,an>. Формула A(y), как и формула A(x) является истинной, когда ее свободные переменные принимают значения <b, a1, a2,..., an>. Отсюда получаем, что формула "x A(x)ÉA(y) имеет истинное значение на наборе <b, a1, a2,..., an>.
2. Значение формулы A(x) на наборе <b, a1, a2,..., an> есть ложь. Следовательно, формула "xA(x) имеет ложное значение на наборе <a1,a2,...,an>. Формула A(y), как и формула A(x) является ложной, когда ее свободные переменные принимают значения <b, a1, a2,..., an>. Отсюда получаем, что формула "xA(x)ÉA(y) имеет истинное значение на наборе <b,a1, a2,..., an>.
В обоих случаях значение формулы "xA(x)ÉA(y) является истинным, чем и заканчивается доказательство.
Теорема 4.2. Формула A(y)É$x A(x), где y не входит в формулу A(x), общезначима.
Доказательство. Пусть {x, x1, x2,..., xn} - множество всех свободных переменных формулы A. Тогда, очевидно, {y, x1, x2,..., xn} будет множеством всех свободных переменных формулы A(y)É$x A(x). Возьмем произвольную интерпретацию этой формулы на произвольном непустом множестве M и пусть <b, a1, a2,..., an> произвольный набор значений переменных {y, x1, x2,..., xn} на множестве M. Требуется доказать, что значение формулы A(y)É$xA(x) на наборе <b, a1, a2,..., an> есть истина.
Рассмотрим два случая.
1. Значение формулы A(x) на наборе <b, a1, a2,..., an> есть ложь. Формула A(y), как и формула A(x) является ложной, когда ее свободные переменные принимают значения <b, a1, a2,..., an>. Отсюда получаем, что формула A(y)É$xA(x) имеет истинное значение на наборе <b, a1, a2,..., an>.
2. Значение формулы A(x) на наборе <b, a1, a2,..., an> есть истина. Следовательно, формула A(y), как и формула A(x) является истинной на этом наборе. Формула $xA(x) имеет истинное значение на наборе <a1,a2,...,an>. Отсюда получаем, что формула A(y)É$xA(x) имеет истинное значение на наборе <b,a1, a2,..., an>.
В обоих случаях значение формулы A(y)É$xA(x)) является истинным, чем и заканчивается доказательство.
Задача распознавания общезначимости формул логики предикатов существенно сложнее, чем формул логики высказываний. Так же, как и в логике высказываний, она называется проблемой разрешимости и ставится следующим образом: указать алгоритм распознавания общезначимости формул (т. е. является ли данная формула общезначимой или нет). Как мы увидим в главе 5, такой алгоритм отсутствует.
Знания забудутся, пробелы в них - никогда.
Михаил Генин
Два мира есть у человека:
Один, который нас творил,
Другой, который мы от века
Творим по мере наших сил.
Н. Заболоцкий