#матлог #учёба #просеминар

💥В среду 5 ноября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Модальная логика" (Оноприенко А.А.).
✨Аннотация. Модальная логика - неклассическая логика, в которой к стандартным классическим связкам (конъюнкция, дизъюнкция, импликация, отрицание) добавляется "модальность", которую в зависимости от контекста можно понимать по-разному: "необходимо", "доказуемо", "известно" и др. Мы обсудим модальное исчисление, семантику Крипке для модальных логик, разные примеры модальных логик, взаимосвязь модальных формул и свойств шкал Крипке, которые они задают.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://t.iss.one/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 modal2025.pdf

➰ ВК

#матлог #учёба #спецсеминар

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425.

7 ноября 2025 г.

Г. Г. Черевиченко
"Номинальная унификация" (продолжение доклада от 31 октября)
Унификация в простейшем случае — это решение уравнений в свободных алгебраических системах. Например, рассмотрим алфавит из двух символов a,b и уравнение aX=Yb, где X и Y обозначают слова в этом алфавите (которые надо найти). Слова с операцией приписывания образуют свободную полугруппу. Решение выглядит так: берём произвольное слово Z и полагаем X=Zb, Y=aZ, тогда aX=aZb=Yb. Мы как бы подобрали слово (aZb), подходящее под оба шаблона aX и Yb, от этого слово "унификация". В более хитрых случаях слова (например, формулы логики первого порядка или лямбда-термы) могут содержать связывающие операции (кванторы, лямбды) и рассматривать их надо с точностью до переименования связанных переменных. Проблема унификации в этом случае имеет неожиданное красивое решение.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 109 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту [email protected].

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

Название: Коммуникационная сложность функции равенства и коды, исправляющие ошибки.

Докладчик: Владимир Подольский

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

➰ ВК

#матлог #учёба #спецсеминар #отмены

7 ноября 2025 г. заседание семинара "Вычислимость и неклассические логики" не состоится.
Продолжение доклада Г. Г. Черевиченко "Номинальная унификация" переносится на 14 ноября.

➰ ВК

#матлог #учёба #просеминар

💥В среду 12 ноября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Модальная логика, продолжение" (Оноприенко А.А.).
✨Аннотация. Модальная логика - неклассическая логика, в которой к стандартным классическим связкам (конъюнкция, дизъюнкция, импликация, отрицание) добавляется "модальность", которую в зависимости от контекста можно понимать по-разному: "необходимо", "доказуемо", "известно" и др. Мы обсудим модальное исчисление, семантику Крипке для модальных логик, разные примеры модальных логик, взаимосвязь модальных формул и свойств шкал Крипке, которые они задают.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://t.iss.one/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 modal2025.pdf

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 12 ноября в 14:00.

Место проведения: ОНЛАЙН. Для получения ссылки пишите на почту [email protected].

Можно подключиться самостоятельно, а можно подойти по адресу, МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идёте на семинар ВШМ и предъявить паспорт.

Докладчик: Д.П. Шкатов (Университет Йоханнесбурга, ЮАР)

Название: Доказательства полноты по Крипке для предикатных модальных логик

Аннотация.

Будут изложены основные идеи, на которых основываются доказательства полноты по Крипке для предикатных модальных логик. Будут приведены примеры канонических и неканонических, но полных по Крипке, логик.

➰ ВК

#матлог #учёба #спецсеминар

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425.

14 ноября 2025 г.

Г. Г. Черевиченко
"Номинальная унификация" (продолжение доклада от 31 октября)
Унификация в простейшем случае — это решение уравнений в свободных алгебраических системах. Например, рассмотрим алфавит из двух символов a,b и уравнение aX=Yb, где X и Y обозначают слова в этом алфавите (которые надо найти). Слова с операцией приписывания образуют свободную полугруппу. Решение выглядит так: берём произвольное слово Z и полагаем X=Zb, Y=aZ, тогда aX=aZb=Yb. Мы как бы подобрали слово (aZb), подходящее под оба шаблона aX и Yb, от этого слово "унификация". В более хитрых случаях слова (например, формулы логики первого порядка или лямбда-термы) могут содержать связывающие операции (кванторы, лямбды) и рассматривать их надо с точностью до переименования связанных переменных. Проблема унификации в этом случае имеет неожиданное красивое решение.

➰ ВК

