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

Опр.1: Формула F(x 1, x 2, …, x n) сигнатуры s называется общезначимой общезначимой (тождественно истинной) в данной модели, если она истинна в этой модели при любых значениях свободных переменных x ₁, x ₂, …, x _n.

Опр.2: Формула F(x ₁, x ₂, …, x _n) сигнатуры s называется общезначимой в широком смысле, если она истинна в любой модели той же сигнатуры на любых наборах значений свободных переменных, взятых из этой модели.

Пример: M, s=<P⁽²⁾>, F(x)= " y (P(x, y)ÚØP(x, y)) – истинна в любой модели данной сигнатуры (общезначима в широком смысле).

Опр.3: Формула F(x 1, x 2, …, x n) называется выполнимой в данной модели, если существует такой набор a ₁, a ₂, …, a _n элементов из этой модели, что F(x ₁, x ₂, …, x _n) истинна в этой модели на этом наборе элементов.

Опр.4: Формула F(x ₁, x ₂, …, x _n) называется выполнимой (в широком смысле), если существует такая модель и такие элементы a 1, a 2, …, a n из этой модели, на которых эта формула истинна.

Опр.5: Формула F(x 1, x 2, …, x n) называется тождественно ложной (в широком смысле), если она ложна в любой модели на любых элементах из этой модели.

Т.: Проблемы общезначимости и выполнимости равносильны.

Замечание 1: Формула F(x 1, x 2, …, x n) общезначима

тогда и только тогда, когда формула Ø F(x 1, x 2, …, x n) является невыполнимой.

Пусть F(x 1, x 2, …, x n) общезначима. Возьмем произвольную модель , a 1, a 2, …, a nÎ M.

╞ F(a 1, a 2, …, a n). Тогда

╞ ØF(a 1, a 2, …, a n).

Это означает, что Ø F(x 1, x 2, …, x n) – тождественно ложная.

Замечание 2. F(x 1, x 2, …, x n) выполнима тогда и только тогда, когда формула Ø F(x 1, x 2, …, x n) не является общезначимой.

Доказательство. Пусть F(x 1, x 2, …, x n) – формула, которую мы хотим проверить на выполнимость. Применим замечание 2, т.е. решим проблему общезначимости для формулы Ø F.

Если Ø F - не общезначимая, то F - выполнимая.