ブール代数

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

数学および理論理学では、ブール代数は代数の分岐であり、変数の値は真理値 trueおよびfalseであり、通常はそれぞれ1および0で表されます。変数の値が数値であり、主演算が加算と乗算である初等代数の代わりに、ブール代数の主な演算は、∧で示される結合および)、∨で示される分離または)、および否定です。 (ではなく)¬として示されます。したがって、初等代数が数値演算を記述するのと同じように、 論理演算を記述するための形式です。

ブール代数は、GeorgeBooleの最初の著書TheMathematical Analysis of Logic [1] (1847)で紹介され、AnInvestigation of the Laws of Thought(1854)で詳しく説明されています。[2]ハンティントンに よれば、「ブール代数」という用語は1913年にシェファーによって最初に提案されましたが[3]チャールズサンダースパースは彼の「最も単純な数学」の最初の章に「1つの定数を持つブール代数」というタイトルを付けました。[4]ブール 代数は、デジタルエレクトロニクスの開発において基本的であり、すべての現代で提供されています。プログラミング言語また、集合論統計でも使用されます[5]

歴史

ブール代数の前身は、ゴットフリート・ウィルヘルム・ライプニッツ概念代数でした。ライプニッツの概念の代数は、集合のブール代数と演繹的に同等です。[6]

ブールの代数は、抽象代数数理論理学の現代の発展に先行していました。ただし、両方のフィールドの原点に関連していると見なされます。[7]抽象的な設定では、ブール代数は19世紀後半に、(抽象的な)数学的構造の現代的な概念に到達するまで、 JevonsSchröderHuntingtonなどによって完成されました。[7]たとえば、集合の代数の式をブールの代数の式に変換することによって、集合の代数の式を操作できるという経験的観察は、集合の代数 ブール代数(不定冠詞に注意してください)。実際、MH Stone 、1936年に、すべてのブール代数が有限加法族と同型であることを証明しました

1930年代に、スイッチング回路を研究している間、クロードシャノンは、この設定でブールの代数の規則を適用することもできることを観察し[8] 、論理ゲートの観点から代数的手段によって回路を分析および設計する方法としてスイッチング代数を導入しました。 シャノンはすでに抽象的な数学的装置を自由に使えるようにしていたので、彼はスイッチング代数を2元ブール代数としてキャストしました。最新の回路工学の設定では、他のブール代数を考慮する必要はほとんどないため、「スイッチング代数」と「ブール代数」は同じ意味で使用されることがよくあります。[9] [10] [11]

ブール関数の効率的な実装は、組み合わせ論理回路の設計における基本的な問題です。VLSI回路用の最新の電子設計自動化ツールは、論理合成形式的検証のために、(順序を減らした)二分決定図(BDD)として知られるブール関数の効率的な表現に依存することがよくあります。[12]

古典的な命題論理で表現できる論理文は、ブール代数で同等の表現を持っています。したがって、ブール論理は、このように実行された命題論理を示すために使用されることがあります。[13] [14] [15]ブール代数は、一階述語論理からのもののように、数量詞を使用して論理式をキャプチャするのに十分ではありません

数理論理学の開発はブールのプログラムに従わなかったが、彼の代数と論理の間の関係は、他の多くの論理の代数システムも研究する代数論理の設定で後に確固たる基盤に置かれた。[7]与えられたブール(提案)式の変数が、式を真と評価するような方法で割り当てることができるかどうかを判断する問題は、ブール充足可能性問題(SAT)と呼ばれ、理論計算機にとって重要です。科学、 NP完全であることが示された最初の問題です。として知られている密接に関連した計算モデルブール回路は、(アルゴリズムの)時間計算量を回路計算量に関連付けます

式は主に初等代数の数値を示しますが、ブール代数では、真理値 falseおよびtrueを示します。これらの値は、ビット(または2進数)、つまり0と1で表されます。1+1 = 2の整数0と1のようには動作しませんが、 2要素フィールドの要素で識別できます。 GF(2)、つまり、1 + 1 = 0である2を法とする整数算術次に、加算と乗算は、論理和x∨yを使用して、それぞれXOR(排他的論理和)とAND 論理積)のブールの役割を果たします。(包括的-または)x + y --xyとして定義可能であり否定¬x1 −xとして定義可能ですGF(2)では、-は同じ操作を表すため、+に置き換えることができます。ただし、このブール演算の記述方法では、整数の通常の算術演算を適用できます(これは、GF(2)が実装されていないプログラミング言語を使用する場合に役立つことがあります)。

ブール代数は、集合{0、1}に値を持つ関数も扱います。このような機能には、ビットのシーケンスが一般的に使用されます。もう1つの一般的な例は、集合Eのサブセットです。EのサブセットFに対して、 Fで値1を取り、Fの外側で0をとるインジケーター関数を定義できます最も一般的な例はブール代数の要素であり、前述のすべてがそのインスタンスです。

初等代数と同様に、変数の明示的な値を考慮せずに、理論の純粋に等式の部分を作成できます。[16]

操作

基本操作

ブール代数の基本的な操作は、論理論理和、および否定です。これらのブール演算は、対応する二項演算子 ANDOR、および単項演算子 NOTで表され、まとめてブール演算子と呼ばれます。[17]

変数xおよびyの基本的なブール演算は、次のように定義されています。

あるいは、x∧y x∨y、および¬x、次のよう に真理値表を使用してそれらの値を表にすることで表すことができます。

真理値0および1が整数として解釈される場合、これらの演算は通常の算術演算(x + yは加算を使用し、xyは乗算を使用)または最小/最大関数 で表すことができます。

否定と論理和の観点から論理積を定義できる次のアイデンティティがあるため、否定と他の2つの操作の1つだけが基本であると考える人もいるかもしれません(De Morganの法則)。

二次操作

上記の3つのブール演算は基本と呼ばれます。これは、演算を組み合わせたり複合したりする方法で、合成によってそれらから構築できる他のブール演算の基礎として使用できることを意味します。基本操作から構成される操作には、次の例が含まれます。

材料条件付き
排他的論理和 XOR):
論理的等価性

これらの定義により、次の真理値表が作成され、4つの可能な入力すべてに対するこれらの操作の値が示されます。

