1. Определение исчисления предикатов

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

1. Алфавит:

связки - основные  

- дополнительные & 

служебные символы ( , )

кванторы - всеобщности 

- существования 

предметные - константы a, b, …, a₁, b₁, …

- переменные x, y, …, x₁, y₁, …

предметные предикаты P, Q, …

функторы f, g, …

2. Формулы имеют следующий синтаксис:

< формула > ::= < атом > |

 < формула > |

(< формула >  < формула > ) |

 < переменная > < формула > |

 < переменная > < формула >

< атом > ::= < предикат > ( < список термов > )

< список термов > ::= < терм > | < терм > | < список термов >

< терм > ::= < константа > |

< переменная > |

< функтор > ( < список термов > )

При этом должны быть выполнены следующие условия: в терме функтор должен быть n-арным, в атоме – предикат должен быть n-арным.

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

Вхождения переменной x в формулы  x A и  x A называются связанными.

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

Одна и та же переменная может иметь в одной и той же формуле как свободные, так и связанные вхождения. Например, рассмотрим формулу  x ( P ( x )   y Q ( x , y ) ) и её подформулы.

В подформулу  y Q ( x, y ) переменная x входит свободно, а вхождения переменной y связаны квантором существования. Таким образом, эта подформула не замкнута. С другой стороны, то же самое вхождение переменной x в данную подформулу является связанным вхождением в первой подформуле  x P ( x ). Поэтому формула замкнута.

3. Аксиомы

Все аксиомы из логики высказываний плюс две следующие:

 x A ( x )  A ( t )

A ( t )   x A ( x )

где терм t свободен для переменной x.

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

A, A  B B  A ( x ) B  A ( x )

 Modus ponens  ⁺  ⁺

B B   x A ( x )  x A ( x )  B

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

Каждое вхождение переменной (если, конечно, они имеются) в формуле находится в области действия квантора по этой переменной. Термы, предикаты и формулы, не содержащие переменных, называются основными.

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

1. Термы представляют объекты предметной области; при этом используются либо конкретные имена (константы), либо обобщённые имена (переменные).

2. Предикаты выражают отношения между объектами предметной области, которые обозначены с помощью термов.

3. Предложения описывают логические свойства отношений.

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

Таким образом, интерпретация должна специфицировать множество объектов, называемых областью интерпретации.

При этом:

1. Каждой константе из формулы ставится в соответствие некоторый определённый элемент из непустой предметной области.

2. Каждой переменной из формулы ставится в соответствие отображение терма из непустой предметной области (конкретизация и подстановка).

3. Каждой n-арной предикатной константе из формулы ставится в соответствие отображение вида { true, false }.

Если задана интерпретация на области D некоторой формулы F логики предикатов, то можно вычислить значение этой формулы по следующим правилам:

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

2. Если заданы значения формул P и Q, то значения формул логики высказываний ( P, PQ, PQ, PQ, P  Q ) вычисляются по таблице истинности.

3. Формула вида  x A принимает значение true, если A принимает значение true хотя бы для одного элемента x  D, в противном случае – false.

4. Формула вида  x A принимает значение true, если A принимает значение true для каждого элемента x  D, в противном случае – false.

3. Выводы

Понятие предикат обобщает понятие высказывание. Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.

Например, возьмём высказывания:

Сократ – человек

Платон – человек

Оба эти высказывания выражают свойство “быть человеком”.

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

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

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

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