Интерпретация формул логики предикатов

Формулы логики высказываний всегда можно рассматривать как высказывательные формы с высказывательными переменными либо как высказывания. Формулы логики предикатов становятся высказывательными формами с предметными переменными или высказываниями, если задать непустое множество М значений, которые можно приписывать предметным переменным, входящим в формулу, а каждому n-местному предикатному символу поставить в соответствие n-местный предикат, определенный на множестве М (причем двум различным n-местным предикатным символам с одинаковыми предикатными буквами ставится в соответствие один и тот же предикат); нуль-местным предикатным символам независимо от выбора множества М приписывается нуль-местный предикат, т.е. одно из значений истинности {И, Л}.

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

Обращение формулы в высказывание описанным выше способом будем называть интерпретацией этой формулы.

Интерпретация замкнутой формулы состоит из следующих шагов:

1. задается множество М;
2. каждой предикатной букве, входящей в n-местный предикатный символ ставится в соответствие n-местный предикат, определенный на множестве М;
3. каждому нуль-местному предикатному символу приписывается одно из значений истинности.

Если формула – открытая, то добавляется еще один шаг:

1. каждому свободному вхождению переменной ставится в соответствие элемент множества М.

Пример 63.

Дать интерпретацию формуле $y "x P(x, y) ® (Q(x) Ù R).

Решение.

Данная формула $y "x P(x, y) ® (Q(x) Ù R) является открытой, следовательно интерпретация будет состоять из четырех шагов:

1. Пусть М = {1, 2}.
2. Предикатной букве Р поставим в соответствие двуместный предикат, заданный таблицей (табл. 65):

Таблица 65

а предикатной букве Q – предикат, принимающий следующие значения:

1. Предикатному символу R припишем значение и.
2. Свободному вхождению переменной х припишем значение 1.

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

В самом деле, посылка данной импликации принимает значение и, так как, согласно таблице Р, высказывание Р(1; 1) и Р(2; 1) – истинные, т.е. существует значение у (равное 1) такое, что при всяком значении х (равном 1 или 2) Р(х; у) истинно. Заключение также принимает значение и, так как Q(1) и R истинны.

Если же, например, переменной х приписать значение 2, либо символу R – значение л, либо букве Q – предикат «быть четным числом», оставляя все остальное без изменения, то всякий раз данная формула будет получать значение л.