Формулы логики предикатов

1. Определение и значение формулы логики предикатов.
2. Равносильные формулы логики предикатов.
3. Предваренная нормальная форма представления формул логики предикатов.
4. Общезначимость и выполнимость формул логики предикатов.
5. Проблема разрешимости для общезначимости и выполнимости формул логики предикатов.

Введение

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

Вопрос 1. Определение и значение формулы логики предикатов

Определим алфавит символов, из которых будут составляться формулы логики предикатов:

1. Переменные высказывания: р, q, r, … (принимают два значения: 1 – истина, 0 - ложь).

2. Предметные переменные: х, у, z, х_i, у_i, z_i (iÎN) (принимают значения из некоторого множества М); предметные константы (значения предметных переменных) - х⁰, у⁰, z⁰, ….

3. Одноместные предикатные переменные: Р(·), F(·),Р_i(·), F_i(·) (iÎN); n-местные предикатные переменные: Q(·, ·, …, ·), R(·, ·, …, ·), Q_i(·, ·, …, ·),R_i (·, ·, …, ·) (iÎN). Эти символы называются переменными предикатами.

Р⁰(·), Q⁰(·, ·, …, ·) - символы постоянных предикатов.

4. Символы логических операций: ¯, Ù, Ú, ®, ↔.

5. Символы кванторных операций: ", $.

6. Вспомогательные символы: скобки, запятые.

Каждая формула является словом в алфавите, содержащем указанные выше в пунктах 1-6 символы.

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

О.1.1.(определение формулы логики предикатов)

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

2. Если Q(·, ·, …, ·) - n-местная предикатная переменная или постоянный предикат, а х₁,х₂,…,х_n – предметные переменные или предметные постоянные (не обязательно все различные), то Q(х₁, х₂, …, х_n) есть формула.

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

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

(1)

так же являются формулами. При этом свободные (связанные) переменные в формулах А и В остаются свободными (связанными) во всех формулах (1), т.е. характер предметных переменных при переходе от формул А и В к формулам (1) не меняется.

4. Если А – формула, то (Ā) – формула, причем характер предметных переменных при переходе от формулы А к формуле (Ā) не меняется.

5. Если А – формула, в которую предметная переменная х входит свободно, то слова ("х А) и

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

6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1-5, не является формулой.

Формулы, определенные в пунктах 1 и 2, называются элементарными или атомарными. Формулы, не являющиеся элементарными, называются составными.

Замечание

Условимся вносить некоторые упрощения в записи формул логики предикатов: опускать внешние скобки и некоторые внутренние, если последовательность операций, исходя из их приоритета, не вызывает сомнений; иногда круглые скобки заменяют квадратными.

Пример 1.

Если Р(х) и Q(х,у) – одноместный и двуместный предикаты, а р и r – переменные высказывания, то:

1) р, Р(х) – элементарные формулы;

2) Р(х) Ù Q(х⁰, у), "х Р(х) ®$х Q(х,у), (Q(х,у) Ú р) ® r – составные формулы;

3) "х Q(х,у) ® Р(х) – не формула (нарушено условие пункта 3, так как в формулу "х Q(х,у) переменная х входит связно, а в формулу Р(х) - свободно).

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

В формулах вида "х А и $х А формула А называется областью действия квантора " и $ соответственно. Ясно, что вхождение переменной в формулу будет связанным, если эта переменная находится в области действия квантора по данной переменной.

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

Пример 2.

Открытые формулы: Р(х), "х Р(х) ®$х Q(х,у), "х $у R(х,у,z).

Замкнутые формулы: р, "z Р(z), "х $у R(х,у), "х Р(х) ®$у "х Q(х,у).

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

а) в формуле свободные и связанные переменные должны обозначаться разными буквами;

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

Нарушение условий а) и б) называется коллизией переменных.

Пример 3. "х (Р(х) ® $х Q(х,у)) – не формула (нарушено условие б)).