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

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

16 мая 2025 г.
Г. Г. Черевиченко
Обзор исчислений процессов.
Математический логик, занявшись computer science, обнаруживает там много исчислений, о которых он не слышал, некоторые из них весьма интересные, имеют довольно долгую историю и активно применяются в приложениях. Например, все новые протоколы (обмен паролями, куками и т.п.) проверяют специальными программами, основанными на pi-calculus Милнера (с тех пор как в 1995 году Gavin Lowe испытал одну из первых таких программ, взломал протокол Нидхема-Шрёдера и открыл атаку man in the middle). Докладчик расскажет о собственных проблемах при написании распределённой программы (объекты обмениваются сигналами) и попытках их формально описать и исследовать с помощью исчислений процессов, упор будет сделан на программу mCLR2
https://mcrl2.org/web/index.html
Можно также посмотреть видео к программе докладчика (регистрироваться не надо, надо найти кнопку "скачать")
https://mega.nz/file/igo0zDBC#JgIYMtie3UmKXgDgtWBKzXE25xPA-qvZuKMKQ3y8fFk

➰ ВК

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

Logic Online Seminar (https://www.mathnet.ru/eng/conf876), Monday 16:00 MSK (UTC+3), Kontur Talk

19.05.2025 Михаил Панов (НИУ ВШЭ, Санкт-Петербург, https://www.hse.ru/org/persons/303615376/): Эпистемическая модель с ограниченно рациональными игроками (очный доклад)

Будет предложена общая и простая модель для анализа эпистемических оснований принятий решений в некооперативной теории игр. В модели игрок сталкивается со стратегической ситуацией, описанной эпистемической картиной — множеством утверждений, записанных на формальном языке. По эпистемической картине игрок строит пространство состояний и набор действий; формирует предпочтения над действиями; и выбирает оптимальное действие. У игрока конечный уровень рассуждений: в своё пространство состояний он включает все возможные варианты действий оппонентов с уровнем ниже своего.

В модели исследуется соответствие между эпистемическими картинами и порождаемым ими поведением. В частности, будут предложены достаточные условия, при которых это поведение будет устойчивым при (i) увеличении точности эпистемических картин, (ii) повышении уровня игроков, (iii) изменения развернутой формы игры. Также, будет дана переоценка эпистемических оснований нескольких основных некооперативных решений.

➰ ВК

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

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

Ball, Liu, Mazor and Pass [BLMP23] proved that the existence of key-agreement protocols is equivalent to a certain estimate of interactive Kolmogorov complexity being in ioBPP. In the previous talk we stated the problem, explained that this estimation problem is decidable, and proved the backward impliciation (in the contra-positive, breaking a specific protocol provides an ioBPP algorithm for the estimation problem). In this talk we will briefly repeat everything and prove the forward implication (again in the contra-positive, with an ioBPP algorithm of the estimation problem we can break each protocol).

Notes: https://arxiv.org/pdf/2504.16311
The previous talk: https://www.youtube.com/watch?v=D1GdCXak0Nw

➰ ВК

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

Уважаемые коллеги,
приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 21 мая в 14:00.

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

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту [email protected].

Докладчик: Дворкин Лев

Название: Финитная аппроксимируемость расширений wK4, наследуемых подшкалами (часть 2)

Подшкалой шкалы Крипке (X; R) называется подмножество S носителя X с индуцированным отношением достижимости. Логика L наследуется подшкалами Крипке, если класс её шкал Крипке замкнут относительно взятия подшкал. Файн доказал, что все полные по Крипке расширения K4, наследуемые подшкалами, финитно аппроксимируемы. Данный результат был усилен Захарьящевым на случай логик, наследуемых конфинальными подшкалами (подшкалами, носитель которых конфинален в исходной шкале). Доказательства Файна и Захарьящева основываются на семантике Крипке. Бежанишвилли, Гильярди и Джибладзе дали чисто алгебраическое доказательство результатов Файна и Захарьящева, одновременно обобщив их на расширения wK4 = K + p → p \/ p. Разбору доказательства последнего результата и посвящён доклад. В первой части мы обсудим некоторые факты, касающиеся алгебраической семантики модальных логик. В отличие от семантики Крипке, данной семантике уделяют мало времени в курсах по модальной логике, поэтому мы остановимся на ней достаточно подробно. Вторая часть посвящена непосредственно доказательству результата. От слушателей предполагается знание базовых фактов о модальных логиках и семантике Крипке.

➰ ВК

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

На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ

"Модальная и алгебраическая логика" и "Логические методы в информатике"

в ближайший четверг 22 мая, начало в 18:30, состоится доклад

А.С.Герасимов
(Санкт-Петербург, СПбПУ )

"Депренексификация в финитарных аналитических исчислениях для первопорядковой бесконечнозначной логики Лукасевича и полнота основанных на них инфинитарных исчислений"

В докладе рассматривается несколько финитарных аналитических гиперсеквенциальных исчислений для первопорядковой бесконечнозначной логики Лукасевича \L$\forall$, включая введённое Баацем (Baaz) и Меткалфом (Metcalfe) исчисление G\L$\forall$ для \L$\forall$. В этих исчислениях правило сечения не допустимо и, вообще говоря, формула и её (определённая чисто синтаксически) пренексная форма не равновыводимы. Однако мы предлагаем метод депренексификации, позволяющий любой вывод любой гиперсеквенции H, в которой выделено вхождение любой пренексной формы любой формулы F, алгоритмически перестроить в вывод гиперсеквенции, полученной из H заменой этого вхождения на F. С помощью этого метода мы устанавливаем полноту инфинитарных аналитических исчислений, основанных на вышеупомянутых финитарных исчислениях для \L$\forall$. В частности, даём первое верное доказательство полноты основанного на G\L$\forall$ инфинитарного аналитического исчисления для \L$\forall$.

Видеозаписи предыдущих докладов:

https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCX

Веб-страница с аннотациями и слайдами:
http://logic.math.msu.ru/sem/ml/

Для получения ссылки Zoom пишите на почту [email protected].
Убедительно просим всех подключающихся указывать в Zoom свои настоящие имя и фамилию!

➰ ВК

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

В ближайшую пятницу (23 мая) в Институте языкознания РАН состоится заседание семинара "Некоторые применения математических методов в языкознании", на котором выступит Борис Николаевич Карлов, представитель тверской школы, известной своей математико-лингвистической традицией. Для участия в заседании (очно либо онлайн) необходимо зарегистрироваться по ссылке: https://forms.gle/PZBiDgLnyxkQqpAt6

Когда: 23 мая 2025 г. в 14:30
Где: Институт языкознания РАН, ауд. 10 (https://yandex.ru/maps/-/CHVNuN9b; первый этаж, по коридору налево) + онлайн
Докладчик: Борис Николаевич Карлов (Тверской государственный университет)
Тема: Лемма об обмене для категориальных грамматик зависимостей
Аннотация:
Как известно, классические категориальные грамматики не способны выражать непроективные зависимости между словами в предложениях, когда зависимое слово стоит в "чужой" синтаксической группе. Одним из расширений категориальных грамматик являются категориальные грамматики зависимостей (КГЗ) и мультимодальные КГЗ (ммКГЗ), введённые в работах А.Я.Диковского и М.И.Дехтяря. Это классические категориальные грамматики, дополнительно оснащённые так называемыми поляризованными валентностями, задающими начала и концы непроективных зависимостей. КГЗ весьма выразительны, в частности, они способны порождать некоторые языки, не задаваемые комбинаторными категориальными грамматиками. Однако были неизвестны примеры "простых" языков, не порождаемых КГЗ. Данный доклад посвящён решению этой проблемы. Для КГЗ-языков будет доказано необходимое условие, являющееся обобщением леммы об обмене для контекстно-свободных языков (interchange lemma). С помощью этой леммы будет доказано, что язык копий не порождается никакой КГЗ, что класс КГЗ-языков не замкнут относительно пересечения и дополнения, а также что существует ммКГЗ-язык, не являющийся КГЗ-языком.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
23 мая (пятница) в 18:30 состоится очередное заседание теоретического семинара "Формальная философия".

Тема доклада: Имплицированное и сказанное. Несколько контрпримеров к дихотомии значения Пола Грайса.

Докладчик: Иван Соболев (стажер-исследователь МЛ ЛогЛинФФ).

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

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

Анонс: https://llfp.hse.ru/announcements/1048098506.html

➰ ВК

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

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

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

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту [email protected].

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Саакян Степан

Название: Парадокс Ябло с точки зрения теории доказуемости

Аннотация.
Как известно, при замене истинности на доказуемость в парадоксе лжеца получается предложение Гёделя. "Это утверждение ложно" превращается в "Это утверждение недоказуемо", и после такой операции парадокс приводит к теореме. Что получится, если подобную замену проделать в парадоксе Ябло? Этим вопросом задались авторы статьи [1], изложением которой я и займусь.
Напомним формулировку парадокса: пусть существует счётная последовательность предложений, каждое из которых утверждает, что все следующие ложны. Рассуждениями, аналогичными таковым в парадоксе лжеца, можно довести это предположение до противоречия.
Оказывается, что замена истинности на доказуемость приводит к интересным результатам, связанным с теоремами Гёделя о неполноте и даже нестандартными моделями арифметики.

[1] Cieśliński, C., Urbaniak, R. Gödelizing the Yablo Sequence. J Philos Logic 42, 679–695 (2013). https://doi.org/10.1007/s10992-012-9244-4

➰ ВК

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

Семинар Добрушинской лаборатории Высшей школы современной математики МФТИ (ВШМ).
27 мая, вторник, 16:15, Адм. корпус ауд.322.
https://www.mathnet.ru/conf167

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный + трансляция в телемосте
Если у вас нет пропуска МФТИ, то на входе сообщайте, что идете на семинар и не забудьте паспорт.

Мусин Олег (University of Texas Rio Grande Valley): Теоремы существования и быстрые алгоритмы для задач справедливого дележа.
Existence theorems and fast algorithms for fair division problems

Аннотация:
У известной проблемы справедливого дележа - долгая история. У этой задачи имеется множество форм и она возникает в многочисленных жизненных ситуациях. В этом докладе я рассмотрю теоремы существования для задач справедливой аренды и разрезания торта, а также обобщения этих теорем.
Вторая часть доклада - это совместная работа, которая была мотивирована публикацией в New York Times: "To Divide the Rent, Start With a Triangle" by Albert Sun (April 28, 2014)", к которой прилагается калькулятор для справедливой аренды, основанный на работе Фрэнсиса Су. В недавно опубликованной статье мы рассматриваем алгоритмическую сложность задач справедливого дележа и минимизацию количества запросов, необходимых для нахождения приближённого решения с желаемой точностью. Для нескольких классов задач справедливого дележа показано, что при определённых естественных условиях на множествах предпочтений достаточно логарифмического количества запросов относительно точности.

➰ ВК

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

Обратите внимание на нестандартное время!
Logic Online Seminar (https://www.mathnet.ru/eng/conf876), Monday 17:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk

02.06.2025, 17:00, совместно с семинаром С.И. Адяна, О.В. Сипачёва (МГУ, мехмат, https://www.mathnet.ru/rus/person12816): Топологические универсальные алгебры: симбиоз алгебры и топологии (очный доклад)

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

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

➰ ВК

#матлог

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

Тема доклада: Модальная логика с точки зрения теоретико-доказательственной семантики.

Докладчик: Юрий Казаков (стажер-исследователь МЛ ЛогЛинФФ).

Аннотация: Помимо традиционной репрезентации модальной логики через модели Крипке, существует длительная традиция исследования теорий доказательств для соответствующего класса логик. При этом в логической семантике редко поднимался вопрос о возможности и целесообразности описания модальных связок через доказательственные конструкции. Для некоторых логик такое описание представляется более естественным или вовсе незаменимым, например, для интуиционистской или субструктурных. Но переносимы ли соответствующие результаты на класс модальных логик? Моё исследование посвящено именно этому вопросу. Я постараюсь познакомить слушателей с некоторыми основными идеями теоретико-доказательственной семантики как целостной программы, обосновать использование секвенций в качестве основных доказательственных конструкций и продемонстрировать результаты, полученные для модальных логик.

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

Анонс: https://llfp.hse.ru/announcements/1051159919.html

➰ ВК

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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 4 июня в 14:00.

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

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту [email protected].

Докладчики: В.Б. Шехтман, А.В. Кудинов

Название: О семантической полноте суперинтуиционистских и модальных логик

Аннотация:
Суперинтуиционистские логики были одним из основных направлений исследований А.В. Кузнецова, и проблемы полноты играют в этом контексте ключевую роль. В частности, Кузнецов поставил проблему о совпадении полноты по Крипке и топологической полноты. В статье Шехтмана "On Neighbourhood Semantics Thirty Years Later, 2005“ приведен контрпример, доказывающий, что топологическая полнота сильнее, чем семантика Крипке, но без явной аксиоматизации. Такие же примеры известны для модальных логик, содержащих S4. В докладе обсуждаются другие аналогичные примеры для суперинтуиционистских и модальных логик. В частности, будет дан пример конечно аксиоматизируемой модальной логики с 3 модальностями, которая полна в окрестностной семантике относительно счетной шкалы, но неполна в семантике Крипке.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
6 июня (пятница) в 18:30 состоится очередное заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Модификация аксиом о позитивности в онтологическом доказательстве Геделя.

Докладчик: Юлия Копчева (стажер-исследователь МЛ ЛогЛинФФ).

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

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

Анонс: https://llfp.hse.ru/announcements/1053296706.html

➰ ВК

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

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

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

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту [email protected].

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Иван Пыльцын

Название: Нефундированное расширение интуиционистской логики и игровая семантика Межирова.

Аннотация:
Семантическая игра Межирова впервые была описана Ильёй Межировым в 2006 году для интуиционистской пропозициональной логики и модальной логики Гжегорчика, представляя из себя независимый (в частности, не опирающийся на модели Крипке) семантический подход к описанию этих логик. Данная теоретико-игровая семантика описывала эти логики как множества тавтологий. Я заинтересовался поиском обобщения игры Межирова, которое бы описывало логики как отношения следования. В процессе моих поисков я обнаружил, что возможные естественные направления модернизации данной семантики приводят к некомпактным отношениям следования.

Представленная и описанная Данияром Шамкановым, модальная логика Гёделя-Лёба, расширенная нефундированными выводами, является одним из естественных примеров логики, представляющейся в виде некомпактного отношения следования. Мне удалось обнаружить некомпактную суперинтуиционистскую логику, которую так же возможно задать как расширение интуиционистской логики нефундированными выводами. Данная логика точно интерпретируется в упомянутом расширении логики Гёделя-Лёба при помощи перевода Гёделя-Тарского. Для неё мне удалось построить искомое естественное обобщение игровой семантики Межирова.

Фокус доклада будет направлен на полученное теоретико-игровое описание нефундированного расширения интуиционистской логики.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
13 июня (пятница) в 18:30 состоится очередное заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Многомерный и одномерный подходы к моделированию языковых значений: монады vs. импозиции.

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

Аннотация: ​​​​​​​В докладе будет рассмотрен многомерный подход к моделированию значений в терминах монад (Shan 2002; Giorgolo and Asudeh 2012, 2014; Charlow 2014). Подход позволяет сохранить интуицию, что высказывание может быть ассоциировано с несколькими независимыми значениями, при этом не исключает взаимодействия значений разных уровней, что важно для моделирования случаев анафоры и эллипсиса. Многомерный подход в терминах монад будет противопоставлен одномерному подходу в рамках динамической семантики в терминах импозиций, моделирующего те же языковые данные (AnderBois et al. 2010). Оба подхода будут применены к эвиденциальным конструкциям с пропозициональными глаголами. Будут рассмотрены сильные стороны каждого подхода и намечен путь их инкорпорации.

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

Анонс: https://llfp.hse.ru/announcements/1055523799.html

➰ ВК

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

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

16.06.2025, совместно с семинаром С.И. Адяна, И.А. Дынников (МИАН, https://www.mathnet.ru/person8990): Алгоритмическое сравнение лежандровых узлов (очный доклад)

Доклад основан на совместных работах с Максимом Прасоловым и Владимиром Шастиным. Мы разрабатываем подход к классификации узлов и зацеплений в трёхмерном пространстве, основанный на монотонном упрощении диаграмм специального вида (называемых прямоугольными). Это по сути означает описание множества всех "неупрощаемых" прямоугольных диаграмм, то есть диаграмм, которые невозможно упростить, применяя не увеличивающие сложность элементарные преобразования. Мы показали, что задача классификации неупрощаемых диаграмм в некотором смысле эквивалентна топологической классификации так называемых лежандровых зацеплений, не допускающих дестабилизации. Это, в свою очередь, позволило построить алгоритм, позволяющий проверять эквивалентность любых двух данных лежандровых зацеплений.

➰ ВК