一次ロジック: 基礎と応用

By Fouad Sabry

一次論理とは

一次論理は、数学、哲学、言語学、コンピューター サイエンスの分野で使用される形式システムの集合です。 1 次論理の別名には、述語論理、数量化論理、および 1 次述語計算などがあります。 一次論理では、数量化された変数が非論理オブジェクトよりも優先され、変数を含む文の使用が許可されます。 その結果、「ソクラテスは人間である」というような主張をするのではなく、「x がソクラテスであり、x が人間であるような x が存在する」という形式の発言を行うことができます。ここで、「存在する」は数量詞であり、「x は人間である」 "は変数です。 これは、量指定子や関係を使用しない命題論理とは対照的です。 この意味で、命題論理は一次論理の基礎として機能します。

どのようなメリットが得られるか

(I) 以下に関する洞察と検証 トピック:

第 1 章: 一階論理

第 2 章: 公理

第 3 章: 命題微積分

第 4 章: ペアノ 公理

第 5 章: 全称数量化

第 6 章: 接続正規形

第 7 章: 一貫性

第 8 章: ゼルメロ?フランケル 集合論

第 9 章: 解釈 (ロジック)

第 10 章: 量子ランク

(II) 一次ロジックに関する一般のよくある質問に答えます。

(III) 多くの分野での一次ロジックの使用例。

(IV) 360 度の各業界における 266 の新興テクノロジーを簡潔に説明する 17 の付録 一次ロジックのテクノロジーを完全に理解するための本です。

本書の対象者

専門家、学部生、大学院生、愛好家、趣味人、および次のことを学びたい人 あらゆる種類の一次ロジックに関する基本的な知識や情報を超えることができます。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 25, 2023

Book preview

第 1 章: 一次論理

一次論理は、数学、哲学、言語学、およびコンピュータサイエンスの分野で使用される一連の形式システムです。一次論理の他の名前には、述語論理、量化論理、および一次述語計算が含まれます。一階論理では、量化された変数は非論理オブジェクトよりも優先され、変数を含む文の使用が許可されます。その結果、「ソクラテスは人間である」などの主張をするのではなく、「存在する」が量化子であり、「x」が変数である「xが存在する」という形式の表現を行うことができます。このように、命題論理は一階論理の基礎と考えることができます。

集合論、群の理論、または算術の形式理論などの主題に関する理論は、典型的には、特定の談話の領域(量化された変数の範囲)、その領域からそれ自体への有限個の関数、その領域上で定義された有限個の述語、およびそれらについて保持されると信じられている公理のセット。時には、より学術的な意味で、「理論」は一次論理の単語の集まりにすぎないと信じられています。

一次論理は、他の述語または関数を入力として取る述語を含む「一次」という単語の使用によって高階論理と区別されてもよいし、述語または関数に対して定量化が代替的に実行されてもよいし、あるいはその両方が許可される。:56 一階理論では、集合と述語が一緒に働くのがよく見られます。

その解釈を伴う高階理論では、述語をコレクションのコレクションと見なすことができます。

