Лекции . Технология построения интеллектуальных систем. Методы представления знаний Формальные языки и формальные системы (стр. 1 )

Лекции

Технология построения интеллектуальных систем.

Методы представления знаний

Формальные языки и формальные системы

Естественный язык: достоинства (и они же  - недостатки): неполнота, избыточность, неоднозначность.

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

Необходимы языки, которые удовлетворяют следующим требованиям:

- однозначность каждого слова

- эксплицитность (абсолютная явность)

- последовательность (то есть невозможность использовать то, что не было определено ранее).

Такой язык является формальным, а при достаточном формализме – математическим.

Рассмотрим такой математический язык:

Язык исчисления предикатов 1-го порядка
Основные конструкции

Этот язык позволяет описывать простые утверждения и простые конструкции (формулы). Терминальные символы языка (термы) - символы, из которых он состоит. Рассмотрим алфавит языка:

Задано счетное число (возможны индексы) символов из конца латинского алфавита: – множество символов для переменных. Задано счетное число (возможны индексы) символов из начала латинского алфавита: - множество констант. Задано счетное число (возможны индексы) прописных символов из середины латинского алфавита:- множество предикатных символов. Задано счетное число (возможны индексы) строчных символов из середины латинского алфавита: - множество функциональных символов. Заданы символы (влечет),(не),… - множество символов логических связок. -  символы для кванторов. - скобки.

Символы  могут быть n - арными.

Арность – то количество переменных или констант, которые следуют до закрывающих скобок (будем использовать бинарность).

Формулы языка определяются рекурсивно:

Переменная есть терм. Константа есть терм. Если  - терм, то -также терм. Если - термы, то - атомарные формулы. Атомарная формула есть формула. Если - формулы, то , , - также формулы. Если - формула, то - формула, - формула

Таким образом, мы дали определение языка исчисления предикатов1.

Заметим, что кванторы  выражаются через остальные:

"и": "или":

Если из формул исключить переменные, то есть в формулах – либо константы, либо формулы замкнуты, то значение истинности формулы зафиксируется, следовательно, имеем частный случай исчисления предикатов – исчисление высказываний. Высказывание – исчисление без переменных.

Введем аксиоматику исчисления высказываний:

1.

2.

3.

Постулаты Аристотеля

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

- принцип исключенного третьего

В исчислении высказываний эти аксиомы обращаются в теоремы.

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

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

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

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

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

Пример. 

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

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

Из Ax2:

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

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

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

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

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

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

Аксиомы исчисления предикатов

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

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

Формальная система

, где

- символы

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

-аксиомы

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

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

Пример.

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

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

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

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

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