一般的な問題解決者: 基礎と応用

By Fouad Sabry

ジェネラル プロブレム ソルバーとは

GPS は「ジェネラル プロブレム ソルバー」の略で、1957 年にハーバート A. サイモンと J. C. ショーによって開発されたコンピューター プログラムです。 、およびアレン・ニューウェルは、普遍的な問題解決マシンとして機能することを目的としています。 論理理論家の取り組みとは対照的に、手段と目的の関係を分析することが GPS の運用の中心です。

どのようなメリットがあるか

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

第 1 章: 一般的な問題ソルバー

第 2 章: 一次ロジック

第 3 章: A* 検索アルゴリズム

第 4 章: Soar (認知アーキテクチャ)

第 5 章: ヒューリスティック

第 6 章: 組み合わせ爆発

第 7 章: 論理理論家

第 8 章: 反復深化 A*

第 9 章: 手段?目的分析

第 10 章: 状態空間探索

(II) 一般問題ソルバーに関する一般のよくある質問に答える。

(III) 多くの分野における一般問題ソルバーの使用例の実例。

(IV) 17 の付録 一般的な問題解決テクノロジーを 360 度完全に理解できるように、各業界の 266 の新興テクノロジーを簡潔に説明します。

この本の対象者

専門家、大学生、大学院生、愛好家、趣味人、そしてあらゆる種類の一般的な問題解決に関する基本的な知識や情報を超えたいと考えている人。

 

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

Book preview

第1章:一般的な問題解決者

1957年、ハーバートA.サイモン、J.C.ショー、アレンニューウェル(ランドコーポレーション)は、汎用問題解決マシンにすることを目的として、一般問題解決者(GPS)と呼ばれるコンピュータープログラムを開発しました。GPSは、廃止された論理理論家プロジェクトとは対照的に、手段終了アプローチを採用しています。

原則として、GPSは、整形式式(WFF)またはホーン句を使用して、1つ以上のソース(つまり、公理)とシンク(つまり、望ましい結論)を持つ有向グラフとして表現できる問題を解決できます。たとえば、GPSを使用して、述語論理とユークリッド幾何学の問題空間で結果を証明できます。これは、論理機械に関するサイモンとニューウェルの研究に基づいていました。問題解決戦略を問題知識(入力データとして表される)から切り離すことにより、GPSはこの種の最初のコンピュータープログラム(汎用ソルバーエンジン)でした。GPSの実装には、3次プログラミング言語であるIPLが使用されました。

組み合わせ爆発で検索が簡単に失われたため、GPSはハノイの塔のような十分に形式化できる些細な問題しか解決できませんでした。推論有向グラフを通る計算上実行不可能な数の「ウォーク」に達しました。(ハノイの塔のような単純な国家空間検索でさえ、実際には計算上実行不可能になる可能性がありますが、国家空間の賢明な剪定は、A*やIDA*などの基本的なAI技術によって達成できます。

問題を解決するために、ユーザー定義のオブジェクトとそれらのオブジェクトに対して実行できる操作、およびGPSは、平均端分析を通じてヒューリスティックを生成しました。可能なプロセスに焦点を合わせ、どの入力が機能し、どの入力が結果を生み出したかを判断しました。次に、途中で達成するためのより小さな目標を設定しました。

AIアーキテクチャSoarは、GPSパラダイムの直接の子孫です。

{第 1 章終了}

第 2 章: 一次論理

一次論理は、数学、哲学、言語学、およびコンピュータサイエンスの分野で使用される一連の形式システムです。一次論理の他の名前には、述語論理、量化論理、および一次述語計算が含まれます。一階論理では、量化された変数は非論理オブジェクトよりも優先され、変数を含む文の使用が許可されます。その結果、「ソクラテスは人間である」などの主張をするのではなく、「存在する」が量化子であり、「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に対して、利用可能なそれらの終わりのない供給があります: