ブラウザよりも高速アクセス！
22 関係: 否定、多項式時間、導出原理、二分決定図、二重否定の除去、リテラル、ブール論理、ド・モルガンの法則、ホーン節、分配法則、クワイン・マクラスキー法、充足可能性問題、節標準形、真理値表、選言標準形、計算複雑性理論、論理式、論理和、論理積、自動定理証明、NP完全問題、数理論理学。
否定
数理論理学において否定 (ひてい、Negation) とは、命題の真と偽を反転する論理演算である。否定は英語で Not であるが、Invert とも言われ論理演算ではインバージョン（Inversion）、論理回路では Not回路やインバータ回路（Inverter）とも呼ばれ入力に対して出力が反転する。 命題 P に対する否定を ¬P, P, !P などと書いて、「P でない」とか「P の否定」、「P 以外の場合」などと読む。 ベン図による論理否定（NOT）.
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: 連言標準形と多項式時間 · 続きを見る »
導出原理
導出原理（どうしゅつげんり、resolution principle）とは、により1965年に提案されたJ.
新しい！!: 連言標準形と導出原理 · 続きを見る »
二分決定図
二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。.
新しい！!: 連言標準形と二分決定図 · 続きを見る »
二重否定の除去
二重否定の除去（にじゅうひていのじょきょ、Double negative elimination）は、論理学、特に命題論理における推論規則の1つである。いわゆる二重否定と等価なものを追加したり（二重否定の導入）、二重の否定作用素を削除したり（二重否定の除去）といった操作を論理式に施す。 これは、次の二つの文が等価であることに基づいている。 と 二重否定の除去を形式的に表すと次のようになる。 二重否定の導入を形式的に表すと次のようになる。 二重否定の導入（Double negative introduction）は、二重否定の除去の逆であり、命題の意味を変えずに二重否定を追加できることを意味している。 これらの規則はシークエントの記法を使うと次のようにも表せる。 これら2つの推論規則に演繹定理を適用すると、以下の2つの妥当な論理式が得られる。 これらは、次の1つの論理式にまとめることができる。 双方向の含意関係は同値関係であるため、整論理式内の任意の ￢￢A は A に置換でき、その際にその整論理式(wff)の真理値は変化しない。 二重否定の除去は古典論理では定理だが、直観論理ではそうではない。直観論理では「この場合、雨が降っていない、のではない（It's not the case that it's not raining）」という文は「雨が降っている」よりも弱いとされる。後者は雨が降っていることを証明する必要があるが、前者は単に雨が降っているとしても矛盾しないことを証明すればよい（自然言語における緩叙法形式でもこのような区別が見られる）。二重否定の導入は直観論理でも定理であり、また \neg \neg \neg A \vdash \neg A も直観主義でも成立する。 素朴集合論でも、補集合が同様の性質を持つ。集合 A と集合 (AC)C は等価である（ここで、AC は A の補集合を意味する）。.
新しい！!: 連言標準形と二重否定の除去 · 続きを見る »
リテラル
リテラル（literal）は、「文字どおり」「字義どおり」を意味する語で、 と同じくラテン語の （文字）に由来する。数理論理学とコンピュータプログラミングで異なる意味の専門用語として使われる。.
新しい！!: 連言標準形とリテラル · 続きを見る »
ブール論理
ブール論理（ブールろんり、Boolean logic）は、古典論理のひとつで、その名称はブール代数ないしその形式化を示したジョージ・ブールに由来する。 リレーなどによる「スイッチング回路の理論」として1930年代に再発見され（論理回路#歴史を参照）、間もなくコンピュータに不可欠な理論として広まり、こんにちでは一般的に使われている。 本項目では、集合代数を用いて、集合、ブール演算、ベン図、真理値表などの基本的解説とブール論理の応用について解説する。ブール代数の記事ではブール論理の公理を満足する代数的構造の型を説明している。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。.
新しい！!: 連言標準形とブール論理 · 続きを見る »
ド・モルガンの法則
ド・モルガンの法則（ド・モルガンのほうそく、De Morgan の法則）は、ブール論理や集合の代数学において、論理和と論理積と否定（集合のことばでは、共通部分と合併と補集合）の間に成り立つ規則性である。名前は数学者オーガスタス・ド・モルガン（1806–1871）にちなむ。 この関係性は（論理のことばで言うと）「真と偽を入替え、論理和を論理積を入替えた論理体系」は、元の論理体系と同一視できる、ということであるので、ド・モルガンの双対性（英: De Morgan's duality）と呼ばれることもある。.
新しい！!: 連言標準形とド・モルガンの法則 · 続きを見る »
ホーン節
ホーン節（ホーンせつ、Horn clause）とは、数理論理学において、節（リテラルの選言結合命題）のうち、肯定形のリテラルの数が1つ以下の物を言う。論理学者のアルフレッド・ホーンによって導入された。.
新しい！!: 連言標準形とホーン節 · 続きを見る »
分配法則
集合 S に対して、積 × と和 + が定義されている時に、.
新しい！!: 連言標準形と分配法則 · 続きを見る »
クワイン・マクラスキー法
ワイン・マクラスキー法（—ほう; Quine–McCluskey algorithm/略:QM法）はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。 クワイン・マクラスキー法は3段階からなる。.
新しい！!: 連言標準形とクワイン・マクラスキー法 · 続きを見る »
充足可能性問題
充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.
新しい！!: 連言標準形と充足可能性問題 · 続きを見る »
節標準形
標準形（英: Clausal normal form、CNF）とは、数理論理学において、論理プログラミングや多くの自動定理証明系で使われる論理式の標準形式である。論理式を節標準形に変換すると論理式の構造が破壊される。また、Tseitin transformation を使用せずに単純な変換をすると式のサイズが最悪ケースではする。.
新しい！!: 連言標準形と節標準形 · 続きを見る »
真理値表
真理値表（しんりちひょう、Truth table）は、論理関数の、入力の全てのパターンとそれに対する結果の値を、表にしたものである。 例1：命題Pの否定「\lnot P」の場合、以下のような真理値表になる。 例2：2つの命題P,Qの論理和「P \lor Q」の場合、以下のような真理値表になる。 例3：2つの命題P,Qの論理積「P \land Q」の場合、以下のような真理値表になる。 なお、この表では「真」「偽」として表記してあるが、「T(.
新しい！!: 連言標準形と真理値表 · 続きを見る »
選言標準形
選言標準形（せんげんひょうじゅんけい、Disjunctive normal form, DNF）は、数理論理学においてブール論理での論理式の標準化（正規化）の一種であり、連言節(AND)の選言(OR)の形式で論理式を表す。加法標準形、主加法標準形、積和標準形とも呼ぶ。正規形としては、自動定理証明で利用されている。.
新しい！!: 連言標準形と選言標準形 · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: 連言標準形と計算複雑性理論 · 続きを見る »
論理式
論理式.
論理和
''P'' ∨ ''Q'' のベン図による表現 数理論理学において論理和（ろんりわ、Logical disjunction）とは、与えられた複数の命題のいずれか少なくとも一つが真であることを示す論理演算である。離接（りせつ）、選言（せんげん）とも呼び、ORとよく表す。 二つの命題 P, Q に対する論理和を P ∨ Q と書き、「P または Q」と読む。後述のように、日常会話における「または」とは意味が異なる。.
論理積
数理論理学において論理積（ろんりせき、logical conjunction）とは、与えられた複数の命題のいずれもが例外なく真であることを示す論理演算である。合接（ごうせつ）、連言（れんげん、れんごん）とも呼び、ANDとよく表す。 二つの命題 P, Q に対する論理積を P ∧ Q と書き、「P かつ Q」や「P そして Q」などと読む。 ベン図による論理積P \wedge Q の表.
自動定理証明
アルゴンヌ国立研究所は1960年代以降2000年代まで、自動定理証明のリーダーだった。 自動定理証明（automated theorem proving, ATP）とは、自動推論 (AR) の中でも最も成功している分野であり、コンピュータプログラムによって数学的定理に対する証明を発見すること。ベースとなる論理によって、定理の妥当性を決定する問題は簡単なものから不可能なものまで様々である。.
新しい！!: 連言標準形と自動定理証明 · 続きを見る »
NP完全問題
NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック（Stephen Cook (1971).
新しい！!: 連言標準形とNP完全問題 · 続きを見る »
数理論理学
数理論理学（mathematische Logik、mathematical logic）は、論理学（形式論理学）の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学（とくに）における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか（逆数学のように）ということに焦点を当てている。.
新しい！!: 連言標準形と数理論理学 · 続きを見る »