二次操作。表1
0 0 1 0 1
1 0 0 1 0
0 1 1 1 0
1 1 1 0 1
材料条件付き
最初の操作x  →  y、またはC xyは、マテリアル含意と呼ばれますxが真の場合、式x  y の結果はyの結果と見なされます(たとえば、xが真でyが偽の場合、x  →  yも偽になります)。ただし、xがfalseの場合、yの値は無視できます。ただし、操作はブール値を返す必要があり、選択肢は2つだけです。したがって、定義上、x  →  y真です。xがfalseの場合。相関論理は、誤った前提を持つ含意を真または偽以外のものと見なすことにより、この定義を示唆します。)
排他的論理和 XOR
2番目の演算x⊕yまたは Jxy は、排他的論理和 XORと略されることが多い)と呼ばれ、包含的論理和としての論理和と区別されます。xyの両方が真である可能性を排除します(たとえば、表を参照)。両方が真の場合、結果は偽になります。算術で定義すると、mod2が1+ 1 = 0の加算です。
論理的等価性
3番目の演算である排他的論理和の補集合は等価またはブール等式です 。x≡y  、またはE xyは、 xyのが同じ場合にのみ真になります。したがって、その補集合としての x⊕y は、 x  ≠  yとして理解でき、 xyが異なる場合にのみ真になります。したがって、算術mod2の対応するものはx + yです。算術mod2の等価物は、x + y +1です。

それぞれ2つの可能な値を持つ2つのオペランドが与えられると、入力の2 2 = 4の可能な組み合わせがあります。各出力は2つの可能な値を持つことができるため、合計2 4 = 16の可能なバイナリブール演算があります。このような演算または関数(およびより多くの入力を持つブール関数)は、上からの基本的な演算で表現できます。したがって、基本的な操作は機能的に完了しています。

法律

ブール代数法則は、2つのブール項の間のx∨(y∨z)=(x∨y)∨zのような単位元です。ここで、ブール変数定数0および1から構築た式として定義されます。操作∧、∨、および¬。この概念は、⊕、→、≡などの他のブール演算を含む用語に拡張できますが、そのような拡張は、法律が適用される目的には不要です。このような目的には、任意のモデルとしてのブール代数の定義が含まれますブール法の法則の、そしてy∧z = z∧yからx∨(y∧z)=x∨(z∧y 導出よう古いものから新しい法則を導出するための手段として§AxiomatizingBoolean代数)。

単調な法則

ブール代数は、∨を足し算で、∧を掛け算で一致させると、通常の代数と同じ法則の多くを満たします。特に、次の法則は両方の種類の代数に共通です。[18] [19]

の結合性
の結合性
の可換性
の可換性
の分配性以上
のアイデンティティ
のアイデンティティ [20]
の消滅者

次の法則はブール代数には当てはまりますが、通常の代数には当てはまりません。

の消滅者 [20]
のべき等
のべき等
吸収1:
吸収2:
の分配性以上

上記の第3法則でx = 2を取ることは、 2×2 = 4であるため、通常の代数法則ではないことを示しています。残りの5つの法則は、すべての変数を1とすることで、通常の代数で改ざんできます。たとえば、吸収法則1では、左側は1(1 + 1)= 2であり、右側は1(等々)。

これまでに扱われたすべての法律は、論理積と論理和に関するものでした。これらの操作には、いずれかの引数を変更すると出力が変更されないままになるか、出力が入力と同じように変更されるという特性があります。同様に、変数を0から1に変更しても、出力が1から0に変更されることはありません。このプロパティを使用した操作は単調であると言われます。したがって、これまでの公理はすべて単調なブール論理に対するものでした。非単調性は、次のように補数¬を介して入ります。[5]

非単調法

補数演算は、次の2つの法則によって定義されます。

[20]

以下の法則を含む否定のすべての特性は、上記の2つの法則のみに従います。[5]

通常の代数とブール代数の両方で、否定は要素のペアを交換することによって機能します。両方の代数で、二重否定の法則(対合法則とも呼ばれます)を満たします。

しかし、通常の代数は2つの法則を満たします

ブール代数は、ド・モルガンの法則を満たしています。

完全性

上記の法則は、主題の残りの部分を伴うという意味で、ブール代数を定義します。法の補完1と2は、単調な法則とともにこの目的に十分であり、したがって、ブール代数の法則または公理化の1つの可能な完全なセットと見なすことができます。ブール代数のすべての法則は、これらの公理から論理的に続きます。さらに、ブール代数は、 §ブール代数で扱われるこれらの公理のモデルとして定義できます。

明確にするために、ブール代数のさらなる法則を書き留めることは、これらの公理の新しい結果を引き起こすことはできず、それらのモデルを除外することもできません。対照的に、すべてではないが一部の同じ法則のリストには、リストにあるものに従わなかったブール法が存在する可能性があり、さらに、ブール代数ではないリストされた法のモデルが存在する可能性があります。

この公理は、決して唯一のものではなく、公理の一部が他の公理に続くかどうかに注意を払わず、十分な法則があることに気付いたときに停止することを選択したことを考えると、必ずしも最も自然なものであり、§公理でさらに扱われますブール代数または、公理の中間概念は、ブール法をトートロジーとして直接定義することによって完全に回避できます。これは、0および1を超える変数のすべての値を保持する方程式として理解されます。[21] [22]ブール代数のこれらすべての定義は同等であることが示されます。

双対原理

原則:{X、R}が半順序集合である場合、{X、R(inverse)}も半順序集合です。

ブール代数の値の記号の選択については、魔法のようなものは何もありません。0と1の名前を変更してαβと言うことができます。これを一貫して行う限り、明らかな外観上の違いはありますが、ブール代数のままになります。

しかし、0と1の名前をそれぞれ1と0に変更するとします。その場合でも、ブール代数であり、さらに同じ値で動作します。ただし、これは元のブール代数と同じではありません。これは、∨が以前のように動作していることがわかり、その逆も同様であるためです。したがって、まだ0と1を使用しているにもかかわらず、表記をいじっていることを示すいくつかの外観上の違いがあります。

しかし、値の名前を交換することに加えて、2つの二項演算の名前も交換する場合、これまでに行ったことの痕跡はありません。最終製品は、私たちが始めたものと完全に区別できません。真理値表のx∧yx∨yのの場所が変わっていることに気付くかもしれませんがその切り替えは重要ではありません。

すべてのペアが同時に切り替えられたときに重要なものがすべて変更されないように値と操作をペアにできる場合、各ペアのメンバーを互いにデュアルと呼びます。したがって、0と1はデュアルであり、∧と∨はデュアルです。ド・モルガンの双対とも呼ばれる双対の原理は、すべての双対が交換されてもブール代数は変わらないと主張しています。

この交換の一環として行う必要がなかった変更の1つは、補完することでした。補集合は自己双対演算であると言います。IDまたは何もしない操作x(入力を出力にコピーする)も自己双対です。自己双対演算のより複雑な例は x∧y y∧z z∧xです両方の引数に依存する自己双対二項演算はありません。自己双対演算の構成は、自己双対演算です。たとえば、fxyz)= x∧y)∨(y∧z ∨(z∧x ffxy z)、xt)は、 4つの引数x y z tの自己双対演算です

