Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Основные определения.

Читайте также:
  1. I. ОСНОВНЫЕ ПРИНЦИПЫ ПОЛИТИКИ ПЕРЕМЕН
  2. II. 1. ОСНОВНЫЕ ПОТРЕБНОСТИ ЧЕЛОВЕКА.
  3. II. НАЗНАЧЕНИЕ, ОСНОВНЫЕ ЗАДАЧИ И ФУНКЦИИ ПОДРАЗДЕЛЕНИЯ
  4. II. ОСНОВНЫЕ ПОЛОЖЕНИЯ ПО ОРГАНИЗАЦИИ ПРАКТИКИ
  5. IV. основные направления военно-патриотического воспитания.
  6. Архитектура и структура современных ЭВМ. Основные устройства и их назначение.
  7. Банки как основные участники кредитного рынка.

Как показывает практика, возможностей логики высказываний явно недостаточно для представления знаний. Напомним основные понятия более сложной логики предикатов первого порядка (ЛППП).

Предикат – это логическая функция одного или нескольких переменных. Результатом этой функции является 1 – истина или 0 – ложь.

Примеры. СТУДЕНТ (Вася), ПРОЖИВАНИЕ (x, Томск).

Терм – это константа, переменная или некоторая n-местная функция (функтор f(x1,…,xn))

Примеры. а, x, f(x, y).

Если P – n-местный предикат и t1…tn – термы, то P(t1,…,tn) – атом.

Примеры. P(x), P(x,y), P(a, x), P(x, y, f(x, y)).

В формулах используются логические связки (операции):ù, Ù, Ú, ®, «и кванторы:", $.

Рекуррентное определение формулы:

A) Атом – есть формула

B) Если F – формула, то ùF – формула.

C) Если F, G – формулы, то FÚG, FÙG, F®G, F«G – формулы.

D) Если F – формула, в которой есть переменная x, то "x F(x), $x F(x) – формулы (при этом переменная x называется связанной квантором всеобщности или существования).

E) Все переменные в формуле связаны кванторами.

Пример. Формализуем утверждение: «для любого натурального числа существует единственное натуральное число, непосредственно следующее за ним».

Введем предикаты E(x, y) – x=y, N(x) – x – натуральное число и функтор f(x) – следующее число (x+1).

"x [N(x)®$y [E(f(x), y)Ù"z [E(f(x), z)®E(y, z)]]].

Интерпретация формул производится следующим образом:

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

B) Каждой константе ставим в соответствие один элемент из D.

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

D) Определяем истинностное значение каждого предиката.

E) Устанавливаем истинностное значение формулы по таблицам истинности (это можно сделать только в случае, если все переменные в формуле связаны кванторами – иначе, формула бессмысленна)

Пример.

//пример на интерпретацию (1)

"x [P(x)→Q(x,f(x))]

A) D = {1, 2} – область определения

B) Константы отсутствуют

С) f (1) = 2 f (2) = 1

D) P (1) = 1 P (2) = 0

Q (1, 1) = 1 Q (1, 2) = 0 Q (2, 1) = 0 Q (2, 2) = 1

E) Вычисляем значение матрицы

x = 1

P (x) → Q (x, f (x)) = P (1) → Q (1, f(1)) = P(1) → Q (1, 2) =1 → 0 = 0

Таким образом:

"x [P(x) → Q (x, f(x))] = 0 в данной интерпретации.

В этой же интерпретации формула

$x [P(x) → Q (x, f(x))] = 1,

т.к.

при x = 2

P(x) → Q (x, f(x) = P(2) → Q (2, f (2)) = 0 → 0 = 1

 

 

Определения общезначимости, противоречивости и логического следствия точно соответствуют аналогичным понятиям в логике высказываний. Имеют место те же теоремы дедукции. Справедливыми остаются и эквивалентные преобразования.

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

А) Избавляются от операций ®, «с помощью соответствующих правил (см. 2.1.1).

B) Добиваются, чтобы ù стояло только перед атомом (используем законы Де Моргана см. 2.1.1)

С) Переносят кванторы в начало формулы, чтобы она имела вид:

//формула (2)

1 x1 2 x2 ….. n x n M [x1, …, xn]

В этом случае говорят, что формула представлена в ПНФ (предваренной норм форме). M[x1,…,xn] называется матрицей формулы.

Используются следующие эквивалентные преобразования:

//формулы (3)

x F(x) G = x [F(x) G]

в случае, если G не содержит переменную x:

1 x F (x) 2x G(x) = 1 x 2 y [F1(x) G2(y)],

т.е. в случае необходимости производим замену переменных.

В двух частных случаях можно избежать переименования переменной:

//формулы (4)

"x F (x) Ù "x G(x) = "x [F(x) Ù G(x)]

$ x F(x) Ú $ x G (x) = $ x [F(x) Ú G(x)]

D) Добиваются, чтобы матрица была представлена в КНФ.

E) Избавляются от $ путем замены связанных им переменных на константы.

//формула (5)

F = x1 xi-1 $ xi xi+1 xn M [x1 …, xi-1, xi ; xi+1; xn]

G = x1 xi-1 xi+1 xn M [x1, …, xi-1, a, xi+1, … xn],

где:

а – некоторая константа.

Таким образом, заменяем переменные под $ на константы.

Это преобразование не является эквивалентным, однако оно сохраняет противоречивость, т.е. F- противоречива, тогда и только тогда, когда противоречива G. Этого достаточно, если мы пользуемся 2-й теоремой дедукции.

 


Дата добавления: 2015-09-06; просмотров: 110 | Нарушение авторских прав


Читайте в этой же книге: Введение | Точка зрения Петрунина. | Данные и знания. Основные модели представления знаний | Булева алгебра. | Стратегии проведения резолюции. | Упорядоченный линейный вывод в ЛППП. | Применение поиска в пространстве состояний при реализации автоматизированного логического вывода. | Логический вывод на хорновских дизъюнктах. | Понятие экспертной системы и применение логического вывода при построении экспертных систем. | Запросы класса C. |
<== предыдущая страница | следующая страница ==>
Метод резолюции в ЛВ.| Метод резолюции в ЛППП.

mybiblioteka.su - 2015-2024 год. (0.008 сек.)