LectLog19 (Старые лекции, в целом тоже самое)
Описание файла
Файл "LectLog19" внутри архива находится в папке "Старые лекции, в целом тоже самое". PDF-файл из архива "Старые лекции, в целом тоже самое", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 19.Интуиционистская логика.Модальные логики.модальныелогикиy6интуиционистскаялогикаyI@yдругиелогическиеоперации@@другаятеориядоказательствсемантика@логических@связок@другиеформылогическоговывода@@yдругие кванторылогикивысших порядков@iспециальные интерпретации-КЛАССИЧЕСКАЯЛОГИКАyаксиоматическиетеорииИНТУИЦИОНИСТСКАЯ ЛОГИКАИнтуиционизм — это философское течение в математике,возникшее в начале 20 века как критический отклик нанеограниченное применение формальных логических методов вматематике, приводящее к парадоксам (антиномиям).По мнению интуиционистов (Брауэр, Вейль, Пуанкаре),парадоксы возникают в связи с тем, что законы логики,справедливые для конечных множеств, безосновательнопереносятся на бесконечные множества.Не все математические утверждения, верные для конечныхмножеств, остаются справедливыми и для бесконечныхмножеств. Например, для конечных множеств верен принципАрхимеда «Часть всегда меньше целого», а длябесконечных множеств — нет.Вполне возможно, что не все законы классической(аристотелевой) логики допускают неограниченное ибезоговорочное использование в математике.ИНТУИЦИОНИСТСКАЯ ЛОГИКАНапример, рассмотрим одну широко распространенную схемудоказательства.Доказать: Если выполнены условия A, то ∃x P(x).Схема доказательства: Предположим противное, т.
е. ∀x ¬P(x).Тогда ...(фа-фа, ля-ля)..., что противоречит условиям A.Значит, предположение ∀x ¬P(x) неверно, и поэтому ∃x P(x).QEDВсе хорошо, но где же та x, для которой верно P(x)?Из такого доказательства это значение извлечь невозможно.Но тогда, по мнению интуиционистов, это не доказательство, асловоблудие.Чтобы исключить доказательства такого рода, нужнопересмотреть семантику логических связок и кванторов.ИНТУИЦИОНИСТСКАЯ ЛОГИКАСемантика Колмогорова–Брауэра–ГейтингаПопробуем взглянуть на логические формулы как наутверждения о разрешимости математических задач.Каждая атомарная формула A будет обозначать некоторуюзадачу. Истинность A будет означает, что задача имеетрешение, и это решение можно предъявить.
Ложность A будетозначать, что задача решения не имеет.Логические связки позволяют конструировать из простыхзадач составные задачи.Оценим, как (не)разрешимость составных задач зависит от(не)разрешимости простых задач.ИНТУИЦИОНИСТСКАЯ ЛОГИКАСемантика Колмогорова–Брауэра–Гейтингаϕ&ψ:Решить обе задачи ϕ и ψ и предъявить решение;ϕ ∨ ψ:Выбрать одну из двух задач ϕ и ψ, решить выбранную задачу и предъявить решение;ϕ → ψ:Показать, что решение задачи ψ сводится к решению задачи ϕ, т. е.
предъявить способ, который позволяет, располагая решением задачи ϕ,построить решение задачи ψ;¬ϕ:Доказать, что задача ϕ не имеет решения.Законами интуиционистской логики считаются только теформулы, которые соответствуют описаниям составных задач,имеющих решение при любых условиях.ИНТУИЦИОНИСТСКАЯ ЛОГИКАЗаконы интуиционистской логикиIP → P — каждую задачу можно свести к ней самой;I(P → Q)&(Q → R) → (P → R) — чтобы свести задача Rк задаче P достаточно найти задачу Q, к которой можносвести задачу R, и которую, в свою очередь, можно свестик задаче P;IP → ¬¬P — чтобы убедиться в том, что не существуетдоказательства неразрешимости задачи P, достаточнонайти решение задачи P;I(¬P ∨ ¬Q) → ¬(P&Q) — чтобы показать, что обе задачиP и Q нельзя решить одновременно, достаточно выбратьодну из этих задач и показать, что она неразрешима.ИНТУИЦИОНИСТСКАЯ ЛОГИКАФормулы, не являющиеся законамиинтуиционистской логикиI¬¬P → P — если вы можете обосновать, что нельзяпостроить доказательства неразрешимости задачи P, тоэтого еще недостаточно, чтобы получить решение самойзадачи P;IP ∨ ¬P — неправда, что для любой задачи можно либополучить решение, либо доказать, что никакого решенияне существует;I¬(P&Q) → (¬P ∨ ¬Q) — если можно доказать, что обезадачи P и Q нельзя решить одновременно, то это не даетоснования считать, что хотя бы одна из них являетсянеразрешимой.Да как же это так?Уж не скрывается ли здесь простая игра слов?ИНТУИЦИОНИСТСКАЯ ЛОГИКАПопробуем строго определить семантику утверждений,касающихся разрешимости задач.Истинность формул оценивается в интерпретациях.
Посколькузадачи решают люди, в качестве интерпретаций могутвыступать способности людей решать задачи.Но эти способности у людей со временем изменяются. Значит,интерпретации должны быть динамическими .Рассмотрим модель идеального математика (DutchMathematician), которыйIможет пребывать в разных состояниях знания ипереходить из одних состояний знания в другие;Iв каждом состоянии знания он точно знает, какие изэлементарных задач он умеет решать, а какие нет;Iне утрачивает навыков в решении задач при переходе изодного состояния знания в другое.ИНТУИЦИОНИСТСКАЯ ЛОГИКАОпределение (модель Крипке)Пусть P = {P1 , P2 , . .
. , Pn , . . . } — множество атомарныхформул (названия задач).Интуиционистская интерпретация — это реляционная системаI = hS, R, ξi, в которой1. S 6= ∅ — множество состояний (состояний знания);2. R ⊆ S × S — отношение переходов на S, которое являетсяотношением нестрогого частичного порядка:рефлексивноеR(s, s);транзитивноеR(s1 , s2 )&R(s2 , s3 ) ⇒ R(s1 , s3 );антисимметричное R(s1 , s2 )&R(s2 , s1 ) ⇒ s1 = s2 ;3. ξ : S × P → {true, false} — оценка атомарных формул,удовлетворяющая условию монотонности:R(s1 , s2 )&ξ(P, s1 ) = true ⇒ ξ(P, s2 ) = true.ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации?ys1@@?s2y?s4y@?Rs@3 y @@@@@?Rs@6 y @@?s5yИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации?s4yP = false?утро ys1 Q = false@@@@@??Rs2s@y3 y @@@@@??s5Rs@y6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретацииP = false?ys1 Q = false@@@@P = false@??Rs2 Q = falseфирма PROGys@3 y @@@@@???s4s5Rs@yy6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретацииP = false?ys1 Q = false@@@@P = false@??Rs2 Q = falses@y3 y @@@@P = false@???s4 Q = trues5Rs@yy6 y экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретацииP = false?ys1 Q = false@@@@P = false P = true @?? лекцияRs2 Q = false Q = false s@y3 y @@@@P = false@???s4 Q = trues5Rs@yy6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретацииP = false?ys1 Q = false@@@@P = false P = true @??Rs2 Q = false Q = false s@y3 y @@@@P = falseP = true@???s4 Q = trues5RQ = falseys@y6 y экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретацииP = false?ys1 Q = false@@@@P = false P = true @??Rs2 Q = false Q = false s@y3 y @@@@P = falseP = trueP = true @???s4 Q = trues5RQ = falseQ = true s@yy6 y экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретацииP = false?ys1 Q = false@@@@P = false P = true @??Rs2 Q = false Q = false s@y3 y @@@@P = falseP = trueP = true @???s4 Q = trues5RQ = falseQ = true s@yy6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАОпределение (семантика Крипке)Пусть I = hS, R, ξi — интуиционистская интерпретация.
Тогдаотношение выполнимости I , s |=I ϕ формулы ϕ в состоянии sинтерпретации I определяется так:1. если ϕ = P ∈ P, то I , s |=I ϕ ⇐⇒ ξ(s, P) = true;2. I , s |=I ϕ1 &ϕ2 ⇐⇒ I , s |=I ϕ1 и I , s |=I ϕ2 ;3. I , s |=I ϕ1 ∨ ϕ2 ⇐⇒ I , s |=I ϕ1 или I , s |=I ϕ2 ;4. I , s |=I ϕ1 → ϕ2 ⇐⇒ для любого состояния s 0 , если(s, s 0 ) ∈ R и I , s 0 |=I ϕ1 , то I , s 0 |=I ϕ2 ;5. I , s |=I ¬ϕ1 ⇐⇒ для любого состояния s 0 , если(s, s 0 ) ∈ R, то I , s 0 6|=I ϕ1 .Формула ϕ называется интуиционистски общезначимой(законом интуиционистской логики), если для любойинтерпретации I и для любого состояния s верно I , s |=I ϕ.ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример необщезначимой формулы6|=I P ∨ ¬Pдискотека? P = falseys1 ¬P = falseвечер@ P ∨ ¬P = false@@@P = false P = true @?? библиотекаs2 ¬P = true ¬P = false s@Ry3 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАДругие необщезначимые формулыДокажите самостоятельно, выбрав подходящую интерпретацию(контрмодель) I ,6|=I ¬¬P → P6|=I ¬(P&Q) → (¬P ∨ ¬Q)6|=I ¬(P ∨ Q) → (¬P&¬Q)ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример общезначимой формулы|=I P → ¬¬PОт противного.
Допустим, что I , s0 6|= P → ¬¬P. ТогдаP = true?¬¬P = falseys0¬P = trueP = falseP = true?ys1?ys2Полученное противоречие свидетельствует о невозможностипостроения контрмодели для формулы P → ¬¬P.ИНТУИЦИОНИСТСКАЯ ЛОГИКАДругие общезначимые формулыДокажите самостоятельно интуиционистскую общезначимостьследующих формул|=I ¬¬¬P → ¬P|=I (¬P ∨ ¬Q) → ¬(P&Q)|=I ¬P ∨ ¬¬PИНТУИЦИОНИСТСКАЯ ЛОГИКАНекоторые особенности интуиционистской логикиТеорема 1|=I ϕ =⇒ |=C ϕТеорема 2 (дизъюнктивное свойство)|=I ϕ ∨ ψ ⇐⇒ |=I ϕ или |=I ψТеорема 3 (экзистенциальное свойство)|=I ∀x1 . . . ∀x1 ∃y ϕ(x1 , . .