ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
無料
ブラウザよりも高速アクセス!
 

二階述語論理

索引 二階述語論理

二階述語論理(にかいじゅつごろんり、second-order predicate logic)あるいは単に二階論理(にかいろんり、second-order logic)は、一階述語論理を拡張した論理体系であり、一階述語論理自体も命題論理を拡張したものである。二階述語論理もさらに高階述語論理や型理論に拡張される。 一階述語論理と同様に議論領域(ドメイン)の考え方を使う。ドメインとは、量化可能な個々の元の集合である。一階述語論理では、そのドメインの個々の元が変項の値となり、量化される。例えば、一階の論理式 ∀x (x ≠ x + 1) では、変項 x は任意の個体を表す。二階述語論理は個体の集合を変項の値とし、量化することができる。例えば、二階の論理式 ∀S ∀x (x ∈ S ∨ x ∉ S) は、個体の全ての集合 S と全ての個体 x について、x が S に属するか、あるいは属さないかのどちらかであるということを主張している。最も一般化された二階述語論理は関数の量化をする変項も含んでいる(詳しくは後述)。.

49 関係: 基数原子論理式型理論健全性単射可算集合存在記号実数完全性帰納的可算集合一階述語論理ペアノの公理チャールズ・サンダース・パースバートランド・ラッセルラッセルのパラドックスレーヴェンハイム–スコーレムの定理レオン・ヘンキン命題論理アルフレッド・ノース・ホワイトヘッドウィラード・ヴァン・オーマン・クワインゲーデルの完全性定理ゲーデルの不完全性定理コンパクト性定理ゴットロープ・フレーゲ全単射全射全称記号公理的集合論Co-NP算術EXPTIME複雑性クラス証明論計算複雑性理論記述計算量高階述語論理議論領域量化自由変数と束縛変数自然演繹集合論NPPH (計算複雑性理論)PSPACEWell-formed formula推移閉包推論規則決定可能性数学

基数

数学において基数(きすう、cardinal number又はcardinals)とは、集合のカーディナリティ(濃度、大きさ、サイズ)を測るためのものとしての自然数の一般化である。有限集合の濃度(cardinality)は、つまり有限集合の要素の個数は自然数である。無限集合のサイズは、超限基数で記述される。 濃度は全単射をもちいて定義される。2つの集合が等しい濃度を持つとは、その集合の間に全単射が存在するということである。有限集合の場合は、サイズの直感的概念に同意できるだろう。無限集合の場合は、振る舞いは複雑になってくる。ゲオルグ・カントールが示した基礎的な理論は無限集合の濃度は1種類だけではないことを示したのである。特に、実数の集合の濃度は自然数の集合の濃度より真に大きいということを示した(カントールの定理)。また、有限集合の真部分集合と元の集合の濃度が等しくなり得ないのに対し、無限集合の真部分集合の濃度が元の集合の濃度と等しいということは起こりうるのである(デデキント無限も参照)。 基数の超限列が存在する: この列は、有限基数である自然数が最初に並んでいて、その後に整列集合の無限基数であるアレフ・ナンバー (aleph number) が続く。アレフ・ナンバーは順序数によって添字付けられている。選択公理の仮定の下で、この超限列はすべての基数を含んでいる。もし、選択公理が仮定されなければ、アレフ・ナンバーでない無限基数に関して状況はさらに複雑になってくる。 濃度は、集合論の一部のために研究されている。また、組合せ論や抽象代数学、解析学を含めた数学の各分野の道具としても使われる。圏論では、基数は集合の圏の skelton を形成する。.

新しい!!: 二階述語論理と基数 · 続きを見る »

原子論理式

原子論理式(atomic formula)または素論理式(そろんりしき)は、それを構成する部分論理式を持たない論理式である。何をもって原子論理式とするかは論理体系による。たとえば命題論理における原子論理式は命題変数である。 原子論理式は論理システムにおける最も単純な論理式である。整論理式はまず全ての原子論理式を示し、次に整論理式から整論理式を形成するルールを与えるという帰納的な方法によって定義される(再帰的定義)。複数の原子論理式から構成される論理式を複合論理式という。 例として命題論理に関する整論理式の定義を示す.

