<<
>>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 66.

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

Решение.

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

Пример 67.

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

1. ;

2. .

Решение.

1.

2.

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

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

  1. Глава 5. Строение предложенийи их символическая запись
  2. Глава 7. Начала логики предикатов
  3. Глава 10. Теория доказательства: кваиториые правила
  4. Выражение силлогистики средствами логики предикатов
  5. ГЛАВА 5 Классическая логика предикатов
  6. Язык классической логики
  7. Теория моделей классической логики предикатов
  8. Теория доказательств классической логики предикатов
  9. Исчисление предикатов.
  10. ЛОГИКА ПРЕДИКАТОВ
  11. 2.1.2. Формулы логики высказываний