#матлог #учёба #миникурсы

На следующей неделе С.Л. Кузнецов и С.О. Сперанский (МИАН) в рамках своего визита в Новосибирский университет прочтут мини-курсы.

Лекции пройдут очно в НГУ, возможно также подключение онлайн. Для получения ссылки нужно зарегистрироваться на соответствующий мини-курс на странице https://sites.google.com/view/mca-logic/

На той же странице размещены аннотации курсов, а после их завершения будут опубликованы видеозаписи и файлы презентаций.

Расписание лекций
ВНИМАНИЕ! Время везде указано новосибирское, т.е. +4 часа от московского, GMT+7.

В рамках мини-курса С.Л. Кузнецова «Бесконечные доказательства для неклассических логик» запланировано три лекции:
(1) 17 ноября 2025 г. (понедельник), 16:20-17:55
(2) 20 ноября 2025 г. (четверг), 16:20-17:55
(3) 21 ноября 2025 г. (пятница), 16:20-17:55

В рамках мини-курса С.О. Сперанского «Аксиоматизация теории слабых вероятностных пространств» запланировано две лекции:
(1) 18 ноября 2025 г. (вторник), 16:20-17:55
(2) 19 ноября 2025 г. (среда), 16:20-17:55

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

The next Proof Society Seminar will take place on Monday 17 November 2025 at 14:00 CET. Our speaker will be Juliette Kennedy (https://www.mv.helsinki.fi/home/jkennedy/), from the University of Helsinki. Details can be found below.

How first order is first order logic?
Juliette Kennedy, University of Helsinki

Fundamental to the practice of logic is the dogma regarding the first order/second order logic distinction, namely that it is ironclad. Was it always so? The emergence of the set theoretic paradigm is an interesting test case. Early workers in foundations generally used higher order systems in the form of type theory; but then higher order systems were gradually abandoned in favour of first order set theory—a transition that was completed, more or less, by the 1930s.

In this talk I will look at first order logic from various points of view, arguing that the distinction between first order and higher order logics, such as second order logic, is somewhat context dependent. From the philosophical or foundational point of view this complicates the picture of first order logic as a canonical logic.

The Proof Society Seminar (https://www.proofsociety.org/proof-society-seminar/) is the official seminar of the Proof Society (https://www.proofsociety.org/), and it presents talks by leading researchers from all areas of proof theory. Everyone who is interested in the subject is warmly invited to attend! The talks take place online via Zoom, usually on Mondays, approximately once per month. They start at 13:00 UTC and may last up to 75 minutes plus questions.

➰ ВК

#матлог #спецсеминар #нпммвя

В четверг 20 ноября в Институте языкознания РАН (с возможностью подключения онлайн) состоится заседание семинара «Некоторые применения математических методов в языкознании» с докладом Максима Евгеньевича Вишникина "Категориальные грамматики с ограничением на количество присваиваемых категорий".

Время: 20.11.2025, 14:00-15:30.
Место: Институт языкознания РАН, Большой Кисловский пер., 1, стр. 1, конференц-зал. Для прохода необходимо зарегистрироваться по ссылке ниже и взять с собой паспорт.

Ссылка для регистрации: https://forms.gle/RwXRf33JE3CP1bHBA
(все зарегистрировавшиеся получат ссылку для онлайн-подключения)

Тема: Категориальные грамматики с ограничением на количество присваиваемых категорий

Анонс:
В докладе будут рассмотрены три типа грамматических формализмов: грамматики Ламбека, AB-грамматики и базовые категориальные грамматики. Основное внимание будет уделено ограничению на количество присваиваемых категорий (параметр k) для каждого из них. Ключевой мотивацией для этого ограничения служит теория обучения грамматик по Голду, то есть задача идентификации грамматики по тексту. Эта концепция, введённая Марком Голдом в 1967 году, будет подробно изложена в первой части. Будут приведены известные результаты о том, что класс всех контекстно-свободных грамматик необучаем; однако при ограничении количества возможных правил полученный подкласс становится обучаемым (теорема Шинохары). Этот результат естественным образом распространяется на случай AB-грамматик (теорема Канадзавы).

В первой части доклада для трёх указанных формализмов будет представлен обзор результатов о классах грамматик с количеством категорий, ограниченным параметром k. Данное ограничение для AB-грамматик исследовал Канадзава, а для грамматик Ламбека — Форе. Также будут рассмотрены методы сведения языков, порождаемых различными грамматическими формализмами, друг к другу. В частности, теорема Сафиуллина, которая утверждает, что грамматики Ламбека с однозначным присвоением типов порождают все контекстно-свободные языки. Из данной теоремы сразу следует, что класс грамматик Ламбека с однозначным присвоением типов необучаем в смысле Голда.

Во второй части доклада будут рассмотрены алгоритмические свойства полученных классов грамматик. В частности, будут представлены результаты Форе, а также их усиление для AB-грамматик и базовых категориальных грамматик.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
19 ноября в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Abstract Model Structures and Compactness Theorems.

Докладчик: Саянтан Рой (научный сотрудник МЛ ЛогЛинФФ).

Аннотация: The compactness theorem for a logic states, roughly, that the satisfiability of a set of well-formed formulas can be determined from the satisfiability of its finite subsets, and vice versa. Usually, proofs of this theorem depend on the syntactic/semantic particularities of the corresponding logic. In this talk, using the notion of abstract model structures, we show that one can develop a generalized notion of compactness that is independent of these. Several characterization theorems for a particular class of compact abstract model structures are also proved.
_____________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1101848996.html

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email [email protected])

17 November, 18:30 MSK

Tomorrow on the seminar there will be the final part of the presentation by Fyodor Kiselyov. We will discuss the definition of randomized reductions between search problems and some sort of "derandomization" result: any randomized reduction from PPP to some class may be transformed to a usual deterministic reduction.

➰ ВК

#матлог #учёба #просеминар

💥В среду 19 ноября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Модальная логика, продолжение 2" (Лев Дворкин).
✨Аннотация. Модальная логика - неклассическая логика, в которой к стандартным классическим связкам (конъюнкция, дизъюнкция, импликация, отрицание) добавляется "модальность", которую в зависимости от контекста можно понимать по-разному: "необходимо", "доказуемо", "известно" и др. Мы обсудим модальное исчисление, семантику Крипке для модальных логик, разные примеры модальных логик, взаимосвязь модальных формул и свойств шкал Крипке, которые они задают.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://t.iss.one/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 modal2025.pdf

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 19 ноября в 15:00.
‼Время необычное‼

Место проведения: ОНЛАЙН. Для получения ссылки пишите на почту [email protected].

Можно подключиться самостоятельно, а можно подойти по адресу:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идете на семинар ВШМ и предъявить паспорт.

Докладчики: Д.П. Шкатов (Университет Йоханнесбурга, ЮАР)

Название: Введение в семантику первопорядковых модальных логик - часть 3

Аннотация.
Третий доклад из серии, основанной на вводных лекциях о семантике первопорядковых модальных логик, прочитанных совместно с В. Б. Шехтманом летом 2025 года в рамках ESSLLI 2025. Будут изложены некоторые методы доказательства полноты по Крипке неканонических логик и представлено краткое введение в семантику пучков Крипке.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar (www.mathnet.ru/conf876), Monday 16:00 MSK, Room 313 + Kontur Talk

24.11.2025, jointly with S.I. Adian seminar, I.G. Lysenok (Steklov Mathematical Institute, https://www.mathnet.ru/person/8818): A sample iterated small cancellation theory for groups of Burnside type.

We develop yet another technique to present the free Burnside group B(m,n) of odd exponent n with m≥2 generators as a group satisfying a certain iterated small cancellation condition. Using the approach, we provide a reasonably accessible proof that B(m,n) is infinite with a moderate bound n2000 on the odd exponent n.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email [email protected])

This Monday 24 November, 18:30 MSK, we will have a talk by Alexander Shen.

Upcrossing inequalities revisited

Bishop used upcrossing inequalities to prove Birkhoff's ergodic theorem. Vyugin used his inequality (in one of the forms) to prove the algorithmic version of it (for Martin-L\"of random sequences). It turns out that another version (a stronger one, from a different paper of Bishop) immediately implies the result of Barmpalias and Lewis-Pye about lower semicomputable randoms: if $a_n$ and $b_n$ are computable increasing sequences of rational numbers that converge to reals $A$ and $B$, and $A$ is random, then $(B-b_n)/(A-a_n)$ converges. And, to finish the story, Misha Andreev invented a simple and nice proof of the Bishop's inequality used in this argument.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/).