新しい!!: 二階述語論理と原子論理式 · 続きを見る »

型理論

型理論(かたりろん、Type theory)は、数理論理学の一分野であり、「型」の階層を構築し、それぞれの型に数学的(あるいはそれ以外の)実体を割り当てるものである。階型理論(かいけいりろん、Theory of Types)とも。ある型のオブジェクトはその前提となる型のオブジェクトから構築される。この場合の「型」とは形而上的な意味での「型」である。バートランド・ラッセルは、彼が発見したラッセルのパラドックスにより素朴集合論の問題が明らかにされたことを受けて、型理論を構築した。型理論の詳細はホワイトヘッドとラッセルの 『プリンキピア・マテマティカ』にある。 型理論は、プログラミング言語の理論における型システムのベースにもなっている。「型システム」と「型理論」の語はほぼ同義として扱われることもあるが、ここでは、この記事では数理論理学の範囲を説明し、プログラミング言語の理論については型システムの記事で説明する。.

新しい!!: 二階述語論理と型理論 · 続きを見る »

健全性

健全性(けんぜんせい、Soundness)は、論証が次の属性を持つことと同値である。.

新しい!!: 二階述語論理と健全性 · 続きを見る »

単射

数学において、単射あるいは単写(たんしゃ、injective function, injection)とは、その値域に属する元はすべてその定義域の元の像として唯一通りに表されるような写像のことをいう。一対一(いったいいち、)の写像ともいう。似ているが一対一対応は全単射の意味で使われるので注意が必要である。.

新しい!!: 二階述語論理と単射 · 続きを見る »

可算集合

可算集合(かさんしゅうごう、countable set 又は denumerable set)もしくは可付番集合とは、おおまかには、自然数全体と同じ程度多くの元を持つ集合のことである。各々の元に 1, 2, 3, … と番号を付けることのできる、すなわち元を全て数え上げることのできる無限集合と表現してもよい。 有限集合も、数え上げることができる集合という意味で、可算集合の一種とみなすことがある。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を可算無限集合と呼び、可算無限集合と有限集合を合わせて高々可算の集合と呼ぶ。可算でない無限集合を非可算集合という。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができない。そのような集合の存在は、カントールによって初めて示された。.

新しい!!: 二階述語論理と可算集合 · 続きを見る »

存在記号

存在記号(そんざいきごう、existential quantifier)とは、数理論理学(特に述語論理)において、少なくとも1つのメンバーが述語の特性や関係を満たすことを表す記号である。通常「∃」と表記され、存在量化子(そんざいりょうかし)、存在限量子(そんざいげんりょうし)、存在限定子(そんざいげんていし)などとも呼ばれる。 これとは対照的に全称記号は、何かが常に真であることを示す。.

新しい!!: 二階述語論理と存在記号 · 続きを見る »

実数

数学における実数(じっすう、 nombre réel, reelle Zahl, real number)は、様々な量の連続的な変化を表す数の体系である。実数全体の空間は、途切れのなさにあたる完備性とよばれる位相的な性質を持ち、代数的には加減乗除ができるという体の構造を持っている。幾何学や解析学ではこれらのよい性質を利用して様々な対象が定義され、研究されている。一方でその構成方法に自明でない手続きが含まれるため、実数の空間は数学基礎論の観点からも興味深い性質を持っている。また、自然科学における連続的なものの計測値を表すのに十分な数の体系だとも考えられている。 実数の概念は、その形式的な定義が19世紀に達成される前から数の体系として使われていた。「実数」という名前は複素数の概念が導入された後に「普通の数」を表現する言葉として導入されたものである。.

新しい!!: 二階述語論理と実数 · 続きを見る »

完全性

数理論理学における完全性(かんぜんせい、completeness)には二つの意味がある。.

新しい!!: 二階述語論理と完全性 · 続きを見る »

帰納的可算集合

帰納的可算集合(きのうてきかさんしゅうごう、Recursively enumerable set)は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 S について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。.

新しい!!: 二階述語論理と帰納的可算集合 · 続きを見る »

一階述語論理

