Задачи.

1. Среди следующих предложений выделить предикаты, и для каждого предиката установить местность и область истинности, если . Для двуместных предикатов изобразить область истинности графически.

1. .

2. При выполняется равенство.

3. .

4. .

5. .

6. .

7. .

8. .

9. Однозначное число является простым.

10. .

2. Определить значение высказывания, полученного из трехместного предиката на множестве .

1. , .

2. , .

3. , .

4. , .

5. , .

6. , .

7) ,.

8) ,.

9) ,.

10) ,.

3. Записать инверсию формулы в предваренной нормальной форме.

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9) .

10) .

4. Записать формулу в приведенной форме, если это необходимо, а затем преобразовать к предваренной форме.

1. .

2. .

3. .

4. .

5. .

6. .

7) .

8) .

9) .

10) .

5. Найти предикат, не содержащий кванторов, логически эквивалентный данному предикату. Предикаты иопределены на множестве.

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

6. Записать с помощью кванторов следующие утверждения и их отрицания.

1. Функция возрастает на интервале.

2. Функция непрерывна на интервале.

3. Множество является собственным подмножеством множества.

4. Точка является точкой экстремума функции.

5. Функция достигает наибольшего значения на отрезкев точке.

6. Функция дифференцируема в точке.

7. Бинарное отношение является симметричным.

8. Функция ограничена на множестве.

9. Булева функция самодвойственна.

10. Множества ине пересекаются.

7. Доказать эквивалентность

.

8. Доказать, что не эквивалентны формулы и.

В Ответы и указания.

В Содержание.

Глава 6. Исчисление предикатов.

Рассмотрим построение теории первого порядка.

Компонентами теории первого порядка являются следующие.

1. Алфавит составляют:

• Предметные константы – буквы начала латинского алфавита с натуральными индексами: ,, …,,, … Предметные символы – это имена (обозначения) предметов.

• Предметные переменные – буквы конца латинского алфавита с натуральными индексами: ,, …,,, …

• Функциональные буквы – строчные буквы латинского алфавита с натуральными индексами (верхний индекс указывает число переменных, нижний – номер функциональной буквы): ,, …

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

• Логические связки: .

• Квантор всеобщности .

• Синтаксические символы – скобки (, ) и запятая.

2. Формула определяется несколькими этапами. Вначале вводится понятие терма.

Определение. 1) Предметные константы и предметные переменные есть термы.

2) Если ,, …,, – термы,– функциональная буква, то– терм.

3) Символ является термом тогда и только тогда, когда это следует из 1) и 2).

Примеры. 1. Пусть – предметная переменная,– предметная константа,,– функциональные буквы. Тогда,– термы.

2. Пусть – предметная переменная,– предметная константа,,– функциональные буквы. Тогда,– термы. Здесь символы,имеют только формальный смысл и не интерпретируются как обозначения тригонометрических функций.

Определение. Если ,, …,, – термы,– предикатная буква, то символназывается элементарной формулой.

Другими словами, элементарная формула образуется при применении предикатной буквы к термам.

Примеры. 1. В условиях первого примера, если – предикатная буква, то– элементарная формула.

2. В условиях второго примера, если – предикатная буква, то– элементарная формула.

Теперь определим формулу логики предикатов.

Определение. 1) Всякая элементарная формула есть формула.

2) Если ,– формулы, то формулами являются также символы,,.

3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

Примеры. 1. В условиях первого примера, – формула.

2. В условиях второго примера, – формула.

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

Здесь мы ненадолго отвлечемся от построения теории первого порядка и рассмотрим некоторые понятия, связанные с формулами.

Определение. Пусть – формула,– переменная, которая входит в формулу(один или несколько раз). Вхождениев формулуназываетсясвязанным, если либо – переменная в кванторе (), либонаходится в области действия квантора. Если вхождениевне связано, то оно называется свободным.

Пример. В формуле вхождения обеих переменных свободные.

