![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
В которых позитивные литералы сгруппированы слева от знака стрелки, а негативные справа.
Более строго, фраза представляет собой выражение вида в котором p1..., рт q1,..., qn являются атомарными формулами, причем т=>0 и п=>0. Атомы в множестве р1,..., рт представляют заключения, объединенные операторами дизъюнкции, а атомы в множестве q1 ..., qn — условия, объединенные операторами конъюнкции. Исчисление предикатов Исчисление высказываний имеет определенные ограничения. Оно не позволяет оперировать с обобщенными утверждениями вроде "Все люди смертны". Конечно, можно обозначить такое утверждение некоторой пропозициональной константой р, а другой константой q обозначить утверждение "Сократ — человек". Но из (р л q) нельзя вывести утверждение "Сократ смертен". Для этого нужно анализировать пропозициональные символы в форме предикатов и аргументов, кванторов и квантифщированных переменных. Логика предикатов предоставляет нам набор синтаксических правил, позволяющих выполнить такой анализ, набор семантических правил, с помощью которых интерпретируются эти выражения, и теорию доказательств, которая позволяет вывести правильные формулы, используя синтаксические правила дедукции. Предикатами обозначаются свойства, такие как "быть человеком", и отношения, такие как быть "выше, чем". Аргументы могут быть отдельными константами, или составным выражением "функция-аргумент", которое обозначает сущности некоторого мира интересующих нас объектов, или отдельными квантифицируемыми переменными, которые определены в этом пространстве объектов. Специальные операторы — кванторы — используются для связывания переменных и ограничения области их интерпретации. Стандартными являются кванторы общности (V) и существования (3). Первый интерпретируется как "все", а второй — "кое-кто" (или "кое-что"). Ниже приведены синтаксические правила исчисления предикатов первого порядка. Любой символ (константа или переменная) является термом. Если rk является символом k-местной функции и а1..., <xk являются термами, то Гk(a1..., ak) является термом. (S 40 Если Tk является символом k-местного предиката и а1..., ak являются термами, то U(а1..., ak) является правильно построенной формулой (ППФ). (S. -) и (S. v) Правила заимствуются из исчисления высказывании.
(S. V) Если U является ППФ и % является переменной, То (любой Х) U является ППФ. Для обозначения используются следующие символы: U — произвольный предикат; Г — произвольная функция; a — произвольный терм; X— произвольная переменная. Действительные имена, символы функций и предикатов являются элементами языка первого порядка. Использование квантора существования позволяет преобразовать термы с квантором общности в соответствии с определением (EX)U определено как -(любой X)-U. Выражение (EХ)(ФИЛОСОФ(Х)) читается как "Кое-кто является философом", а выражение ( любой Х)(ФИЛОСОФ(Х)) читается как "Любой является философом". Выражение ФИЛОСОФ(Х) представляет собой правильно построенную формулу, но это не предложение, поскольку область интерпретации для переменной X не определена каким-либо квантором. Формулы, в которых все упомянутые переменные имеют определенные области интерпретации, называются замкнутыми формулами. Как и в исчислении высказываний, в исчислении предикатов существует нормальная форма представления выражений, но для построения такой нормальной формы используется расширенный набор правил синтаксических преобразований. Ниже приведена последовательность применения таких правил. Для приведения любого выражения к нормальной форме следует выполнить следующие операции. (1) Исключить операторы эквивалентности, а затем импликации. (2) Используя правила Де Моргана и правила замещения (E X)U на -(любой X)-U (а следовательно, и (любой X) U на -(E X)-U), выполнить приведение отрицания. (3) Выполнить приведение переменных. При этом следует учитывать особенности определения области интерпретации переменных кванторами. Например, в выражении (E Х)(ФИЛОСОФ(Х))&(E Х)(АТЛЕТ(Х)) переменные могут иметь разные интерпретации в одной и той же области. Поэтому вынесение квантора за скобки — (E Х)(ФИЛОСОФ(Х))&.(АТЛЕТ(Х)) — даст выражение, которое не следует из исходной формулы. (4) Исключить кванторы существования. Кванторы существования, которые появляются вне области интерпретации любого квантора общности, можно заменить произвольным именем (его называют константой Сколема), в то время как экзистенциальные переменные, которые могут существовать внутри области интерпретации одного или более кванторов общности, могут быть заменены функциями Сколема. Функция Сколема— это функция с произвольным именем, которая имеет следующий смысл: "значение данной переменной есть некоторая функция от значений, присвоенных универсальным переменным, в области интерпретации которых она лежит".
(5) Преобразование в префиксную форму. На этом шаге все оставшиеся кванторы (останутся только кванторы общности) переносятся "в голову" выражения и таким образом оказываются слева в списке квантифицированных переменных. За ними следует матрица, в которой отсутствуют кванторы. (6) Разнести операторы дизъюнкции и конъюнкции. (7) Отбросить кванторы общности. Теперь все свободные переменные являются неявно универсально квантифицированными переменными. Экзистенциальные переменные станут либо константами, либо функциями универсальных переменных. (8) Как и ранее, отбросить операторы конъюнкций, оставив множество фраз. (9) Снова переименовать переменные, чтобы одни и те же имена не встречались в разных фразах. Снова о роботах и комнатах В главе 3 мы уже упоминали об исчислении предикатов в упрощенном виде. Там выражение вида At(робот, комнатаА) Означало, что робот находится в комнате А. Термы робот и комнатаА в этом выражении представляли собой константы, которые описывали определенные реальные объекты. Но что будет означать выражение вида At(X, комнатаА), В котором х является переменной? Означает ли оно, что нечто находится в комнате А? Если это так, то говорят, что переменная имеет экзистенциальную подстановку (импорт). А может быть, выражение означает, что все объекты находятся в комнате А? В таком случае переменная имеет универсальную подстановку. Таким образом, отсутствие набора четких правил не позволяет однозначно интерпретировать приведенную формулу. Перечисленные в этом разделе правила исчисления предикатов обеспечивают однозначную интерпретацию выражений, содержащих переменные. В частности, фраза at(X, комнатаА)<—at (X, ящик1) интерпретируется как "для всех X X находится в комнате А, если X находится в ящике 1". В этой фразе переменная имеет универсальную подстановку. Аналогично, фраза at(X, комнатаА) <-интерпретируется как "для всех X X находится в комнате А". А вот фраза <— at(X, комнатаА) интерпретируется как "для всех XX не находится в комнате А". Иными словами, это не тот случай, когда некоторый объект X находится в комнате А и, следовательно, переменная имеет экзистенциальную подстановку. Теперь можно преобразовать фразовую форму, в которой позитивные литералы сгруппированы слева от знака стрелки, а негативные — справа. Если фраза в форме P1,..., Рт <— q1,...qn содержит переменные х1,..., хk, то правильная интерпретация имеет следующий вид: для всех x1,..., хk p1 или... или pm является истинным, если q1 и... и qn являются истинными. Если п = 0, т.е. отсутствует хотя бы одно условие, то выражение будет интерпретироваться следующим образом: для всех x1 ,..., xk p1 или... или рт является истинным. Если т = 0, т.е. отсутствуют термы заключения, то выражение будет интерпретироваться следующим образом:
для всех x1,..., xk не имеет значения, что q1 и... и qn являются истинными. Если же т = п = 0, то мы имеем дело с пустой фразой, которая всегда интерпретируется как ложная. Язык PROLOG Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением В языке PROLOG эта же фраза записывается в таком виде (обратите внимание на символ точки в конце): р:- q1,...,qn. Такая фраза интерпретируется следующим образом: "Для всех значений переменных в фразе p истинно, если истинны q1 и... и qn", т.е. пара символов ":-" читается как "если", а запятые читаются как "и". PROLOG — это не совсем обычный язык программирования, в котором программа состоит в основном из логических формул, а процесс выполнения программы представляет собой доказательство теоремы определенного вида. Фраза в форме р:- q1,...,qn.
|
|||||||
Последнее изменение этой страницы: 2016-04-07; просмотров: 202; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.0.88 (0.018 с.) |