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

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

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

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

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

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

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

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

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

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

${\displaystyle [(\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))}$

где и обозначают предикаты ^{[ необходимо уточнить ]} бытия, соответственно, собакой, млекопитающим и птицей .${\displaystyle D}$${\displaystyle М}$${\displaystyle Б}$

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

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

или

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

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

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

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

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