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

Пример 9.3

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

Логическое значение формулы логики предикатов зависит от значений трех видов переменных:

1) входящих в формулу переменных высказываний;

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

3) предикатных переменных.

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

Показать, при каких значениях переменных формула

,

в которой двухместный предикат определен на множестве , где , является истинной или ложной.

Решение. В данную формулу входит переменный предикат (предикат переменный, поскольку в нем – свободная переменная), предметные переменные , две из которых и связаны кванторами, и – свободная.

Возьмем за конкретное значение предиката фиксированный предикат , например, «», а свободной переменной придадим значение . Тогда при значениях , меньших , предикат : принимает значение ложь, а импликация при всех принимает значение истина, то есть высказывание имеет значение «истина».

Можно подобрать другие фиксированные предикаты, при которых это высказывание будет истинным.

Равносильные формулы логики предикатов на области М – это формулы, которые принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.

Равносильные формулы логики предикатов – это формулы, которые принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к любой области.

Все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Кроме того, существуют и равносильности самой логики предикатов. Для простоты обозначения равносильность формул будем обозначать традиционным знаком равенства «=».

Равносильности логики предикатов. и – переменные предикаты, С – переменное высказывание.

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. .

13. .

14. .

15. .

16. .

17. .

Равносильность 1 читается следующим образом: если не для всех истинно , то существует , при котором будет истиной .

Равносильность 2: если не существует , при котором истинно , то для всех будет истиной .

Аналогичным образом можно прочитать и другие равносильности.

Некоторые равносильности легко доказываются на основании ранее приведенных равносильностей. Например, равносильности 3 и 4 получаются из равносильностей 1 и 2 соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.

Кроме указанных равносильностей можно получить любую равносильную формулу, заменяя связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора.

Например , .

Дата добавления: 2017-02-01