2.4.8. Классификация формул логики предикатов

Сформулируем классификационные определения для формул логики предикатов. Рассмотрим некоторую интерпретацию с множеством М.

Определение. Формула А выполнима в данной интерпретации, если существует набор , aiÎ M, значений свободных переменных xi1, …, xin формулы А такой, что А|=И.

Определение. Формула А истинна в данной интерпретации, если она принимает значение И на любом наборе , aiÎ M, значений своих свободных переменных xi1, …, xin.

Определение. Формула А выполнима (в логике предикатов), если существует интерпретация, в которой А выполнима.

Определение. Формула А, истинная при любой интерпретации, называется общезначимой или тождественно-истинной (в логике предикатов).

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

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

Пример 64.

Выяснить является ли формула выполнимой и опровержимой: .

Решение.

Поскольку на переменную х навешены кванторы, то она является связной. В свою очередь переменная у является свободной. Формула не имеет вхождений нуль-местных предикатов. Значит, интерпретация будет состоять из трех шагов.

1. Для того чтобы выяснить является ли формула выполнимой, достаточно привести одну интерпретацию, которая обращает исходную формулу в истинное высказывание. Зададим множество М = {0}. Зададим предикат Р(х, у): «х = у». Поскольку заданное множество М имеет единственные элемент, то свободному вхождению переменной у припишем значение 0.

При такой интерпретации данная формула обращается в истинное высказывание.

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

Действительно, посылка данной импликации принимает значение и. Заключение импликации также принимает значение и.

Значит, исходная формула является выполнимой.

2. Для того чтобы выяснить является ли формула опровержимой, достаточно привести одну интерпретацию, которая обращает исходную формулу в ложное высказывание. Зададим множество М = N. Зададим предикат Р(х, у): «х < у». Свободному вхождению переменной у припишем значение 5.

При такой интерпретации данная формула обращается в ложное высказывание.

Действительно, посылка данной импликации принимает значение и, т.к. действительно во множестве натуральных чисел N найдутся числа меньше числа 5. Заключение импликации принимает значение л, т.к. не верно, что любое натуральное число меньше числа 5.

Значит, исходная формула является опровержимой.

Пример 65.

Доказать общезначимость формулы "х Р(х) ® $х Р(х).

Решение.

Допустим, что Р поставлен некоторый предикат на множестве М. Данная формула представляет собой импликацию. Вспомним, что импликация ложна только тогда, когда посылка истинна, а заключение ложно. В нашем случае такая ситуация невозможна. Поскольку, если не для любого элемента хÎМ выполняется предикат Р, то автоматически исходная формула обращается в истинное высказывание (независимо от того какое значение примет заключение импликации). Если же для любого элемента хÎМ выполняется предикат Р, то естественно заключение верно, т.е. найдется хÎМ такой, что выполняется предикат Р.

Таким образом, исходная формула "х Р(х) ® $х Р(х) общезначима.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.4.8. Классификация формул логики предикатов:

  1. Глава 5. Строение предложенийи их символическая запись
  2. Глава 7. Начала логики предикатов
  3. Глава 10. Теория доказательства: кваиториые правила
  4. Выражение силлогистики средствами логики предикатов
  5. ГЛАВА 5 Классическая логика предикатов
  6. Язык классической логики
  7. Теория моделей классической логики предикатов
  8. Теория доказательств классической логики предикатов
  9. Исчисление предикатов.
  10. ЛОГИКА ПРЕДИКАТОВ
  11. Интерес к разуму в арабо-исламской философии, разработанность концепции рационального знания, учения логики как способа достижения истины, вера в безграничные способности разума. Онтологические основания рационализма в арабо-исламской философии. Рационализм арабо-исламской философии как один из типов рационализма (в сопоставлении с рационалистическими тенденциями в индийской и китайской культурах). Рационализм критический и догматический. Значение мистической философии в развитии рационализма.
  12. 2.1.2. Формулы логики высказываний
  13. 2.1.3. Равносильность формул логики высказываний
  14. 2.2.1. Представление булевой функции формулой логики высказываний
  15. 2.4. Логика предикатов
  16. 2.4.6. Формулы логики предикатов
  17. 2.4.7. Интерпретация формул логики предикатов
  18. 2.4.8. Классификация формул логики предикатов
  19. 2.4.9. Равносильность формул логики предикатов