<<
>>

3.4. Основные равносильности для предикатов

Пусть формулы А и В имеют одно и то же множество свободных переменных (в том числе и пустое).

Формулы А и В равносильны в данной интерпретации, если на любом наборе значений свободных переменных они принимают одинаковое значение (т.

е. формулы выражают один и тот же предикат).

Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М.

Формулы А и В равносильны (),если они равносильны на всех множествах.

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

· Перенос квантора через отрицание

· Вынос квантора за скобки

Q – не зависит от х

Q – зависит от х

только в одну сторону!

Пусть P(x) – x пошел в театр, Q(x) – x пошел в кино, тогда

.

Но .

Аналогично, пусть P(x) – x делится на 2, Q(x) – x делится на 3, тогда

, но

.

· Перестановка одноименных кванторов

1. Перестановка разноименных кванторов

· Переименование связанных переменных

х, у принадлежат одной предметной области

· Отбрасывание квантора

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

Доказательство.

1. - аксиома исчисления предикатов.

2. - аксиома исчисления предикатов.

3. Для исчисления высказываний доказано правило транзитивности:

4. Из 1 и 2 по правилу транзитивности получаем:

5. Введение квантора существования (правило вывода исчисления предикатов ):

6. Введение квантора общности (правило вывода исчисления предикатов

):

7. Преобразуем связанную переменную {y/z}

8. Преобразуем связанную переменную {x/v}

Таким образом, теорема доказана.

<< | >>
Источник: Викентьева О. Л.. Математическая логика и теория алгоритмов. Конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ. Пермь, 2007г.. 2007

Еще по теме 3.4. Основные равносильности для предикатов:

  1. Пафос фактов - вот основной прием для возбуждения чувства у слушателей на суде.
  2. 7.1. Основания (мотивы) для слияний и приобретений
  3. Глава 6. Начала логики предложений
  4. Глава 7. Начала логики предикатов
  5. Глава 9. Конструктивные и неконструктивные выводы
  6. Глава 10. Теория доказательства: кваиториые правила
  7. 2.1 Концепции управления процессами взаимоотношений промышленных предприятий с потребителями продукции как точка отсчета для планирования производства
  8. Приложение Д Примерный перечень основных вопросов для проведения вводного инструктажа (программа)5 1. Общие сведения о структурном подразделении
  9. ПУТИ УЛУЧШЕНИЯ ИСПОЛЬЗОВАНИЯ ОСНОВНЫХ ФОНДОВ
  10. Основные равносильности.
  11. ОСНОВНЫЕ УЗЛЫ РУССКОЙ РЕЧИ-ИДЕИ Б XIX—XX ВЕКАХ
  12. Основные равносильности
  13. 2.1.3. Равносильность формул логики высказываний
  14. 2.4.1. Основные понятия, связанные с предикатами
  15. 2.4.9. Равносильность формул логики предикатов
  16. 3.4. Основные равносильности для предикатов
  17. Риторические предикаты
  18. 9. Основні питання для підготовки до заліку