概要
ブール代数は、19世紀にジョージ・ブールによって考案された数学的体系であり、論理演算の基礎となる重要な代数体系である。
ブール代数の概念は、値として0 (偽)と 1 (真) のみを扱い、これらの値に対して論理演算を適用することである。
主要な演算として、論理和 (OR、+で表記)、論理積 (AND、・で表記)、否定 (NOT、上線で表記) がある。
これらの演算を組み合わせることにより、複雑な論理関係を表現することができる。
交換則、結合則、分配則等があり、これらの法則を適用することにより、複雑な論理式を簡単化、等価な式に変換することができる。
例えば、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + A \cdot B = A}
という吸収則を用いる場合、冗長な論理式を簡略化することができる。
ブール代数の応用例として、デジタル回路の設計がある。
論理ゲート (AND、OR、NOT等) を組み合わせることで、加算器や記憶素子 (RS-FF) 等の複雑な回路を構築することができる。
例えば、半加算器は次の論理式で表現できる。
- 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S = A \oplus B} (和)
- 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C = A \cdot B} (桁上げ)
また、プログラミングにおいても、条件分岐や真偽値の判定にブール代数の概念が使用されているす。
データベースの検索条件の組み立てや正規表現のパターンマッチング等も、ブール代数の原理に基づいている。
ブール代数の重要な概念として、双対性がある。
任意のブール式において、ANDとORを入れ替え、0と1を入れ替えると、等価な式が得られる。
これはド・モルガンの法則 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A + B} = \overline{A} \cdot \overline{B}}
に代表される性質である。
カルノー図やクワイン・マクラスキー法等のブール式の簡単化手法も開発されており、
これらの手法を使用することで、複雑な論理回路を最適化してハードウェアの実装コストを削減することができる。
双対論理式
双対論理式は、元の式に対して以下に示す操作を行った論理式である。
- 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0 \rightarrow 1, \, \, 1 \rightarrow 0}
- 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \cdot \rightarrow +, \, \, + \rightarrow \cdot}
式 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X}
の双対論理式は 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X^d}
と表す。
例: 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x + y) \cdot z}
の双対論理式は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x \cdot y + z}
になる。
ブール代数の公式
| 交換則 | |
|---|---|
| 結合則 | |
| 分配則 | |
| 恒等則 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + 1 = 1}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot 1 = A} 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + 0 = A} 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot 0 = 0} |
| 同一則 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot A = A}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + A = A} |
| 補元則 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot \overline{A} = 0}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + \overline{A} = 1} |
| 吸収則 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + A \cdot B = A}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot (A + B) = A} |
| ド・モルガンの法則 | 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A + B} = \overline{A} \cdot \overline{B}}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A \cdot B} = \overline{A} + \overline{B}} |