27 ноября и 4 декабря 2025 г. состоятся два доклада Т.Г. Пшеницына «Сложность релевантной логики и её разновидностей».

Время: 16:00
Место: МИАН, ауд. 530 + Контур.Толк
Для получения ссылки зарегистрируйтесь на странице семинара: https://www.mathnet.ru/conf2533
(ссылка единая для всех заседаний в этом семестре).

Аннотация:
Классическая импликация не является релевантной, поскольку в классической логике верен закон A→(B→A): истинное утверждение A следует из любого другого утверждения B. Этот закон соответствует структурному правилу ослабления, согласно которому можно произвольным образом усиливать посылку импликации или ослаблять ее заключение. Релевантная логика R — это субструктурная логика классического типа без правила ослабления, но с правилом дистрибутивности. Оказывается, что задача доказуемости в этой логике неразрешима: к ней можно свести задачу равенства в полугруппах (Уркхарт, 1984). С другой стороны, R без дистрибутивности — в литературе такая логика ещё обозначается через CFL_{ec} — оказывается разрешимой, что следует из так называемого "трюка Крипке". При этом сложность доказуемости в CFL_{ec} является Аккерман-полной задачей; если же ограничиться импликативным фрагментом R, сложность падает до 2-EXPTIME. В доказательстве последних двух результатов используются алгоритмические задачи для разновидностей счетчиковых машин с "ненадёжными вычислениями".

