Методы представления знаний Формальные языки и формальные системы



страница2/17
Дата15.01.2013
Размер1.11 Mb.
ТипЛекции
1   2   3   4   5   6   7   8   9   ...   17

Правила вывода в исчислении высказываний


  1. Правило отделения: Если выводимо из , то выводимо B:

  2. Правило подстановки: в любую формулу исчисления высказываний на место пропозициональной переменной можно подставить формулу исчисления высказываний, при этом истинность не изменится:

пусть - формула исчисления высказываний

- некоторая формула с другими переменными.

Тогда подстановка в формулу (в переменные) не изменит смысл .
Пример.

Докажем один из постулатов, например .

Используем Ax1 и правило подстановки:

Из Ax2:

Вместо подставим :

Применим правило вывода:

Следовательно, Y - выводимо.

К Y опять применим правило вывода: .

Следовательно, Y’ -выводимо.
Формулы, в которых нет свободных переменных, называются высказываниями. Если кванторами связываются только переменные, то имеем предикат 1-го порядка. Если кванторами связываются формулы, то имеем предикат 2-го порядка.
    1. Аксиомы исчисления предикатов


В первую очередь, к ним относятся Ax1, Ax2, Ax3 (при этом на место пропозициональных переменных ставятся переменные). Кроме этого, есть и собственные аксиомы:

  1. Аксиома генерализации:

  2. Аксиома спецификации (если есть общее утверждение, то верно частное): , -терм.
    1. Формальная система


, где

- символы

- множество правил грамматики, формулы, порожденные символами

-аксиомы

- множество правил вывода. Способ порождения из A правил G.


Если среди аксиом существуют прикладные аксиомы (аксиомы предметной области), то формальная система называется формальной теорией.
Пример.

Теория чисел (формальная арифметика). Чтобы прийти к ней от логики, нужно добавить функциональные символы , сложения , умножения и предикатный символ равенства .

Понятие полуразрешимости

Не существует алгоритма, по которому можно сказать, является - ли данная формула исчисления предикатов теоремой (в исчислении высказываний этот алгоритм существует).

Интерпретация (построение модели).

Пусть дан язык, дано множество . Определим функцию - функцию интерпретации, которая каждой константе языка ставит в соответствие некоторый элемент :



a - переменная

- объекты реального мира

- n-местный функциональный символ.

- отношение

- предикат

Тогда – модель (или интерпретация).

Понятие истинности модели



Атомарная формула , где , - константы, истинна в модели (записывается ), если пара .

Далее по индукции.

Полнота и корректность модели

Модель корректна, если всякая формула, выводимая в исчислении, оказывается истинна в модели.

Модель полна, если всякая формула, истинная в модели, выводима в исчислении.

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

Напомним, что модель  – это некоторая пара , где М – множество, F – отображение, которое каждой формуле исчисления предикатов ставит в соответствие некоторое отношение на множестве М (некоторое его подмножество).

Пусть  – n-местная атомарная формула.

Предикат: функция отображает формулу в . Иногда атомарную формулу будем называть предикатом.

Пусть - константа.

Формула , где , - константы, истинна в модели ( ), если пара .

- предикатные символы.

-атомарная формула (или, если нестрого, предикат).

Определение. Предикат – функция, которая формулу отображает в множество {0,1}
Пример.

Пусть в качестве модели взяли таблицу (например, из БД):

Мать

Отец

Ребенок

Аня

Петя

Вася

Галя

Петя

Коля

Пусть задано исчисление, в котором определен предикат Родственные_отношения - трехместная атомарная формула. Чтобы определить истинность этой формулы, необходима модель . Эта таблица ее и задает. Хотим узнать что-нибудь об истинности формулы в модели.

– Родственные отношения в Москве

- родственные отношения могут быть в разных городах

Таким образом, , .

Если переменные означены1 чем-то, чего нет в таблице, то ложна.

Формула истинна в , если истинна в и истинна в .

Формула истинна в , если истинна в или истинна в .

Формула истинна в , если ложна в .

Формула ложна в , если истинна в и ложна в ; во всех остальных случаях она истинна в .
Таким образом, мы построили отношение истинности для любых формул исчисления предикатов 1-го порядка. Если формула истинна во всех моделях, то говорят, что она истинна. Иногда называют интерпретацией формул исчисления предикатов 1-го порядка.

1   2   3   4   5   6   7   8   9   ...   17

Похожие:

Методы представления знаний Формальные языки и формальные системы iconРабочая программа дисциплины теория автоматов и формальных языков направление подготовки
Уметь: строить формальные грамматики, деревья вывода, распознающие автоматы; анализировать формальные языки
Методы представления знаний Формальные языки и формальные системы icon4. Введение в формальные (аксиоматические) системы 1 Формальные модели
Принципы построения формальных теорий. Аксиоматические системы, формальный вывод
Методы представления знаний Формальные языки и формальные системы iconЛекция 3 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Методы представления знаний Формальные языки и формальные системы iconЛекция 4 Исчисления. Формальные системы. Формальные грамматики. Автоматы
...
Методы представления знаний Формальные языки и формальные системы icon1. Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки
Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей. Язык как способ представления информации: естественные...
Методы представления знаний Формальные языки и формальные системы iconКодирование информации
Представление информации. Язык как способ представления информации: естественные и формальные языки. Дискретная форма представления...
Методы представления знаний Формальные языки и формальные системы iconБилет 1 Понятие информации. Виды информации. Роль информации и живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки. Основные информационные процессы: хранение
Понятие информации. Виды информации. Роль информации и живой природе и в жизни людей. Язык как способ представления информации: естественные...
Методы представления знаний Формальные языки и формальные системы iconБилет 1 Понятие информации. Виды информации. Роль информации и живой природе и в жизни людей. Язык как способ представления информации: естественные и формальные языки. Основные информационные процессы: хранение
Понятие информации. Виды информации. Роль информации и живой природе и в жизни людей. Язык как способ представления информации: естественные...
Методы представления знаний Формальные языки и формальные системы iconЭкзаменационные билеты по информатике 9 класс
Понятие информации. Виды информации. Язык как способ представления информации. Естественные и формальные языки. Основные информационные...
Методы представления знаний Формальные языки и формальные системы iconФормальные модели программных агентов в задаче семантического индексирования документов
В работе рассматриваются формальные модели делиберативных агентов, т е агентов базирующихся на базируется на принципах и методах...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org