Научно-учебный семинар "Логическая семантика"

Научно-учебный семинар посвящен схеме Скотта-Леммона, которая устанавливает соответствие между аксиомами и условиями ограничения на отношение достижимости. Несмотря на то, что существует ряд условий ограничения на отношение достижимости, которые не соответствуют никаким аксиомам, благодаря схеме Скотта-Леммона это удается сделать для аксиом общего вида:

◊^k□^lp → □^m◊ⁿp

Следующие несколько семинаров будут посвящены введению в структурную теорию доказательств. Мы рассмотрим базовые идеи альтернатив гильбертовскому аксиоматическому исчислению: естественной дедукции и исчисления секвенций. 
В этот раз мы начнем с естественной дедукции для логики высказываний: вспомним гильбертовскую аксиоматику для КЛВ, объясним мотивацию для построения альтернативных теорий доказательств, введем основные правила естественной дедукции. Если останется время, рассмотрим естественную дедукцию для логики предикатов первого порядка.

Доклад продолжает серию семинаров, которые посвящены введению в структурную теорию доказательств. Мы рассмотрим базовые идеи альтернатив гильбертовскому аксиоматическому исчислению: естественной дедукции и исчисления секвенций. 
В этот раз мы приступим к исчислению секвенций. Будут рассмотрены основные понятия и принципы классического исчисления секвенций.

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

Этот вводный семинар будет посвящен основам синтаксиса. Будет дан краткий обзор истории возникновения и развития генеративной грамматики, а также объяснены такие базовые понятия как составляющие, вершины и зависимые, аргументы и адъюнкты. Также на конкретных примерах мы посмотрим, какими критериями можно руководствоваться для определения вершин и выделения составляющих, а также как строить самые простые деревья зависимости (деревья составляющих).

Stit-логики (от англ. sees to it that) — семейство логик действия, предлагающих формальный анализ агентивов в рамках модальной логики: выражения о действиях предлагается переводить в синтаксические конструкции вида «агент i гарантирует, что ϕ», где «агент i гарантирует, что» понимается как модальность. Изначально stit-логики применялись исключительно в философских исследованиях агентности, способностей, действий, но в последние годы  эти формализмы иногда используют в области моделирования мульти-агентных систем и распределенных вычислений. Мы рассмотрим стандартные stit-логики, предложенные Белнэпом и соавторами, а также поговорим о современных модификациях и результатах по полноте и разрешимости некоторых фрагментов, если останется время.

На семинаре будут рассмотрены принципы работы экзистенциальных графов Ч. С. Пирса в подсистеме "Альфа". Диаграмматическая логика Пирса позволяет графически строить выводы для классической логики высказываний и теорий первого порядка. В ходе семинара мы разберем правила вывода для диаграмматической логики и потренируемся в доказательстве некоторых теорем логики высказываний.

Аннотация:
В мысленном эксперименте «Головоломка с токсином» у участника пари есть шанс выиграть миллион, если ему удастся сформировать намерение выпить яд, заранее зная, что его можно не пить. Грегори Кавка разбирает процесс создания намерения и приходит к выводу, что невозможно сформировать намерение действовать без достаточных оснований совершать это действие. Помимо обзора уже существующих решений головоломки с токсином, в докладе будет рассмотрены возможные способы её формализации (главным образом через BDI logics). Новизна подхода состоит в рассмотрении намерения как перформативного акта, который предполагает возможность радикального обновления агента, тем самым давая объяснение, почему получится выиграть пари в токсиновой головоломке: успешно сформировать намерение выпить пузырек с ядом, но избежать этого действия в будущем. 

Литература:
– Kavka G. S. The Toxin Puzzle. Analysis, 1983. pp. 33–36.
– Gauthier D. Assure and Threaten. Ethics, 1994. pp. 690–721
– Mele A. R. Intentions, Reasons, and Beliefs: Morals of the Toxin Puzzle. Philosophical Studies: An International Journal for Philosophy in the Analytic Tradition, 1992. pp. 171–194.

Головоломка с токсином (PDF, 191 Кб)

Аннотация:
Как и в IV в. до н.э., так и в XX веке н.э. логиков волновал вопрос: как нужно рассуждать, чтобы находить лучшее? Чтобы достичь этой цели, один исследователь использовал диалектические силлогизмы, другой - формальную модальную логику, то есть совершенно разные методы. Чем больше каждый из них пытался приблизиться к объективности, тем глубже понимал, насколько предпочтения укоренены в несовершенной повседневности и языке. В ходе доклада будет представлено, как логике, перфекционистичной в своем стремлении к строгости и чистоте, удалось найти компромисс с реальностью и не изменить себе в поисках истины.

