ЛОГИЧЕСКИЕ ЗАКОНЫ ДЛЯ ЭКЗИСТЕНЦИАЛЬНЫХ МОНАДИЧЕСКИХ ФОРМУЛ С БЕСКОНЕЧНОЙ ЧАСТЬЮ ПЕРВОГО ПОРЯДКА

Мы рассматриваем экзистенциальные монадические предложения вида ∃Х φ(Х) о неориентированных графах, где ∃Х - конечная последовательность кванторов по монадическим переменным, а φ(Х) ∈ Lω∞ω - бесконечная формула первого порядка. Мы доказали, что существует такое предложение с двумя монадическими переменными и двумя переменными первого порядка, для которого вероятность его истинности для случайного графа G(n, p) расходится. Кроме того, аналогичный пример удаётся построить для одной монадической переменной и трёх переменных первого порядка.