双対性の原理は、グループ理論の観点から、ブール多項式のセットのそれ自体への1対1のマッピング(自己同型)である正確に4つの関数があるという事実によって説明できます:恒等関数、補数関数、デュアル機能とコントラデュアル機能(補完デュアル)。これらの4つの関数は、ブール多項式のセットに作用する、クラインの4グループと同型の関数合成の下でグループを形成します。Walter Gottschalkは、結果として、現象のより適切な名前は原理(または正方形)になるだろうと述べましたquaternalityの[23]

概略図

ベン図

ベン図[24]は、影付きの重なり合う領域を使用したブール演算の表現として使用できます。変数ごとに1つの領域があり、ここの例ではすべて円形です。領域xの内部と外部は、変数xの値1(true)と0(false)にそれぞれ対応します陰影は、領域の各組み合わせに対する操作の値を示し、暗いは1を示し、明るい0を示します(一部の作成者は反対の規則を使用します)。

下の図の3つのベン図は、それぞれ接続詞x∧y 論理和x∨y 、および補集合¬xを表します

図2.論理積、論理和、および補集合のベン図

接続詞として、両方の変数が1の場合にx∧yが1であることを示すために、両方の円の内側の領域に影が付けられます。他の3つの組み合わせでは、x∧yが0であることを示すために他の領域は影なしまま なります

2番目の図は、いずれかまたは両方の円の内側にある領域をシェーディングすることにより、論理x∨yを表しています。3番目の図は、円の内側に ない領域をシェーディングすることにより、補数¬xを表しています。

定数0と1のベン図は示していませんが、これらは些細なものであり、それぞれ白いボックスと暗いボックスであり、どちらにも円は含まれていません。ただし、これらのボックスにxの円を入れることもできます。その場合、それぞれが1つの引数xの関数を示し、定数関数と呼ばれるxとは無関係に同じ値を返します。それらの出力に関する限り、定数と定数関数は区別できません。違いは、定数はゼロまたはnullary演算と呼ばれる引数をとらないのに対し、定数関数は1つの引数を取り、それを無視し、単項演算であるということです。

ベン図は、法則を視覚化するのに役立ちます。∧と∨の可換性の法則は、図の対称性から見ることができます。xyを交換すると、図を水平方向に反映する効果があり、可換性が失敗すると、可換でない2項演算では、対称な図が得られません。その後、対称性の失敗として表示されます。

∧と∨のべき等は、2つの円を一緒にスライドさせ、∧と∨の両方について、影付きの領域が円全体になることに注意することで視覚化できます。

最初の吸収法則x∧(x∨y)= xを確認する x∨y中央図から始めて、 x共通の影付きの領域の部分がx円全体であることに注意ください2番目の吸収法則x∨ x∧y)= xの場合、 x∧yの左側の図から始めて、 x円全体をシェーディングするとのシェーディングが内側にあったため、x円だけシェーディングされることに注意してください。 x _サークル。

二重否定の法則は、x円 をシェーディングする¬xの3番目の図のシェーディングを補完することで確認できます。

最初のド・モルガンの法則(¬x)∧(¬y)=¬(x∨y)を視覚化するには、x∨y中央から始めその陰影を補完し、両方の円の外側の領域のみが陰影付けされるようにします法の右側が説明していることです。結果は、 x外側とy円の両方の外側にある領域、つまり、法則の左側で説明されている外側の接続詞 をシェーディングした場合と同じです。