一階述語論理(いっかいじゅつごろんり、first-order predicate logic)とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理(にかいじゅつごろんり、second-order predicate logic)と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理(こうかいじゅつごろんり、higher-order predicate logic)という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。.

新しい!!: 二階述語論理と一階述語論理 · 続きを見る »

ペアノの公理

ペアノの公理(ペアノのこうり、Peano axioms) とは、自然数全体を公理化したものである。1891年に、ジュゼッペ・ペアノによって定義された。.

新しい!!: 二階述語論理とペアノの公理 · 続きを見る »

チャールズ・サンダース・パース

チャールズ・サンダース・パース(Charles Sanders Peirce、1839年9月10日 - 1914年4月19日)は、アメリカ合衆国の哲学者、論理学者、数学者、科学者であり、プラグマティズムの創始者として知られる。マサチューセッツ州ケンブリッジ生まれ。パースは化学者としての教育を受け、米国沿岸測量局に約三十年間、科学者として雇われていた。「アメリカ合衆国の哲学者たちの中で最も独創的かつ多才であり、そしてアメリカのもっとも偉大な論理学者」ともいわれる。存命中はおおむね無視されつづけ、第二次世界大戦後まで二次文献はわずかしかなかった。莫大な遺稿の全ては今も公表されていない。パースは自分をまず論理学者とみなし、さらに論理学を記号論(semiotics)の一分野とみなした。.

新しい!!: 二階述語論理とチャールズ・サンダース・パース · 続きを見る »

バートランド・ラッセル

3代ラッセル伯爵、バートランド・アーサー・ウィリアム・ラッセル(Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS、1872年5月18日 - 1970年2月2日)は、イギリスの哲学者、論理学者、数学者であり、社会批評家、政治活動家である。ラッセル伯爵家の貴族であり、イギリスの首相を2度務めた初代ラッセル伯ジョン・ラッセルは祖父にあたる。名付け親は同じくイギリスの哲学者ジョン・スチュアート・ミル。ミルはラッセル誕生の翌年に死去したが、その著作はラッセルの生涯に大きな影響を与えた。生涯に4度結婚し、最後の結婚は80歳のときであった。1950年にノーベル文学賞を受賞している。.

新しい!!: 二階述語論理とバートランド・ラッセル · 続きを見る »

ラッセルのパラドックス

