4.2. Выполнимость и общезначимость

Рассмотрим некоторую модель с множеством M. При логической интерпретации формул логики предикатов возможны три основные ситуации:

1) формула Fназываетсявыполнимой в данной модели, если существует набор <a₁,a₂, ...,a_n>,a_iM, значений свободных переменных x₁,x₂, ...,x_nформулыFтакой, что;

2) формула Fназываетсяистинной в данной модели, если она принимает значение И на любом наборе <a₁,a₂, ...,a_n>,a_iM, значений своих свободных переменных x₁,x₂, ...,x_n;

3) формула Fназываетсяложной в данной модели, если она принимает значение Л на любом наборе <a₁,a₂, ...,a_n>,a_iM, значений своих свободных переменных x₁,x₂, ...,x_n.

Формула F общезначимаилитождественно истинна(в логике предикатов), если она истинна в каждой модели.

Формула F противоречиваилитождественно ложна(в логике предикатов), если она ложна в каждой модели. ЕслиF общезначима, то^F– противоречива.

Формула F выполнима(в логике предикатов), если существует модель, в которойFвыполнима.

Формула F опровержима(в логике предикатов), если существует модель, в которойFневыполнима.

Формула Fобщезначима тогда и только тогда, когда формула^Fне является выполнимой, и формулаFвыполнима тогда и только тогда, когда формула^Fне является общезначимой.

Теорема Чёрча.Не существует алгоритм, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

Пример 36.Определить истинность, ложность или выполнимость следующих формул:

1); 2); 3);

4); 5).

1. Возьмем в качестве Aпредикат «быть мужчиной». Тогда, если в качестве основного множества модели взять множество людей, то=Л, а если основным множеством является множество мужчин, то=И. Значит, существует модель (но не любая) в которой формула принимает значение «И». Следовательно, формулавыполнима.

2. – выполнима. В качестве доказательства можно привести предикат суммы, определенный на множестве целых чисел, тогда=И, а=Л. (В этой модели предикат=И, еслиy – четное.)

3. – выполнима. Пусть, тогда на множестве натуральных чисел=И, так как действительно для любого натуральногоxсуществует делитель (тоже натуральный), например 1. Если же в качествевзять отношение «x женат наy», то=Л.

4. – ТИФ, так как она истинна в любой модели. Действительно, при подстановке любой константыa(из любого основного множества) предикатлибо истинен, т.е., тогдаи, либо ложен, т.е., тогдаи.

5. – ТЛФ. Доказательство аналогично предыдущему.

Пример 37.Доказать общезначимость формулы:

.

Докажем от противного.

1	Пусть:
2	Импликация равна Л, только если
3	––//––		Импликация равна Л, только если
4	––//––		––//––
5	Найдется константа a из области определения переменной x, такая что		––//––	––//––
6	Конъюнкция равна И, только если		––//––	––//––
7	––//––	––//––	Для всех x, а значит и для x=a	––//––
8	––//––	Так как, то	Так как, то	––//––
		Противоречие
	Значит, предположение о том, что –ложно. Следовательно:.