Кванторные версии логик Хальперна для рассуждений о знании и вероятности

Разрабатываются две естественных кванторных версии пропозициональной логики для рассуждений о знании и вероятности, которая была предложена ранее Р. Фейгином и Дж. Хальперном (1994, Journal of the ACM). Их можно также воспринимать как модальные обогащения так называемых «первопорядковых вероятностных логик» Хальперна (1990, Artificial Intelligence). Обозначим эти обогащения через L^{K}_{1} и L^{K}_{2}. Изучаются вычислительные аспекты L^K_1, L^K_2 и их фрагментов без кванторов по вещественным числам. Сначала мы получаем нижние оценки сложности для соответствующих проблем общезначимости путём кодирования определённых фрагментов арифметик второго и третьего порядков. Затем показывается, что эти оценки являются точными, используя аналоги теоремы Лёвенгейма-Сколема (о понижении мощности) и подходящие переводы из вероятностных языков в язык арифметики высших порядков. В заключение обсуждаются некоторые естественные фрагменты L^{K}_{2}, которые встречаются в литературе.