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

В логике предикатов пользуются следующей символикой:

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

2. Предметные переменные – x, y, z, …, которые пробегают значения из некоторого множества М; , … - предметные константа, т.е. значения предметных переменных.

3. , N - предикатные символы, - - местный предикатный символ.

4. , - функциональные символы, - - местный функциональный символ.

5. Символы логических операций , , , -, .

6. Символы кванторных операций , .

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

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

2. Если P(…) – n-местная предикатная переменная или постоянный предикат, a , , …, - предметные переменные или предметные постоянные, все различные, то P( , , …, ) есть формула.

В этой формуле предметные переменные являются свободными. Формулы вида 1 и 2 называются элементарными.

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

4. Если A – формула, то - формула, и характер предметных переменных при переходе от формулы A к формуле не меняется.

5. Если A(x) – формула , в которую предметная переменная x входит свободно, то слова xA(x) и xA(x) являются формулами, причем предметная переменная в них входит связно.

6. Никакая другая строка символов формулой не является.

Пример1.

1. ;

2. ( );

3. ;

4. ;

5. ;

6. ;

Решение. Выражения 1, 2, 4, 6 являются формулами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3 и 5 не являются формулами.

В выражении 3 операция конъюнкции применена к формулам и : В первой из них переменная x свободна, а во второй связана квантором общности, что противоречит определению формулы. В выражении 5 квантор существования по переменной у навешен на формулу , в которой переменная y связана квантором общности, что так же противоречит определению формулы.

В формуле 1 переменная y свободна, а переменнаые x и z связаны. В формуле 2 нет предметных переменных. В формуле 4 переменная x связанна, а переменная y свободна.

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту форму предикаты. Логическое значение формулы логики предикатов зависит от значения трех видов переменных ,входящих в формулу:

а) переменных высказываний;

б) свободных предметных переменных из множества М;

в) предикатных переменных;

При конкретных значениях этих переменных формула принимает конкретное логическое значение.

Пример 2. Дана формула

,

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

1. P(x): «число x делится на 3», Q(x): «число x делится на 4», R(x) : « число x делится на 2»;

2. P(x): “ число x делится на 3», Q(x): « число x делится на 4», R(x): 2 число x делится на 5».

Решение. В обоих случаях конъюнкция P(x)&Q(x) есть утверждение, что число x делится на 12. Но тогда при всех x, если число x делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.

Так как из делимости числа x на 12 не при всех x следует делимость числа x на 5, то в случае 2) формула ложна.

Пример 3. Вычислить значение формулы

, если предикат P(x,y) имеет значение - «число x меньше числа y» и определен на множестве М=N*N.

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

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

Две формулы логики предикатов A и B называются равносильными, если они равносильны на всякой области.

Обозначение равносильности:

Все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Сюда, в первую очередь, следует отнести равносильности

,

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

Пример 4. Найти отрицание следующих формул

1.

2. ;

3. ;

Решение.

1. ;

2. ;

3.

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

Пример 5. Доказать равносильность

Решение. Для доказательства равносильности достаточно рассмотреть 2 случая:

1. Пусть предикаты A(x) и B(x) тождественно ложны. Тогда будет тождественно ложным и предикат . При этом будут ложными высказывания и .

2. Пусть теперь хотя бы один из предикатов (например, A(x)) не тождественно ложный. Тогда будет не тождественно ложным и предикат . При этом будут истинными высказывания и , а значит, будут истинными и исходные формулы.

Следовательно