Студопедия — Основные определения.
Студопедия Главная Случайная страница Обратная связь

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

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






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

Предикат – это логическая функция одного или нескольких переменных. Результатом этой функции является 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-10-19; просмотров: 462. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Опухоли яичников в детском и подростковом возрасте Опухоли яичников занимают первое место в структуре опухолей половой системы у девочек и встречаются в возрасте 10 – 16 лет и в период полового созревания...

Способы тактических действий при проведении специальных операций Специальные операции проводятся с применением следующих основных тактических способов действий: охрана...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Меры безопасности при обращении с оружием и боеприпасами 64. Получение (сдача) оружия и боеприпасов для проведения стрельб осуществляется в установленном порядке[1]. 65. Безопасность при проведении стрельб обеспечивается...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия