Монадическое исчисление предикатов

В логике монадическое исчисление предикатов (также называемое монадической логикой первого порядка ) — это фрагмент логики первого порядка, в котором все символы отношения в сигнатуре являются монадическими (то есть принимают только один аргумент) и не содержат функциональных символов. Таким образом, все атомарные формулы имеют вид $P(x)$, где $P$ является символом отношения и $x$ является переменной .

Монадическое исчисление предикатов можно противопоставить полиадическому исчислению предикатов, которое допускает символы отношений, принимающие два или более аргументов.

Выразительность

Отсутствие символов полиадических отношений серьезно ограничивает возможности выражения в монадическом исчислении предикатов. Оно настолько слабое, что, в отличие от полного исчисления предикатов, оно разрешимо — существует процедура принятия решения , которая определяет, является ли данная формула монадического исчисления предикатов логически допустимой (верной для всех непустых областей ). Однако добавление одного символа двоичного отношения к монадической логике приводит к неразрешимой логике.

с

Необходимость выйти за пределы монадической логики не была оценена до тех пор, пока не появились работы по логике отношений Огастеса Де Моргана и Чарльза Сандерса Пирса в девятнадцатом веке, а также Фреге в его «Begriffsschrift» 1879 года . До работы этих троих термин логика (силлогистическая логика) широко считался адекватным для формальных дедуктивных рассуждений.

Все выводы в терминологической логике могут быть представлены в монадическом исчислении предикатов. Например, аргумент

Все собаки являются млекопитающими.

Ни одно млекопитающее не является птицей.

Таким образом, ни одна собака не является птицей.

можно записать на языке монадического исчисления предикатов как

$[(\forall x\,D(x)\Rightarrow M(x))\land \neg (\exists y\,M(y)\land B(y))]\Rightarrow \neg (\exists z\,D(z)\land B(z))$

где $D$, $M$ и $B$ обозначим предикаты быть соответственно собакой, млекопитающим и птицей.

И наоборот, монадическое исчисление предикатов не намного более выразительно, чем логика терминов. Каждая формула в монадическом исчислении предикатов эквивалентна формуле, в которой кванторы появляются только в замкнутых подформулах вида

$\forall x\,P_{1}(x)\lor \cdots \lor P_{n}(x)\lor \neg P'_{1}(x)\lor \cdots \lor \neg P'_{m}(x)$

или

$\exists x\,\neg P_{1}(x)\land \cdots \land \neg P_{n}(x)\land P'_{1}(x)\land \cdots \land P'_{m}(x),$

Эти формулы несколько обобщают основные суждения, рассматриваемые в терминологике. Например, эта форма допускает такие утверждения, как « Каждое млекопитающее является либо травоядным, либо плотоядным (или и тем и другим) », $(\forall x\,\neg M(x)\lor H(x)\lor C(x))$. Однако рассуждения о таких утверждениях все же можно проводить в рамках терминологической логики, хотя и не только с помощью 19 классических аристотелевских силлогизмов .

Если принять логику высказываний как данность, каждая формула монадического исчисления предикатов выражает нечто, что аналогичным образом может быть сформулировано в терминах логики. С другой стороны, современный взгляд на проблему множественной общности в традиционной логике приходит к выводу, что кванторы не могут быть полезными вложенными, если нет полиадических предикатов для связи связанных переменных.

Варианты

Описанную выше формальную систему иногда называют чистым монадическим исчислением предикатов, где «чистый» означает отсутствие функциональных букв. Разрешение монадических функциональных букв меняет логику лишь поверхностно. , тогда как допущение даже одной буквы двоичной функции приводит к неразрешимой логике.

Монадическая логика второго порядка допускает использование в формулах предикатов более высокой арности , но ограничивает количественную оценку второго порядка унарными. предикаты, т.е. единственными разрешенными переменными второго порядка являются переменные подмножества .