В формуле вхождения переменнойв посылку связаны, а вхождение в следствие свободно. Вхождение переменнойсвободно, так как отсутствует квантор.

В формуле вхождения обеих переменных связаны.

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

Пример. Рассмотрим подстановку вместо всех свободных вхожденийв формулы из предыдущего примера.

В формуле вхождениесвободное, следовательно, получаем.

В формуле вхождения переменнойв посылку связаны, а вхождение в следствие свободно. Получаем:.

В формуле вхождения обеих переменных связаны, поэтому осуществить подстановкуневозможно.

Определение. Терм называется свободным для переменнойв формулетогда и только тогда, когда никакое свободное вхождениев формулуне лежит в области действия квантора, где– переменная в терме.

Пример. Рассмотрим формулу и терм.не свободен для переменнойв данной формуле, так каклежит в области действия квантора, тем болеене свободен для переменной.

Пусть теперь дан терм .свободен для переменной.

Уточним понятие интерпретации для множества формул теории первого порядка.

Определение. Интерпретацией множества формул называется область интерпретациии заданное на ней соответствие, которое каждой предикатной буквеставит в соответствие-местный предикат на, каждой функциональной букве–-местную функцию на, каждой предметной константе– элемент множества.

При интерпретации формулы превращаются в предикаты на множестве . Если формула не имеет свободных переменных, то после интерпретации она превращается в высказывание.

Пример. На множестве рассмотрим формулу. Интерпретируем эту формулу следующим образом:. Тогда мы получим предикат.

Рассмотрим теперь формулу . При интерпретации она превращается в истинное высказывание.

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

Определение. Формула называется общезначимой (логически общезначимой), если она истинна в любой интерпретации.

Определение. Формулы иназываютсялогически эквивалентными тогда и только тогда, когда формула логически общезначима.

Справедлива теорема, аналогичная теореме из логики высказываний.

Теорема. Отношение логической эквивалентности является отношением эквивалентности.

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

Теорема. Отношение логического следствия является отношением предпорядка.

Определение. Формула называется противоречивой, если она ложна в любой интерпретации.

Теорема. Пусть – формула,– переменная в формуле, термсвободен для переменнойв формуле. Тогда формулаобщезначима.

Доказательство. Пусть имеется некоторая интерпретация исходной формулы, то есть множество и– предикат на. Покажем, что– тождественно истинный предикат. Возьмем произвольный набор значенийпеременных. Подставим этот набор в предикат. Получим высказывание:

.

Покажем, что это высказывание истинно. Возможны два случая.

1. , следовательно .

2. .

Соотношение выполнено при любых значениях . Подставим этот набор значений в терм:. Подставим последнее выражение в предикат. Получим:

.

Но, поскольку терм свободен для переменнойв формуле, получаем:

Следовательно, по свойству импликации получаем, что , что и требовалось доказать.

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

Доказательство аналогично доказательству предыдущей теоремы.

Теперь мы можем вернуться к построению теории первого порядка.

3. Аксиомы теории первого порядка делятся на два класса:

• Логические аксиомы:

1. .

2. .

3. .

4. , где терм свободен для переменнойв формуле.

5. , где – несвободная переменная в формуле.

Отметим, что аксиомы 1) – 3) – тавтологии, 4) и 5) – общезначимые формулы.

• Собственные аксиомы.

У каждой теории первого порядка свои собственные аксиомы.

4. Правила вывода.

1. Modus ponens (МР).

├.

2) Правило обобщения Gen.

├.

Определение. Теория первого порядка без собственных аксиом называется исчислением предикатов первого порядка (или чистым исчислением предикатов).

Без доказательства приведем теоремы.

Теорема. Всякая теорема исчисления предикатов логически общезначима, то есть исчисление предикатов непротиворечиво.

Теорема о полноте. Всякая логически общезначимая формула является теоремой исчисления предикатов.

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