Литература:
Аристотель. Сочинения: в 4-х т. Т. 2. Философское наследие. М.: Мысль, 1978. С. 394-403
Halldén S. Preference logic and theory choice. Synthese,1966. P. 307-320.

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

Литература:
Кэрролл, Л. Символическая логика, или Безупречная бессмыслица. М.: Лекстор, 2017.

Аннотация:
Сформулированная в 1983 году идея “Разрыва в объяснении” является до сих пор открытой проблемой, напрямую отражающей главный вопрос о сущности человеческого сознания. “Разрыв” возникает при попытке соотнести знание квалиа со знанием любой другой, “физической” информации. Тем самым возникает вопрос о природе ментального, а также, в некоторых случаях, ставится под сомнение идея о том, что действительный мир представлен единственной и полностью физической реальностью. Один из наиболее релевантных ответов на проблему “разрыва” заключается в объяснении его причин. В общем виде он утверждает некорректность самой постановки данной проблемы. В качестве доказательства философы стремятся обосновать независимость знания о квалиа от знания физических фактов. В ходе доклада будет предложено объяснение, почему такое доказательство не достигает поставленной цели, а значит, является “слабым”. Будет также предложен альтернативный метод, задействующий аппарат динамической эпистемической логики и основанный на натурализации категории знания.

Литература:
Butterworth G. Origins of Self-Perception in Infancy // Psychological Inquiry, 1992. ― Vol. 3. ― № 2. ― Pp. 103–111.
Chalmers D. Phenomenal Concepts and the Explanatory Gap. In: Phenomenal Concepts and Phenomenal Knowledge: New Essays on Consciousness and Physicalism // Oxford University Press, 2006. ― Pp. 167-195.
Gazzaniga M. Nature's Mind: The Biological Roots of Thinking, Emotions, Sexuality, Language and Intelligence // NY: BasicBooks, 1994. ― 240 p.

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

Литература:

Binmore, K. Game theory: A Very Short Introduction. Oxford University Press, 2013.
Данилов, В.И. Введение в теорию игр. М.: Российская экономическая школа, 2002.
Захаров, А. В. Теория игр в общественных науках. М.: Издательский дом Высшей школы экономики, 2015.

Формулировка задачи:

"Three gods A, R, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, R, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for "yes" and "no" are "dam and "ja," in some order. You do not know which word means which."

Boolos, G. (1996). The hardest logic puzzle ever. The Harvard Review of Philosophy, 6(1), 62. 

Формулировка задачи:

"A group of children has been playing outside and they are called back into the house by their father. The children gather round him. As one may imagine, some of them have become dirty from the play. In particular: they may have mud on their face. Children can only see whether other children are muddy, and not if there is any mud on their own face. All this is commonly known, and the children are, obviously, perfect logicians. Father now says: ‘‘At least one of you is muddy.’’ And then: ‘‘Will those who know whether they are muddy step forward.’’ If nobody steps forward, father keeps repeating the request. At some stage all muddy children will step forward. When will this happen if m out of k children in total are muddy, and why?"

Van Ditmarsch, H., & Kooi, B. (2015). One hundred prisoners and a light bulb, p. 21.

"Из колоды вынули 7 карт, показали всем, перетасовали и раздали Грише и Лёше по 3 карты, а оставшуюся карту
а) спрятали;
б) отдали Коле.
Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Лёша не договаривались о каком-либо особом способе общения; все переговоры происходят открытым текстом.)" (А. Шаповалов) 
Источник: Московская математическая олимпиада
 

"Группе из ста заключенных, которые вместе сидят в тюремной столовой, говорят, что онивсе будут помещены в изоляторы, а затем будут допрошены один за другим вкомнате с лампочкой, у которой будет выключатель. Заключенные могут общатьсядруг с другом, включая и выключая свет (и это единственный способ, которымони могут общаться). Свет изначально выключен. Фиксированного порядка допросов нет, и нет интервала между допросами, и тот же заключенный можетбыть допрошенным снова. При допросе заключенный может ничего не делатьили переключать выключатель света, или объявить, что все заключенные были допрошены. Если это объявление истинно, заключенные будут освобождены (все), ноесли это объявление будет ложным, они будут казнены. Могут ли заключенные, пока они находятся в столовой..., так договориться о протоколе, что они все будут освобождены?"