2番目のドモルガンの法則(¬x ∨(¬y =¬(x∧y 2つの図を入れ替えても同じように機能します。

最初の補数の法則x∧¬x = 0は、xの内側と外側に重なりがないことを示しています。2の補数の法則x∨¬x = 1は、すべてがxの内側または外側にあることを示しています

デジタル論理ゲート

デジタル論理は、回路図を形成するために接続された論理ゲートで構成される電子ハードウェアへの0と1のブール代数の適用です各ゲートはブール演算を実装し、演算を示す形状で概略的に示されています。論理積(ANDゲート)、論理和(ORゲート)、および補数(インバーター)のゲートに関連付けられている形状は次のとおりです。[25]

左から右へ:ANDOR、およびNOTゲート。

各ゲートの左側の線は、入力ワイヤまたはポートを表しています。入力の値は、リード線の電圧で表されます。いわゆる「アクティブハイ」ロジックの場合、0はゼロまたは「グラウンド」に近い電圧で表され、1は電源電圧に近い電圧で表されます。active-lowはこれを逆にします。各ゲートの右側の線は出力ポートを表しており、通常は入力ポートと同じ電圧規則に従います。

補数はインバータゲートで実装されます。三角形は、入力を出力にコピーするだけの操作を示しています。出力の小さな円は、入力を補完する実際の反転を示します。このような円を任意のポートに配置するという規則は、このポートを通過する信号が、入力ポートか出力ポートかに関係なく、途中で補完されることを意味します。

下の図4に示すように、双対原理、またはドモルガンの法則は、ANDゲートの3つのポートすべてを補完するとORゲートに変換され、その逆も同様であると主張するものとして理解できます。ただし、インバータの両方のポートを補完すると、動作は変わりません。

DeMorganGates.GIF

より一般的には、ANDまたはORゲートの3つのポートの8つのサブセットのいずれかを補完することができます。結果として得られる16の可能性は、8つのブール演算、つまり真理値表に奇数の1を持つ演算のみを生成します。「odd-bit-out」は0または1のいずれかであり、真理値表の4つの位置のいずれかに配置できるため、このようなものは8つあります。16個のバイナリブール演算があります。これにより、真理値表に偶数の1を含む8つの演算を残す必要があります。これらのうちの2つは、定数0と1です(両方の入力を無視する二項演算として)。4つは、2つの入力の1つ、つまりxy、¬x および¬y自明ではないことに依存する操作です。残りの2つはx⊕y XOR )その補集合x≡y

ブール代数

「代数」という用語は、主語、つまり代数の主語と、オブジェクト、つまり代数的構造の両方を意味します。前述の内容はブール代数の主題を扱っていますが、このセクションでは、ブール代数と呼ばれる数学的対象を扱います。これは、ブール法の任意のモデルとして完全に一般的に定義されています。法則を参照せずに定義できる概念の特殊なケース、つまり具体的なブール代数から始めて、次に一般的な概念 の正式な定義を示します。

具体的なブール代数

具体的なブール代数または集合のフィールドは、 Xを基準にした和集合集合、および集合の集合演算の下で閉じられた、与えられた集合Xのサブセットの空でない集合です。[5]

(余談ですが、歴史的には、縮退または1要素のブール代数を除外するためにX自体も空でない必要がありました。これは、縮退代数がすべての方程式を満たすため、すべてのブール代数が同じ方程式を満たすという規則の1つの例外です。ただし、この除外は、「ブール代数」の好ましい純粋な方程式の定義と矛盾します。方程式のみを使用して1要素代数を除外する方法はありません。0≠1はカウントされず、否定された方程式です。したがって、現代の著者は縮退を許可します。ブール代数で、Xを空にします。)

1.Xすべてのサブセット構成されるXのべき集合2X ここで、 Xは任意の集合である可能性があります:空、有限、無限、または数えられない

例2.空集合X。この2要素代数は、具体的なブール代数が無限集合のサブセットで構成されている場合でも有限である可能性があることを示しています。Xのサブセットのすべてのフィールドには、空集合とXが含まれている必要があることがわかります。したがって、空集合とXを一致 させるために、 Xを空にすることによって得られる縮退代数以外に、より小さな例はあり得ません。

例3.整数の有限集合と補有限集合。ここで、補有限集合は、有限個の整数のみを省略したものです。これは、補集合の下で明らかに閉じられ、任意の集合との補有限集合の和集合が有限であるのに対し、2つの有限集合の和集合は有限であるため、和集合の下で閉じられます。交差点は、「有限」と「補有限」が入れ替わった結合のように動作します。

例4.例2で作成された点の自明ではない例として、図を2 n個の領域に分割するn個の閉じた曲線によって形成されたベン図を考え、 Xを平面上のすべての点の(無限)集合とします。曲線以外は図のどこかにあります。したがって、各領域の内部はXの無限のサブセットであり、Xすべての点は正確に1つの領域にあります。次に、すべての2 2 nの可能な領域の和集合のセット(空の領域のセットの和集合として取得された空のセットと、すべての2nの和集合として取得されたXを含む)領域)は、 Xに対して和集合、共通部分、および補集合の下で閉じられているため、具体的なブール代数を形成します。ここでも、具体的なブール代数を形成する無限集合のサブセットが有限数あります。例2は、曲線がない 場合のn = 0として発生します。

ビットベクトルとしてのサブセット

XのサブセットYは、インデックスセットXを持つインデックス付きビットファミリーで識別できます。x∈Xでインデックス付けされたビットは、x∈Yであるどうかに応じて1または0なります(これは、サブセットのいわゆる特性関数の概念です。)たとえば、32ビットのコンピューターワードは、0と31のセット{0,1,2、...、31}によってインデックス付けされた32ビットで構成されます。下位ビットと上位ビットにそれぞれインデックスを付けます。小さな例として、X = { a、b、c }の場合、a、b、cは左から右の順序でビット位置として表示され、8つのサブセット{}、{ Xのc }、{ b }、{ bc }、 { a } 、{ ac } 、{ ab }、および{ abc }は、それぞれのビットベクトル000、001で識別できます。 、010、011、100、101、110、および111。自然数のセットによってインデックス付けされたビットベクトルはビットの無限シーケンスですが、単位間隔の実数によってインデックス付けされたビットベクトルは[0,1]は密集しすぎて従来の方法で記述できませんが、それでも明確に定義されたインデックス付きファミリーを形成します(間隔[0,1]のすべてのポイントを個別に黒または白に色付けすることを想像してください。その後、黒のポイントは任意のサブセットを形成します[0,1]の)。

このビットベクトルの観点から、具体的なブール代数は、すべて同じ長さのビットベクトルの空でないセットとして同等に定義でき(より一般的には、同じセットによってインデックスが付けられます)、ビット単位の∧、∨、および¬、1010∧0110= 0010、1010∨0110 = 1110、および¬1010= 0101のように、それぞれ交差、和集合、および補数のビットベクトルの実現。

原型的なブール代数

上記で扱われた集合{0,1}とそのブール演算は、長さ1のビットベクトルの特殊なケースとして理解できます。これは、サブセットを持つビットベクトルの識別によって、1要素の2つのサブセットとしても理解できます。セットする。これを典型的なブール代数 と呼び、次の観察によって正当化されます。

すべての非縮退の具体的なブール代数によって満たされる法則は、典型的なブール代数によって満たされる法則と一致します。

この観察は次のように簡単に証明されます。確かに、すべての具体的なブール代数が満たす法則は、具体的であるため、典型的な法則によって満たされます。逆に、特定のブール代数で失敗する法則は、特定のビット位置で失敗している必要があります。その場合、その位置自体が、その法則に対する1ビットの反例を提供します。空のビットベクトルは1つしかないため、非縮退により、少なくとも1つのビット位置が確実に存在します。

次のセクションの最終的な目標は、上記の観察から「具体的な」ものを排除することとして理解できます。ただし、同型写像まではすべてのブール代数が具体的であるという驚くほど強力な観察によって、その目標を達成します。

ブール代数:定義

これまで見てきたブール代数はすべて具体的であり、ビットベクトルまたは同等にいくつかのセットのサブセットで構成されています。このようなブール代数は、ブール代数の法則を満たす ことを示すことができるセットとそのセットに対する演算で構成されます。

ブール法が満たされていることを示す代わりに、集合X 、 Xに対する2つの二項演算、および1つの単項演算を仮定し、これらの演算がブール代数の法則を満たすことを要求できます。Xの要素は、ビットベクトルまたはサブセットである必要はありませんが、何でもかまいません。これは、より一般的な抽象的な定義につながります。

ブール代数は、二項演算∧と∨、およびブール法を満たす単項演算¬を持つ任意のセットです[26]

この定義の目的のために、法定紙幣であろうと証拠であろうと、どのように操作が法律を満たすようになったのかは無関係です。すべての具体的なブール代数は法則を満たします(フラットではなく証明によって)。ここで、すべての具体的なブール代数は、私たちの定義によるとブール代数です。ブール代数の集合としてのこの公理的定義と、フィアットによる特定の法則または公理を満たす特定の操作は、現代または抽象代数に特徴的な群環などの抽象定義に完全に類似しています。

補完された 分配束の公理など、ブール代数の完全な公理を考えると、この種の代数構造がすべてのブール法則を満たすための十分な条件は、それらの公理だけを満たすことです。したがって、以下は同等の定義です。

ブール代数は、補完された分配束です。

公理化に関するセクションには、他の公理化がリストされており、それらのいずれも同等の定義の基礎にすることができます。

表現可能なブール代数

すべての具体的なブール代数はブール代数ですが、すべてのブール代数が具体的である必要はありません。n平方のない正の整数とし、整数の2乗で割り切れないものとします。たとえば30ですが、12ではありません。最大公約数最小公約数、およびnへの除算(つまり、¬x = n の演算/ x )、引数がnの正の約数を超える場合、すべてのブール法則を満たすことを示すことができますしたがって、これらの除数はブール代数を形成します。これらの約数は集合のサブセットではないため、nの約数になります。私たちの定義によれば具体的ではないブール代数。

ただし、nの各除数をその主因子のセットで表すと、この非具体的なブール代数は、 nのすべての主因子のセットで構成される具体的なブール代数と同形であり、和集合は最小公倍数の交差に対応します。最大公約数に、そしてnへの分割を補完します。したがって、この例は、技術的には具体的ではありませんが、同型写像と呼ばれる、この表現を介して少なくとも「道徳的に」具体的です。この例は、次の概念のインスタンスです。

ブール代数は、具体的なブール代数と同型である場合、表現可能と呼ばれます。

明らかな次の質問は次のように肯定的に答えられます。

すべてのブール代数は表現可能です。

つまり、同型写像までは、抽象ブール代数と具体的なブール代数は同じものです。この非常に重要な結果は、選択公理よりもわずかに弱い選択原理であるブールの素イデアル定理に依存し、ブール代数のストーンの表現定理の記事でより詳細に扱われますこの強い関係は、表現可能性の次の簡単な結果に対する前のサブセクションの観察を強化する弱い結果を意味します。

すべてのブール代数が満たす法則は、典型的なブール代数が満たす法則と一致します。

それ自体が表現可能性を意味しないという意味で、それは弱いです。ブール代数はここでは特別です。たとえば、関係代数は追加の構造を持つブール代数ですが、すべての関係代数が関係代数に適した意味で表現できるわけではありません。

ブール代数の公理化

集合としての抽象的なブール代数の上記の定義と「the」ブール法を満たす演算は、疑問を提起します、それらの法は何ですか?単純な答えは「すべてのブール法則」です。これは、0と1のブール代数を保持するすべての方程式として定義できます。このような法則は無限にあるため、実際にはそれほど満足のいく答えではなく、次の質問:保持するのに有限の数の法則だけを要求するだけで十分ですか?

ブール代数の場合、答えは「はい」です。特に、上記でリストした有限数の方程式で十分です。ブール代数は、有限に公理化可能または有限に基づいていると言います。

このリストをさらに短くすることはできますか?繰り返しますが、答えはイエスです。そもそも、上記の法則のいくつかは、他の法則のいくつかによって暗示されています。上記の法則の十分なサブセットは、結合法則、可換法則、および吸収法則のペア、∧に対する∧の分配法則(または他の分配法則-1つで十分)、および2つの補数法則で構成されます。実際、これは、補完された 分配束としてのブール代数の従来の公理化です

上記にリストされていない追加の法律を導入することにより、リストをさらに短縮することが可能になります。たとえば、垂直バーがシェファーストローク操作を表す場合、単一の公理ブール代数を完全に公理化するには十分です。より一般的な操作を使用して、より長い単一の公理を見つけることも可能です。ブール代数の最小公理を参照してください[27]

命題論理

命題論理は、ブール代数に密接に関連している論理システムです。[5] ブール代数の多くの構文概念は、表記法と用語をわずかに変更するだけで提案論理に引き継がれますが、提案論理のセマンティクスは、提案論理のトートロジー(定理)が方程式の定理に対応するようにブール代数を介して定義されますブール代数の。

構文的には、すべてのブール項は命題論理の命題式に対応します。ブール代数と命題論理の間のこの変換では、ブール変数x 、y ...は命題変数(または原子)になりますP 、Q、...、x∨yなどのブール項命題式になりますP∨Q 0はfalseになりますまたは、そして1が真になるかT一般的な命題を参照する場合、命題を表すメタ変数(命題論理について話すときに使用される、命題論理の言語外の変数)としてギリシャ語の文字Φ、Ψ、...を使用すると便利です

命題論理のセマンティクスは、真理の割り当てに依存しています。真理値の割り当ての基本的な考え方は、命題変数が固定ブール代数の要素にマップされ、これらの文字を使用する命題式の真理値は、の値を計算することによって得られるブール代数の要素であるということです。式に対応するブール項。古典的なセマンティクスでは、2要素のブール代数のみが使用されますが、ブール値のセマンティクスでは、任意のブール代数が考慮されます。トートロジーは、真理値1が割り当てられた命題式です。任意のブール代数への命題変数のすべての真理代入(または、同等に、2要素ブール代数へのすべての真理代入)によって。

これらのセマンティクスにより、命題論理のトートロジーとブール代数の等式定理の間の変換が可能になります。命題論理のすべてのトートロジーΦは、ブール代数の定理となるブール方程式Φ= 1として表すことができます。逆に、ブール代数のすべての定理Φ=Ψは、トートロジー(Φ∨¬Ψ)∧(¬Φ∨Ψ)および(Φ∧Ψ)∨(¬Φ∧¬Ψ)に対応します。→がその言語である場合、これらの最後のトートロジーは(Φ→Ψ)∧(Ψ→Φ)、または2つの別々の定理Φ→ΨおよびΨ→Φとして書くこともできます。≡が利用可能な場合、単一のトートロジーΦ≡Ψを使用できます。

アプリケーション

命題論理の動機付けとなるアプリケーションの1つは、自然言語での命題と演繹的議論の分析です。[28]命題「ifx = 3 then x +1 = 4」は、+や1などの記号の意味に依存しますが、命題「if x = 3 then x = 3」は依存しません。それは単にその構造のおかげで真実であり、「x = 3」が「 x = 4」に置き換えられても「月は緑のチーズでできている」に置き換えられても真実のままです。このトートロジーの一般的または抽象的な形式は、「if P then P」、またはブール代数の言語では「要出典]

Px = 3またはその他の命題で置き換えることは、その命題によるPのインスタンス化と呼ばれます抽象命題でPをインスタンス化した結果は、命題のインスタンスと呼ばれます。したがって、「x = 3→ x = 3」は、抽象的なトートロジー「PP」のインスタンスであるため、トートロジーです。Px = 3またはx = 3→ x = 4のようなナンセンスを回避するために、インスタンス化された変数のすべての出現は同じ命題でインスタンス化される必要があります

命題論理は、ブール演算を使用して命題変数から構築された抽象的な命題への注意を制限します。命題論理内でもインスタンス化は可能ですが、P →(QP )でQPをインスタンス化してインスタンスP →((QP)→ P)を生成するなど、抽象的な命題によって命題変数をインスタンス化することによってのみ可能です

(命題論理の機構の一部としてのインスタンス化の可用性は、通常の命題変数が任意の命題を示すために言語内で考慮されることができるので、命題論理の言語内のメタ変数の必要性を回避します。メタ変数自体はインスタンス化の範囲外です、命題論理の言語の一部ではなく、この文が書かれていることについて話すための同じ言語の一部であり、命題変数とそのインスタンス化を別個の構文エンティティとして区別できる必要があります。)

命題論理のための演繹システム

命題論理の公理化は、公理と呼ばれる一連のトートロジーと、古いものから新しいトートロジーを生成するための1つ以上の推論規則です。公理システムAの証明は、命題有限の空でないシーケンスであり、それぞれがAの公理のインスタンスであるか、証明の前半に現れる命題からのAの規則に従う(循環論法を許可しない)。最後の命題は、証明によって証明された定理です。証明の空でない最初のセグメントはすべてそれ自体が証明であり、証明のすべての命題はそれ自体が定理です。すべての定理がトートロジーである場合、公理化は健全であり、完全ですすべてのトートロジーが定理である場合。[29]

シークエント計算

命題論理は一般にヒルベルト流の体系として編成され、その演算はブール代数の操作であり、その定理はブールトートロジーであり、それらのブール項はブール定数1に等しい。別の形式は、通常のように2種類の命題を持つ連続微積分です。命題論理、およびA∨BA∧C 、..などシーケンシャル呼ばれる命題のリストのペア ABC、....シークエントの2つの半分は、それぞれ前件と後件と呼ばれます。先行詞またはその一部を示す通常のメタ変数はΓであり、後続詞の場合はΔです。したがって、Γ、A Δは、後続詞がリストΔであり、先行詞がリストΓであり、その後に追加の命題Aが追加されたシークエントを示します。前件はその命題の論理積として解釈され、後件はその命題の論理和として解釈され、後件自体は前件による後件 の含意として解釈されます。

含意は含意とは異なり、後者はブール代数で値を返す2項演算であるのに対し、前者は保持するか保持しないかのいずれかの2項関係です。この意味で、含意は、ブール代数の外部を意味する外部形式の含意であり、シークエントの読者を外部であると考え、いくつかのブール代数の先行と後続を解釈および比較します。の自然な解釈x∨y = yの場合、x≤yで定義されるブール代数の半順序でなります外部の影響を混合するこの機能そして内部含意→1つの論理では、シークエント計算と命題論理の本質的な違いの1つです。[30]

アプリケーション

2つの値の計算としてのブール代数は、コンピューター回路、コンピュータープログラミング、および数理論理学の基本であり、集合論や統計などの数学の他の分野でも使用されます。[5]

コンピュータ

20世紀初頭、数人の電気技師は、ブール代数が特定の種類の電気回路の動作に類似していることを直感的に認識しました。クロード・シャノンは、そのような振る舞いが1937年の修士論文「リレーとスイッチング回路のシンボリック分析」でブール代数と論理的に同等であることを正式に証明しました。

今日、すべての最新の汎用コンピューターは、2つの値のブール論理を使用して機能を実行します。つまり、それらの電気回路は、2つの値のブール論理の物理的な表現です。高速回路や容量性ストレージデバイスのワイヤの電圧、強磁性ストレージデバイスの磁区の向き、パンチカード紙テープの穴など、さまざまな方法でこれを実現します。(一部の初期のコンピューターは、2値論理回路の代わりに10進回路またはメカニズムを使用していました。)

もちろん、任意の媒体で3つ以上のシンボルをコーディングすることは可能です。たとえば、それぞれ0、1、2、および3ボルトを使用して、ワイヤに4シンボルのアルファベットをコーディングしたり、パンチカードにさまざまなサイズの穴をコーディングしたりできます。実際には、高速、小型、低電力という厳しい制約が組み合わさって、ノイズが主要な要因になります。これにより、単一のサイトで発生する可能性のあるシンボルが複数ある場合、シンボルを区別することが困難になります。デジタル設計者は、1本のワイヤの4つの電圧を区別しようとするのではなく、ワイヤごとに高電圧と低電圧の2つの電圧を使用することにしました。

上記の理由により、コンピューターは2値ブール回路を使用します。最も一般的なコンピュータアーキテクチャは、ビットと呼ばれる32または64値のブール値の順序付けられたシーケンスを使用します(例:01101000110101100101010101001011)。マシンコードアセンブリ言語、およびその他の特定のプログラミング言語でプログラミングする場合、プログラマはデータレジスタこれらのレジスタは電圧で動作します。ゼロボルトはブール0を表し、基準電圧(多くの場合、+ 5 V、+ 3.3 V、+ 1.8 V)はブール1を表します。このような言語は数値演算と論理演算の両方をサポートします。この文脈では、「数値」とは、コンピューターがビットのシーケンスを2進数として扱うことを意味します。(2進数を基数)、加算、減算、乗算、除算などの算術演算を実行します。「論理」とは、ビットの2つのシーケンス間の論理和、論理積、および否定のブール論理演算を指します。この場合、一方のシーケンスの各ビットは、もう一方のシーケンスの対​​応するビットと単純に比較されます。したがって、プログラマーは、必要に応じて、数値代数またはブール代数のいずれかのルールを使用して適用することができます。これらの操作ファミリ間の主要な差別化機能は、最初の操作に キャリー操作が存在するが、2番目の操作には存在しないことです。

二値論理

2つの値が適切な選択である他の領域は、法と数学です。日常のリラックスした会話では、「たぶん」や「週末だけ」などの微妙な答えや複雑な答えが受け入れられます。しかし、法廷や定理に基づく数学などのより焦点を絞った状況では、単純な「はい」または「いいえ」の答えを認めるために質問を組み立てることが有利であると見なされます。被告は有罪か無罪か、命題は真か偽か—そして他の答えを禁止する。これが回答者にとって実際に証明されるかもしれない拘束衣の多くは、単純なイエス・ノー質問の原則が司法論理と数理論理の両方の中心的な特徴になり、2つの価値のある論理をそれ自体で組織化と研究に値するものにします。

集合論の中心的な概念はメンバーシップです。現在、組織は、初心者、アソシエート、フルなど、複数のレベルのメンバーシップを許可する場合があります。ただし、セットを使用すると、要素はインまたはアウトのいずれかになります。セットのメンバーシップの候補者は、デジタルコンピューターのワイヤーと同じように機能します。各ワイヤーが高いか低いかのように、各候補者はメンバーまたは非メンバーのいずれかです。

代数は、数学的な扱いに適したあらゆる分野の基本的なツールであり、これらの考慮事項を組み合わせて、コンピューターハードウェア、数理論理学、および集合論にとって基本的に重要な2つの値の代数を作成します。

2値論理は、特にブール領域{0、1}を単位間隔[0,1]に置き換えることにより、多値論理に拡張できます。この場合、値0または1だけを取得するのではなく、との間の任意の値を取得します。 0と1を含むと想定できます。代数的に、否定(NOT)は1 −  xに置き換えられ、接続詞(AND)は乗算()、および論理和(OR)は、ド・モルガンの法則によって定義されます。これらの値を論理的真理値として解釈すると、多値論理が生成されます。これは、ファジー論理確率論理の基礎を形成します。これらの解釈では、値は真理の「程度」、つまり命題がどの程度真であるか、または命題が真である確率として解釈されます。

ブール演算

ブール演算の元々のアプリケーションは数理論理学であり、個々の数式の真理値または真理値を組み合わせています。

自然言語

英語などの自然言語には、いくつかのブール演算、特に論理積(および)、論理和(または)、否定(ではない)、および含意(含意)を表す単語があります。しかし、notはと同義であり、ではありません「ブロックはテーブルの上にある」や「猫はミルクを飲む」などの状況アサーションを組み合わせるために使用される場合、これらは素朴に真または偽のいずれかであり、これらの論理接続詞の意味多くの場合、論理的な対応物の意味を持っています。しかし、「ジムがドアを通り抜けた」などの行動の説明では、可換性の失敗などの違いに気づき始めます。たとえば、「ジムがドアを開けた」と「ジムがドアを通り抜けた」の順序は次のとおりです。そして、通常はそのような場合を意味するので、他の順序でのそれらの論理積と同等ではありません質問も同様です。「空は青いのか、なぜ空は青いのか」という順序です。逆の順序よりも理にかなっています。行動に関する接続コマンドは、服を着て学校に行くときのように、行動の主張のようなものです。私を愛したり、私を離れたり、魚を釣ったり、餌を切ったりするような選言的なコマンド1つの選択肢があまり好ましくないという含意により、非対称になる傾向があります。お茶やミルクなどの結合名詞は、一般に集合和と同じように集合を表しますが、お茶やミルクが選択されます。ただし、コンテキストはこれらの感覚を逆転させる可能性があります。これは、選択がコーヒーと紅茶であるため、通常、選択がコーヒーまたは紅茶(代替)と同じことを意味します。「ミルクが好きではない」のような二重否定は、文字通り「ミルクが好き」を意味することはめったになく、3番目の可能性があることを意味するかのように何らかのヘッジを伝えます。「Pではない」は「確かにP」と大まかに解釈できますが、Pは必然的に「 Pではない」を意味します。直観主義論理自然言語での接続詞の非常に特異な使用法を考慮すると、ブール代数はそれらを解釈するための信頼できるフレームワークとは見なされません。

デジタルロジック

ブール演算は、デジタルロジックで使用され、個々のワイヤで伝送されるビットを結合して、{0,1}を介してそれらを解釈します。n個の同一のバイナリゲートのベクトルを使用して、それぞれnビットの2つのビットベクトルを組み合わせる場合、個々のビット演算は、 2n個の要素 を持つブール代数からの値に対する単一の演算としてまとめて理解できます。

素朴集合論

ナイーブ集合論は、ブール演算を特定の集合Xのサブセットに作用するものとして解釈します。前に見たように、この動作はビットベクトルの座標ごとの組み合わせと正確に平行しており、2つのセットの和集合は2つのビットベクトルの論理和に対応します。

ビデオカード

3つのジェネレーターの256要素の自由ブール代数は、ラスターグラフィックスに基づくコンピューターディスプレイに展開されます。ラスターグラフィックスは、ビットブリットを使用してピクセルで構成される領域全体を操作し、ブール演算に依存して、ソース領域を宛先と組み合わせる方法を指定します。マスクと呼ばれる3番目の領域の助けを借りて最新のビデオカードはすべて223を提供します =この目的のための256の三項演算。演算の選択は1バイト(8ビット)パラメーターです。定数SRC = 0xaaまたは10101010、DST = 0xccまたは11001100、およびMSK = 0xf0または11110000を使用すると、(SRC ^ DST)&MSK(ソースと宛先のXOR、次にマスクを使用した結果のXORを意味する)などのブール演算を書き込むことができます。コンパイル時に計算されたバイトを表す定数として直接、(SRC ^ DST)&MSKの例では0x80、SRC ^ DSTの場合は0x88など。実行時に、ビデオカードはバイトを元の式で示されたラスター演算として解釈します。非常に少ないハードウェアを必要とし、式の複雑さに完全に関係なく時間がかかる均一な方法で。

モデリングとCAD

コンピューター支援設計用のソリッドモデリングシステムは、他のオブジェクトからオブジェクトを構築するためのさまざまな方法を提供し、ブール演算による組み合わせもその1つです。この方法では、オブジェクトが存在する空間ボクセルのセットS(2次元グラフィックスのピクセルの3次元アナログ)として理解され、形状はSのサブセットとして定義されます。、オブジェクトを和集合、交差などを介してセットとして組み合わせることができます。1つの明白な用途は、単純な形状から単純な後者の和集合として複雑な形状を構築することです。別の用途は、材料の除去として理解される彫刻です。物理的な材料に対して物理的な機械で実行できる研削、フライス盤、ルーティング、またはドリル操作は、ブール演算 x∧¬yまたはx −yを使用してコンピューター で シミュレートできます。集合論では集合差であり、xの要素からyの要素を削除しますしたがって、一方が機械加工され、もう一方が除去される材料の2つの形状が与えられた場合、前者を機械加工して後者を除去した結果は、単純にそれらのセットの差として記述されます。

ブール検索

検索エンジンのクエリもブール論理を採用しています。このアプリケーションでは、インターネット上の各Webページは「セット」の「要素」と見なすことができます。次の例では、 Googleがサポートする構文を使用しています[31]

  • ダブルクォートは、空白で区切られた単語を1つの検索語に結合するために使用されます。[32]
  • 空白は、検索語を結合するためのデフォルトの演算子であるため、論理積を指定するために使用されます。
「検索語1」「検索語2」
  • ORキーワードは、論理ORに使用されます。
「検索語1」または「検索語2」
  • 接頭辞付きのマイナス記号は、論理NOTに使用されます。
「検索語1」-「検索語2」

も参照してください