ラッセルのパラドックス(Russell's paradox)とは、素朴集合論において矛盾を導くパラドックスである。バートランド・ラッセルからゴットロープ・フレーゲへの1902年6月16日付けの書簡における、フレーゲの『算術の基本法則』における矛盾を指摘する記述に表れる。これは1903年に出版されたフレーゲの『算術の基本法則』第II巻(Grundgesetze der Arithmetik II)の後書きに収録されている。同じパラドックスはツェルメロが1年先に発見していたが、彼はその発見を公開せず、ヒルベルトやフッサールなどのゲッティンゲン大学の同僚たちだけに知られているだけだった。 ラッセルが型理論(階型理論)を生み出した目的にはこの種のパラドックスを解消するということも含まれていた。.

新しい!!: 二階述語論理とラッセルのパラドックス · 続きを見る »

レーヴェンハイム–スコーレムの定理

レーヴェンハイム–スコーレムの定理(Löwenheim–Skolem theorem)とは、可算な一階の理論が無限モデルを持つとき、全ての無限濃度 κ について大きさ κ のモデルを持つ、という数理論理学の定理である。そこから、一階の理論はその無限モデルの濃度を制御できない、そして無限モデルを持つ一階の理論は同型の違いを除いてちょうど1つのモデルを持つようなことはない、という結論が得られる。.

新しい!!: 二階述語論理とレーヴェンハイム–スコーレムの定理 · 続きを見る »

レオン・ヘンキン

レオン・ヘンキン レオン・ヘンキン(Leon Henkin、1921年4月19日 – 2006年11月1日)はアメリカ合衆国の数学者、論理学者。カリフォルニア大学バークレー校数学科教授。「ヘンキン版一階述語論理の意味論的完全性の証明」で知られる。.

新しい!!: 二階述語論理とレオン・ヘンキン · 続きを見る »

命題論理

命題論理(propositional logic)とは、数理論理学(記号論理学)の基礎的な一部門であり、命題全体を1つの記号に置き換えて単純化し、論理演算を表す記号(論理記号・論理演算子)を用いて、その命題(記号)間の結合パターンを表現・研究・把握することを目的とした分野のこと。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。 命題を1つの記号で大まかに置き換える命題論理に対して、命題の述語(P)と主語(S)を、関数のF(x)のように別記号で表現し、更に量化子で主語(S)の数・量・範囲もいくらか表現し分けることを可能にした、すなわちより詳細に命題の内部構造を表現できるようにしたものを、述語論理と呼ぶ。.

新しい!!: 二階述語論理と命題論理 · 続きを見る »

アルフレッド・ノース・ホワイトヘッド

アルフレッド・ノース・ホワイトヘッド (Alfred North Whitehead、1861年2月15日 - 1947年12月30日)は、イギリスの数学者、哲学者である。論理学、科学哲学、数学、高等教育論、宗教哲学などに功績を残す。ケンブリッジ大学、ユニバーシティ・カレッジ・ロンドン、インペリアル・カレッジ・ロンドン、ハーバード大学の各大学において、教鞭をとる。哲学者としての彼の業績は、ハーバード大学に招聘されてからが主体であり、その時既に63歳であった。.

新しい!!: 二階述語論理とアルフレッド・ノース・ホワイトヘッド · 続きを見る »

ウィラード・ヴァン・オーマン・クワイン

ウィラード・ヴァン・オーマン・クワイン(Willard van Orman Quine, 1908年6月25日 - 2000年12月25日)は、アメリカ合衆国の哲学者、論理学者であり、20世紀の哲学者のなかで最も影響力のある人物の一人である。分析哲学の伝統の正当な継承者であるが、哲学は概念分析ではないという考えの主たる提唱者でもあった。母校であるハーバード大学で哲学と数学を教えた。主要な業績に「経験主義のふたつのドグマ」(『論理的観点から』所収)があり、分析命題と総合命題とを区別できるとする論理実証主義がはらむような経験主義を批判し、個別の命題だけでは経験によった確証は得られない(確証されるのは命題体系全体である)とする確証の全体論(ホーリズム)を提唱した(参考:デュエム-クワイン・テーゼ)。『ことばと対象』ではさらにこの立場を発展させ、有名な翻訳の不確定性テーゼを導入した。.

新しい!!: 二階述語論理とウィラード・ヴァン・オーマン・クワイン · 続きを見る »

ゲーデルの完全性定理

数理論理学においてゲーデルの完全性定理(ゲーデルのかんぜんせいていり、Gödel's completeness theorem、Gödelscher Vollständigkeitssatz)とは、第一階述語論理の恒真な論理式はその公理系からすべて導出可能であることを示した定理を言う。1929年にクルト・ゲーデルが証明した。.

新しい!!: 二階述語論理とゲーデルの完全性定理 · 続きを見る »

ゲーデルの不完全性定理

ーデルの不完全性定理(ゲーデルのふかんぜんせいていり、)又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。;第1不完全性定理: 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。;第2不完全性定理: 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。.

新しい!!: 二階述語論理とゲーデルの不完全性定理 · 続きを見る »

コンパクト性定理

ンパクト性定理()とは、一階述語論理の文の集合がモデルを持つこと(充足可能であること)と、その集合の任意の有限部分集合がモデルを持つことが同値であるという定理である。つまりある理論の充足可能性を示すにはその有限部分についてのみ調べれば良いという非常に有用性の高い定理であり、モデル理論における最も基本的かつ重要な成果のひとつである。.

新しい!!: 二階述語論理とコンパクト性定理 · 続きを見る »

ゴットロープ・フレーゲ

フリードリヒ・ルートヴィヒ・ゴットロープ・フレーゲ(Friedrich Ludwig Gottlob Frege, 1848年11月8日 - 1925年7月26日)は、ドイツの哲学者、論理学者、数学者であり、現代の数理論理学、分析哲学の祖にあたる。 フレーゲはバルト海に面したドイツの港町ヴィスマールの生まれである。母のアウグステ・ビアロブロツキーはポーランド系である。彼ははじめイェーナ大学で学び、その後ゲッティンゲン大学に移り1873年に博士号を取得した。その後イェーナに戻り、1896年から数学教授。1925年に死去した。.

新しい!!: 二階述語論理とゴットロープ・フレーゲ · 続きを見る »

全単射

数学において、全単射(ぜんたんしゃ)あるいは双射(そうしゃ)(bijective function, bijection) とは、写像であって、その写像の終域となる集合の任意の元に対し、その元を写像の像とする元が、写像の定義域となる集合に常にただ一つだけ存在するようなもの、すなわち単射かつ全射であるような写像のことを言う。例としては、群論で扱われる置換が全単射の良い例である。 全単射であることを一対一上への写像 (one-to-one onto mapping)あるいは一対一対応 (one-to-one correspondence) ともいうが、紛らわしいのでここでは使用しない。 写像 f が全単射のとき、fは可逆であるともいう。.

新しい!!: 二階述語論理と全単射 · 続きを見る »

全射

数学において、写像が全射的(ぜんしゃてき、surjective, onto)であるとは、その終域となる集合の元は何れもその写像の像として得られることを言う。即ち、集合 から集合 への写像 について、 の各元 に対し となるような の元 が(一般には複数あってもよいが)対応させられるとき、写像 は全射 (surjection, onto mapping/function) であるという。全写(あるいは全写像)とも書く。 全射(および単射、双射)の語は20世紀フランスの数学結社ブルバキ(1935年以降『数学原論』シリーズを刊行している)により導入されたものである。接頭辞 sur- はフランス語で「上の」を意味し、写像の始域が終域全体をすっぽり覆い尽くすように写し込まれるイメージを反映したものになっている。sur, in, bi, jection いずれもラテン語源である。.

新しい!!: 二階述語論理と全射 · 続きを見る »

全称記号

全称記号(ぜんしょうきごう、universal quantifier)とは、数理論理学において「全ての」(全称量化)を表す記号である。通常「∀」と表記され、全称量化子(ぜんしょうりょうかし)、全称限量子(ぜんしょうげんりょうし)、全称限定子(ぜんしょうげんていし)、普遍量化子(ふへんりょうかし)、普通限定子(ふつうげんていし)などとも呼ばれる。.

新しい!!: 二階述語論理と全称記号 · 続きを見る »

公理的集合論

公理的集合論(こうりてきしゅうごうろん、axiomatic set theory)とは、公理化された集合論のことである。.

新しい!!: 二階述語論理と公理的集合論 · 続きを見る »

Co-NP

co-NPとは計算量理論における問題クラスの一つである。.

新しい!!: 二階述語論理とCo-NP · 続きを見る »

算術

算術 (さんじゅつ、arithmetic) は、数の概念や数の演算を扱い、その性質や計算規則、あるいは計算法などの論理的手続きを明らかにしようとする学問分野である。.

新しい!!: 二階述語論理と算術 · 続きを見る »

EXPTIME

EXPTIME(EXPとも)は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。 DTIMEでは次のように表される。 以下の関係が知られている。 また、時間階層定理と領域階層定理により、次のようになる。 従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P.

新しい!!: 二階述語論理とEXPTIME · 続きを見る »

複雑性クラス

複雑性クラス(ふくざつせいクラス、Complexity class)は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である(例えば'''FP''')。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される(記述計算量)。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.

新しい!!: 二階述語論理と複雑性クラス · 続きを見る »

証明論

証明論(proof theory)は、数理論理学の一分野であり、証明を数学的対象として形式的に表し、それに数学的解析を施す。.

新しい!!: 二階述語論理と証明論 · 続きを見る »

計算複雑性理論

計算複雑性理論(けいさんふくざつせいりろん、computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.

新しい!!: 二階述語論理と計算複雑性理論 · 続きを見る »

記述計算量

記述計算量(きじゅつけいさんりょう、Descriptive complexity)は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、'''PH'''は二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。.

新しい!!: 二階述語論理と記述計算量 · 続きを見る »

高階述語論理

階述語論理(こうかいじゅつごろんり、Higher-order logic)は、一階述語論理と様々な意味で対比される用語である。 例えば、その違いは量化される変項の種類にも現われている。一階述語論理では、大まかに言えば述語に対する量化ができない。述語を量化できる論理体系については二階述語論理に詳しい。 その他の違いとして、基盤となる型理論で許されている型構築の違いがある。高階述語(higher-order predicate)とは、引数として1つ以上の別の述語をとることができる述語である。一般に n 階の高階述語の引数は1つ以上の (n − 1) 階の述語である(ここで n > 1)。同じことは高階関数(higher-order function)にも言える。 高階述語論理は表現能力が高いが、その特性、特にモデル理論に関わる部分では、多くの応用について性格が良いとは言えない。クルト・ゲーデルの業績により、古典的高階述語論理は(帰納的に公理化された)健全で完全な証明計算が認められないとされた。しかし、Henkin model によれば、健全で完全な証明計算は存在する。 高階述語論理の例として、アロンゾ・チャーチの Simple Theory of Types や Calculus of Constructions (CoC) がある。.

新しい!!: 二階述語論理と高階述語論理 · 続きを見る »

議論領域

議論領域(ぎろんりょういき、Domain of discourse)は、演繹、特に一階述語論理で使われる用語である。量化子で扱われる実体の適切な集合を指す。 議論領域という用語は一般に、特定の議論で使われる項全体の集合を指す。特定の議論とはすなわち、任意の1つの関心領域での言語学的または意味論的項の集まりである。モデル理論的な意味論では、議論領域という用語は、モデルが基づく実体集合を指す。 データベースは組織の現実のある面をモデル化したものである。このような現実を便宜的に「議論領域」と呼ぶこともある。.

新しい!!: 二階述語論理と議論領域 · 続きを見る »

量化

量化(りょうか、Quantification)とは、言語や論理学において、論理式が適用される(または満足される)議論領域の個体の「量」を指定すること。.

新しい!!: 二階述語論理と量化 · 続きを見る »

自由変数と束縛変数

数学や形式言語に関連する分野(数理論理学と計算機科学)において、自由変数(または自由変項、free variable)は数式や論理式で置換が行われる場所を指示する記法である。この考え方はプレースホルダーやワイルドカードにも関連する。 変数x は、例えば次のように書くと 束縛変数(または束縛変項、bound variable)になる。 あるいは これらの命題では、x の代わりに別の文字を使っても論理的には全く変化しない。しかし、複雑な命題で同じ文字を別の意味で再利用すると混乱が生じる。すなわち、自由変数が束縛されると、ある意味ではその後の数式の構成をサポートする作業に関与しなくなる。 プログラミングにおいては、自由変数とは関数の中で参照される局所変数や引数以外の変数を意味する。.

新しい!!: 二階述語論理と自由変数と束縛変数 · 続きを見る »

自然演繹

自然演繹(しぜんえんえき、Natural deduction)は、「自然な」ものとしての論理的推論の形式的モデルを提供する証明理論の手法であり、哲学的論理学の用語である。.

新しい!!: 二階述語論理と自然演繹 · 続きを見る »

集合論

集合論(しゅうごうろん、set theory, théorie des ensembles, Mengenlehre)は、集合とよばれる数学的対象をあつかう数学理論である。 通常、「集合」はいろいろな数学的対象の集まりを表していると見なされる。これは日常的な意味でのものの集まりやその要素、特定のものが入っているかいないか、という概念を包摂している。現代数学の定式化においては集合論がさまざまな数学的対象を描写する言葉をあたえている。(論理や述語論理とともに)集合論は数学の公理的な基礎付けをあたえ、数学的な対象を形式的に(無定義語の)「集合」と「帰属関係」によって構成することが可能になる。また、集合論の公理として何を仮定するとどんな体系が得られるか、といった集合それ自体の研究も活発に行われている。 集合論における基本的な操作には、あたえられた集合のべき集合や直積集合をとる、などがある。また二つの集合の元同士の関係(二項関係)を通じて定義される順序関係や写像などの概念が集合の分類に重要な役割を果たす。集合論では二つの集合はそれぞれの集合の元の間に全単射が存在するとき濃度が等しいという。そこで集合を濃度の等しさによって類別した各々の同値類のことを濃度という。この定義では濃度は真のクラスになってしまうので、濃度そのものを集合論的な対象として取り扱い難い。選択公理を仮定すると任意の集合は整列可能であることが導かれる。整列集合の順序型を順序同型で類別した各々の同値類と定義してしまうと、それは真のクラスとなってしまう。幸いなことに任意の整列集合は順序数と呼ばれる特別な集合(を帰属関係で順序付けしたもの)と順序同型となる。そのためそれら順序数を整列集合の順序型と定義することができる。また順序数全体 \mathrm(これは真のクラスになる)もまた整列順序付けられている。以上のもとで、集合の濃度を と定義することができる。すなわち濃度というのを特別な順序数として定義するわけである。このようにすることで濃度の定義から真のクラスを追放することができる。ただし選択公理を仮定することなく濃度を定義し取り扱うことはできる。基本的なアイデアは濃度で類別した各々同値類から累積階層の意味で階数が最小なものだけを分出するというものである。詳細はを参照。.

新しい!!: 二階述語論理と集合論 · 続きを見る »

NP

NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time(非決定性多項式時間)の略である(「Non-P」ないしは「Not-P」ではない)。.

新しい!!: 二階述語論理とNP · 続きを見る »

PH (計算複雑性理論)

計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。 PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、PPP('''PP'''をオラクルとして持つ神託機械で多項式時間で解ける問題のクラス)、P#P(戸田の定理による)、PSPACE がある。 PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。 PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。 P.

新しい!!: 二階述語論理とPH (計算複雑性理論) · 続きを見る »

PSPACE

PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。.

新しい!!: 二階述語論理とPSPACE · 続きを見る »

Well-formed formula

数理論理学において well-formed formula(wff、整式などとも)とは、形式言語といったような概念が広まる以前に、"formula" を単なる「記号を任意の順序に並べたもの」であるとして、それらのうち、数式などとして意味をなすような記号列を特に区別したものである。形式言語の考え方が広まるにつれ、そもそも意味のある数式などは何らかのルールに従って導出されるもので、それ以外の、任意の順序に並べたようなものは最初から議論の対象外として扱われるのが普通となった。.

新しい!!: 二階述語論理とWell-formed formula · 続きを見る »

推移閉包

推移閉包(すいいへいほう、transitive closure)は、集合 X における二項関係 R に対して、R を含む X 上の最小の推移関係 R を意味する。 たとえば X を人間(生死は問わない)の集合とし、「x は y の親である」という関係 xRy を考えると、その推移閉包は「x は y の先祖である」という関係 xRy である。あるいは X を空港の集合とし、「x から y への直通便が存在する」という関係 xRy を考えると、その推移閉包は「x から y まで一回または複数の航空便で行くことができる」という関係 xRy である。.

新しい!!: 二階述語論理と推移閉包 · 続きを見る »

推論規則

推論規則(すいろんきそく、rule of inference, inference rule, transformation rule)とは、論理式から他の論理式を導く推論の規則である。 記号、公理、代入規則、推論規則によって理論を形式化したものを公理系という。 公理は記号だけで記述されるが、推論規則や代入規則はこれらの記号について述べているメタ言語で記述される。 恒真式 (トートロジー)から推論規則を導くと妥当性のある推論になる。.

新しい!!: 二階述語論理と推論規則 · 続きを見る »

決定可能性

決定可能(けっていかのう、decidable)は、論理学において、論理式の集合のメンバーシップの決定をする実効的(effectiveな)方法が存在することを指す。決定可能性(けっていかのうせい、decidability)は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式(または定理)の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論(論理的帰結で閉じている論理式の集合)は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。.

新しい!!: 二階述語論理と決定可能性 · 続きを見る »

数学

数学(すうがく、μαθηματικά, mathematica, math)は、量(数)、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.

新しい!!: 二階述語論理と数学 · 続きを見る »

ここにリダイレクトされます:

第二階述語論理

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »