Задать вопрос юристу

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

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

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

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

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

Определение. Формулы А и В равносильны в логике предикатов, если они равносильны на всех множествах (АºВ).

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

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

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

Кроме этого, существуют следующие правила:

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

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

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

"х "у А(х, у) º "у "х А(х, у),

$х $у А(х, у) º $у $х А(х, у).

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

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

Определение. Формула А, равносильная формуле В, и не содержащая символов ®, », а также составных формул под знаком отрицания, называется приведенной формой формулы В.

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

Пример 66.

Преобразовать в приведенную форму формулу .

Решение.

Определение. Приведенная формула называется нормальной (ПНФ), если она не содержит символов кванторов или все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы.

Пример 67.

Преобразовать в ПНФ формулы:

1. ;

2. .

Решение.

1.

2.

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

Еще по теме 2.4.9. Равносильность формул логики предикатов:

  1. 2.1.3. Равносильность формул логики высказываний
  2. 2.4.6. Формулы логики предикатов
  3. 2.4.8. Классификация формул логики предикатов
  4. 2.4.7. Интерпретация формул логики предикатов
  5. 3.4. Основные равносильности для предикатов
  6. 1.5. Равносильные формулы
  7. ЛОГИКА ПРЕДИКАТОВ
  8. Глава 7. Начала логики предикатов
  9. Тема 3. Логика и исчисление предикатов
  10. Теория моделей классической логики предикатов
  11. Теория доказательств классической логики предикатов