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

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

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

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

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

Предикаты

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

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

X<Y

X+Y=Z

X,Y – братья.

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

Например:

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

2<5

2+3=5

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

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

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

Р(х1,…,хn) : Mn®{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. Квантор общности ( Тема 3. Логика и исчисление предикатов - student2.ru ).

Тема 3. Логика и исчисление предикатов - student2.ru - высказывание истинное для каждого Тема 3. Логика и исчисление предикатов - student2.ru , т. е. это высказывание не зависит от xi.

2. Квантор существования ( Тема 3. Логика и исчисление предикатов - student2.ru ).

Тема 3. Логика и исчисление предикатов - student2.ru - высказывание истинно, если существует Тема 3. Логика и исчисление предикатов - student2.ru , для которого это высказывание истинно.

Для конечных множеств операции навешивания кванторов можно выразить через операции & и Тема 3. Логика и исчисление предикатов - student2.ru .

Пусть Тема 3. Логика и исчисление предикатов - student2.ru

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

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

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

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

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

1. Алфавит:

· Связки: Тема 3. Логика и исчисление предикатов - student2.ru (основные), & , Тема 3. Логика и исчисление предикатов - student2.ru ( дополнительные).

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

· Кванторы Тема 3. Логика и исчисление предикатов - student2.ru , Тема 3. Логика и исчисление предикатов - student2.ru .

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

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

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

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

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

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

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

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

2) Если А – формула, то Тема 3. Логика и исчисление предикатов - student2.ru - тоже формула.

3) Если А и В – формулы, то Тема 3. Логика и исчисление предикатов - student2.ru - формулы.

4) Если А – формула, содержащая свободную переменную х, то Тема 3. Логика и исчисление предикатов - student2.ru - формулы.

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

Вхождения переменных в формулах Тема 3. Логика и исчисление предикатов - student2.ru называются связанными, переменные не равные х остаются свободными.

Пример

Тема 3. Логика и исчисление предикатов - student2.ru - х – свободная переменная, у – связанная переменная.

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

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

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

А1: Тема 3. Логика и исчисление предикатов - student2.ru

А2: Тема 3. Логика и исчисление предикатов - student2.ru

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

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

P1: Тема 3. Логика и исчисление предикатов - student2.ru ,

P2: Тема 3. Логика и исчисление предикатов - student2.ru ,

где t – терм.

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

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

2. Тема 3. Логика и исчисление предикатов - student2.ru - введение квантора общности,

3. Тема 3. Логика и исчисление предикатов - student2.ru - введение квантора существования.

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

Интерпретация

Интерпретация I исчисления предикатов K с областью интерпретацией M – это набор функций, который сопоставляет:

· каждой предметной константе a элемент I(a)ÎM;

· каждому n-местному функтору f операцию I(f):Mn®M. Тема 3. Логика и исчисление предикатов - student2.ru

· каждому n-местному предикату Р отношение I(P)Ì Mn.

Для нас имеют смысл только интерпретированные предикаты, т. е. те, которым поставлены в соответствие некоторые отношения (для одноместных предикатов – свойства).

Пример.

Рассмотрим 3 формулы.

1. P(x,y)

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

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

В качестве области интерпретации возьмем множество целых положительных чисел и интерпретируем P(x,y) как отношение Тема 3. Логика и исчисление предикатов - student2.ru .

Тогда формула 1 – это предикат Тема 3. Логика и исчисление предикатов - student2.ru . Он принимает значение истинно при любых a,b принадлежащих множеству целых положительных чисел, если Тема 3. Логика и исчисление предикатов - student2.ru .

Формула 2 – это предикат, который принимает значение истинно при x=1, т. е. он выражает свойство, что для каждого положительного целого числа y Тема 3. Логика и исчисление предикатов - student2.ru .

Формула 3 – это предикат, который всегда будет истинен. Он выражает свойство: существует положительное целое число y, для которого Тема 3. Логика и исчисление предикатов - student2.ru .

Формула называется истинной, если она выполняется на любом наборе элементов М.

Формула называется ложной, если она не выполняется на любом наборе элементов М.

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

Теорема: Любая выводимая в исчислении предикатов формула – общезначима.

Наши рекомендации