Логика вероятности и вероятностная логика

Одним из актуальных направлений исследований в современной математической логике и теоретической информатике является вероятностная логика (см., например, [13, 15, 21, 22, 25, 33, 37]), чья цель — введение в рассмотрение и дальнейшее изучение разнообразных языков для рассуждений о вероятностях. Исторически, однако, становлению указанного направления предшествовал ряд дискуссий о пвозможпностях создания индуктивной логики (или логики вероятностисм. [10, 18, 20, 27, 35]), задачи которой, а также суть взгляда на роль вероятности существенно отличались от приведённой выше формально-логической позиции. Настоящая работа посвящена изучению математической стороны обоих этих подходов, что естественным образом нашло отражение в стуктурном разбиении диссертации на две главы. Обсудим теперь каждое из направлений несколько более подробно.

Начнём со второго из упомянутых направлений — это соответствует историческому ходу событий. Индуктивная логика (в отличие от вероятностной) ставит во главу угла проблему индуктивного синтеза непротиворечивых теорий, пропозициональных или первопорядковых, на основе специальных вероятностных критериев [10, 19, 20]: решение данной проблемы должно было способствовать созданию «логики научного открытия», важность которой как для философии науки, так и для практики хорошо осознавалась многими исследователями [10, 18, 29].

Проблема индуктивного синтеза (логически) непротиворечивых теорий порой именуется проблемой статистической двусмысленности вероятностных предсказаний. С целью её решения К. Гемпелем было выдвинуто требование максимальной специфичности [19], применяемое к правилам в языке, когда над последним задано конкретное вероятностное распределение (см., например, [33]). Однако поскольку требование специфичности у К. Гемпеля носит довольно неформальный характер, интерес представляет рассмотрение его формальных версий, для которых непротиворечивость соответствующих теорий может быть установлена. Кроме того, для таких версий обосновано изучение вычислительных аспектов сопутствующих понятий и, в частности, вопроса о разрешимости свойства максимальной специфичности. Отметим, что варианты формализации (требования специфичности), предложенной в [39] и впоследствии развитой в [51, 52, 55], использовались в прикладных исследованиях по экономике, биоинформатике и медицине (см. обширную библиографию в [3]), а также по когнитивным наукам (дополнительно см. [53, 54]). Такие варианты и будут изучаться в Главе 1.

Напротив, в качестве главной задачи в вероятностной логике выступает изучение (фрагментов) самого языка теории вероятностей логическими средствами. Разумеется, появление этого направления тесно связано с аксиоматизацией исчисления вероятностей [23], позволившей погружать указанное исчисление в стандратные формальные системы для рассуждения о множествах (будь то ZFC или ЫСВ). Значит, к числу основных проблем вероятностной логики можно отнести выделение достаточно естественных фрагментов языка теории вероятностей и изучение их свойств (как теоретико-модельных, так и вычислительных).

Ядро вероятностных пространств составляют булевы алгебры, снабжённые аддитивными мерами, один из наиболее фундаментальных объектов математики. Тем не менее, хотя теоретико-модельным свойствам такого сорта метрических структур посвящено довольно большое количество литературы (см. [8, 11, 33, 40]), вычислительные особенности языков, чья семантика задаётся специальными классами этих структур, стали исследоваться относительно недавно (например, см. [7, 13, 21, 38]). Здесь, поскольку о вероятностных пространствах можно рассуждать в различных языках, особый интерес представляет изучение сравнительно слабых фрагментов теории вероятностей на предмет разрешимости, классификация возникающих алгоритмических проблем (точнее, их т-степеней) по вычислительной сложности и т. п.

С точки зрения теории вероятностей (и математической статистики), естественным и одновременно полезным выглядит обобщение известных бескванторных формализмов с разрешимой проблемой общезначимости (к примеру, таков язык из [13, Раздел 5]) за счёт введения кванторов по случайным величинам. При обобщении формализма из [13] можно воспользоваться пропозициональной классической логикой для записи измеримых событий, а простейшие (бернуллиевские) случайные величины, выраженные в терминах пропозициональных формул, взять за область квантификации переменных. Получающийся язык (обозначим его прежде не изучался, однако, он весьма тесно связан со слабыми фрагментами теоретико-модельных логик Д. Хувера и Д. Кейслера [21, 22] и «чистой индуктивной логики» Д. Пэриса [27], в которых допускаются бесконечные конъюнкции и дизъюнкции особого типа. Вычислительной характеризации и его вариантов (возникающих при варьировании семантики) и посвящена Глава 2.

В диссертации используются методы классической теории вычислимости [32], а также теоретико-модельные подходы к разрешимости (примером служит метод относительной элементарной определимости [4]) и техника работы с определимостью в арифметике второго порядка, изложенная в [34]. Получены следующие основные результаты:

• Доказано, что универсально аксиоматизируемые теории (в логике первого порядка), построенные с помощью формального требования максимальной специфичности, чья формулировка приведена в работе и опирается на идеи К. Гемпеля и Е. Е. Витяева, логически непротиворечивы. Предложен ряд модификаций упомянутого требования специфичности, причём для каждого случая установлена непротиворечивость соответствующих теорий. [47].

• Доказано, что даже если ограничиться рассмотрением пропозициональных правил, т. е. когда требование специфичности приводится в терминах пропозициональной логики, существуют рациональ-но-значные вычислимые вероятностные распределения (над пропозициональными формулами), для которых совокупность максимально специфичных правил невычислима. Согласно приведённому в работе определению, посылка любого специфичного правила лежит в специальном вычислимом множестве конъюнкций Faci д. Для вероятностных мер, принимающих лишь конечное число значений на элементах FactA, рассмотрено несколько вспомогательных рационально-значных параметров и установлено, знание каких из указанных параметров позволяет по клиниевскому номеру вычислимой меры с конечным числом значений на FactA эффективно строить разрешающую процедуру для соответствующей совокупности максимально специфичных правил. [48].

• Введён вероятностный язык Q7L, естественным образом расширяющий бескванторный формализм Фэйгина-Хальперна-Мегиддо за счёт добавления кванторов по бернуллиевским случайным величинам, выраженным в терминах пропозициональных формул. [49].

• Найдена точная граница для разрешимости проблемы общезначимости в префиксных фрагментах языка Q3?: доказано, что проблема общезначимости для /Э-ОТ?.-предложений разрешима, а для ЗУ-ОУ?-предложений — неразрешима. [49, 50].

• Доказано, что проблема общезначимости для ОУ?-предложений является П}-полной (более того, П}-полнота достигается уже на уровне ЗУЗ/-предложений). [50].

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

Вышеупомянутые результаты неоднократно докладывались на:

• семинарах «Алгебра и логика», «Автоматы и сложность вычислений», «Нестандартные логики», «Конструктивные модели» и «Теория вычислимости» Новосибирского национального исследовательского государственного университета;

• семинаре Лаборатории логических систем Института математики им. С. Л. Соболева СО РАН, и были представлены на международных конференциях «Мальцевские чтения» (Новосибирск, 2009, 2010, 2011) и «Logic Colloquium» (София,.

Болгария, 2009; Париж, Франция, 2010; Барселона, Испания, 2011), международном конгрессе «Continuity, computability, constructivity» (Триер, Германия, 2012), а также совместном российско-американском семинаре «Вычислимость и модели» (Новосибирск, 2012). Основные результаты диссертации опубликованы в работах автора [41]—[50].

Дадим краткий обзор содержания Глав 1−2.

1. Боровков А. А. Математическая Статистика. Новосибирск: ИМ СО РАН, 1997. 772 с.

2. Боровков А. А. Теория Вероятностей. М.: УРСС, 2009. 656 с.

3. Витяев Е. Е. Извлечение Знаний из Данных. Компьютерное Познание. Моделирование Когнитивных Процессов. Новосибирск: НГУ, 2006. 293 с.

4. Ершов Ю. JI. Проблемы Разрешимости и Конструктивные Модели. М.: Наука, 1980. 416 с.

5. Матиясевич Ю. В. Десятая Проблема Гильберта. М.: Наука, 1993. 224 с.

6. Трулстра А. С. Аспекты конструктивной математики // Справочная Книга по Математической Логике, Ч. IV / Ред. Дж. Барвайс. М.: Наука, 1983. С. 160−240.

7. Abadi М., Halpern J.Y. Decidability and expressiveness for first-order logics of probability // Inf. Comput. 1994. V. 112, No. 1. P. 1−36.

8. Barwise J., Feferman S. (eds.) Model-theoretic Logics. Berlin: Springer, 1985. 893 p.

9. Carnap R. A basic system of inductive logic, Part 1 // Studies in Inductive Logic and Probability, Vol. 1 / Eds. R. Carnap, R. C. Jeffrey. Univ. of California Press, 1971. P. 33−165.

10. Carnap R. The Continuum of Inductive Methods. Chicago: Univ. of Chicago Press, 1952. 92 p.

11. Chang C.C., Keisler H.J. Continuous Model Theory. Princeton: Princeton Univ., 1966. 165 p.

12. Enderton H. B. A Mathematical Introduction to Logic. New York: Academic Press, 2001. 317 p.

13. Fagin R., Halpern J. Y., Megiddo N. A logic for reasoning about probabilities // Inf. Comput. 1990. V. 87, No. 1−2. P. 78−128.

14. Garfunkel S., Schmerl J. H. The undecidability of theories of grupoids with an extra predicate // Proceedings of AMS. 1974. V. 42, No. 1. P. 286−289.

15. Halpern J. Y. An analysis of first-order logics of probability // Artificial Intelligence. 1990. V. 46. P. 311−350.

16. Halpern J.Y. Presburger arithmetic with unary predicates is n} complete // J. Symbolic Logic. 1991. V. 56, No. 2. P. 637−642.

17. Harel D., Pnueli A., Stavi J. Propositional dynamic logic of nonregular programs // J. Comput. System Sci. 1983. V. 26, No. 2. P. 222−243.

18. Hempel C. G. Deductive-nomological versus inductive-statistical explanation // Minnesota Studies in the Philosophy of Science, Vol. 3 / Eds. H. Feigl, G. Maxwell. Univ. of Minnesota Press, 1962. P. 98−169.

19. Hempel C. G. Maximal specificity and lawlikeness in probabilistic explanation // Philosophy of Science. 1968. V. 35, No. 2. P. 116−133.

20. Hintikka J., Hilpinen R. Knowledge, acceptance, and inductive logic // Aspects of Inductive Logic / Eds. J. Hintikka, P. Suppes. Amsterdam: North-Holland, 1966. P. 1−20.

21. Hoover D. N. Probability logic // Ann. Math. Logic. 1978. V. 14. P. 287−313.

22. Keisler H.J. Probability quantifiers // Model-theoretic Logics / Eds. J. Barwise, S. Feferman. Berlin: Springer, 1985. P. 509−556.

23. Kolmogorov A. N. Grundbegriffe der Wahrscheinlichkeitsrechnung, Berlin: Julius Springer, 1933. 62 p.

24. Lloyd J. W. Foundations of Logic Programming. Springer-Verlag, 1987. 212 p.

25. Ng R., Subrahmanian V. S. Probabilistic logic programming // Inf. Comput. 1993. V. 101, No. 2. P. 150−201.

26. Nies A. Undecidable fragments of elementary theories // Algebra Universalis. 1996. V. 35. P. 8−33.

27. Paris J. Pure inductive logic // The Continuum Companion to Philosophical Logic / Eds. L. Horsten and R. Pettigrew. London: Continuum International Publishing Group, 2011. P. 428−449.

28. Poonen B. Characterizing integers among rational numbers with a universal-existential formula // American J. of Math. 2009. V. 131, No. 3. P. 675−682.

29. Popper K. R. The Logic of Scientific Discovery. Hutchinson & Co, London, 1959. 479 p.

30. Priest G. An Introduction to Non-classical Logic: From If to Is. Cambridge: Cambridge Univ. Press, 2008. 613 p.

31. Robinson J. Definability and decision problems in arithmetic // J. Symbolic Logic. 1949. V. 14. P. 98−114.

32. Rogers H. Theory of Recursive Functions and Effective Computability. New York: McGraw-Hill, 1967. 482 p.

33. Scott D., Krauss P. Assigning probabilities to logical formulas // Aspects of Inductive Logic / Eds. J. Hintikka, and P. Suppes. Amsterdam: North-Holland, 1966. P. 219−264.

34. Simpson S. G. Subsystems of Second Order Arithmetic. Cambridge: Cambridge Univ. Press, 2009. 444 p.

35. Suppes P. A Probabilistic Theory of Causality. Amsterdam: North-Holland, 1970. 130 p.

36. Tarski A. A Decision Method for Elementary Algebra and Geometry. Univ. of California Press, 1951. 63 p.

37. Terwijn S. A. Probabilistic logic and induction // J. Logic and Comput. 2005. V. 15, No. 4. P. 507−515.

38. Terwijn S.A. Decidability and undecidability in probability logic // Proceedings of Logical Foundations of Computer Science, LNCS 5407. Springer, 2009. P. 441−450.

39. Vityaev E. E. The logic of prediction // Mathematical Logic in Asia 2005, Conference Proceedings, Novosibirsk, Russia / Eds. S. S. Goncha-rov, R. Downey, and H. Ono. World Scientific, 2006. R 263−276.

40. Сперанский С. О. К вопросу непротиворечивости семантического вероятностного предсказания // Тезисы, Малъцевские Чтения 2009, Новосибирск, Россия, Август 24−28. С. 230.

41. Speranski S. О. On the question of consistence of the semantic ??-prediction // The Bulletin of Symbolic Logic. 2010. V. 16, No. 1. P. 131−132.

42. Сперанский С. О. О неразрешимости свойства максимальной специфичности // Тезисы, Малъцевские Чтения 2010, Новосибирск, Россия, Май 2−6. С. 36.

43. Speranski S. О. On undecidability of the property of maximal specificity // The Bulletin of Symbolic Logic. 2011. V. 17, No. 2. P. 328−329.

44. Speranski S. O. Complexity for probability logic with quantifiers over propositions // Abstracts, Maltsev Meeting 2011, Novosibirsk, Russia, October 11−14. P. 111.

45. Speranski S. 0. Quantification over propositional formulas in probability logic: computability issues // The Bulletin of Symbolic Logic. 2012. V. 18, No. 3. P. 464−465.Статьи в журналах и трудах конференций.

46. Сперанский С. О. О логической непротиворечивости вероятностных предсказаний // Вестник НГУ. Серия: Матем., Механика, Ин-форм. 2011. Т. 11, Вып. 1. С. 99−115.

47. Сперанский С. О. О вычислительных аспектах максимальной специфичности в вероятностном объяснении // Вестник НГУ. Серия: Матем., Механика, Информ. 2011. Т. И, Вып. 4. С. 78−93.

48. Сперанский С. О. Квантификация по пропозициональным формулам в вероятностной логике: вопросы разрешимости // Алгебра и Логика. 2011. Т. 50, Вып. 4. С. 533−546.

49. Speranski S.O. Complexity for probability logic with quantifiers over propositions // J. Logic and Comput. 2012. doi: 10.1093/logcom/exs041.

50. Сперанский С. О., Витяев Е. Е. Синтез логики, вероятности и обучения: формализация предсказания // Сиб. электрон, матем. изв. 2009. Т. 9. С. 340−365.

51. Vityaev E. E., Perlovsky L. I., Kovalerchuk B.Ya., Speranski S.O. Probabilistic dynamic logic of phenomena and cognition // Proceedings of the World Congress on Computational Intelligence 2010, Barcelona, Spain, July 18−23. 2010. P. 3361−3366.

52. Витяев E. E., Перловский JI. И., Ковалерчук Б. Я., Сперанский С. О. Вероятностная динамическая логика мышления // Нейроинформа-тика. 2011. Т. 5, № 1. С. 1−20.

53. Vityaev Е. Е., Speranski S.O. On the problem of prediction // Knowledge Processing and Data Analysis: KONT/KPP 2007, LNAI 6581 / Eds. K.E. Wolff et al. Springer, 2011. P. 280−296.l i0 ?