WikiDer > Монадическое исчисление предикатов
В логика, то монадическое исчисление предикатов (также называемый монадическая логика первого порядка) является фрагментом логика первого порядка в котором все символы отношений в подпись находятся монадический (то есть они принимают только один аргумент), и нет функциональных символов. Все атомарные формулы таким образом имеют форму , куда является символом отношения и это Переменная.
Монадическое исчисление предикатов можно противопоставить полиадическому исчислению предикатов, которое позволяет использовать символы отношения, которые принимают два или более аргумента.
Выразительность
Отсутствие полиадическое отношение символы сильно ограничивают то, что может быть выражено в монадическом исчислении предикатов. Он настолько слаб, что, в отличие от полного исчисления предикатов, разрешимый-Существует процедура принятия решения который определяет, является ли данная формула монадического исчисления предикатов логически действительный (верно для всех непустых домены).[1][2] Однако добавление единственного символа двоичного отношения к монадической логике приводит к неразрешимой логике.
Связь с терминологией
Необходимость выйти за рамки монадической логики не была оценена до тех пор, пока не начали работать над логикой связи, к Огастес Де Морган и Чарльз Сандерс Пирс в девятнадцатом веке, и Frege в его 1879 Begriffsschrifft. До работы этих трех мужчин, термин логика (силлогистическая логика) широко считалась подходящей для формального дедуктивного мышления.
Все выводы в терминологической логике могут быть представлены в монадическом исчислении предикатов. Например, силлогизм
- Все собаки - млекопитающие.
- Ни одно млекопитающее не является птицей.
- Таким образом, ни одна собака не является птицей.
можно записать на языке монадического исчисления предикатов как
куда , и обозначают предикаты быть, соответственно, собакой, млекопитающим и птицей.
И наоборот, монадическое исчисление предикатов ненамного более выразительно, чем логика терминов. Каждая формула в монадическом исчислении предикатов имеет вид эквивалент к формуле, в которой кванторы появляются только в закрытых подформулах вида
или же
Эти формулы несколько обобщают основные суждения, рассматриваемые в терминологической логике. Например, эта форма позволяет использовать такие утверждения, как "Каждое млекопитающее - либо травоядное, либо хищное (или и то, и другое)", . Однако рассуждения по поводу таких утверждений все же можно рассматривать в рамках терминологической логики, хотя и не в рамках классической аристотелевской теории. силлогизмы один.
Принимая логика высказываний как дано, каждая формула в монадическом исчислении предикатов выражает нечто, что аналогичным образом может быть сформулировано в терминологической логике. С другой стороны, современный взгляд на проблема множественной общности в традиционной логике заключает, что кванторы не могут быть полезными вложениями, если нет полиадических предикатов, связывающих связанные переменные.
Варианты
Формальную систему, описанную выше, иногда называют чистый монадическое исчисление предикатов, где «чистый» означает отсутствие функциональных букв. Разрешение монадических функциональных букв меняет логику только поверхностно[нужна цитата], в то время как допуск даже одной двоичной буквы функции приводит к неразрешимой логике.
Монадический логика второго порядка позволяет предикаты высших арность в формулах, но ограничивает количественную оценку второго порядка до унарный предикаты, то есть разрешены только переменные второго порядка подмножество переменных.
Сноски
- ^ Генрих Беманн, Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem, в Mathematische Annalen (1922)
- ^ Löwenheim, L. (1915) "Über Möglichkeiten im Relativkalkül", Mathematische Annalen 76: 447-470. Переведено как «О возможностях в исчислении родственников» у Жана ван Хейеноорта, 1967. Справочник по математической логике, 1879-1931. Harvard Univ. Пресс: 228-51.