参考文献

  1. ^ ブール、ジョージ(2011-07-28)。演繹的推論の微積分に向けたエッセイであるLogicBeingの数学的分析
  2. ^ ブール、ジョージ(2003)[1854]。思想の法則の調査プロメテウスブックス。ISBN 978-1-59102-089-9
  3. ^ 「ブール代数(またはブール代数 ')の名前は、ブールによって始まり、シュレーダーによって拡張され、ホワイトヘッドによって完成されたもので、1913年にシェファーによって最初に提案されたようです。」EVハンティントン、「論理の代数のための独立した仮定の新しいセット、特にホワイトヘッドとラッセルのプリンキピア・マセマティカに関連して」、 トランス。アメル。算数。Soc。 35(1933)、274-304; 脚注、278ページ。
  4. ^ パース、チャールズS.(1931年)。収集した論文3.ハーバード大学出版局。p。13. ISBN 978-0-674-13801-8
  5. ^ a b c d e f Givant、Steven; ハルモス、ポール(2009)。ブール代数の紹介数学の学部テキスト、SpringerISBN 978-0-387-40293-2
  6. ^ レンゼン、ヴォルフガング。「ライプニッツ:論理」哲学のインターネット百科事典
  7. ^ a b cJ 。マイケルダン; ゲイリーM.ハーディグリー(2001)。哲学的論理学における代数的方法オックスフォード大学出版局米国。p。2. ISBN 978-0-19-853192-0
  8. ^ ワイスタイン、エリックW. 「ブール代数」mathworld.wolfram.com 2020年9月2日取得
  9. ^ ノーマンバラバニアン; ブラッドリーカールソン(2001)。デジタルロジック設計の原則ジョン・ワイリー。pp。39–40。ISBN 978-0-471-29351-4オンラインサンプル
  10. ^ Rajaraman&Radhakrishnan(2008-03-01)。デジタルコンピュータデザイン入門PHIラーニングPvt。株式会社p。65. ISBN 978-81-203-3409-0
  11. ^ ジョンA.カマラ(2010)。電気およびコンピュータPE試験のための電気および電子リファレンスマニュアルwww.ppi2pass.com。p。41. ISBN 978-1-59126-166-7
  12. ^ 湊真一、室賀三郎(2007)。「二分決定図」。ワイカイチェン(編)。VLSIハンドブック(第2版)。CRCプレス。ISBN 978-0-8493-4199-1第29章。
  13. ^ アランパークス(2002)。言語、機械、論理の紹介:計算可能な言語、抽象機械、形式論理スプリンガー。p。276. ISBN 978-1-85233-464-2
  14. ^ ジョン・バーワイズ; ジョン・エチェメンディ; Gerard Allwein; デイブバーカー-プランマー; アルバート劉(1999)。言語、証明、および論理CSLI出版物。ISBN 978-1-889119-08-3
  15. ^ ベンゲルツェル(1994)。混沌とした論理:複雑系科学の観点からの言語、思考、現実スプリンガー。p。48. ISBN 978-0-306-44690-0
  16. ^ ハルモス、ポール(1963)。ブール代数に関する講義。ヴァンノストランド。
  17. ^ ベーコン、ジェイソンW.(2011)。「コンピュータサイエンス315講義ノート」2021年10月1日取得
  18. ^ O'Regan、Gerard(2008)。コンピューティングの簡単な歴史スプリンガー。p。33. ISBN 978-1-84800-083-4
  19. ^ 「ブール代数の要素」www.ee.surrey.ac.uk 2020年9月2日取得
  20. ^ a b c コンピュータプログラミングのビット演算場合、1を0xFFFFとして読み取ると役立つ場合があります。2進数のすべてのビットは1でなければなりません。
  21. ^ McGee、Vann、Sentential Calculus Revisited:ブール代数(PDF)
  22. ^ * Goodstein、RL(2012)、「第4章:文論理」、ブール代数、Courier Dover Publications、ISBN 9780486154978
  23. ^ スティーブンR.ギバント; ポール・リチャード・ハルモス(2009)。ブール代数の紹介スプリンガー。pp。21–22。ISBN 978-0-387-40293-2
  24. ^ ベン、ジョン(1880年7月)。「I.命題と推論の図式的および機械的表現について」(PDF)ロンドン、エディンバラ、ダブリンのフィロソフィカルマガジンとジャーナルオブサイエンス5. 10(59):1–18。土井10.1080 / 147864480086268772017-05-16のオリジナルからアーカイブ(PDF) 。 [1] [2]
  25. ^ シャノン、クロード(1949)。「2端子スイッチング回路の合成」。ベルシステムテクニカルジャーナル28:59–98。土井10.1002 /j.1538-7305.1949.tb03624.x
  26. ^ Koppelberg、Sabine(1989)。「ブール代数の一般理論」。ブール代数のハンドブック、Vol。1(ed。J。Donald Monk with Robert Bonnet)アムステルダム:北ホラント。ISBN 978-0-444-70261-6
  27. ^ McCune、William ; ベロフ、ロバート; フィテルソン、ブランデン; ハリス、ケネス; ファイスト、アンドリュー; Wos、Larry(2002)、「ブール代数の短い単一公理」、Journal of Automated Reasoning29(1):1–16、doi10.1023 / A:1020542009983MR 1940227S2CID 207582048  
  28. ^ オールウッド、イェンス; アンダーソン、グンナー-グンナー; アンダーソン、ラーズグンナー; ダール、オステン(1977-09-15)。言語学における論理ケンブリッジ大学出版局。ISBN 978-0-521-29174-3
  29. ^ ハウスマン、アラン; ハワード・カハネ; Paul Tidman(2010)[2007]。論理と哲学:現代の紹介ワズワースセンゲージラーニング。ISBN 978-0-495-60158-6
  30. ^ ジラール、ジャン=イヴ; ポールテイラー; イヴ・ラフォント(1990)[1989]。証明とタイプケンブリッジ大学出版局(理論計算機科学のケンブリッジトラクト、7)。ISBN 978-0-521-37181-0
  31. ^ すべての検索エンジンが同じクエリ構文をサポートしているわけではありません。さらに、一部の組織(Googleなど)は、代替構文または拡張構文をサポートする「特殊な」検索エンジンを提供しています。(たとえば、構文の虎の巻参照してください。Googleコード検索は正規表現をサポートしています)。
  32. ^ 二重引用符で区切られた検索用語は、Googleのドキュメントでは「正確なフレーズ」検索と呼ばれます。

ソース

  • マノ、モリス; Ciletti、Michael D.(2013)。デジタルデザインピアソン。ISBN 978-0-13-277420-8

さらに読む

  • J.エルドンホワイトシット(1995)。ブール代数とその応用クーリエドーバー出版。ISBN 978-0-486-68483-3応用分野の学生に適した紹介。
  • ドウィンガー、フィリップ(1971)。ブール代数の紹介ヴュルツブルク:PhysicaVerlag。
  • シコルスキ、ローマ(1969)。ブール代数(3 / e ed。)ベルリン:Springer-Verlag。ISBN 978-0-387-04469-9
  • Bocheński、JózefMaria(1959)。数理論理学のプレシスオットーバードによるフランス語版とドイツ語版からの翻訳。南ホラント州ドルトレヒト:D。ライデル。

歴史的展望

外部リンク