Лекция №15

Тема: ЯЗЫКИ ПЕРВОГО ПОРЯДКА И ИНТЕРПРЕТАЦИИ

Основные вопросы, рассматриваемые на лекции:

1. Логические и нелогические символы языков первого порядка

2. Термы и формулы языков первого порядка

3. Интерпретации языков первого порядка

4. Оценки переменных и значения термов и формул

5. Свободные и связанные вхождения переменных

Краткое содержание лекционного материала

Каждый язык первого порядка L определяется одним и тем же множеством логических символов и одними и теми же правилами построения термов и формул. Отличаются языки первого порядка множествами нелогических символов.

Логические символы: переменные, логические связки, кванторы. Переменных имеется счетное множество. Логические связки и кванторы подразделяются на два вида: неопределяемые и определяемые. Мы в качестве неопределяемых символов рассмотрим логические связки Ø, Þ и квантор ".

Нелогические символы: константы, n -арные функциональные и предикатные символы (n ³1). Множество нелогических символов содержит хотя бы один предикатный символ.

Термами и формулами языка L называются слова в алфавите языка L, которые получаются строго по следующим правилам:

1) переменная – терм;

2) константа – терм;

3) слово вида ft ₁ ...t_n – терм, если f – n -арный функциональный символ, а t ₁, ..., t_n – термы;

4) слово вида Pt ₁ ...t_n – формула, если P – n -арный предикатный символ, а t ₁, ..., t_n – термы;

5) слово вида Ø A – формула, если A – формула;

6) слово вида A Þ B – формула, если A и B – формулы;

7) слово вида " xA – формула, если x – переменная, а A – формула.

Пусть L – язык первого порядка (с равенством или без равенства).

Интерпретация нелогических символов I языка L – это непустое множество I, на котором определены следующие объекты:

элемент e_I для каждой константы e из L;

n -местное отображение f_I: Iⁿ ® I для каждого n -арного функционального символа f из L;

n -местное отношение P_I Í Iⁿ для каждого n -арного предикатного символа P из L (кроме =).

Оценка (иначе интерпретация) v переменных языка L – это некоторое отображение v множества X всех переменных языка L в множество I.

Пара (I, v), состоящая из некоторой интерпретации I нелогических символов языка L и некоторой оценки v переменных языка L называется интерпретацией I при оценке v. Обозначение: I^v.

Через v^x обозначим любую оценку следующего вида:

Определим по индукции значение I_v (t) терма t и истинностное значение I_v (A) формулы A языка L в интерпретации I при оценке v:

I_v (x)= v (x) для переменной x из L;

I_v (e)= e_I для константы e из L;

I_v (ft ₁… t_n)= f_I ((t ₁) _I,…,(t_n) _I) для терма ft ₁… t_n из L;

для предиката Pt ₁… t_n из L (кроме =);

для равенства t ₁= t ₂ из L;

для отрицания Ø B из L;

для импликации B Þ C из L;

для обобщения " xB из L.

Формула A языка L называется в интерпретации I:

истинной, если I_v (A)=1 при любой оценке v;

выполнимой, если I_v (A)=1 при некоторой оценке v;

опровержимой, если I_v (A)=0 при некоторой оценке v;

ложной, если I_v (A)=0 при любой оценке v.

Истинные (ложные) формулы в интерпретации I называются иногда тождественно истинными (тождественно ложными) на множестве I.

Отметим, что формулы, истинные (ложные) и неопровержимые (невыполнимые) в интерпретации I, совпадают.

В каждой интерпретации I формулы подразделяются на 3 вида: истинные, выполнимые и опровержимые, ложные. Пример: в одноэлементной интерпретации формула x = y истинна и формула x ¹ y ложна, а в интерпретации с более чем одним элементом обе эти формулы выполнимы и опровержимы.

Формула A языка L называется:

истинной, если A истинна в каждой интерпретации I;

выполнимой, если A истинна в некоторой интерпретации I;

опровержимой, если A ложна в некоторой интерпретации I;

ложной, если A ложна в каждой интерпретации I.

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

Формулы подразделяются на 3 вида: логически общезначимые, выполнимые и опровержимые, противоречия. Пример: формула x = x истинна, формула x ¹ x ложна, а формулы x = y и x ¹ y и выполнимы, и опровержимы.

Пример. Пусть P – бинарный предикатный символ. Тогда:

1) формула P (x, y)Þ P (x, y) логически общезначима по определению связки Þ;

2) формула " x " yP (x, y)Þ" y " xP (x, y) логически общезначима по смыслу квантора ";

3) формула Ø P (x, y)Þ P (x, y) выполнима, так как предложение x ¹ y Þ x = y истинно на одноэлементном множестве;

4) формула Ø P (x, y)Þ P (x, y) логически не общезначима, так как предложение x ¹ y Þ x = y не истинно на двухэлементном множестве;

5) формула Ø(P (x, y)Þ P (x, y))) является противоречием определению связок Ø и Þ.

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

Формулы A и B языка L называются логически эквивалентными, если A^I = B^I для любой интерпретации I языка L и для любых значений переменных. Формулы A и B языка L логически эквивалентны тогда и только тогда, когда формула A Û B логически общезначима.

Формулы A языка L логически следует из множества формул G языка L, если для любой интерпретации I языка L и для любых значений переменных A^I =1 каждый раз, когда B^I =1 для всех B ÎG. При этом Формула A называется логическим следствием формулы B.

Подформула B формулы A – это часть формулы A, также являющейся формулой. Вхождение переменной x в формуле A связанное (свободное), если это вхождение (не) является частью подформулы формулы A вида " xB.

Запись A_x [ t ] обозначает формулу, которая получается из формулы A заменой каждого вхождения переменной x термом t; при этом предполагается, что терм t допустим для подстановки в формулу A вместо переменной x, т.е. формула A не содержит подформул вида " yB, где y – переменная из t.

Приведем пример, показывающий необходимость ограничения допустимости термов для подстановки вместо переменных. Пусть P – унарный предикатный символ, формула A имеет вид " y Ø(Ø P (x)Þ P (y)), терм t является переменной y. Тогда формула A_x [ t ] имеет вид " y y ¹ y, и получается, что формула A выполнима, но формула A_x [ t ] невыполнима.