Cтраница 3
Система логики умолчаний представляется теорией с умолчаниями, состоящей из некоторого множества особо выделенных формул и правил вывода. В ней содержатся формулы логики предикатов, представляющие основную информацию о прикладной системе, обрабатываемую в соответствии с имеющимися аксиомами, а также имеются правила умолчаний, отражающие исключения. [31]
Рассмотрен пример применения алгоритма к решению шахматной задачи. Условие задачи записывается в виде формулы логики ветвящегося времени, выполнимость которой означает существование решения, и это решение извлекается из модели, построенной для формулы. [32]
В логике высказываний интерпретация формулы заключается в приписывании атомарным подформулам логических значений true или false. В логике предикатов понятие интерпретации представляется более сложным, так как формула логики предикатов не является логической константой, и ее значение зависит от значений ее аргументов. [33]
В логике предикатов задание интерпретации логической формулы связано с указанием предметной области. Поскольку таких областей можно придумать бесконечное множество, то и интерпретаций для формулы логики предикатов существует бесконечное множество, и алгоритм перебора возможных интерпретаций и вычисления в каждой из них логического значения формулы будет работать бесконечно долго. [34]
Сравнивая аксиоматические системы для PL и PrL, можно заметить, что аксиомы и правило для PL содержатся среди аксиом и правил для PrL. Однако, логика высказываний имеет дело с высказываниями, тогда как логика предикатов рассматривает более сложные объекты - формулы логики предикатов. [35]
Уже сам термин NP-свойство приводит к альтернативному определению: свойство является NP-своисговсш тогда и только тогда, когда оно может быть распознано недетерминированной машиной Тьюринга за полиномиальное время. Другой красивый способ определить эти свойства следующий: это в точности такие свойства конечных графов, которые можно выразить формулами логики второго порядка, содержащими одну свободную переменную второго порядка ( смежность) и произвольное число связанных переменных второго порядка, на которые действуют только кванторы существования. [36]
В логике первого порядка мы должны сделать больше, так как в игру вступают переменные. Чтобы определить интерпретацию для формулы логики первого порядка, мы должны указать предметную область ( область значений предметных переменных) и значения констант, функциональных и предикатных символов, встречающихся в формуле. Ниже следует формальное определение интерпретации формулы логики первого порядка. [37]
Процедуры, позволяющие строить доказательства формул такого типа, называются доказательствами посредством опровержения. Они помогают избегать менее перспективных направлений поиска. Системы доказательства теорем во многих приложениях включают формулы логики предикатов с переменными, связанными кванторами существования. В таких случаях доказательства позволяют находить конкретизации для этих переменных. [38]
Однако результаты Черча и Тьюринга о неразрешимости логики предикатов первого порядка в какой-то степени оттеснили работы Эрбрана на задний план. Интерес к ним возрос лишь в 60 - е годы, когда Гилмор реализовал эрбрановскую процедуру вывода на компьютере. Действительно, если нет процедуры для проверки противоречивости ( общезначимости) формул логики предикатов первого порядка, то самое большее, что можно сделать - это проверить противоречивость ( общезначимость) формулы, если она на самом деле таковой и является. [39]
В самом деле, если формула 51 истинна, то формула 51 невыполнима, и обратно. Проблема разрешения для логики предикатов является обобщением проблемы разрешения для исчисления высказываний, так как все формулы исчисления высказываний входят в число формул логики предикатов. Однако в то время как решение проблемы разрешения для исчисления высказываний никаких трудностей не представляет, проблема разрешения для логики предикатов оказалась связанной с серьезными трудностями. [40]
Большие готические буквы употребляются для разговора о формулах, но сами формулами не являются. Вместо знака мы будем часто употреблять точку ( как отмечено в § 1, точка может и опускаться); таким образом, если 91 и S3 - формулы логики суждений, то ( 91 - S3) - тоже формула логики суждений. Договоримся, что в одной и той же формуле знаки и не должны встречаться. [41]
Большие готические буквы употребляются для разговора о формулах, но сами формулами не являются. Вместо знака мы будем часто употреблять точку ( как отмечено в § 1, точка может и опускаться); таким образом, если 91 и S3 - формулы логики суждений, то ( 91 - S3) - тоже формула логики суждений. Договоримся, что в одной и той же формуле знаки и не должны встречаться. [42]
Фактически можно указать одно конкретное натуральное число, которое реализует любой арифметический пример вышеуказанной формулы. Как говорят, формула Цейтина допускает постоянную реализацию. Возможно, что все формулы LR допускают постоянную реализацию. Для формул логики предикатов это не так, что следует из вышеупомянутых работ Плиско. [43]
В логике первого порядка мы должны сделать больше, так как в игру вступают переменные. Чтобы определить интерпретацию для формулы логики первого порядка, мы должны указать предметную область ( область значений предметных переменных) и значения констант, функциональных и предикатных символов, встречающихся в формуле. Ниже следует формальное определение интерпретации формулы логики первого порядка. [44]
ЛОГИЧЕСКАЯ ФОРМУЛА - выражение в языке формальной логики, являющееся аналогом предложения. Как правило, определение формулы имеет индуктивный характер: выделяется класс выражений, называемых элементарны-м и, или атомарными, формулами, и указываются правила, позволяющие из уже построенных формул строить новые формулы, используя символы логических операций. Всякая пропозициональная переменная есть ( элементарная) формула. Формулы логики предикатов строятся из пропозициональных, предикатных и предметных переменных с использованием логич. Формулы исчисления предикатов определяются следующим образом: а) всякая элементарная формула есть формула; б) если А и В - формулы, у - предметная переменная, то выражения ( П) ( А & В), ( AvB), ( ЛгзЯ), ( VyA), ( ЭуА) суть формулы. [45]