ブラウザよりも高速アクセス！
25 関係: 原子論理式、導出原理、一階述語論理、バックトラック、リテラル、ヒューリスティクス、デービス・パトナムのアルゴリズム、命題論理、アルゴリズム、エルブランの定理、ギルモアのアルゴリズム、再帰、充足可能性問題、矛盾、計算機科学、論理式、自動定理証明、電子情報通信学会、連言標準形、IBM 704、探索、恒真式、数理論理学、1960年、1962年。
原子論理式
原子論理式（atomic formula）または素論理式（そろんりしき）は、それを構成する部分論理式を持たない論理式である。何をもって原子論理式とするかは論理体系による。たとえば命題論理における原子論理式は命題変数である。 原子論理式は論理システムにおける最も単純な論理式である。整論理式はまず全ての原子論理式を示し、次に整論理式から整論理式を形成するルールを与えるという帰納的な方法によって定義される（再帰的定義）。複数の原子論理式から構成される論理式を複合論理式という。 例として命題論理に関する整論理式の定義を示す.
新しい！!: DPLLアルゴリズムと原子論理式 · 続きを見る »
導出原理
導出原理（どうしゅつげんり、resolution principle）とは、により1965年に提案されたJ.
新しい！!: DPLLアルゴリズムと導出原理 · 続きを見る »
一階述語論理
一階述語論理（いっかいじゅつごろんり、first-order predicate logic）とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理（にかいじゅつごろんり、second-order predicate logic）と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理（こうかいじゅつごろんり、higher-order predicate logic）という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。.
新しい！!: DPLLアルゴリズムと一階述語論理 · 続きを見る »
バックトラック
バックトラック（backtrack）.
新しい！!: DPLLアルゴリズムとバックトラック · 続きを見る »
リテラル
リテラル（literal）は、「文字どおり」「字義どおり」を意味する語で、 と同じくラテン語の （文字）に由来する。数理論理学とコンピュータプログラミングで異なる意味の専門用語として使われる。.
新しい！!: DPLLアルゴリズムとリテラル · 続きを見る »
ヒューリスティクス
ヒューリスティック（heuristic, Heuristik）とは、必ず正しい答えを導けるわけではないが、ある程度のレベルで正解に近い解を得ることができる方法である。ヒューリスティックスでは、答えの精度が保証されない代わりに、回答に至るまでの時間が少ないという特徴がある。主に計算機科学と心理学の分野で使用される言葉であり、どちらの分野での用法も根本的な意味は同じであるが、指示対象が異なる。すなわち、計算機科学ではプログラミングの方法を指すが、心理学では人間の思考方法を指すものとして使われる。なお、論理学では仮説形成法と呼ばれている。.
新しい！!: DPLLアルゴリズムとヒューリスティクス · 続きを見る »
デービス・パトナムのアルゴリズム
デービス・パトナムのアルゴリズム（Davis–Putnam algorithm）は、与えられた論理式の充足可能性を調べるアルゴリズムで、連言標準形で表現された命題論理式を対象とする。アメリカ国家安全保障局の支援を受け、一階述語論理での定理自動証明のための方法として（Martin Davis）とヒラリー・パトナム（Hilary Putnam）により1958年に考案され Davis Martin.
新しい！!: DPLLアルゴリズムとデービス・パトナムのアルゴリズム · 続きを見る »
命題論理
命題論理（propositional logic）とは、数理論理学（記号論理学）の基礎的な一部門であり、命題全体を1つの記号に置き換えて単純化し、論理演算を表す記号（論理記号・論理演算子）を用いて、その命題（記号）間の結合パターンを表現・研究・把握することを目的とした分野のこと。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。 命題を1つの記号で大まかに置き換える命題論理に対して、命題の述語（P）と主語（S）を、関数のF(x)のように別記号で表現し、更に量化子で主語（S）の数・量・範囲もいくらか表現し分けることを可能にした、すなわちより詳細に命題の内部構造を表現できるようにしたものを、述語論理と呼ぶ。.
新しい！!: DPLLアルゴリズムと命題論理 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: DPLLアルゴリズムとアルゴリズム · 続きを見る »
エルブランの定理
ルブランの定理（Herbrand's theorem）は1930年にジャック・エルブランが発表した数理論理学上の基本定理である 。 エルブランの定理は様々な表現方法があるが、単純には以下のように表現できる。 エルブランの定理は一階述語論理における任意の恒真な論理式の証明が有限回の機械的な操作で終わることを保証し、ほとんどの自動定理証明の理論的な基盤になっている。チューリングマシンの停止性問題と同様、一般的な述語論理式が証明可能かどうかを求めるアルゴリズムは存在しないが、エルブランの定理では一階述語論理を命題論理と結び付けることで、一階述語論理での証明可能性についての部分的な回答を与えている。 なお、エルブランの本来の証明は任意の一階述語論理式を対象としたものだがBuss, Samuel R., "On Herbrand's Theorem", in Maurice, Daniel; Leivant, Raphaël, Logic and Computational Complexity, Lecture Notes in Computer Science, Springer-Verlag, pp.
新しい！!: DPLLアルゴリズムとエルブランの定理 · 続きを見る »
ギルモアのアルゴリズム
ルモアのアルゴリズム（Gilmore's algorithm）は、エルブランの定理にもとづき一階述語論理式が充足不能（unsatisfiable）かどうかを調べる半アルゴリズム（semi-algorithm）である。ギルモアのアルゴリズムは1960年に発表された。 P. Gilmore.
新しい！!: DPLLアルゴリズムとギルモアのアルゴリズム · 続きを見る »
再帰
再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。 主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳（回帰#物理学及び再帰性を参照のこと）や、reflexiveの訳として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。.
新しい！!: DPLLアルゴリズムと再帰 · 続きを見る »
充足可能性問題
充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.
新しい！!: DPLLアルゴリズムと充足可能性問題 · 続きを見る »
矛盾
矛盾（むじゅん、contradiction）とは、あることを一方では肯定し、同時に他方では否定するなど、論理の辻褄（つじつま）が合わないこと。物事の筋道や道理が合わないこと。.
新しい！!: DPLLアルゴリズムと矛盾 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: DPLLアルゴリズムと計算機科学 · 続きを見る »
論理式
論理式.
新しい！!: DPLLアルゴリズムと論理式 · 続きを見る »
自動定理証明
アルゴンヌ国立研究所は1960年代以降2000年代まで、自動定理証明のリーダーだった。 自動定理証明（automated theorem proving, ATP）とは、自動推論 (AR) の中でも最も成功している分野であり、コンピュータプログラムによって数学的定理に対する証明を発見すること。ベースとなる論理によって、定理の妥当性を決定する問題は簡単なものから不可能なものまで様々である。.
新しい！!: DPLLアルゴリズムと自動定理証明 · 続きを見る »
電子情報通信学会
一般社団法人電子情報通信学会（でんしじょうほうつうしんがっかい、The Institute of Electronics, Information and Communication Engineers）は、電子・情報・通信の三分野を取り扱っている学会である。略称は IEICE。 日本学術会議協力学術研究団体。事務局を東京タワー近くの機械振興会館内に置いている。.
新しい！!: DPLLアルゴリズムと電子情報通信学会 · 続きを見る »
連言標準形
連言標準形（れんげんひょうじゅんけい、Conjunctive normal form, CNF）は、数理論理学においてブール論理における論理式の標準化（正規化）の一種であり、選言節の連言の形式で論理式を表す。乗法標準形、主乗法標準形、和積標準形とも呼ぶ。正規形としては、自動定理証明で利用されている。.
新しい！!: DPLLアルゴリズムと連言標準形 · 続きを見る »
IBM 704
NASAの IBM 704 (1957) LLNL.) IBM 704はIBMが1954年4月に発表したコンピュータ。浮動小数点数演算ハードウェアを量産機として世界で初めて採用した。704 は IBM 701 のアーキテクチャと実装を大幅に強化したもので、互換性はない。.
新しい！!: DPLLアルゴリズムとIBM 704 · 続きを見る »
探索
探索（たんさく、search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（search）も参照。.
新しい！!: DPLLアルゴリズムと探索 · 続きを見る »
恒真式
恒真式（こうしんしき、トートロジー、tautology、ギリシャ語のταυτο「同じ」に由来）とは論理学の用語で、「aならば aである（a → a）」「aである、または、aでない（a ∨ ￢a）」のように、そこに含まれる命題変数の真理値、あるいは解釈に関わらず常に真となる論理式である。.
新しい！!: DPLLアルゴリズムと恒真式 · 続きを見る »
数理論理学
数理論理学（mathematische Logik、mathematical logic）は、論理学（形式論理学）の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学（とくに）における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか（逆数学のように）ということに焦点を当てている。.
新しい！!: DPLLアルゴリズムと数理論理学 · 続きを見る »
1960年
アフリカにおいて当時西欧諸国の植民地であった地域の多数が独立を達成した年であることに因み、アフリカの年と呼ばれる。.
新しい！!: DPLLアルゴリズムと1960年 · 続きを見る »
1962年
記載なし。
新しい！!: DPLLアルゴリズムと1962年 · 続きを見る »
