10 関係: ハミング距離、ハミング重み、ブール関数、ウィラード・ヴァン・オーマン・クワイン、カルノー図、充足可能性問題、真理値表、選言標準形、NP困難、指数関数。
ハミング距離
4ビット文字列のハミング距離を図示したもの。頂点に特定のビットの組合せが対応していて、頂点間の辺の数がハミング距離に対応する 情報理論において、ハミング距離(ハミングきょり、Hamming distance)とは、等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。別の言い方をすれば、ハミング距離は、ある文字列を別の文字列に変形する際に必要な置換回数を計測したものである。この用語は、リチャード・ハミング (Richard Wesley Hamming) にちなんで命名されたもので、鼻歌 (humming) ではない。 ハミング距離は、遠距離通信における固定長バイナリー文字列の中で弾かれたビット数や、エラーの概算を数えるのに用いられるために、信号距離とも呼ばれる。文字数 n の1ビット文字列間のハミング距離は、それらの文字列間の排他的論理和のハミング重み(文字列内の 1 の個数)か、 n 次元超立方体の 2 頂点間のマンハッタン距離に相当する。 ハミング距離の例:.
新しい!!: クワイン・マクラスキー法とハミング距離 · 続きを見る »
ハミング重み
ハミング重み(ハミングおもみ、Hamming weight)とは、シンボル列中の 0 以外のシンボルの個数である。典型的には、ビット列中の1の個数として使われる。.
新しい!!: クワイン・マクラスキー法とハミング重み · 続きを見る »
ブール関数
ブール関数(ブールかんすう、Boolean function)は、非負整数 k 個のブール領域 B.
新しい!!: クワイン・マクラスキー法とブール関数 · 続きを見る »
ウィラード・ヴァン・オーマン・クワイン
ウィラード・ヴァン・オーマン・クワイン(Willard van Orman Quine, 1908年6月25日 - 2000年12月25日)は、アメリカ合衆国の哲学者、論理学者であり、20世紀の哲学者のなかで最も影響力のある人物の一人である。分析哲学の伝統の正当な継承者であるが、哲学は概念分析ではないという考えの主たる提唱者でもあった。母校であるハーバード大学で哲学と数学を教えた。主要な業績に「経験主義のふたつのドグマ」(『論理的観点から』所収)があり、分析命題と総合命題とを区別できるとする論理実証主義がはらむような経験主義を批判し、個別の命題だけでは経験によった確証は得られない(確証されるのは命題体系全体である)とする確証の全体論(ホーリズム)を提唱した(参考:デュエム-クワイン・テーゼ)。『ことばと対象』ではさらにこの立場を発展させ、有名な翻訳の不確定性テーゼを導入した。.
新しい!!: クワイン・マクラスキー法とウィラード・ヴァン・オーマン・クワイン · 続きを見る »
カルノー図
ルノー図の例 カルノー図(カルノーず、Karnaugh map)は論理回路などにおいて論理式を簡単化するための表であり、その方法をカルノー図法という。よく似た概念にベイチ 図と呼ばれる図があり、変数と数字の書き方のみが異なる。.
新しい!!: クワイン・マクラスキー法とカルノー図 · 続きを見る »
充足可能性問題
充足可能性問題(じゅうそくかのうせいもんだい、satisfiability problem, SAT)は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.
新しい!!: クワイン・マクラスキー法と充足可能性問題 · 続きを見る »
真理値表
真理値表(しんりちひょう、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)の形式で論理式を表す。加法標準形、主加法標準形、積和標準形とも呼ぶ。正規形としては、自動定理証明で利用されている。.
新しい!!: クワイン・マクラスキー法と選言標準形 · 続きを見る »
NP困難
NP完全、'''NP困難'''の相関を表すベン図 NP困難(エヌピーこんなん、NP-hard)とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難なとき次のことが言える(以下は定義ではなく主張)。.
新しい!!: クワイン・マクラスキー法とNP困難 · 続きを見る »
指数関数
実解析における指数関数(しすうかんすう、exponential function)は、冪における指数 を変数として、その定義域を主に実数の全体へ拡張して定義される初等超越関数の一種である。対数関数の逆関数であるため、逆対数 と呼ばれることもある。自然科学において、指数関数は量の増加度に関する数学的な記述を与えるものとして用いられる(や指数関数的減衰の項を参照)。 一般に、 かつ なる定数 に関して、(主に実数の上を亙る)変数 を へ送る関数は、「a を'''底'''とする指数函数」と呼ばれる。「指数関数」との名称は、与えられた底に関して冪指数を変数とする関数であることを示唆するものであり、冪指数を固定して底を独立変数とする冪関数とは対照的である。 しばしば、より狭義の関数を意図して単に「指数関数」と呼ぶこともある。そのような標準的な (the) 指数関数(あるいはより明示的に「自然指数関数」)はネイピア数 を底とする関数 である。これを のようにも書く。この関数は、導関数が自分自身に一致するなど、他の指数関数と比べて著しい性質を持つ。底 を他の底 に取り換えるには自然対数 を用いて、等式 を適用すればよいから、以下本項では主に自然指数関数について記述し、多くの場合「指数関数」は自然指数関数の意味で用いる。.
新しい!!: クワイン・マクラスキー法と指数関数 · 続きを見る »
ここにリダイレクトされます:
QM法。