記号論理学
記号論理学は、人間の推論を記号と規則によって形式化する学問です。日常言語のあいまいさを排除し、数学的に厳密な方法で「正しい推論と...
記号論理学を学ぶ第一歩は、命題と真理値を理解することです。命題とは真か偽かが定まる文のことであり、真理値とはその真偽を表す値のこ...
命題論理では、単純な命題を組み合わせて複合命題を作ります。その基本となるのが否定（NOT）と連言（AND）です。これらは最も基礎...
前回は否定と連言を学びました。今回は選言（OR）を扱います。選言には「包含的選言」と「排他的選言」の2種類があり、その違いを理解...
含意（implication）は「ならば」を表す論理結合子で、記号論理学において最も重要かつ最も誤解されやすい概念の一つです。日...
同値（equivalence）は「p であることと q であることは同じ」を表す論理結合子です。双条件文（bicondition...
真理値表（truth table）は、論理式の真偽をすべての可能な場合について網羅的に示す表です。論理式が正しいかどうかを機械的...
トートロジー（恒真式）と矛盾（恒偽式）は、論理式の重要な分類です。命題変数にどんな真理値を代入しても常に同じ結果になる論理式であ...
論理的同値（logical equivalence）は、2つの論理式が「同じ意味」を持つことを表す概念です。同じ意味とは、命題変...
論理的帰結（logical consequence）は、「前提から結論が導かれる」とはどういうことかを形式的に定義する概念です。...
これまでは真理値表を使って推論の妥当性を判定してきました。しかし、変数が増えると真理値表は急速に大きくなり、実用的ではなくなりま...
モーダスポネンス（modus ponens）とモーダストレンス（modus tollens）は、含意を扱う最も基本的な推論規則で...
自然演繹（natural deduction）は、人間の自然な推論過程を模した証明体系です。仮定を立てて推論し、その仮定を解消す...
自然演繹において含意（→）は中心的な役割を果たします。「p ならば q」を証明したり、すでに証明された含意を使ったりする方法を、...
連言（AND）と選言（OR）にも、それぞれ導入規則と除去規則があります。これらは含意の規則と比べて直感的で、使いやすいものが多い...
否定（¬）の扱いは、自然演繹の中でも特に興味深い部分です。否定を導入するには背理法を使い、否定を除去するには矛盾から任意の命題を...
自然演繹とは異なるアプローチとして、公理系（axiomatic system）があります。少数の公理と推論規則だけを使って、命題...
健全性（soundness）と完全性（completeness）は、証明体系と意味論の関係を表す重要な概念です。この2つが成り立...
命題論理では、命題を分解不可能な最小単位として扱いました。しかし「すべての人間は死ぬ」や「ある数は素数である」のような文は、命題...
全称量化子（universal quantifier）は、「すべての」を形式化する記号です。記号 ∀ で表し、述語論理の表現力を...
存在量化子（existential quantifier）は、「存在する」を形式化する記号です。記号 ∃ で表し、全称量化子 ∀...
量化子を使う際に重要なのが、束縛変数と自由変数の区別です。変数が量化子によって「縛られている」かどうかで、論理式の意味が大きく変...
述語論理を厳密に扱うためには、言語を形式的に定義する必要があります。どのような記号を使い、どのように式を構成するかを明確にするこ...
述語論理の推論規則は、命題論理の規則に加えて、量化子を扱う規則を持ちます。全称量化子と存在量化子それぞれに導入規則と除去規則があ...
等号（=）は、2つの項が同じ対象を指すことを表す特別な述語です。「2 + 2 = 4」や「明けの明星 = 宵の明星」のように、数...
述語論理の完全性定理は、20世紀論理学の金字塔の一つです。クルト・ゲーデルが1929年に証明したこの定理は、「証明できること」と...
モデル理論は、論理式とそれを解釈する数学的構造（モデル）の関係を研究する分野です。構造と解釈という概念を通じて、論理式に意味を与...
充足可能性（satisfiability）は、論理式にモデルが存在するかどうかを問う概念です。モデルの存在は、論理式の「実現可能...
コンパクト性定理（compactness theorem）は、モデル理論の基本定理の一つです。無限と有限をつなぐ橋渡しの役割を果...
レーヴェンハイム・スコーレム定理（Löwenheim-Skolem theorem）は、モデルのサイズに関する驚くべき結果を与え...
形式的体系（formal system）は、証明を数学的対象として厳密に定義するための枠組みです。何が公理であり、どのような規則...
ゲーデルの第一不完全性定理は、1931年にクルト・ゲーデルが証明した、数学史上最も重要な結果の一つです。十分に強い形式的体系は、...
ゲーデルの第二不完全性定理は、第一不完全性定理をさらに深化させた結果です。十分に強い理論は、自分自身の無矛盾性を証明できないこと...
決定可能性（decidability）は、問題を機械的に解けるかどうかを問う概念です。記号論理学と計算理論が交わる重要なテーマで...
様相論理（modal logic）は、「必然性」と「可能性」を形式化する論理体系です。古典述語論理を拡張して、「必ず〜である」「...
直観主義論理（intuitionistic logic）は、古典論理とは異なる基盤に立つ論理体系です。「構成的な証明」を重視し、...
288
views
