[2026前期火５] 論理学（京都大学文学部 前期 第5回）「 ならばの問題演習・proof net・かつの規則」

科学哲学科学史 (演習) 前期 第5回　論理学　（京都大学文学部・矢田部俊介）
「 ならばの問題演習・proof net・かつの規則」
2026年5月19日（火）1645〜1815（予定）

Transcript

1. Պֶ఩ֶՊֶ࢙ (ԋश) લظ ୈ 5 ճ ࿦ཧֶ ͳΒ͹ͷ໰୊ԋशɾproof netɾ͔ͭͷنଇ → ͷূ໌ԋशɾূ໌ωοτͷಡΈํɾ∧ ೖ໳ 2026 ೥ 5 ݄ 19 ೔ʢՐʣ16:45–18:15 จֶ෦ୈ 4 ߨٛࣨ ୲౰ɿ໼ా෦ढ़հʢ੢೔ຊཱྀ٬మಓגࣜձࣾʣ yatabe.shunsuke.24n@st.kyoto-u.ac.jp
2. ຊ೔ͷϝχϡʔ 0. ࿦ཧࣜͷུهنଇͱ൱ఆͷఆٛʢલճͷิ଍ʣ 1. લճͷ॓୊ղ౴ 2. ͳΒ͹ͷ໰୊ԋश 3. proof netɿݟํͱඳ͖ํ 4. ∧ʢ͔ͭʣͷنଇ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 2
3. ຊतۀ͸੢೔ຊཱྀ٬మಓגࣜձࣾͷۀ຿ͱ࣮ͯ͠ࢪ͍ͯ͠·͢ ੢೔ຊཱྀ٬మಓ͸ LLM ͷ׆༻Λਪਐ͍ͯ͠·͢ɻ
4. 0. ࿦ཧࣜͷུهنଇͱ൱ఆͷఆٛʢલճͷิ଍ʣ
5. →-ಋೖنଇʢ→Iʣ ఆٛ [u : A] . . . B →+u A → B ಡΈํɿA ΛԾఆͯ͠ B ͕ূ໌Ͱ͖ͨͱ͖ɺ A → B ͕ূ໌͞ΕΔ ԾఆͷΩϟϯηϧʢdischargeʣ [u : A]ɿԾఆ A ʹϥϕϧ u ΛషΓɺ ࢖͍ऴΘͬͨ͜ͱΛએݴ͢Δ ϥϕϧ͸೚ҙʢu, v, w, . . . ͳͲʣ ଞͷϥϕϧͱࠞಉ͠ͳ͚Ε͹Α͍ ࠷΋୹͍ྫɿA → A ͷূ໌ [u : A] →+u A → A Ծఆ A ͔Β A ͕ʢࣗ໌ʹʣಘΒΕΔ ˠ →I Ͱ A → A Λߏ੒ ূ໌໦ͷߏ଄ ઌ୺ʢ༿ʣɿԾఆʢΩϟϯηϧલʣ ֤εςοϓɿنଇͷҰճద༻ ࠜʢ຤୺ʣɿূ໌͞Εͨ݁࿦ Ωϟϯηϧ͢ΔԾఆ͕ͳ͘ͳͬͨΒূ໌׬ྃ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 5
6. →-আڈنଇʢ→Eɺmodus ponensʣ ఆٛ A A → B →− B ಡΈํɿA ͱ A → B ͕͋Ε͹ B ͕ಘΒΕΔ ओͳԾఆɿ→ ΛؚΉଆʢA → Bʣ ෭࣍తͳԾఆɿؚ·ͳ͍ଆʢAʣ modus ponens ݹ͔͘Β modus ponensʢલ݅ߠఆʣͱݺ͹ΕΔ ࿦ཧ๏ଇͷ୅දྫͷͻͱͭ ʮA ͳΒ͹ BʯͱʮAʯ͔ΒʮBʯ →I ͱ →E ͷରൺ ໾ׂ → ͷಈ͖ →I ߏ੒ → Λ࡞Δ →E ղମ → ΛऔΓআ͘ ϋʔϞχʔͷ৚݅ʢ௚ײʣ →E ͰऔΓग़ͤΔͷ͸ →I ͰೖΕͨ಺༰͚ͩ ˠ نଇ͕ʮ௼Γ߹͍ͬͯΔʯঢ়ଶ ࠷খ໋୊࿦ཧͷ → அย →I ͱ →E ͚ͩΛ࣋ͭମܥ ˠ ࠷খ໋୊࿦ཧͷ → அย ࠓ೔ͷԋशͱ॓୊͸͜ͷମܥͷதͰߦ͏ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 6
7. ͖Ε͍ͳূ໌ͷॻ͖ํŠŠʮ࠷ޙͷ݁߹ࢠʯ͔Βٯࢉ͢Δ ٯࢉͷखॱ Step 1ɿূ໌໋͍ͨ͠୊ͷ ʮ࠷ޙʹಋೖ͞Εͨ݁߹ࢠʯΛಛఆ Step 2ɿͦͷ௚લͷ໋୊ͷ ܗΛ֬ఆ͢Δ Step 3ɿStep 2 Λ܁Γฦͯ͠ Ծఆ·Ͱ૎Δ Step 4ɿআڈنଇͰ Ծఆ͔Β݁࿦Λ૊ΈཱͯΔ ͖Ε͍ͳূ໌ʢਖ਼نͳূ໌ʣ ճΓಓͷͳ͍ূ໌ ʮಋೖ͙ͯ͢͠আڈ͢Δʯ ແବͳεςοϓ͕ͳ͍ ˠ ෦෼࿦ཧࣜݪཧΛຬͨ͢ ྫɿA → (B → A) ͷٯࢉ ࠷ޙͷ݁߹ࢠɿ֎ଆͷ →ʢA ͱ B → Aʣ ˠ Ծఆ [u : A] ͔Β B → A Λূ໌ ࣍ͷ݁߹ࢠɿ಺ଆͷ →ʢB ͱ Aʣ ˠ Ծఆ [v : B] ͔Β A Λূ໌ A ͸طʹԾఆʹ͋Δ ˠ ׬੒ʂ [u : A] →+v B → A →+u A → (B → A) ʢ[v : B] ͸࢖ΘΕͳ͍ŠŠऑԽଇʣ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 7
8. લճͷ࿦఺੔ཧɿׅހʹؔ͢Δ4ͭͷٞ࿦ ࿦఺ ಺༰ ݁࿦ 1 ݪࢠ໋୊ʹׅހΛ͚ͭͨ΋ͷ ʢྫɿ(Z=S(¯ 0))ʣ͸ WFF ͔ WFF Ͱͳ͍ŠŠఆٛʹॻ͍͍ͯͳ͍ ✓ ίϯύΠϥΤϥʔʹ૬౰ɻֶੜͷࢦఠ͸׬શʹਖ਼͔ͬ͠ ͨɻ 2 ʮA ͕จͳΒ (A) ΋จʯͱ͍͏ن ଇΛೖΕͨΒͲ͏ͳΔ͔ A, (A), ((A)), . . . ͱແݶʹॏෳൃੜ ˠ ࠾༻͠ͳ͍ɻ݁߹ࢺ࢖༻࣌͸࠷ॳ͔ΒׅހࠐΈͰ ఆٛɻ 3 ʮ࿦ཧ݁߹ࢺͷ಺ଆʹׅހΛ෇͚ Δʯͱ͍͏ֶੜఏҊ ਖ਼ࣜʹ͸ (A) ∧ (B) ͱॻ͘ඞཁ͕͋Δɻ ུهͱͯ͠ A ∧ B ͱॻ͘͜ͱΛೝΊΔʢࠓޙͷදه ن໿ʣ ɻ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 8
9. ׅހͷলུنଇɿӈ݁߹ͱ༏ઌॱҐ نଇ 1ɿ→ ͸ӈ݁߹ʢright-associativeʣ ׅހͷͳ͍ → ͷ࿈࠯͸ӈ͔Β݁߹͢Δ A → B → C ≡ A → (B → C) A → B → C → D ≡ A → (B → (C → D)) ஫ҙɿ(A → B) → C ͸লུෆՄ ׅހΛ֎͢ͱҙຯ͕มΘΔ نଇ 2ɿ݁߹ࢠͷ༏ઌॱҐʢڧ͍ॱʣ ڧ ¬ʢ൱ఆʣ ∧ʢ͔ͭʣ ∨ʢ·ͨ͸ʣ ऑ →ʢͳΒ͹ʣ ࠓޙͷදهن໿ʢ֬ఆʣ ུهͱͯ͠ A ∧ Bʢਖ਼ࣜʹ͸ (A) ∧ (B)ʣͱॻ͘͜ͱΛೝΊΔɻ্ه 2 نଇͷൣғ ͰׅހΛলུ͢ΔɻͦΕҎ֎͸ׅހΛ໌ࣔ͢Δɻ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 9
10. ࿅शɿলུ͞ΕׅͨހΛ͢΂ͯॻ͖ೖΕΑ ໰୊ʢA, B, C ͸೚ҙͷ໋୊ه߸ʣ 1. A → A → B 2. (A → A → B) → A → B 3. A → B → A ∧ B ղ౴ 1. A → (A → B) → ͸ӈ݁߹ͳͷͰӈ͔ΒׅހΛ෇͚Δ 2. ( (A → (A → B)) → (A → B) ) ·ͣ A → A → B Λ A → (A → B) ʹల։ɺ࣍ʹશମͷओ݁߹ࢺ → ΛׅހͰғΉ 3. A → ( B → (A ∧ B) ) Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 10
11. ൱ఆͷఆٛɿ¬A = A → ⊥ ⊥ʢϘτϜʣͷಋೖ ⊥ ͸ಛघͳ໋୊ه߸ ௨ৗͷݪࢠ໋୊ p, q, r, . . . ͱ͸ผʹɺܗࣜݴ ޠͷఆٛʹ໌ࣔతʹ௥Ճ͢Δ ໋୊ʢจʣͷؼೲతఆٛʢվగ൛ʣ (1) t1 = t2 ʢt1 , t2 ͸߲ʣ͸จ (1’) ⊥ ͸จʢಛघ໋୊ه߸ʣ (2) A, B ͕จ ⇒ (A ∧ B) ͸จ (3) A, B ͕จ ⇒ (A → B) ͸จ (4) A, B ͕จ ⇒ (A ∨ B) ͸จ (5) ্هҎ֎͸จͰͳ͍ ¬A ͷఆٛ ¬A ͸ A → ⊥ ͷུه ¬A := A → ⊥ ¬¬A := (A → ⊥) → ⊥ ʮA ΛԾఆ͢Δͱໃ६͢Δʯ = A ͔Β ⊥ ͕ূ໌Ͱ͖Δɺ ͱ͍͏ҙຯʹͳΔʢޙͰʣ ݱ࣌఺Ͱͷ஫ҙ ⊥ ʹର͢Δਪ࿦نଇ͸༩͑ͳ͍ ⊥ Λ݁࿦ͱͯ͠ಋग़͢Δنଇ΋ɺ⊥ Λ લఏͱͯ͠࢖͏نଇ΋ࠓճ͸ಋೖ͠ͳ͍ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 11
12. 1. લճͷ॓୊ղ౴
13. ॓୊໰୊ͷ࠶ܝ Ұൠ໰୊ʢA, B, C ͸೚ҙͷ໋୊ʣ ͖Ε͍ͳূ໌Ͱࣔ͠ɺͦͷޙ proof net Λඳ͚ɻূ໌Ͱ͖ͳ͍৔߹͸ʮূ໌ෆՄೳʯͱ ໌ه͢Δ͜ͱɻ (1) (A → A → B) → (A → B) ώϯτɿಉ͡Ծఆ A Λ 2 ճ࢖ͬͯΑ͍ʢॖ໿ଇʣ (2) A → (B → C) → (A → B) → C ώϯτɿԾఆΛઌʹܾΊ͔ͯΒʮٯࢉʯΛ࢝ΊΑ νϟϨϯδ໰୊ ҎԼͷূ໌໦Λ proof net ʹม׵ͤΑɻ [u:A → B] [w:A] →− B [v:B → C] →− C →+w A → C →+v (B → C) → (A → C) →+u (A → B) → (B → C) → (A → C) Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 13
14. 2. ͳΒ͹ͷ໰୊ԋश
15. ԋश໰୊Ұཡ ໰୊ʢA, B, C ͸೚ҙͷ໋୊ɻ¬A ͸ A → ⊥ ͷུهʣ ՄೳͳݶΓ͖Ε͍ͳূ໌Ͱূ໌ͤΑɻূ໌Ͱ͖ͳ͍৔߹͸ʮূ໌ෆՄೳʯͱ໌ه͢Δ ͜ͱɻ ໰ ໋୊ ϙΠϯτ ໰ 1 A → ((A → B) → A) ऑԽͷయܕ ໰ 2 A → (A → B → C) → B → C ࡾͭͷԾఆͷ૊Έ߹Θͤ ໰ 3 A → ¬¬A ¬ Λల։ͯ͠ߟ͑Δ ໰ 4 ¬¬¬A → ¬A ໰ 3 ͷԠ༻ Extra (A → B → C) → (A → B) → A → C S ίϯϏωʔλʢ4 Ծఆʂʣ ࡞ઓɿٯࢉʢτοϓμ΢ϯʣͰߟ͑Α ূ໌໋͍ͨ͠୊ͷ࠷ޙͷ → ʹ஫໨͠ɺͦͷલͷஈ֊ͰԿΛࣔͤ͹Α͍͔Λ্޲͖ʹٯ ࢉ͢Δɻ໰ 3ɾ໰ 4 Ͱ͸·ͣ ¬ Λల։͔ͯ͠ΒٯࢉΛ࢝ΊΔ͜ͱɻ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 15
16. ূ໌໦ͷߏ଄ʢ1ʣ ɿ༿ɾװɾࠜ [u:A → B → C] [w:A] →− B → C [v:A → B] [w:A] →− B →− C →+w A → C →+v (A → B) → A → C →+u (A → B → C) → (A → B) → A → C લఏ u ొ৔ લఏ w ొ৔ લఏ v ొ৔ લఏ w ࠶ొ৔ ʮূ໌໦ʯ (Proof Tree) Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 16
17. ূ໌໦ͷߏ଄ʢ2ʣ ɿओࢬͱैଐԋ៷ [u:A → B → C] [w:A] →− B → C [v:A → B] [w:A] →− B →− C →+w A → C →+v (A → B) → A → C →+u (A → B → C) → (A → B) → A → C લఏ u ొ৔ લఏ w ొ৔ લఏ v ొ৔ લఏ w ࠶ొ৔ ʮओࢬʯ (Main Stem) ʮैଐ ԋ៷ʯ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 17
18. ূ໌໦ͷߏ଄ʢ3ʣ ɿ෼ੳత෦෼ͱ૯߹෦෼ [u:A → B → C] [w:A] →− B → C [v:A → B] [w:A] →− B →− C →+w A → C →+v (A → B) → A → C →+u (A → B → C) → (A → B) → A → C ෼ੳత෦ ෼ ࠷খ෦ ෼ ૯߹෦ ෼ আڈن ଇ ಋೖن ଇ ͖Ε͍ͳূ໌ʹ෼ੳʢআڈʣ্͕ɺ૯߹ʢಋೖʣ ͕ԼͷҰํ޲ߏ଄ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 18
19. 3. proof netɿݟํͱඳ͖ํ
20. ূ໌ਤͷதʹજΉߏ଄ proof net ͱ͸ ূ໌ਤͱ proof net ͸ผ෺Ͱ͸ͳ͍ proof net ͸ɺূ໌ਤͷதʹ͢ͰʹજΜͰ͍Δ ߏ଄ΛऔΓग़ͨ͠΋ͷ ূ໌ਤͷ໋֤୊ʹؙΛ෇͚ɺ ʮͲͷ໋୊͔ΒͲ ͷ໋୊΁৘ใ͕ྲྀΕΔ͔ʯΛ໼ҹͰࣔ͢ˠ proof net ͕ݱΕΔ ূ໌ਤ → proof net ͷखॱ ᶃ ূ໌ਤͷ໋֤୊ʹؙΛ෇͚Δ ᶄ ਪ࿦نଇΛʮശʢϊʔυʣ ʯʹ͢Δ ᶅ ໋୊ͷྲྀΕΛʮઢʢϫΠϠʣ ʯʹ͢Δ ᶆ Ωϟϯηϧ͞ΕͨԾఆ͸఺ઢʹ ରԠද ূ໌ਤ proof net ໋୊ʢࣜʣ ϫΠϠʢઢʣ ਪ࿦نଇ ϊʔυʢശʣ ։͍ͨԾఆ ஦ͿΒΓΜͷϫΠϠ ΩϟϯηϧԾఆ ఺ઢϫΠϠ ࢖ΘΕͳ͍Ծఆ dangling wire ʢऑԽʣ ʢΦϨϯδ఺ઢʣ proof net ͸ূ໌ਤ͔ΒԿ͔৽͍͠΋ͷΛ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 20
21. →-আڈنଇͷ proof netɿ2ೖྗ1ग़ྗͷϊʔυ ূ໌ਤ A → B A →− B A → B ͱ A ͱ͍͏ 2 ͭͷલఏ͔Β B Λ݁࿦͢Δ ରԠؔ܎ A → B ˠ ࠨͷϫΠϠ A ˠ ӈͷϫΠϠ →E ͷنଇ ˠ ϊʔυʢശʣ B ˠ ग़ྗϫΠϠ proof net A → B A →E B 2 ຊͷ࣮ઢϫΠϠ͕ೖྗ 1 ຊͷ࣮ઢϫΠϠ͕ग़ྗ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 21
22. →-ಋೖنଇͷ proof netɿ఺ઢϫΠϠͷొ৔ ূ໌ਤ [u:A] . . . B →+u A → B Ծఆ [u:A] ΛΩϟϯηϧʢdischargeʣ͠ ͯ A → B Λ݁࿦͢Δ ରԠؔ܎ [u:A]ʢΩϟϯηϧԾఆʣˠ ఺ઢϫΠϠ Bʢূ໌ͷ݁࿦ʣˠ ࣮ઢϫΠϠʢೖྗʣ →I[u] ˠ ϊʔυʢശʣ proof net [u:A] B →I[u] A → B ׅހॻ͖ [u:A] ͕ proof net Ͱ͸఺ઢϫΠϠͱͯ͠ՄࢹԽ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 22
23. ྫɿA → A ͷ proof netŠŠ࠷΋γϯϓϧͳ proof net ূ໌໦ [u:A] →+u A → A Ծఆ [u:A] Λͦͷ··Ωϟϯηϧ͠ ͯ A → A ΛಘΔ proof net [u:A] →I[u] A → A ϫΠϠ͕ 2 ຊ͚ͩʢ఺ઢ 1 ຊʴ࣮ઢ 1 ຊʣ ໋୊͕ A → A ͷҰछྨ͔͠ొ৔͠ͳ͍͜ ͱ͕Ұ໨ྎવ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 23
24. ྫɿA → (B → A) ͷ proof netŠŠऑԽଇͷՄࢹԽ ূ໌໦ [u:A] →+v B → A →+u A → B → A [v:B] Λಋೖ͕ͨ͠Ұ౓΋࢖Θͣ Ωϟϯηϧ ˠ ऑԽଇͷ࢖༻ proof net [u:A] [v:B] →I[v] B → A →I[u] A → B → A [v:B] ͷϫΠϠ͕஦ͿΒΓΜʢdangling Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 24
25. ॖ໿ଇͱYࣈϊʔυŠŠ proof net ͷʮ೉఺ʯͷՄࢹԽ ॖ໿ଇͱ͸ ಉ͡ϥϕϧͷԾఆΛෳ਺ՕॴͰ࢖͍ɺҰว ʹΩϟϯηϧ͢Δنଇ ྫɿ॓୊ (1) (A → A → B) → (A → B) ͷ ূ໌Ͱ [v:A] ͕ 2 Օॴʹग़ݱͨ͠ proof net ͰͷදݱɿY ࣈϊʔυ Ծఆ [v:A] ͷϫΠϠ్͕தͰೋވʹ෼ذ [v:A] branch 1branch 2 Y ࣈϊʔυͷূ໌࿦తҙຯ Y ࣈͳ͠ʢΞϑΟϯ࿦ཧʣ ˠ Χοτআڈ͕ہॴతॻ͖׵͚͑ͩͰ ׬݁ ˠ ূ໌ͷਖ਼نԽ͕៉ྷʹऴΘΔ Y ࣈ͋Γʢ࠷খ໋୊࿦ཧʣ ˠ ΧοτআڈͰ Y ࣈΛ௨ա͢Δͱ͖ূ ໌ͷҰ෦͕ෳ੡͞ΕΔ ˠ ෳ੡ʹ·ͨ Y ࣈ͕͋Ε͹͞Βʹ ෳ੡ʜʜ ˠ ऴྃੑͷূ໌ʹ ε0 ʢ௒ݶؼೲ๏ʣ͕ ඞཁ ʮূ໌࿦త೉఺ʯͷՄࢹԽ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 25
26. νϟϨϯδͷ proof net ΛվΊͯಡΉ proof net ͷಡΈํνΣοΫϦετ ᶃ ϫΠϠͷຊ਺Λ਺͑Δ ˠ Ծఆͷݸ਺ͱҰக͢Δ͔ʁ ᶄ ఺ઢϫΠϠΛ֬ೝ ˠ Ωϟϯηϧ͞ΕͨԾఆͷ਺ ᶅ dangling wire ͕͋Δ͔ʁ ˠ ͋Ε͹ऑԽଇΛ࢖͍ͬͯΔ ᶆ Y ࣈϊʔυ͕͋Δ͔ʁ ˠ ͋Ε͹ॖ໿ଇΛ࢖͍ͬͯΔ ᶇ ग़ྗϫΠϠͷϥϕϧ͸ূ໌໋͍ͨ͠ ୊͔ʁ νϟϨϯδͷ proof net ͷ֬ೝ [u:A → B] [w:A] [v:B → C] →E B →E C →I[w] A → C →I[v] (B → C) → (A → C) Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 26
27. 4. ∧ʢ͔ͭʣͷنଇ
29. ∧ʢ͔ͭʣͷಋೖنଇͱআڈنଇ ϝλϨϕϧͷʮ͔ͭʯͷྫ ௚֯ࡾ֯ܗ △ABCʢ∠A = 90◦ʣ ಋೖɿ ∠B = 45◦ ͕੒ཱ͠ɺ ∠C = 45◦ ͕੒ཱ͢Δͱ͖ɺ ʮ∠B = 45◦ ͔ͭ ∠C = 45◦ʯͱݴ͏ আڈɿ ʮ∠B = 45◦ ͔ͭ ∠C = 45◦ʯ͔Β ∠B = 45◦ ͚ͩΛऔΓग़ͤΔʢࠨআڈʣ ∠C = 45◦ ͚ͩΛऔΓग़ͤΔʢӈআڈʣ ∧ ͷಋೖنଇͱআڈنଇ ಋೖنଇɿ A B ∧+ A ∧ B আڈنଇʢུه൛ʣɿ A ∧ B ∧−ࠨ A A ∧ B ∧−ӈ B ∧ ͸ʮ,ʢίϯϚʣ ʯͱಉ͡ಇ͖Λ͢Δ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 29
30. ∧ ͷূ໌ྫ ྫ 1ɿA → B → A ∧ B [u:A] [v:B] ∧+ A ∧ B →+v B → A ∧ B →+u A → B → A ∧ B A ͱ B ΛԾఆͯ͠ A ∧ B Λߏ੒ ˠ ∧-ಋೖنଇͷయܕత࢖༻ ྫ 2ɿA ∧ B → A [u:A ∧ B] ∧−ࠨ A →+u A ∧ B → A A ∧ B Λ෼ղͯ͠ A ΛऔΓग़͢ ˠ ∧-আڈنଇʢࠨʣͷయܕత࢖༻ ಉ༷ʹ A ∧ B → B ΋ূ໌Ͱ͖Δʢআڈن ଇʮӈʯΛ࢖͏ʣ ∧ ͷੑ࣭ ্ͷྫΛ߹ΘͤΔͱɿA ∧ B ΛԾఆ͢Δ͜ͱͱɺA ͓Αͼ B ΛԾఆ͢Δ͜ͱ͸ಉ஋ ˠ A ∧ B ͸ʮA, BʯͷུهͰ͋Γɺ∧ ͸·͘͞͠ʮ,ʢίϯϚʣ ʯͷུه Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 30
31. ·ͱΊͱ࣍ճ༧ࠂ ࠓ೔ͷϙΠϯτ 0. ུهنଇɾ൱ఆͷఆٛ → ͸ӈ݁߹ɺ༏ઌॱҐ ¬> ∧ > ∨ > → ¬A := A → ⊥ʢ⊥ ͸ಛघ໋୊ه߸ʣ 1. ॓୊ղ౴ ॖ໿ଇ ˠ Y ࣈϊʔυ ͖Ε͍ͳূ໌ ˠ Y ࣈͳ͠ɾdangling wire ͳ͠ 2. ͳΒ͹ͷԋश ¬ Λల։ͯ͠ → ͚ͩͰߟ͑Δ ໰ 3ɿA → ¬¬Aɺ໰ 4ɿ¬¬¬A → ¬A 3. proof net ͷಡΈํ ূ໌ਤͷʮ໋୊ͷྲྀΕʯͷՄࢹԽ ࣍ճʢୈ 6 ճɿ5 ݄ 26 ೔ʣͷ༧ఆ ∨ʢ·ͨ͸ʣͷنଇ ಋೖنଇɾআڈنଇ proof net Ͱͷදݱ ∧, ∨, → ͷ໰୊ԋश ࠷খ໋୊࿦ཧͷ·ͱΊ ಋೖɾআڈنଇͷҰཡ ͖Ε͍ͳূ໌ͱ෦෼࿦ཧࣜݪཧ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 31
32. ॓୊ʢ࣍ճतۀ։࢝લʹKULMS΁ఏग़ʣ ຊ೔ͷԋश໰୊Ͱղ͚ͳ͔ͬͨ΋ͷΛఏग़ͤΑ A, B, C ͸೚ҙͷ໋୊ɻ¬A ͸ A → ⊥ ͷུهɻ ՄೳͳݶΓ͖Ε͍ͳূ໌Ͱࣔ͢͜ͱɻ ໰ ໋୊ ೉қ౓ɾඋߟ ໰ 1 A → ((A → B) → A) ˒ ऑԽ ໰ 2 A → (A → B → C) → B → C ˒˒ ࡾԾఆ ໰ 3 A → ¬¬A ˒˒ ¬ Λల։ ໰ 4 ¬¬¬A → ¬A ˒˒˒ ໰ 3 ͷԠ༻ Extra (A → B → C) → (A → B) → A → C ˒˒˒ S ίϯϏωʔλ ఏग़ͷϧʔϧ तۀதʹղ͚ͨ໰୊͸ఏग़ෆཁɻղ͚ͳ͔ͬͨ໰୊͚ͩఏग़͢Δ͜ͱɻ શ໰ղ͚ͨ৔߹͸ʮશ໰ղ͚ͨʯͱ KULMS ʹهೖͯ͠ఏग़ͤΑɻ ໰ 4ɾExtra ͸೉͍͠ͷͰɺͰ͖ͳ͚Ε͹ʮূ໌ෆՄೳͱࢥ͏ʯ·ͨ͸ ʮ్த·Ͱɿ. . . ʯͱॻ్͍ͯதܦաΛఏग़ͯ͠΋ߏΘͳ͍ɻ Պֶ఩ֶՊֶ࢙ (ԋश) ࿦ཧֶʢલظʣ ୲౰ɿ໼ా෦ढ़հ 32