一次論理にはさまざまな演繹システムがあり、それらのほとんどは有効で健全であり、すべての検証可能な命題はすべてのモデルで真です)および完全(つまり、

すべてのモデルに当てはまる場合、任意の命題を証明することができます。

論理的帰結間のリンクは単に半決定可能であるという事実にもかかわらず、 一次論理では、自動定理証明は近年大きな進歩を遂げています。

さらに、一階論理は多くのメタロジー定理に準拠しているため、レーヴェンハイム・スコーレムの定理やコンパクト性定理などの証明理論のレンズを介して調べることができます。

数学を公理に形式化するための業界標準として機能する一階論理の研究は、数学的研究の基礎に含まれています。数論の一次論理への公理化はペアノ算術として知られており、集合論の一次論理への公理化はツェルメロ・フレンケル集合論として知られている。自然数や実数直線のような無限の定義域を持つ構造は、そのような理論がそうするために必要な力を欠いているため、一次理論では適切に記述できません。2階論理などのより強力な論理は、これらの構造の両方を分類的に記述する公理システムを生成することを可能にします。これらはカテゴリ公理システムとして知られています。

ゴットロープ・フレーゲとチャールズ・サンダース・パースは、それぞれ1階論理の開発に大きく貢献した。

一階論理の発展とそれが形式論理を支配するようになった理由の詳細については、José Ferreirós(2001)を参照してください。

命題論理とは対照的に、一次論理は、述語と定量化にも対処しますが、より単純な宣言文に関係しています。

述語は、談話の領域内の1つ以上の事柄に基づいて真または偽のいずれかに評価されるステートメントです。「ソクラテスは哲学者である」と「プラトンは哲学者である」の両方が真実であるという事実について考えてください。これらのステートメントは、命題論理では互いに接続されていないと考えられているため、たとえばpやqなどの変数で表される可能性があります。これらの句はそれぞれ「aは哲学者である」という基本構造を持っており、これは「哲学者である」という述語が両方に現れることを意味します。最初のフレーズでは、変数anは「ソクラテス」という名前で表され、2番目の文では、変数anは「プラトン」という名前で表されます。この特定の例では、「哲学者である」などの述語の使用は、一階論理の枠組みの中で許容されますが、命題論理は許容されません。

論理接続詞は、述語間に存在する関係の性質を表現することを可能にします。たとえば、「anが哲学者であれば、anは学者である」という一次規則を考えてみましょう。この定式化は条件付きステートメントの例であり、「aは哲学者である」という仮説と、「aは学者である」という結論があります。この方程式の妥当性は、aで表されるものの性質だけでなく、「哲学者である」および「学者である」という述語の意味をどのように理解するかにも左右されます。

数式では、量指定子を変数と組み合わせて使用できます。上記の式における変数anの値は、例えば、「任意のaについて、anが哲学者であれば、anは学者である」という一階句を用いてグローバルに定量化することができる。このステートメントでの普遍的な量指定子「すべての人」の使用は、「anが哲学者である場合、anは学者である」という主張が文字aのすべての可能な組み合わせに当てはまるという概念を伝えます。

「任意のaについて、anが哲学者である場合、anは学者である」というフレーズの論理的に同等の反対は、「anが哲学者であり、anが学者ではないようなものが存在する」というステートメントです。「aは哲学者であり、anは学者ではない」という声明が「a」の選択に当てはまるという概念は、「存在する」という実存的量化子が私たちに伝えようとしていることです。

「哲学者である」と「学者である」はどちらも、単一の変数を引数として受け入れる述語の例です。ほとんどの場合、述語はいくつかの変数を受け入れることができます。「ソクラテスはプラトンの教師である」という一次句の述語「の教師である」には、それが参照している2つの変数があります。

モデルとも呼ばれる 1 次式の解釈は、各述語の意味を明確にし、変数をインスタンス化できるエンティティを識別します。しばしば宇宙として知られている談話の領域は、通常、空ではないセットであることが期待されます。これらのものが宇宙を構成しています。たとえば、言説の領域がすべての人間で構成され、「哲学者である」という述語が「共和国の作者であった」と理解される解釈では、プラトンがそれを目撃した人であったため、「そのような人が哲学者であるような人が存在する」という文は真実と見なされます。

一次論理には、2つの基本コンポーネントがあります。一階論理では、整形式の式は構文に従って記号の有限列であると決定され、これらの式の意味は言語の意味論に従って決定されます。

一階論理の言語は、英語などの自然言語とは対照的に、完全に形式的です。その結果、特定の文が正しく構成されているかどうかを機械化された方法で評価することができます。整形式の表現は、物事を直感的に説明する単語と、真または真ではない命題を直感的に伝える数式の2つの主要なカテゴリに分類できます。一階論理では、単語と式は記号の文字列で表され、言語のアルファベットは記号自体によって形成されます。形式論理は、すべての形式言語の場合のように、記号自体の性質に適用することはできません。それでも、ほとんどの人はそれらを文字と句読点にすぎないと考えています。

アルファベットの文字を対応する論理記号に分離するのが通常の方法です, 彼らは通常、非論理記号に加えて、同じことを意味すると理解されています, その意味はそれがどのように解釈されるかに依存します.

たとえば、論理記号 \land は常に and を表します。論理記号で表される文脈で「または」を意味するために使用されることはありません \lor 。

ただし、Phil(x)などの非論理述語記号の1つの可能な解釈は、その時点で適用されている解釈に応じて、「xは哲学者である」、「人xはフィリップとして知られている」、またはその他の単項述語を意味することです。

論理記号は、作成者によって外観が異なる文字のコレクションですが、多くの場合、次のもので構成されます。

量指定子記号: 普遍的定量化のための∀、および存在的定量化のための∃

論理接続詞:接続詞の∧、論理和の∨、含意の→、↔双条件、¬の否定。

一部の著者は、→の代わりに  C pqを使用し、 の代わりに ↔ Epq を使用します 、特に→が他の目的で使用されるコンテキストで。

さらに、馬蹄形⊃は→を置き換え、トリプルバー ≡ ↔は¬を置き換え、チルダ(~)、Np、またはF pは¬を置き換え、ダブルバー、、、または pqは∨ \| + を置き換え {\displaystyle \bigwedge pq} ることができ、アンパサンド、Kpq 、または中央のドット⋅は∧特に、技術的な制約のために特定のシンボルを使用できない場合。

(前述の記号Cpq、E pq、Np、Apq、およびKpqは、ポーランド語表記で使用される記号です。

括弧や角かっこを囲むなど、さまざまな句読点。このようなシンボルの選択は、周囲の環境に依存します。

考えられる結果の終わりのないリスト、アルファベットx、y、zの最後に来る小文字で表されることが多い記号 。

.

添字は、変数を区別するためによく使用されます:x0、x1、x2,...

等号(等号とも呼ばれる)、恒等記号)=(以下の§等式とその公理を参照)。

一次論理では、これらの各シンボルを使用する必要はありません。否定演算子、接続詞 (または論理和)、変数、角かっこ、および等価に加えて、量指定子のいずれか 1 つを使用するだけで十分です。

論理シンボルの他の例を次に示します。

真理の不変量: T、V、または ⊤ は 真 を表し、F、O、または ⊥ は 偽 を表します (V と O はポーランド語表記から)。

原子価のこれらの論理演算子はいずれも0存在しないため、量指定子を使用することによってのみ、これら2つの定数を述べることができます。

シェファーストローク、Dpq(NAND)、Jpq(排他的論理和)などの追加の論理接続詞も含まれています。

述語 (関係)、関数、および定数はすべて、非論理記号を使用して表すことができます。過去には、単一の、不変の、計り知れないほど大きな非論理的なシンボルのコレクションの使用は、すべての状況で受け入れられた規範でした。

すべての整数 n ≥ 0 に対して、n 項構造のグループがここ、または n 位の述語記号にあります。

これらは n 個の異なるコンポーネント間の接続を示すため、接続シンボルとも呼ばれます。

任意の算術値nに対して、利用可能なそれらの終わりのない供給があります:

Pn0, Pn1, Pn2, Pn3, ..

すべての整数 n ≥0に対して、n項関数には無限の数の異なる記号があります。

f n0, f n1, f n2, f n3, ..

述語記号または関数記号から上付き文字 n を削除するのが一般的な方法です。

この昔ながらの方法では、1 次ロジックは 1 つの構文のみを使用して表現されます。この方法は、特に哲学的な立場をとる作品で、今でも広く使用されています。

最近では、検討されているアプリケーションに応じて、さまざまな非論理シンボルを利用することが一般的になっています。

したがって、特定のアプリケーションで使用される非論理シンボルのコレクション全体に名前を指定することが不可欠になりました。

この決定は、署名を使用して行われます。

順序付きフィールドの場合は {0, 1, +, ×, <} です。

使用できる非論理シンボルの量に制限はありません。

署名は、空白、有限、または無限、さらには不可算である可能性があります。

不可算署名は、例えばレーヴェンハイム・スコーレムの定理の現代の証明において生じる。

署名は、特定の状況では、非論理記号がどのように読み取られるかを示す場合がありますが、署名に含まれる非論理記号の解釈は、署名自体の意味とは異なります(必ずしも固定されているわけではありません)。シグネチャは、意味よりも構文に関心があります。

この方法によれば、非論理符号は次のいずれかのカテゴリに分類できます。

述語記号 (関係記号とも呼ばれ、価数 (または引数の数を指すアリティ) が 0 以上である。P、Q、Rなどの大文字は、これらを示すためによく使用されます。例：

P は、式 P(x) の価数が 1 の述語記号です。与えられるかもしれない1つの解釈は、「xは男です」です。

述語記号 Q は、式 Q(x,y) で使用される場合、原子価が 2 になります。「xはyより大きい」と「xはyの父である」の両方が、与えられた文の実行可能な読みです。

原子価0の関係は、任意のアサーションの代わりになる可能性のある変数である命題変数を使用して識別することができます。「ソクラテスは男である」というフレーズは、Rに与えられるかもしれない1つの解釈です。

0より大きいか0に等しい価数を持つ関数のシンボル。ほとんどの場合、f、g、h などの小文字のローマ字で示されます。例：

f(x) の解釈の 1 つは、「x の父」です。「-x」が数学の略である可能性があります。集合論では、「xのべき集合」を指す可能性があります。.

数学の分野では、 x+yは記号g(x,y)で表すことができます。集合論では、「xとyの和集合」を指す可能性があります。

定数記号は原子価が0の機能記号であり、a、b、cなどのアルファベットの先頭に小文字で示されることがよくあります。これは、定数シンボルが時間の経過と共に変化しないためです。文字aがソクラテスを表している可能性があります。算術演算で0の記号として使用される場合があります。集合論では、空集合を指す可能性があります。

「カスタム」シグネチャは非論理シンボルの従来のシーケンスで構成されているべきであると述べるだけで、現代の方法の枠組みの中で従来の方法を復活させることができます。

一階論理で使用される概念と方程式は、形成規則によってそれらの定義が与えられます。これらの原則は、用語や数式を表す記号の文字列に適用すると、用語や数式の正式な言語を構築するために使用できます。これらのルールは通常、コンテキストフリーです(各プロダクションの左側に1つのシンボルがあります)が、シンボルのセットが無限であることが許可され、項の場合の変数など、多数の開始シンボルが存在する可能性があることを除いて。

次のルールのコレクションは、単語のセットの帰納的定義を提供します。

変数。項は任意の変数記号で表すことができます。

関数。

f が n 項関数の記号であり、t1, .., tn が項である場合、f(t1,...,tn) は項である。

特に、個々の定数を表す記号はヌル関数記号と呼ばれ、その用語は以下の通りである。

ルール 1 と 2 を限られた回数適用することによって導出できる式のみが用語と見なされます。たとえば、述語記号を含むステートメントは単語とは見なされません。

次の一連のガイドラインでは、整形式の数式または WFF と呼ばれることもある数式のセットを帰納的に定義します。

述語記号。

P が n 項述語記号で t1, ..,  tn が項である場合、 P (t1,...,tn) は数式です。

平等。

等式の記号が論理の構成要素と見なされ、t1とt2が項である場合、t1 = t2は式です。

否定。

が数式の場合 \varphi 、 {\displaystyle \lnot \varphi } は数式です。

バイナリ接続詞。

\varphi と \psi が数式の場合、( \varphi \rightarrow \psi ) は数式です。

他のバイナリ論理接続詞は、上記と同じ一連の原則に従います。

量指定子。

\varphi が式で  x が変数である場合、(すべての x に対して成 \forall x\varphi り立つ) と \varphi ( のような x