Подсчет количественных показателей

Квантор подсчета — это математический термин для квантификатора вида «существует по крайней мере k элементов, удовлетворяющих свойству X ». В логике первого порядка с равенством квантификаторы подсчета можно определить в терминах обычных квантификаторов, поэтому в этом контексте они являются сокращенной записью. Однако они интересны в контексте логик, таких как двухпеременная логика с подсчетом , которая ограничивает количество переменных в формулах. Кроме того, обобщенные квантификаторы подсчета, которые говорят «существует бесконечно много», не могут быть выражены с использованием конечного числа формул в логике первого порядка.

Квантификаторы подсчета можно определить рекурсивно в терминах обычных квантификаторов.

Пусть обозначает «существует ровно ». Тогда${\displaystyle \exists ^{=k}}$${\displaystyle к}$

${\displaystyle {\begin{align}\exists ^{=0}xPx&\leftrightarrow \neg \exists xPx\\\exists ^{=k+1}xPx&\leftrightarrow \exists x(Px\land \exists ^{=k}y(y\neq x\land Py))\end{align}}}$

Пусть обозначает «существует по крайней мере ». Тогда${\displaystyle \exists ^{\geq k}}$${\displaystyle к}$

${\displaystyle {\begin{align}\exists ^{\geq 0}xPx&\leftrightarrow \top \\\exists ^{\geq k+1}xPx&\leftrightarrow \exists x(Px\land \exists ^{\geq k}y(y\neq x\land Py))\end{align}}}$

• Количественная оценка уникальности
• Квантификатор Линдстрема

• Эрих Грэдель, Мартин Отто и Эрик Розен. «Двухпараметрическая логика с подсчетом разрешима». В трудах 12-го симпозиума IEEE по логике в компьютерных науках LICS `97 , Варшава. 1997. Файл постскриптума OCLC  282402933

Эта статья, связанная с логикой, является заглушкой . Вы можете помочь Википедии, расширив ее.

• в
• т
• е