Тавтологии алгебры логики

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

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

В алгебре высказываний мы подробно изучили

одно из важнейших ее понятий и инструментов 

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

Теперь наша задача состоит в том, чтобы определить и

изучить соответствующее понятие в логике предикатов,

а затем на его основе продемонстрировать, насколько

тоньше и точнее язык и логика предикатов отражают

процессы человеческого мышления, нежели это делают

язык и логика высказываний.

Алфавит символов для формул

1. Предметные переменные: x, y, z, xi, yi, zi …(iN).

2. Нульместные предикатные формулы: P, Q, Pi, Qi …(iN).

3. Nместные предикатные переменные P(x,…), Q(y,…).

4. Символы логических операций: , , , ↔, —.

5. Кванторы: , .

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

Определение формулы предикатов

1. Каждая нульместная предикатная переменная есть формула.

2. Каждая nместная предикатная переменная P(x1,…,xn) есть

формула, в которой все предметные переменные свободны.

3. Если F  формула, и x  свободная предметная переменная,

то (x)(F), ( x)(F)  формулы, в которых переменная x 

связанная, а остальные свободные (если нет других кванторов).

4. Если F, F1, F2  формулы, то

 тоже формулы, причем предметные переменные, свободные

(или связанные) в одной из формул F, F1, F2, такие же и в новых

формулах.

5. Других формул нет.

Интерпретация формулы логики предикатов

Если в формулу логики предикатов вместо каждой

предикатной переменной подставить конкретный предикат,

определенный на некотором выбранном множестве М, то

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

множеством М.

Если подставить вместо свободных предметных переменных

конкретные предметы из множества М, то полученный предикат