Van Ditmarsch, H., & Kooi, B. (2015). One hundred prisoners and a light bulb, p. 83.

Формулировка задачи:

«Аня и Борис слышат следующее: «Даны два натуральных числа. Это последовательные числа. Я собираюсь прошептать одно из этих чисел Ане, а другое - Борису.» Это происходит. Затем происходит следующий разговор:
• Аня: «Я не знаю номер Бориса.»
• Борис: «Я не знаю номер Ани».
• Аня: «Теперь я знаю твой номер.»
• Борис: «Тогда я знаю твой номер».
Назовите одно из двух чисел.»

А говорит S и P: «Я выбрал два таких целых числа x и y, что 1 < x < y и x+y ≤ 100. Сейчас я скажу S сумму, s = x + y. Затем я скажу P произведение этих двух чисел, p = xy. S не будет знать, что я скажу P, и P не будет знать, что я скажу S. Вам необходимо отгадать, каковы эти два числа». А сделал так, как сказал: сообщил числа. Дальше происходит следующий диалог S и P:

1.      P говорит: «Я не знаю, какие числа были загаданы».

2.      S говорит: «Я знал, что ты не знал, какие числа были загаданы».

3.      P говорит: «Теперь я знаю числа».

4.      S говорит: «Теперь и я тоже знаю числа».

Определите x и y.

"Задача формулируется, как описание игры в телевизионном шоу «Let’s Make a Deal» на одном из американских каналов. Ведущим этой передачи был Монти Холл, в честь которого и был назван этот парадокс. Наиболее распространённая формулировка этой задачи звучит так: «Допустим, некоему игроку предложили поучаствовать в известном американском телешоу Let’s Make a Deal, которое ведет Монти Холл, и ему необходимо выбрать одну из трех дверей. За двумя дверьми находятся козы, за одной – главный приз, автомобиль, ведущий знает расположение призов. После того, как игрок делает свой выбор, ведущий открывает одну из оставшихся дверей, за которой находится коза, и предлагает игроку изменить свое решение. Стоит ли игроку согласиться или лучше сохранить свой первоначальный выбор?"

(Воронцов, И.Д., Райцин, А.М. ПАРАДОКС МОНТИ ХОЛЛА (рус.) // Телекоммуникации и информационные технологии. — 2015. — № 2. — С. 5.) 

См. также: 
Van Ditmarsch, H., & Kooi, B. (2015). One hundred prisoners and a light bulb, p. 33-38.

Формулировка задачи:

"Однажды в воскресенье начальник тюрьмы вызвал преступника, приговорённого к казни, и сообщил ему:

• Вас казнят на следующей неделе в полдень.
• День казни станет для вас сюрпризом, вы узнаете о нём, только когда палач в полдень войдёт к вам в камеру.

Начальник тюрьмы был честнейшим человеком и никогда не врал.

Заключённый подумал над его словами и улыбнулся: «В воскресенье меня казнить не могут! Ведь тогда уже в субботу вечером я буду знать об этом. А, по словам начальника, я не буду знать день своей казни. Следовательно, последний возможный день моей казни — суббота. Но если меня не казнят в пятницу, то я буду заранее знать, что меня казнят в субботу, значит, и её можно исключить». Последовательно исключив пятницу, четверг, среду, вторник и понедельник, преступник пришёл к выводу, что начальник не сможет его казнить, выполнив все свои слова.

На следующей неделе палач постучал в его дверь в полдень в среду — это было для него полной неожиданностью. Всё, что начальник тюрьмы сказал, осуществилось. Где недостаток в рассуждении заключённого?"


См. также: 
Van Ditmarsch, H., & Kooi, B. (2015). One hundred prisoners and a light bulb, p. 13-19.

К семинару нужно прочитать: Mendelson E. Introduction to Mathematical
Logic. Section 2.15, pp. 135 - 139. Главное в этом фрагменте: правила
вывода на стр. 136 и примеры доказательства на стр. 137-139.

К семинару нужно прочитать: Fitting M., Mendelsohn R. First Order Modal
Logic. Sections 2.1, 2.2, pp. 46-51.

На первом семинаре будут даны предварительные пояснения по этому фрагменту.

Чтение: Fitting M., Mendelsohn R. First Order Modal Logic. Sections 5.1,
5.2, pp. 116-121.

На втором семинаре будут даны предварительные пояснения по этому фрагменту.

Методическое пособие "Язык, интерпретация, истина", раздел I ("Формальный язык") - понятие формулы.

Язык, интерпретация, истина (PDF, 710 Кб)