Логические системы

Логический вывод

Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях "õ — ОТЕЦ у" и "х — МАТЬ у". Чтобы обработать запросы типа:

ИВАНОВ А.И. — ДЕД ПЕТРОВА В.А.?

ПЕТРОВ В.А. — ВНУК ИВАНОВА А.И.?

необходимо либо ввести в базу данных также и сведения об отношениях "х — ДЕД у" и "х — ВНУК у", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном алгоритмическом подходе требует написания все новых и новых программ для реализации новых типов запросов.

Логический вывод позволяет расширять возможности "общения" наиболее просто и наглядно. Так, для приведенных типов запросов системе достаточно будет сообщить три правила:

1. х—ДЕД у если х—ОТЕЦ а и а—РОДИТЕЛЬ у

2. х—РОДИТЕЛЬ у если х—ОТЕЦ у или х—МАТЬ у

3. х—ВНУК у если у—ДЕД х

Эти правила содержат естественные и очевидные определения понятий ДЕД, РОДИТЕЛЬ, ВНУК. Поясним в чем состоит логический вывод для запроса "А—ДЕД В?" в предположении, что в базе данных имеются факты: А—ОТЕЦ Б и Б—МАТЬ В. При этом для упрощения опустим тонкости, связанные с падежными окончаниями. Пользуясь определением 1 система придет к необходимости проверки существования такого индивидуума а, что факты А—ОТЕЦ а и а—РОДИТЕЛЬ В истинны. Если такой а существует, то А—ДЕД В, если не существует такого а, то А не является дедом В.

 

В основе логических систем представления знаний лежит понятие формальной логи-ческой системы. Оно является также одним из основополагающих понятий формализации. Основные идеи формализации заключаются в следующем. Вводится множество базовых элементов (алфавит) теории. Определяются правила построения правильных объектов (предложений) из базовых элементов. Часть объектов объявляется изначально заданными и правильными по определению — аксиомами. Задаются правила построе-ния новых объектов из других правильных объектов системы (правила вывода).
Данная схема лежит в основе построения многих дедуктивных СИИ. В соответствии с ней база знаний описывается в виде предложений и аксиом теории, а механизм вывода реализует правила построения новых предложений из имеющихся в базе знаний. На вход СИИ поступает описание задачи на языке этой теории в виде запроса (предложения, тео-ремы), которое явно не представлено в БЗ, но если оно верно с позиций заложенных в БЗ знаний и не противоречит им, то может быть построено из объектов БЗ путем примене-ния правил вывода. Процесс работы механизма вывода называют доказательством зап-роса (теоремы). Если запомнить шаги процесса вывода в виде трассы и представить ее пользователю, то она будет объяснением выработанного СИИ решения задачи.
Формальные языки, на которых записываются предложения (формулы) с использо-ванием рассмотренных понятий, получили названия логических языков. С практичес-кой и теоретической точек зрения наиболее важными и изученными являются язык логи-ки высказываний и язык логики предикатов. В языке логики высказываний элементарные предложения рассматриваются как неделимые сущности, в языке логики предикатов, наоборот, делается расчленение предложения на субъект и предикат.
В процессе математизации рассуждений различают два вида слов: термы — аналоги имен существительных и формулы — аналоги повествовательных предложении.
Для записи предложений используются стандартные формы высказываний, что дает воз-можность, с одной стороны, стандартизовать рассуждения, т. е. рассматривать только определенные структуры посылок и заключений, а с другой — ввести в термы переменные — именные формы, которые обращаются в имена после подстановки вместо переменных конкретных значений.
Формулы с переменными, обращающиеся в высказывания при подстановке вместо переменных значений, называют высказывателъными-формами или переменными высказываниями. Одна форма порождает множество истинных или ложных высказывание.
Однако не все предложения, содержащие переменные, являются высказывательными формами. Различают связанные и свободные переменные Так, сложные предложения с переменными, содержащие логические связки СУЩЕСТВУЕТ или ВСЕ, обозначают высказывания, а переменные, к которым они относятся, являются связанными.
Расчленение предложения на субъект и предикат в математической логике математизируется путем соотнесения предложения, выражающего свойства предмета, с функцией одной переменной Р(х). При этом сама функция Р — логическая функция одной переменной, т. е. одноместный предикат, а аргумент х — субъект. Если же предложение описывает отношение между несколькими (n) субъектами, то с ним можно связать n- местную логическую функцию Р(х1,х2...xn) — n-местный предикат.
Логические связки «И», «ИЛИ», «НЕ» и т. д., с помощью которых строятся сложные предложения (формулы), соотносятся с операциями логики следующим образом:
НЕВЕРНО ЧТО — Ø(знак отрицания);
И — L (знак конъюнкции);
ИЛИ — V (знак дизъюнкции);
ЕСЛИ ... ТО — ®(знак импликации);
ТОГДА, КОГДА — Û(знак эквивалентности).
Логические связки «ДЛЯ ВСЯКОГО», «СУЩЕСТВУЕТ» относятся к переменным, в предложении и обозначают:
ДЛЯ ВСЯКОГО — "(знак квантора общности);
СУЩЕСТВУЕТ — $ (знак квантора существования).
В различных логических системах используются разнообразные правила вывода. Приведем два наиболее распространенных из них.
Первое — «правило подстановки» имеет следующую формулировку. В формулу, которая уже выведена, можно вместо некоторого высказывания подставить любое другое при соблюдении условия: подстановка должна быть сделана во всех местах вхождения
заменяемого высказывания в данную формулу.
Второе — «правило заключения» (латинское название Modus Ponens — положительный модус) состоит в следующем: Если a и a®b являются истинными высказываниями посылками, тогда и высказывание заключение b также истина. Записывается правило в виде дроби: