Александр Грефенштейн//Бескванторная линейная вероятностная логика (в измеримом случае)

НИС "Современные проблемы математической логики" в ВШЭ

Дата и время: 15.04.2022 в 16:20

Докладчик:
Александр Грефенштейн

Название: Бескванторная линейная вероятностная логика (в измеримом случае)

Аннотация:

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

На докладе мы рассмотрим одну такую логику. В её синтаксисе события будут выражаться пропозициональными формулами, а вероятностные формулы будут строиться из линейных комбинаций вероятностей с помощью обычных логических связок; её семантика будет определена в терминах подходящих вероятностных структур. Далее, мы предъявим корректную аксиоматизацию для этой логики и покажем, что для неё будет верна теорема о слабой полноте. Кроме того, пользуясь некоторыми полезными утверждениями из линейного программирования, мы докажем, что проблема выполнимости для данной логики NP-полна.

Видео Александр Грефенштейн//Бескванторная линейная вероятностная логика (в измеримом случае) канала Логика в Москве