Главная | Обратная связь | Поможем написать вашу работу!

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

Интерпретацией формулы в данной модели называется отображение I_R:Dⁿ®{0,1}, которое ставит в соответствие каждой упорядоченной n-ке аргументов предикатного символа логическое значение 0 (ложь) или 1 (истина). В выбранной интерпретации всякой замкнутой формуле ставится в соответствие ее логическое значение, а всякой формуле, содержащей свободные вхождения переменных – ее таблица, соответствующая всем возможным интерпретациям параметрических термов, являющихся ее аргументами. Логическое значение формулы А в интерпретации I обозначается I[A]. Для постоянной формулы это 0 или 1, для формулы, содержащей свободные вхождения переменных - вектор, элементами которого являются 0 и 1, длина которого зависит от числа различных наборов значений свободных переменных в данной предметной области. Формулу А сигнатуры S назовем выполнимой, если существует такая алгебраическая система M=(D;S), что А истинна в M при некоторых значениях свободных переменных. Формула А называется тождественно истинной (тавтологией), если А истинна в любой алгебраической системе сигнатуры S при любых значениях свободных переменных.

Говорят, что формула А семантически следует из множества формул Г (Г|-A), если для любой алгебраической системы M из истинности в M всех формул из Г при некоторых значениях переменных следует истинность А в M при тех же значениях переменных.

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

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

Примеры

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

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

Таблица 3

I(x)

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

Пусть D-предметная область, на которой задан 0-местный предикат r, т.е. I_R:D⁰ ® {0,1}. По определению D⁰= Æ (пустое множество). Поэтому на всей предметной области значение предиката одинаково и равно 0 или 1, а 0-местный предикат есть просто константа.

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

Пара переменных (х,у) в данной предметной области принимает 2²=4 набора значений, которым соответствуют четыре строки (табл. 4). Для каждого набора значений переменных функция интерпретации определяет логическое значение предиката как 0 или 1. Полное число функций интерпретации равно 2⁴=16. Каждый столбец в табл. 4 определяет один из 16 возможных предикатов. При принятом способе записи функций I_j(x,y) индекс j равен номеру двоичного набора j-го столбца, старший разряд которого находится в верхней строке таблицы. Конкретный предикат может быть задан указанием интерпретирующей функции. Например, Р(х,у)ÛI₁₁(x,y)Û(1011).

Таблица 4

x	y	I₀	I₁	I₂	...	I₇	I₈	I₉	...	I₁₄	I₁₅
					...				...
					...				...
					...				...
					...				...

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

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

Таблица 5

x₁x₂... x_n	I₀[P⁽ⁿ⁾]	I₁[P⁽ⁿ⁾]
1 1... 1

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

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

Таблица 6

x	I₀	I₁	I₂	I₃	I₄	I₅	I₆	I₇

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

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