Аннотация:
По множеству слов в данном алфавите строится шкала Крипке с отношением «слова имеют одинаковую длину и отличаются в одной позиции» и рассматриваются модальные логики таких шкал. Оказывается, что эти логики тесно связаны со степенями (в смысле модального произведения) логики S5. Доказано, что в случае конечной фиксированной длины слов эти логики неразрешимы и не обладают конечной аксиоматикой (более того, не могут быть аксиоматизируемы никаким множеством формул, содержащих в совокупности лишь конечное число переменных). Относительно бесконечных последовательностей доказана полнота логики DB — конечно аксиоматизируемой логики с достаточно невысокой алгоритмической сложностью (PSPAСE).
Доклад основан на совместной работе с А. В. Кудиновым и В. Б. Шехтманом.
|
