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), а формула

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

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

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

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

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

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

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

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

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

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

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

1. х(А(х)с)хА(х)с;

2. хА(х)уВ(у)ху(А(х)В(х)).

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

5. Предикаты А(х, у) и В(у, 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. х(А(х)В(х))…;

    2. х(А(х)vB(x))…;

    3. Cvx(B(x))…;

    4. Cx (B(x))…;

    5. Cx(B(x))…;