2.9. Некоторые теоремы теории £

Множество теорем теории £ бесконечно. Рассмотрим некоторые из них.

1. (закон двойного отрицания).

2. (закон двойного отрицания).

3. (из ложного что угодно).

4. (закон де Моргана)

5. (закон де Моргана)

и т. д.

(Вывод законов см. Ф.А. Новиков “Дискретная математика для программистов”, стр.114).

Теорема. Теоремами теории £ являются только общезначимые формулы.

Следствие.Теория £ формально непротиворечива.

Выводы.

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

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

Тема 3. Логика и исчисление предикатов

Логика высказываний – очень узкая логическая теория. Есть такие типы логических рассуждений, которые не могут быть осуществлены в рамках логики высказываний. Например:

1. Всякий друг Ивана есть друг Петра. Павел не друг Ивана, следовательно, Павел не друг Петра.

2. Простое число 2 – четное, следовательно, существуют четные простые числа.

Корректность таких выводов базируется не только на истинности соответствующих предложений, но и на смысле слов «всякий» и «существуют». Чтобы сделать более понятной структуру сложных высказываний используют специальный язык – язык предикатов первого порядка.

3.1. Предикаты

Рассмотрим предложения, зависящие от параметров:

Х – четное число.

X<Y

X+Y=Z

X,Y– братья.

Если заменить переменные X,Y,Zнекоторыми конкретными значениями, то мы получим определенные высказывания, которые могут быть истинными или ложными.

Например:

3 – четное число.

2<5

2+3=5

Иван и Павел – братья.

Предложения такого рода называются предикатами.

Предикат Р(х₁,…,х_n) – функция, переменные которой принимают значения из некоторого множестваM, а сама функция принимает значение истина (1) или ложь (0).

Р(х₁,…,х_n) :M_n{0,1}

Высказывания - это 0-местные предикаты. Над предикатами выполняются логические операции, в результате чего получаются новые предикаты.

С каждым предикатом связано число, которое называется местностью или арностью предиката (количество переменных).

Язык предикатов – наиболее приближенный к естественным языкам формальный математический язык.

Примеры:

1. Р(х) – х делится на 2

Q(x) –xделится на 3

P(x)&Q(x) –xделится на 2 и 3, т. е. определен предикат делимости на 6.

2. S(x,y) – x равно y.

S(x,y)&S(y,z)S(x,z)

Кроме операций логики высказываний, к предикатам можно применять операции связывания кванторами.

1. Квантор общности ().

- высказывание истинное для каждого, т. е. это высказывание не зависит отx_i.

2. Квантор существования ().

- высказывание истинно, если существует, для которого это высказывание истинно.

Для конечных множеств операции навешивания кванторов можно выразить через операции & и .

Пусть

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

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

Исчисление предикатов первого порядка – это формальная теория K, в которой определены :

1. Алфавит:

• Связки: (основные), & ,( дополнительные).

• Служебные символы: (,).

• Кванторы ,.

• Предметные константы a,b,c,….

• Предметные переменные x,y,z,….

• Символы предикатов P,Q,R,….

• Символы функций f,g,h,….

Константы, переменные, функторы – называются термами.

2. Формулы. Слово называется формулой, если оно имеет следующий синтаксис:

1) Р(х₁,…,х_n) – атомарная формула (А).

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

2) Если А – формула, то - тоже формула.

3) Если А и В – формулы, то - формулы.

4) Если А – формула, содержащая свободную переменную х, то - формулы.

Слово является формулой, если это следует из 1-4.

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

Пример

- х – свободная переменная, у – связанная переменная.

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

3. Аксиомы (логические).

1) Любая система аксиом исчисления высказываний.

А1:

А2:

А3:

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

P1:,

P2:,

где t– терм.

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

1. ,

2. - введение квантора общности,

3. - введение квантора существования.

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