Введение в системы БД (542480), страница 238
Текст из файла (страница 238)
Прежде всего, нужно отметить, что правило резолюции фактически является правилом, которое позволяет сокрая1агпь подформулы. Например, рассмотрим следующие формулы. 10йд НОТ д Ой л В этом случае д и НОТ д по правилу резолюции можно сократить до упрощенной формулы. В частности, на основе заданных формул Г Ой д и вОТ д (т.е. допуская, что Ь является истинным) можно вывести 1.
Таким образом, можно отметить, что в общем случае данное правило применяется к конъюнкяии (ййО) двух формул, каждая из которых является дизьюнкяией (Ок) двух формул. Для применения правила резолюции нужно поступить следующим образом.
(Чтобы 905 Глава 23. Логические системы управления базами данных обсуждение этого вопроса было более конкретным, рассмотрим его на примере.) Допустим, что необходимо определить, будет ли верным следующее предполагаемое доказательство (где А, В, С и Р являются формулами). А ~ ( В ~ С ), ВОТ Р Ой А, В )- Р =ь С Сначала следует принять отрицание заключения в качестве дополнительной предпосылки, а затем записать каждую предпосылку в отдельной строке.
А~( В~С) ВОТ Р Ой А В ВОТ ( Р =ь С ) Обратите внимание на то, что эти четыре строки неявным образом связаны межлу собой с помощью операции АВР. Теперь нужно конвертировать каждую отдельную строку в конъюнктивную нормальную форму, т.е. в форму, состоящую из нескольких объединенных связками АВР формул, каждая из которых может содержать связки ВОТ и Ой, но не связку йВР (подробнее это описано в главе 17). В рассматриваемом примере вторая и третья строки уже имеют требуемый вид.
В двух других строках следует исключить все вхождения связки "~", используя для этого ее определение на основе связок КОТ и Ой. В случае необходимости можно применить упомянутые выше дистрибутивные законы и законы Де Моргана. Кроме того, необходимо убрать лишние скобки и пары смежных связок ))ОТ, которые образуют двойное отрицание. После выполнения всех этих действий строки примут следующий вид.
ВОТ А Ой ВОТ В О)( С ВОТ Р Ой А В Р ййР НОТ С Каждую строку, которая явным образом содержит связку АВР, следует заменить набором отдельных строк по одной для каждой формулы, связанной связкой АВР (опуская при этом все связки АКР). В данном примере выполнить это действие необходимо только над четвертой строкой. В результате все предпосылки будут выглядеть так, как показано ниже.
ВОТ А Ок ВОТ В Ой С ВОТ Р Ой А В Р ВОТ С Далее для объединения строк начнем применять правило резолюции. Для этого выберем пару "совмещаемых" строк, одна из которых содержит часть формулы, а другая— ее отрицание. Например, выберем первые две строки, содержащие ВОТ А и А соответственно. После их совмещения получится следуюший результат. ВОТ Р Ой ВОТ В Ой С В Р )(ОТ С 906 Часть г'. Дополнительные аспекты (Замечание. В общем случае необходимо также сохранить две исходные строки, однако в данной ситуации они больше не нужны,) Теперь можно снова применить правило резолюции для первых двух строк (совмещая ВОТ В и В), в результате чего будет получено следующее. ВОТ 0 Ой С 0 ВОТ С После еше одного совмещения первых двух строк (ВОТ В и В) получится приведенный ниже результат. С ВОТ С Наконец после заключительного совмещения (С и ВОТ С) будет получено пустое множество заключений, которое обычно обозначается как "()" и представляет собой противоречие.
Таким образом, путем приввдвиия к противоречию получен нужный результат. ° 23.4. Исчисление предикатов Основным отличием исчисления предикатов от исчисления высказываний является использование в формулах исчисления предикатов переменных' и кванторов.
Благодаря этому эффективность и диапазон применения формул значительно увеличиваются. Например, утверждения "Поставщик с номером '31' поставляет некоторую деталь с номером р*' и "Некоторый поставщик с номером в поставляет некоторую деталь с номером р" нельзя использовать в исчислении высказываний, однако это вполне допустимо в исчислении предикатов.
Таким образом, в исчислении предикатов можно составлять запросы наподобие "Какие детали поставляются поставщиком с номером 'Я1'?", "Найти поставщиков, поставляющих некоторые детали" и даже "Найти поставщиков, которые вовсе не поставляют никаких деталей". Предикаты Как указывалось в главе 3, предикат — это логическая функция, которая при заданных для ее параметров аргументах возвращает значение истина или лаясь. Например, выражение >(х,у) (оно чаще записывается в виде х>у) является предикатом с двумя параметрами, х и у.
Этот предикат возвращает значение истина, если аргумент, соответствующий параметру х, больше аргумента, соответствующего параметру у, и значение ложь — в противном случае. Предикат, содержащий л аргументов (что равносильно предикату, содержащему л параметров), называется л-местным предикатом. Утверждение (т,е, формула в смысле, определенном в разделе 23.3) может рассматриваться как нуль-местный првдикат„поскольку не имеет параметров и оценивается либо как истинное, либо как ложное утверждение. Такие переменные являются логическими переменными, а не переменными некоторого языка программирования.
В данном случае ил можно рассматривать как переложенные кортежей в смысля, определенно ч в савв 7. 907 Глава 23. Логические системы управления базами Данных Для удобства предполагается, что предикаты, соответствующие операциям "=", '»", "" и т.д., — встроенные (т.е. являются частью данной формально определенной системы) и выражения, которые их включают, могут записываться обычным образом.
Однако пользователи, безусловно, могут определять предикаты самостоятельно. Как известно из предыдущих глав, в терминах баз данных заданный пользователем предикат фактически представляет собой определенную пользователем перененную-отношение. Например, переменная-отношение поставщиков Я может рассмазриваться как предикат с четырьмя параметрами, а именно: 8$, ЯКИЕ, ЯТКТОЯ, С1ТУ. Более того, выражения типа Я('81', 'Яп1сй', 20, 'Еопдоп') и Я('Яб', '((й1се', 45, 'Коже') представляют собой "экземпляры" или "вызовы" такого предиката, который вычисляется в результате со значением соответственно истина или лоэсь (в контексте рассматриваемой здесь базы данных). Неформально говоря, такие предикаты (вместе с любыми юраниченилнм цезостности, которые также являются предикатами) можно рассмазривать в качестве определения того, что "подразумевает" база данных, как уже объяснялось в предыдущих частях книги, в частности в главе 8.
Правильно построенные формулы Во избежание путаницы с термином "формула" из предыдущего раздела (термин, который фактически относится к частному случаю) будем употреблять термин правильно построенная формула (че!(-(оппеб Гоггпц(а; произносится как "вэфф"), определение которого было дано в главе 7. Ниже приведен упрощенный синтаксис ФГГ-формулы. <терм КОТ ( <мЕТ> ) ( <м1Е> ) йКО ( <ИТ> ) ( <мГЕ> ) ОК ( <м1Е> ) ( <мГТ> ) ~ ( <мТГ> ) ЕХ1ЯТЯ <имя переменной> ( <мЕТ> ) КОККЕР <ямя переменной> ( <мЕТ> ) <терм> ::= [ КОТ ) <ямя предяката> ( ( <слисок аргументов> ) ] Отметим некоторые особенности этого синтаксиса.
!. Под словом терм подразумевается просто экземпляр предиката, который может быть отрицаемым. Если рассматривать предикат как логическую функцию, то экземпляр преднката — вызов такой функции. Каждый аргумент в параметре <слясок аргументов> должен быть константой, именем переменной или обращением к функции, а каждый аргумент функции, в свою очередь, — константой, именем переменной или обращением к функции. Для нуль-местного предиката параметр <спясок аргументов> и окружающие его скобки опускаются. Замечание.
Использование логических функций допускается для того, чтобы позволить включать в состав %ГГ-формулы вычисляемые выражения типа +(х,у), которые обычно записываются в виде х+у. 2. Как и в разделе 23.3, для сокращения числа необходимых скобок здесь применяется обычный приоритет выполнения операций (КОТ, затем йКО, затем ОК, затем ~). 3.
Кванторы ЕХ1ЯТЯ и РОЕШЬ уже описывались в этой книге. 908 Часть г'. Дополнительные аспекты Замечание. Здесь полразумевается, что не существует "предикатных переменных'*, т.е. переменных, значениями которых являются предикаты, поэтому будут рассмотрены только предикаты первого порядка.
Следовательно, имеется в виду, что предикаты сами по себе не могут быть под знаком квантора. (См. упр. 7.9 в главе 7.) 4. Законы Де Моргана можно обобщить на случай использовании квантификации %ГГ-формул следующим образом. ЕОт ( ГОЕЕЫ, х ( т ) ) = ЕХ1БтБ х ( ЕОт ( т ) ) ЕОт ( ЕХЗБтБ х ( т ) ) = ГОЕЛЫ. х ( БОт ( т ) ) Эта тема также обсуждалась в главе 7. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
