В интуиционистской логике , то формулы Харропа , названные в честь Рональда Харроп , являются классом формул индуктивно , определенных следующим образом : [1] [2] [3]
- Атомарные формулы Харропа, включая ложность (⊥);
- предоставляется Харроп а также находятся;
- является Харропом для любой правильной формулы ;
- предоставляется Харроп есть, и любая правильно построенная формула;
- предоставляется Харроп является.
Исключая дизъюнкцию и экзистенциальную количественную оценку (кроме антецедента импликации), можно избежать неконструктивных предикатов, что имеет преимущества для компьютерной реализации. С конструктивистской точки зрения формулы Харропа «хорошо работают». Например, в арифметике Гейтинга формулы Харропа удовлетворяют классической эквивалентности, которая обычно не выполняется в конструктивной логике: [1]
Формулы Харропа были введены примерно в 1956 году Рональдом Харропом и независимо Хеленой Расиовой . [2] Варианты основного понятия используются в разных разделах конструктивной математики и логического программирования .
Наследственные формулы Харропа и логическое программирование
Более сложное определение наследственных формул Харропа используется в логическом программировании как обобщение предложений Хорна и составляет основу языка λProlog . Наследственные формулы Харропа определяются в терминах двух (иногда трех) рекурсивных наборов формул. В одной формулировке: [4]
- Жесткие атомарные формулы, т.е. константы или формулы , являются потомственными Харропами;
- является наследственным Харропом а также находятся;
- является наследственным Харропом является;
- является наследственным Харропом жестко атомарен, и является G -формулой.
G -формулы определяются следующим образом: [4]
- Атомарные формулы - это G- формулы, включая истину (⊤);
- является G -формулой при условии а также находятся;
- является G -формулой при условии а также находятся;
- является G -формулой при условии является;
- является G -формулой при условии является;
- является G -формулой при условии есть, и является потомственным Харропом.
Смотрите также
Рекомендации
- ^ a b Даммит, Майкл (2000). Элементы интуиционизма (2-е изд.). Издательство Оксфордского университета . п. 227. ISBN. 0-19-850524-8.
- ^ а б AS Troelstra, Х. Швихтенберг. Основная теория доказательств . Издательство Кембриджского университета . ISBN 0-521-77911-1.CS1 maint: использует параметр авторов ( ссылка )
- ^ Рональд Харроп (1956). «О дизъюнкциях и экзистенциальных утверждениях в интуиционистских логических системах». Mathematische Annalen . 132 (4): 347. DOI : 10.1007 / BF01360048 .
- ^ a b Дов М. Габбей, Кристофер Джон Хоггер, Джон Алан Робинсон, Справочник по логике в искусственном интеллекте и логическом программировании: логическое программирование , Oxford University Press , 1998, стр. 575, ISBN 0-19-853792-1