Интерпретация атомных формул

Логическое значение постоянной формулы может быть определено как 0 или 1 (ложь или истина) в данной модели. Для параметрических формул функция интерпретации определяет значение формулы на каждом из возможных наборов значений переменных в предметной области. Если |D| - мощность предметной области, n - местность предикатного символа, то число различных наборов значений переменных равно числу размещений с повторениями , т.е. число различных интерпретаций предикатного символа равно быстро возрастает с ростом n.

Примеры

1. Пусть предметной областью является множество натуральных чисел N, и сигнатура содержит единственный предикатный символ: «(х - простое число)».

Таблица функции интерпретации бесконечна, ее фрагмент приведен в табл. 1.

Таблица 1Функция интерпретация предиката Р "X – простое число"

x

2. Указать значения 0-местного предиката на любой предметной области.

Пусть D-предметная область, на которой задан 0-местный предикат r. Тогда . По определению (пустое множество). Поэтому на всей предметной области интерпретация предиката одинакова и равна 0 или 1, т.е. 0-местный предикат есть просто константа.

3. Определить таблицы истинности всех 2-местных предикатов A(x,y) в предметной области .

Пара переменных (х,у) в данной предметной области принимает набора значений, которым соответствуют четыре строки, табл. 2. Для каждого набора значений переменных функция интерпретации определяет логическое значение предиката как 0 или 1. Полное число функций интерпретации равно Каждый столбец в табл. 2 определяет один из 16 возможных предикатов. В таблице истинности шестнадцати предикатов каждой функции сопоставлен столбец, обозначенный как , где j равен десятичному номеру двоичного вектора интерпретации, находящегося в данном столбце. Номер вектора читается в столбце таблицы сверху вниз, т.е. верхний разряд имеет вес , в следующем разряде – вес в двух последних – и соответственно.

Например, вектор функции интерпретации, помеченный индексом 10, имеет вид (1010).

Таблица 2Функции интерпретации двухместного предиката

x

y

4. Пусть D={1}. Найти множество значений предикатов произвольной местности.

В одноэлементной предметной области при любой местности n предиката набор значений переменных фиксирован и содержит одни единицы. В этом случае возможны два различных значения предикатов, табл. 3.

Таблица 3Интерпретация предиката произвольной местности в одноэлементной предметной области

11…1

5. Задать все возможные 1-местные предикаты на трехэлементной предметной области D={1,2,3}. Сколько различных 2-местных предикатов существует в данном случае ?

В одноместном предикате число различных наборов значений переменных равно 3. Следовательно, число строк таблицы равно трем, а число различных интерпретаций равно =8. Они представлены в табл.4.

Таблица 4 Функции интерпретации одноместного предиката в трехэлементной предметной области

x

Число 2-местных предикатов в данном случае определим так: число различных наборов значений переменных длины 2 , равно числу размещений с повторениями из 3-х элементов по 2, т.е. , а число возможных различных интерпретаций 2-местного предикатного символа равно . Например, вектор функции интерпретации с номером 497 Р(х,у)=I497=(111110001).

Дата добавления: 2014-11-08; просмотров: 390; Нарушение авторских прав

Мы поможем в написании ваших работ!