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

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

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 – любое подмножество области определения М.

Не нашли, что искали? Воспользуйтесь поиском: