ブール代数は2つの値からなる等式理論のモデルである。この定義は束による定義および環による定義と同値である。
ブール代数は抽象代数学の数学的に豊かな一分野である。『スタンフォード哲学百科事典』はブール代数を「文結合子のみをもつ2値論理の代数、あるいは同値なことだが、合併と補元の下での集合の代数」と定義している。群論が群を、線型代数学がベクトル空間を扱うのと同様に、ブール代数は2つの値 0 と 1（その解釈は必ずしも数値的である必要はない）の等式理論のモデルである。ブール代数、群、ベクトル空間に共通するのは代数的構造、すなわち一定の等式を満たすいくつかの演算について閉じた集合という概念である。
整数の群 や 個の対象の置換のなす対称群 のように群に基本的な例があるのと同様に、ブール代数にも次のような基本的な例がある。
論理和・論理積・否定を含む論理演算の下での2進数字（ビット）0 と 1 の代数。応用としては命題論理やデジタル回路の理論がある。 和集合、共通部分、補集合を含む集合演算の下での集合代数。集合論は数学の標準的な基礎であるため、その応用は広範囲に及ぶ。
このようにブール代数は、抽象代数学の方法を数理論理学やデジタル論理に適用することを可能にする。
有限位数の群が複雑性と多様性を示し、その一階理論が特別な場合にのみ決定可能性 （論理学）であるのとは異なり、すべての有限ブール代数は同じ定理を共有し、決定可能な一階理論をもつ。その代わり、ブール代数の複雑さは無限代数の構造と、その統語的構造のアルゴリズム的複雑性とに分かれて現れる。
定義
ブール代数は、ブール原型（Boolean prototype）と呼ばれる極大な2元有限項代数の等式理論と、その理論のモデルであるブール代数とを扱う。これらの用語は次のように定義される。
代数とは、その代数の台集合と呼ばれる集合上の演算の族である。ブール原型の台集合は {0,1} とする。
代数が有限項的（finitary）であるとは、その各演算が有限個の引数しかとらないことをいう。原型については、演算の各引数は または であり、演算の結果も同様である。そのような極大の代数は、{0,1} 上のすべての有限項演算からなる。
各演算がとる引数の個数はその演算のアリティと呼ばれる。アリティ の {0,1} 上の演算（ 項演算）は、その 個の引数について 通りの値のいずれにも適用できる。引数の各選択に対して演算は か を返しうるので、 項演算は 個ある。
したがって原型は、引数をとらない演算（0項演算、zeroary またはヌル項演算）を2つ、すなわち0と1をもつ。単項演算は4つあり、そのうち2つは定数演算、もう1つは恒等演算であり、最もよく使われるものは否定と呼ばれ、引数の反対を返す（ なら 、 なら ）。二項演算は16個あり、やはりそのうち2つは定数演算、1つは第1引数を返し、もう1つは第2引数を返し、1つは論理積と呼ばれて両引数が1のとき1を、そうでなければ0を返し、別の1つは論理和と呼ばれて両引数が0のとき0を、そうでなければ1を返す、といった具合である。原型における 項演算の個数は 項演算の個数の2乗であるから、3項演算は 個、4項演算は 個、というように増えていく。
族は添字集合によって添字づけられる。代数をなす演算の族の場合、その添字は演算記号と呼ばれ、その代数の言語を構成する。各記号によって添字づけられた演算は、その記号の表示または解釈と呼ばれる。各演算記号はその解釈のアリティを指定するので、1つの記号のすべての可能な解釈は同じアリティをもつ。一般には、1つの代数が異なる記号を同じ演算で解釈することもありうるが、原型についてはそうではなく、その記号は演算と1対1に対応する。したがって原型は 個の 項演算記号をもち、これらはブール演算記号と呼ばれ、ブール代数の言語を構成する。慣用的な記号をもつ演算はごく少数で、否定に対する 、論理積に対する 、論理和に対する などである。以下の真理値表の節で行うように、 番目の 項記号を と表すのが便利である。
与えられた言語における等式理論は、その言語の記号を用いて変数から構成される項の間の等式からなる。ブール代数の言語における典型的な等式は 、、、 などである。
代数が等式を充足するとは、演算記号がその代数の指定するとおりに解釈されたとき、その代数における変数のすべての可能な値についてその等式が成り立つことをいう。ブール代数の法則とは、原型によって充足されるブール代数の言語における等式のことである。上の例のうち最初の3つはブール代数の法則であるが、4番目は であるからそうではない。
代数の等式理論とは、その代数によって充足されるすべての等式の集合である。したがってブール代数の法則は、ブール原型の等式理論を構成する。
理論のとは、その理論の言語における演算記号を解釈し、その理論の等式を充足する代数のことである。
ブール代数とは、ブール代数の法則の任意のモデルである。
すなわち、ブール代数とは、1つの集合と、その上のブール演算記号を解釈しブール原型と同じ法則を充足する演算の族である。
ある代数のホモローグ（homologue）を、その代数の等式理論のモデルと定義するならば、ブール代数は原型の任意のホモローグとして定義することができる。
例1。ブール原型はブール代数である。なぜなら、それは自明に自分自身の法則を充足するからである。したがってそれは原型的なブール代数である。定義に循環があるように見えることを避けるため、最初はそのように呼ばなかった。
基底
演算はすべてを明示的に述べる必要はない。基底（basis）とは、そこから残りの演算を合成によって得ることができる任意の集合のことである。「ブール代数」はいくつかの異なる基底のいずれからも定義できる。ブール代数の基底としては、束による基底、環による基底、そしてシェファーの棒記号（NAND）による基底の3つが一般に用いられる。これらの基底はそれぞれ、この主題に論理的な性格、算術的な性格、そして節約的な性格を与える。
束による基底は19世紀に、論理的思考過程の代数的形式化を求めたブール、パースらの仕事に由来する。 環による基底は20世紀にとストーンの仕事とともに現れ、抽象代数学の素養をもってこの主題に取り組む代数学者にとって選好される基底となった。ブール代数の大半の取り扱いは束による基底を前提としているが、注目すべき例外はハルモス（1963）であり、線型代数の素養をもつ彼にとって環による基底が明らかに好ましかった。 {0,1} 上のすべての有限項演算はシェファーの棒記号 NAND（あるいはその双対である NOR）によって定義できるため、結果として得られる経済的な基底はデジタル回路、特にデジタル電子回路におけるゲートアレイの解析にとって選好される基底となった。
束による基底と環による基底に共通する要素は、定数0と1、および結合的かつ可換な二項演算であり、後者は束による基底では交わりと結び 、環による基底では乗法 と呼ばれる。この区別は用語上のものにすぎない。束による基底はさらに交わりと結び と補元 という演算をもつ。環による基底は代わりに加法の算術演算 をもつ（記号 ではなく が用いられるのは、前者がときに結びというブール的な読み方をされるためである）。
基底であるとは、合成によって他のすべての演算を生み出すことであるから、任意の2つの基底は相互に翻訳可能でなければならない。束による基底は を環による基底では と、 を と翻訳する。逆に環による基底は を束による基底では と翻訳する。
これら2つの基底はいずれも、ブール演算の等式的性質の部分集合を通じてブール代数を定義することを可能にする。束による基底については、ブール代数を および を満たす分配束、すなわち相補束分配束として定義すれば十分である。環による基底はブール代数をブール環、すなわち を満たす環に変える。
エミール・ポストは、ある演算の集合が非ヌル項ブール演算の基底となるための必要十分条件を与えた。非自明な性質とは、基底を構成する演算の一部はもつが全部はもたない性質のことである。ポストは演算の非自明な性質を5つ挙げた。これらは5つのと同一視でき、それぞれ合成によって保存される。そして彼は、各性質について、その性質を欠く演算をその集合が含むならば、その演算の集合は基底をなすことを示した。（「ならば」を「であるとき、かつそのときに限り」に拡張するポストの定理の逆は、候補となる基底のすべての演算についてこれら5つの性質のいずれかが成り立つならば、その候補から合成によって作られるすべての演算についてもそれが成り立ち、したがってその性質の非自明性により候補は基底となりえない、という容易な観察である。）ポストの5つの性質は次のとおりである。
単調 — 0から1への入力の遷移が1から0への出力の遷移を引き起こすことがない。 アフィン — 双線型項以上の項を欠くで表現できる。たとえば はそうだが はそうでない。 自己双対 — すべての入力を補元にすると出力も補元になる。 や中央値演算子 、あるいはそれらの否定がそうである。 厳密（strict） — すべて0の入力を0に写す。 余厳密（costrict） — すべて1の入力を1に写す。
NAND 演算（双対的には NOR）はこれらすべてを欠くので、それ自体で基底をなす。
真理値表
{0,1} 上の有限項演算は、0と1を真理値偽および真とみなすことで真理値表として示すことができる。それらは、個々に名前を付ける（あるいは少なくとも番号を付ける）ことができるような、統一的で応用から独立した仕方で配置できる。これらの名前はブール演算の便利な略記を与える。 項演算の名前は ビットの2進数である。そのような演算は 個あるので、これ以上簡潔な命名法は望めない。なお、各有限項演算はスイッチング関数と呼ぶことができる。
この配置と付随する演算の命名を、アリティ0から2までについて完全な形で以下に示す。
+ アリティ2までのブール演算の真理値表+ 定数0 1+ 単項演算00 1 0 110 0 1 1+ 二項演算000 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1100 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1010 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1110 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
これらの表はより高いアリティへと続き、アリティ では 行をもつ。各行は 個の変数 への付値または束縛を与え、 を見出しとする各列はその付値における 番目の 項演算の値 を与える。これらの演算には変数自身も含まれる。たとえば は であり、 も（その単項版の2つのコピーとして） であり、 は（単項版をもたない） である。否定あるいは補元 は として、また として現れ、（、アリティ1では現れなかった）もある。論理和あるいは合併 は 、論理積あるいは交わり は 、含意 は 、排他的論理和（対称差） は 、差集合 は である。
内容よりも形式の面で重要な細かい点として、代数の演算は伝統的にリストとして組織される。ここではブール代数の演算を {0,1} 上の有限項演算によって添字づけているが、上記の真理値表による提示は、期せずして演算をまず第一にアリティによって、第二に各アリティにおける表の配置によって順序づけている。これにより、すべてのブール演算の集合を伝統的なリスト形式で組織することが可能になる。与えられたアリティの演算についてのリストの順序は、次の2つの規則によって決まる。
(i) 表の左半分の 番目の行は、最下位ビット（ 番目のビット）を左に置いた の2進表現である（「リトルエンディアン」順。もともとアラン・チューリングが提案したものであり、チューリング順と呼んでも不当ではない）。
(ii) 表の右半分の 番目の列は、やはりリトルエンディアン順の の2進表現である。実質的に、演算の添字はその演算の真理値表そのものである。計算可能関数のゲーデル数化との類比により、このブール演算の番号づけをブール番号づけと呼ぶことができる。
C や Java でプログラミングする際、ビットごとの論理和は x|y、論理積は x&y、否定は ~x と表記される。したがってプログラムは、たとえば演算 をこれらの言語で x&(y|z) と表現できる。あらかじめ変数への代入またはマクロの定義によって x = 0xaa、y = 0xcc、z = 0xf0 と設定しておく（「0x」は続く定数を16進数として読むことを示す）。これらの1バイト（8ビット）定数は、上記の表を3変数に拡張したときの入力変数の列に対応する。この技法は、画像を組み合わせたりマスクしたりする柔軟な多様な方法を提供するために、ラスターグラフィックスのハードウェアでほぼ普遍的に用いられており、典型的な演算は3項でソース・デスティネーション・マスクの各ビットに同時に作用する。
例
ビットベクトル
例2。与えられた長さのすべてのビットベクトルは「各点ごとに」ブール代数をなす。すなわち、任意の 項ブール演算を、 個のビットベクトルに1ビット位置ずつ適用できる。たとえば、長さ4の3つのビットベクトルの3項ORは、4つのビット位置それぞれで3つのビットのORをとって得られる長さ4のビットベクトルであり、 となる。もう1つの例は上記の 項演算の真理値表であり、その列はすべて長さ のビットベクトルであるから各点ごとに組み合わせることができ、したがって 項演算はブール代数をなす。これは有限長・無限長どちらのビットベクトルについても同様に成り立つ。唯一の規則は、「対応する位置」が well-defined であるようにビット位置がすべて同じ集合で添字づけられていることである。
そのような代数のは、ちょうど1個の1を含むビットベクトルである。一般にブール代数の原子とは、 が または という2つの値しかとらないような元 のことである。
冪集合代数
例3。冪集合代数、すなわち与えられた集合 のすべての部分集合の集合 。これは がビット位置の添字の役割を果たす、例2の言い換えにすぎない。 の任意の部分集合 は、 の元によって添字づけられるビット位置にのみ1をもつビットベクトルとみなせる。したがって全ゼロベクトルは の空部分集合であり、全1ベクトルは 自身であって、それぞれ冪集合代数の定数0と1にあたる。論理和 に対応するのは合併 であり、論理積 に対応するのは共通部分 である。否定 は に関する補集合 となる。差集合 、対称差 、3項合併 なども同様である。ここでの原子は一元集合、すなわちちょうど1個の元をもつ部分集合である。
例2と例3は、直積と呼ばれる代数の一般的な構成の特別な場合であり、これはブール代数だけでなく群や環を含むあらゆる種類の代数に適用できる。添字集合 （必ずしも有限や可算である必要はない）を動く についてのブール代数の族 の直積は、 番目の要素が から取られるすべての 組 からなるブール代数である。直積の演算は、それぞれの座標内で作用する構成代数の対応する演算である。特に、積の演算 は、 のすべての について、 個の組の 番目の座標にある 個の元に の演算 を適用することで、 個の 組に作用する。
このようにして掛け合わされる代数がすべて同じ代数 であるとき、その直積を の直冪と呼ぶ。すべての32ビットビットベクトルのブール代数は二元ブール代数の32乗、すなわち32元集合の冪集合代数であり、 と表される。すべての整数の集合のブール代数は である。ここまでに挙げたブール代数はすべて二元ブール代数の直冪であり、「冪集合代数」という名称を正当化している。
表現定理
すべての有限ブール代数は何らかの冪集合代数と同型であることが示せる。したがって有限ブール代数の濃度（元の個数）は の冪、すなわち のいずれかである。これは、有限ブール代数を冪集合代数として表現することでその本性に洞察を与えるため、表現定理と呼ばれる。
この表現定理は無限ブール代数には拡張されない。すべての冪集合代数はブール代数であるが、すべてのブール代数が冪集合代数と同型である必要はない。特に、可算無限の冪集合代数は存在しえない（最小の無限冪集合代数は自然数の集合の冪集合代数 であり、カントールによって非可算であることが示された）のに対し、可算無限のブール代数はさまざまなものが存在する。
冪集合代数を超えて進むには別の構成が必要である。代数 の部分代数とは、 の演算について閉じた の任意の部分集合のことである。ブール代数 のすべての部分代数は、 について成り立つ等式を依然として充足しなければならない。なぜなら、いかなる違反も 自身にとっての違反となるからである。したがってブール代数のすべての部分代数はブール代数である。
冪集合代数の部分代数は集合体 （数学）と呼ばれる。同値なことだが、集合体とはある集合 の部分集合の集まりで、空集合と を含み、有限合併と に関する補集合について閉じている（したがって有限共通部分についても閉じている）もののことである。ブール代数に対するストーンの表現定理は、すべてのブール代数が集合体と同型であることを述べている。さて、多様体に対するバーコフのHSP定理は、代数の類 の等式理論のモデルの任意の類は、 の代数の直積の部分代数の準同型像である、と述べられる。通常はH・S・Pの3つすべてが必要である。これら2つのバーコフの定理のうち最初のものが示すのは、ブール代数の多様体という特別な場合には準同型を同型で置き換えられるということである。したがって一般の多様体に対するバーコフのHSP定理は、ブール代数の多様体 （普遍代数学）に対してはバーコフのISP定理となる。
その他の例
自然数の集合 X について語るときには、 であるとき、かつそのときに限り となるようなビットの列 とみなすのが便利である。この見方は冪集合代数 の部分代数について語ることを容易にし、この見方のもとでそれはすべてのビット列のブール代数となる。これは真理値表の列ともよく適合する。列を上から下へ読むとビット列をなすが、同時にその列が表す関数が1と評価されるような付値（表の左半分における変数への割り当て）の集合とみなすこともできる。
例4。最終的に定数となる列。最終的に定数となる列の任意のブール結合は最終的に定数となるので、これらはブール代数をなす。最終的に0となる列を非負の2進数（列のビット が下位ビット）とみなし、最終的に1となる列を負の2進数（全1列を とする2の補数演算を考えよ）とみなすことで、これらを整数と同一視できる。これにより整数はブール代数となり、合併はビットごとのOR、補元は である。整数は可算個しかないので、この無限ブール代数は可算である。原子は2の冪、すなわち1, 2, 4, ... である。この代数を記述する別の方法は、自然数のすべての有限集合と補有限集合の集まりとして述べることであり、最終的に全1となる列が補有限集合（有限個の自然数のみを除いた集合）に対応する。
例5。周期列。列が周期的であるとは、すべての について となるような、周期性の証拠と呼ばれる数 が存在することをいう。周期列の周期とはその最小の証拠である。否定は周期を変えず、2つの周期列の論理和は周期的であり、その周期は高々2つの引数の周期の最小公倍数である（任意の列とその補元の合併のように、周期が と小さくなることもある）。したがって周期列はブール代数をなす。
例5は可算である点で例4に似ているが、原子をもたない点で異なる。後者は、任意の非零周期列 と互いに素な周期（1より大きい）をもつ列との論理積が でも でもないためである。すべての可算無限の原子をもたないブール代数は同型であること、すなわち同型を除いてそのような代数は1つしかないことが示せる。
例6。周期が2の冪である周期列。これは例5の真の部分代数である（真の部分代数は自身とその代数との共通部分に等しい）。これらは有限項演算として理解でき、そのような列の最初の周期がそれが表す演算の真理値表を与える。たとえば二項演算の表における の真理値表、すなわち は周期 をもつ（したがって第1変数しか使っていないと認識できる）が、二項演算のうち12個は周期 をもつ。周期が であるとき、その演算は最初の 個の変数にしか依存せず、この意味でその演算は有限項的である。この例もまた可算無限の原子をもたないブール代数である。したがって例5は自分自身の真の部分代数と同型である。例6、したがって例5は、可算個の生成元上の自由ブール代数、すなわち可算無限個の生成元あるいは変数の集合上のすべての有限項演算のブール代数をなす。
例7。最終的に周期的となる列、すなわち最初の有限の無法則な部分の後に周期的となる列。これらは例5の真の拡大をなし（つまり例5は例7の真の部分代数である）、また定数列は周期1で周期的であるから例4の真の拡大でもある。列が落ち着く時点はさまざまでありうるが、任意の有限個の列は、最も遅く落ち着くものより遅くなることなくすべて最終的に落ち着くので、最終的に周期的となる列はすべてのブール演算について閉じており、したがってブール代数をなす。この例は例4と同じ原子および余原子をもつので、原子をもたないわけではなく、したがって例5・6とは同型でない。しかしそれは無限の原子をもたない部分代数、すなわち例5を含むので、例4とも同型ではない。例4のすべての部分代数は有限集合とその補集合のブール代数でなければならず、したがって原子的だからである。この例は例4と例5の直積と同型であり、これが別の記述を与える。
例8。周期列（例5）と任意の有限だが自明でないブール代数との直積。（自明な一元ブール代数は唯一の有限な原子をもたないブール代数である。）これは原子と原子をもたない部分代数の両方をもつ点で例7に似ているが、原子が有限個しかない点で異なる。例8は実際には無限個の例からなる族であり、原子の可能な有限個数それぞれに1つずつ対応する。
これらの例は、可算なものに限っても、可能なブール代数を尽くしているわけではない。実際、同型でない可算ブール代数は非可算個存在し、Jussi Ketonen(1978) はそれらをある種の遺伝的可算集合によって表現される不変量によって完全に分類した。
ブール演算のブール代数
項ブール演算それ自体が冪集合代数 をなす。すなわち、 を 個の入力の 通りの付値の集合ととったときである。 を2進で表したものが真理値表の1つの列であるような演算の命名系 の観点からいえば、それらの列は任意のアリティのブール演算によって組み合わせて、表に現れる他の列を作り出せる。すなわち、任意の と について、アリティ の任意のブール演算をアリティ の 個のブール演算に適用して、アリティ のブール演算を得ることができる。
この規約のソフトウェアおよびハードウェアにとっての実際上の意義は、 項ブール演算を適当な長さの語として表現できるということである。たとえば256個の3項ブール演算はそれぞれ符号なし1バイトとして表現できる。そして AND や OR といった利用可能な論理演算を用いて新しい演算を作ることができる。、、（ここでは添字付き変数を省く）をそれぞれ 、、（10進で170, 204, 240、16進で , , ）とすると、それらの対ごとの論理積は 、、 であり、対ごとの論理和は 、、 である。3つの論理積の論理和は であり、これはたまたま3つの論理和の論理積でもある。こうして我々は、バイトに対する十数回の論理演算によって、2つの3項演算
と
が実際には同じ演算であることを計算した。すなわち、二元ブール代数について等式恒等式
を証明したのである。「ブール代数」の定義により、この恒等式はしたがってすべてのブール代数において成り立たなければならない。
ちなみにこの3項演算は、Grau(1947) の3項ブール代数の基礎をなし、彼はこの演算と否定によってそれを公理化した。この演算は対称的である。すなわちその値は引数の 通りの置換のいずれにも依存しない。その真理値表 の2つの半分は の真理値表 と の真理値表 であるから、この演算は「もし ならば 、そうでなければ 」と言い表せる。対称的であるから、「もし ならば 、そうでなければ 」、あるいは「もし ならば 、そうでなければ 」とも同様に言い表せる。8頂点の3次元立方体のラベル付けとみると、上半分が1、下半分が0とラベル付けされる。このため、これは中央値演算子と呼ばれ、任意の奇数個の変数への明白な一般化をもつ（ちょうど半数の変数が0のときの同点を避けるために奇数とする）。
ブール代数の公理化
ブール代数の恒等式を証明するために今用いた技法は、ブール論理の等式的法則に対する健全かつ完全な公理化あるいは公理系とみなせる仕方で、すべての恒等式へ体系的に一般化できる。公理系の慣用的な定式化は、いくつかの初期的な恒等式によって「呼び水を差す」公理の集合と、公理および既に証明された恒等式から残りの恒等式を導くための推論規則の集合とからなる。原理的には公理は有限個であることが望ましいが、実際上はその必要はない。無限個の実例をもつ有限の公理図式をもち、証明において使われる各実例が正当な実例であることを容易に検証できれば同じだけ有効だからであり、ここではその方針を採る。
ブール恒等式とは という形の主張であり、ここで と は 項項、すなわちここでは変数が から までに限られる項を意味する。 項項とは原子か適用のいずれかである。適用 とは、 項演算 と、被演算子と呼ばれる 個の 項項のリスト（ 組） との対である。
すべての項には高さと呼ばれる自然数が伴う。原子の高さは0であり、適用の高さは最も高い被演算子の高さに1を加えたものである。
さて原子とは何か。慣例的には原子は定数（0か1）か、 なる変数 である。ここでの証明技法にとっては、原子を代わりに 項演算 と定義するのが便利である。これはここでは原子として扱われるが、正確な形 の通常の項と同じ意味である（「正確な」とは、変数が繰り返しや省略なしに示された順に並べられていなければならないという意味）。これは制限ではない。この形の原子は通常の原子をすべて含むからである。すなわち定数0と1は各 について 項演算 と （ を と略記）として現れ、変数 は真理値表から見てとれるように現れる（ は単項演算 としても二項演算 としても現れ、 は として現れる）。
次の公理図式と3つの推論規則が、n 項項のブール代数を公理化する。
A1。。ここで であり、 は の転置で と定義される。 R1。前提なしに を導く。 R2。 と から を導く。ここで , , は 項項である。 R3。 から を導く。ここですべての項 は 項である。
A1 の付帯条件の意味は、 が、 番目のビットが の 番目のビットであるような ビットの数だということである。各量の範囲は 、、、 である。（したがって は ビット数の 組であり、 の転置である は ビット数の 組である。ゆえに と はいずれも ビットを含む。）
A1 が公理ではなく公理図式であるのは、メタ変数、すなわち , , , および から を含むからである。公理化の実際の公理は、メタ変数に具体的な値を設定することで得られる。たとえば とすると、 と から の2ビットを計算でき、（2ビット数として書けば ）となる。得られる実例 は、二重否定というよく知られた公理 を表している。すると規則 R3 により、 を すなわち 、 を すなわち 、 を すなわち ととることで を導ける。
各 と について、A1 を具体化する公理は有限個、すなわち 個しかない。各実例は ビットで指定される。