В докладах будет дан обзор всех этих результатов.

Литература:
[1] Urquhart, A. (1984). The Undecidability of Entailment and Relevant Implication. The Journal of Symbolic Logic, 49(4), 1059–1073.
[2] Urquhart, A. (1999). The Complexity of Decision Procedures in Relevance Logic II. The Journal of Symbolic Logic, 64(4), 1774–1802.
[3] Schmitz, S. (2016). Implicational Relevance Logic is 2-EXPTIME-complete. The Journal of Symbolic Logic, 81(2), 641–661.

➰ ВК

#матлог #учёба #просеминар

💥В среду 26 ноября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Деревья решений и вопросная сложность" (Верещагин Н.К., профессор кафедры).
✨Аннотация. Деревом решений данной булевой функции называется двоичное дерево: в каждой вершине спрашивается значение переменной, и далее идём в левый или правый потомок в зависимости от значения этой переменной. Вопросной сложностью называется минимальная глубина такого разрешающего дерева. На просеминаре обсудим задачи, касающиеся вопросной сложности.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://t.iss.one/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 Вопросная_сложность_2025.pdf

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 26 ноября в 14:00.

Место проведения:
МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идете на семинар ВШМ и предъявить паспорт.
Будет интернет-трансляция, для получения ссылки пишите на почту [email protected].

Название: Проблема унификации для подсистем полимодальной логики доказуемости GLP

Докладчик: Никита Лукашов (НИУ ВШЭ)

Аннотация:

Полимодальная логика доказуемости GLP со счётным числом модальностей была введена Г. Джапаридже в 1980-х годах и нашла интересные применения в теории доказательств. Несмотря на неполноту по Крипке, GLP разрешима и для неё были установлены многие обычные свойства модальных логик.

Большинство положительных результатов о GLP были получены с помощью сведения к её подсистеме J, которая уже является полной по Крипке относительно класса, так называемых, стратифицированных моделей. Однако это сведение, к сожалению, не сохраняет тип унификации: Л.Д. Беклемишевым (2025 год) было показано, что логика GLP в языке даже с двумя модальностями обладает нулевым типом унификации, в то время как мною было установлено, что соответствующие подсистемы J с ограниченным числом модальностей обладают конечным типом унификации.

В своём докладе я представлю мои результаты касательно типа унификации J и её подсистем J_t в языках с модальностями [0], [1], … [t-1]. Обобщив методы С. Гилярди (конец 1990-х годов) для одномодального случая, мне удалось показать, что для всех t логики J_t обладают конечным типом унификации. При этом для всей логики J с бесконечным числом модальностей мне удалось установить нулевой тип унификации.

Доклад основан на статье: Lukashov N. V. Unification in subsystems of polymodal provability logic GLP //Logic Journal of the IGPL. – 2025. – Т. 33. – №. 6. – (to appear).

➰ ВК