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

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

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

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

4. Р(^.), F(^.) - одноместные предикатные перемен­ные; q(^.,^.,...,^.), R(^.,^.,...,^.) n-местные предикатные переменные. P⁰(^.), Q⁰(^., ^., …,^.) - символы постоянных предика­тов.

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

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

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

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

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

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

3. Если А и В — формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой - свободной, то слова А v В, А& В, А®В есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, явля­ются свободными, а те, которые были связанными, яв­ляются связанными.

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

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

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

Например, если Р(х) и Q(x, у) - одноместный и двухме­стный предикаты, а q, r -переменные высказывания, то формулами будут слова: q, Р(х), P(x)Q(x°,y),

"хР(х)® $xQ(x, у),

Не является формулой слово: "xQ(x, y) ® Р(х). Здесь нарушено условие п.3, так как в формулу"xQ(x, y) пе­ременная х входит связано, а в формулу Р(х) перемен­ная х входит свободно.

Выражение "у($уР(х,у))VQ(x) не является формулой, т.к. квантор всеобщности на у навешан на формулу $уР(х,у), в которой переменная у уже связана квантором существования.

Выражение "у, хР(х, у) не является формулой, т.к. переменной х не присвоен квантор.

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

3. Значение формулы логики предикатов.

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

При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное зна­чение.

Рассмотрим формулу $y"z(P(x,y)®P(y,z)). Двухместный предикат Р(х,у) определен на множестве М х М, где М = {0,l,2,...,n,..}. В формулу входит переменный предикат Р(х,у), предметные переменные х, у,z, две из которых у и z — связанные кванторами, а х - свободная.

Возьмем за конкретное значение предиката Р(х,у)фиксированный предикат Р°(х,у): «х<у», а свобод­ной переменной х придадим значение х⁰ = 5 ÎМ. Тогда при значениях у, меньших х° = 5 предикат Р⁰(х⁰,y) при­нимает значение ложь, а импликация Р(х, у) ® Р(у, z)при всех z Î М принимают значение истина, то есть высказывание $y"z(P⁰(x,y)®P⁰(y,z)) имеет значение «истина».

Рассмотрим еще пример на вычисление значения формулы.

Дана формула "x(P(x)Q(x)®R(x)), где предикаты определены на множестве N. Найти ее значение, если P(x): «х делится на 3», Q(x): «х делится на 4», R(x): «х делится на 2».

Данная формула является высказыванием, т.к. х связанная переменная. Следовательно, значение формулы будет зависеть только от значений предикатных переменных. P(x)Q(x)- означает, что х делится на 12. Тогда предикат P(x)Q(x)®R(x): «если х делится на 12, то х делится на 2» - тождественно истинный, следовательно формула "x(P(x)Q(x)®R(x) принимает значение «истина».

4. Равносильные формулы логики предикатов.

Определение 1. Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.

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

Здесь, как в алгебре высказываний, для равносиль­ных формул принято обозначение А º В.

Ясно, что все равносильности алгебры высказыва­ний будут верны, если в них вместо переменных выска­зываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносиль-ностей. Пусть А(х) и В(х) - переменные предикаты, а С - переменное высказывание. Тогда:

Справедливость первых двух равносильностей очевидна. Первая означает, что если не верно, что для любого х истинно А(х), значит, найдется такое х, что А(х) – не истина. Аналогичные рассуждения доказывают справедливость и второй равносильности. Равносильности 1 и 2 широко используются при преобразованиях с выражениями, содержащими отрицания.

Пример: Найти отрицание формул

Докажем справедливость какой-либо из остальных равносильностей, например, равносильности 10: $х(А(х)vB(x))º$xA(x)v$xB(x).

Для доказательства достаточно рассмотреть два случая:

1. Пусть А(х) и В(х) – тождественно ложны. Тогда будет тождественно ложным предикат А(х)vB(x) и будут ложными высказывания $хА(х)v$xB(x), $х(А(х)vB(x)).

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

Аналогичным образом доказываются и остальные равносильности.

Отметим, что формула "х[А(х) v В(х)] не равносильна формуле "хА(х) v "xB(x), а формула

$х[А(х)L В(х)] не равносильна формуле $хА(х)L $хВ(х). Однако, справедливы равносильности:

Рассмотрим еще примеры применения равносильных преобразований.

На множестве М определены предикаты А(х) и В(х). Доказать, что высказывание "хА(х) ложно, если истинно высказывание

Преобразуем формулу:

значит, "хА(х)=0.

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

тогда $хА(х)=0, значит, I_A = Æ, I_B – любое подмножество области определения М.

Задачи для самостоятельного решения.

1. Какие из следующих выражений являются формулами? В каждой формуле выделить свободные и связанные переменные:

2. Даны утверждения А(n):«число п делится на 3», В(n): «число п делится на 2», С(n): «число п делит­ся на 4», D(n): «число п делится на 6», Е(n): «число п делится на 12». Укажите, какие из следующих утверж­дений истинны, какие ложны:

3. Доказать равносильности:

1) "х(А(х)®с)º$хА(х)®с;

2) $хА(х)$уВ(у)º$х$у(А(х)В(х)).

4. Каким условиям удовлетворяют области истинности предикатов А(х) и В(х), определенных на множестве М, если истинно высказывание:

1. Предикаты А(х, у) и В(у, z) определены на множестве МхМ, где М={a, b, c}. Записать формулу $x$уA(x, y)®$у"хB(х, у) без кванторных операций.

6. Дан предикат Q(x,y): «х делится на у». Какие из предикатов тождественно истинные и какие тождественно ложные: "хQ(x,y), $уQ(x,y), "уQ(x,y), $хQ(x,y). Найти значения высказываний: $х$уQ(x,y): "у$хQ(x,y): $у"хQ(x,y): "х"уQ(x,y).

Контрольные вопросы

1. Как одноместный предикат можно превратить в единичное высказывание?

2. Что понимают под выражением "хР(х)?

3. Что понимают под выражением $хР(х)?

4. Каким образом двухместный предикат превратить в одноместный и - в высказывание?

5. Какой символикой можно пользоваться в логике предикатов?

6. Сформулировать определение формулы логики предикатов.

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

8. Сформулировать оба определения равносильных формул логики предикатов.

9. Какие равносильности используются при построении отрицаний формул?

10. Закончите равносильности:

1) "х(А(х)LВ(х))º…;

2) $х(А(х)vB(x))º…;

3) Cv"x(B(x))º…;

4) CL"x (B(x))º…;

5) C®"x(B(x))º…;