Лекция №14.

Тема: ОГРАНИЧЕННЫЕ КВАНТОРЫ. ВИДЫ ТЕОРЕМ

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

1. Определение ограниченных кванторов

2. Перенос свойств неограниченных кванторов на ограниченные

3. Прямая, обратная, противоположная и контрапозитивная теоремы

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

Кванторы вида xD и xD называются также ограниченными.

В математике используются, как правило, ограниченные кванторы (в частности, следующие их видоизменения: xa, xa и т.п.).

Принимаются следующие определения предложений с ограниченными кванторами (ограниченного обобщения и ограниченного подтверждения):

xD P(x)x(xDP(x));

xD P(x)x(xDP(x)).

При таком определении свойства неограниченных кванторов переносятся на ограниченные кванторы: например, свойство отрицания квантора всеобщности:

xD P(x)(определение ограниченного обобщения)

x(xDP(x))(отрицание обобщения)

x(xDP(x))(отрицание импликации)

x(xDP(x))(определение ограниченного подтверждения)

xD P(x).

Теорема, обычно, имеет следующее строение:

xD (P(x)Q(x)), (1)

где P(x), Q(x) – предикаты с областью определения D, или, проще, PQ.

Теоремы вида QP, PQ и QP называются соответственно обратной, противоположной и контрапозитивной к теореме PQ.

Теоремы PQ и QP эквивалентны (по таблице истинности).

Прямая теорема PQ и обратная теорема QP, вообще говоря, не являются эквивалентными. Если прямая и обратная теоремы PQ и QP верны, то их объединяют в одну теорему PQ.

Если импликация PQ истинна (или теорема), то, говорят, что условие Q необходимое для условия P, а условие P достаточное для условия Q. Поэтому теорема PQ формулируется также как теорема о том, что Q является необходимым и достаточным условием для условия P.

Что значит утверждение теоремы (1) не верно?

Ответ следует из свойств отрицания ограниченного обобщения и отрицания импликации: xD (P(x)Q(x)). Чтобы опровергнуть теорему (1), надо найти такое значение a переменной x, что P(a)И и Q(a)Л. Конъюнкция P(a)Q(a) называется контрпримером к теореме (1).

Чтобы доказать теорему вида xD P(x), надо найти такое значение a переменной x, что P(a)И (построении примера к теореме существования).

Лекция №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 логически следует из множества формул  языка L, если для любой интерпретации I языка L и для любых значений переменных A^I1 каждый раз, когда B^I1 для всех B. При этом Формула 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] невыполнима.