論理代数の概要
定義と基本的な対象
論理代数は、二値的な「真／偽」のような要素を扱うための代数的枠組みである。対象は、論理値の集合と、その上で定義される演算（否定、積、和など）であり、これらにより論理式を形式的に変形できる。目的は、論理式の同値性を体系的に判定し、計算や設計で生じる表現の無駄を取り除くことである。
この分野では、論理演算が満たす恒等式や法則を基盤にして、複雑な論理関数をより扱いやすい形へ導く。結果として、離散数学としての厳密性と、工学的な計算効率の双方を得ることができる。
主要な論理演算
否定（NOT）
否定は、真偽を反転する操作として定義される。一般に、入力が「真」なら出力は「偽」、入力が「偽」なら出力は「真」となる。論理回路では反転ゲートに相当し、論理式の中では一項演算として扱われる。
否定は他の演算とも相互作用し、吸収や補元といった性質、ならびに後述する双対性（交換による同型性）を通じて、式変形の道具になる。
論理積（AND）
論理積は、二つの入力がともに真であるときのみ真とする演算である。片方でも偽なら結果は偽となる。集合論的に見ると交差に近い振る舞いを示し、論理式では乗法的な記法（しばしば積記号やアンド記号）で表される。
回路では「どちらの条件も満たす」ことを表し、組合せ論理の構成要素として頻出する。
論理和（OR）
論理和は、二つの入力の少なくとも一方が真なら真とする演算である。両方が偽の場合だけ結果が偽となる。論理式では和として表記され、回路では「いずれかの条件が成立する」場合を表現する。
積と和は対になる役割を持ち、分配則などの関係により互いの表現を変換できる。
真理値と論理式の扱い
真理値は、論理演算の入力・出力として機能する離散的な値である。最も基本的には、真理値は二値に限られ、論理関数は入力の組に対して出力の真偽を決める対応として定義される。
論理式は、変数と論理演算で構成される構文的対象であり、評価規則により具体的な入力に対して真理値を与える。さらに、論理式同士の等価性は、すべての入力組に対して出力が一致するという意味で定義されるため、代数的な変形を通じて効率よく検証できる。
ブール代数（論理代数）の公理と性質
ブール代数としての定式化
ブール代数は、論理演算の性質を満たすことにより、論理式変形の正しさを保証する代数として定式化される。集合の要素は真理値に相当し、演算として積・和・否定が与えられる。加えて、特定の要素として単位元と零元が導入される。
この枠組みの利点は、論理回路や論理関数の最適化が、代数的な恒等式の適用として理解できる点にある。
一意な単位元・零元
単位元は、積や和に対して「計算を変えない」役割を持つ要素である。たとえば論理積に関して単位となる要素は、他の要素との積が変化しないような性質を持つ。一方、零元は、いずれと組み合わせても結果を固定する要素として振る舞う。
これらは公理または導出によって一意に定まり、ブール代数内で定数として用いられる。論理表現では「常に真」「常に偽」を与える定数に対応する。
基本法則と恒等式
可換・結合・分配
可換律は、積や和の順序を入れ替えても結果が変わらないことを保証する。結合律は、複数演算の括弧の置き方による違いをなくす。分配則は、積と和の間の相互変換を可能にし、より大きな式を別の構造へ組み替えるための基盤になる。
これらの法則により、論理式は木構造としての括弧や順序の違いを吸収しつつ、必要な変形だけを行えるようになる。
吸収則・冪等律・補元律
吸収則は、ある形で冗長に見える部分が式全体の値に影響しないことを示す。冪等律は、同じ変数を繰り返しても結果が変わらないことを述べる。補元律は、変数とその否定を組み合わせたときに、一定の結果（単位元や零元）へ帰着することを表す。
これらの恒等式は、簡約や正準形への変換の際に中心的な役割を果たす。特に冗長な節を取り除く操作として重要である。
双対性と恒等変形
双対性は、積と和、または単位元と零元を交換するような対応を行っても、恒等式の真偽が保たれるという考え方である。したがって、一つの法則の「積・和の入れ替え」を行うことで、そのまま別の法則が得られる。
恒等変形は、この性質に基づき、論理式を正しさの保証された手順で書き換えることを指す。論理関数の同値性を保ちながら、評価や実装に適した形へと導くことができる。
論理関数の表現
真理値表による表現
真理値表は、入力変数の値のすべての組に対して出力を列挙した表である。入力の数が増えると行数は指数的に増えるため、大規模な関数では直接の列挙が現実的でない場合もあるが、定義としては完全であり等価性の判定に使える。
また、真理値表から論理式を構成する方向の手法（後述の正準形への変換）にもつながる。
論理式（構文）の表現
論理式による表現では、変数と演算記号の組を用いて構造的に関数を表す。式は、評価規則により具体的な入力に対する真理値を決定する。真理値表と異なり、変数数や演算の構造に依存した形で保存されるため、簡約や最適化の対象となりやすい。
さらに、式の同値性は代数的法則を用いて確認できる。これにより、回路実装の観点ではゲート数や段数に関する改善が可能になる。
正準形（標準形）
論理積の標準形（積の標準形）
積の標準形（積和標準形の一種として扱われることが多い）は、論理関数を「積（AND）の形でまとめた項の和（OR）」として表す形である。具体的には、各項が変数やその否定の論理積からなり、それらを論理和で結ぶ構造を取る。
この形は、真理値表から機械的に構成でき、出力が真となる入力組に対応する項だけを残すといった直観的な対応がある。
論理和の標準形（和の標準形）
和の標準形（和積標準形の一種として扱われることが多い）は、逆向きの発想で、各項を和（OR）の形にし、それらを積（AND）で結ぶ構造として表す。項は変数とその否定から構成され、出力が偽となる入力組に対応する条件を押さえる形になる。
標準形は冗長になりやすいが、変換や簡約の出発点として有用である。またカルノー図などの視覚手法と組み合わせると効率よく最適化できる。
論理式の簡約と回路応用
簡約の目的と評価指標
簡約は、論理式が計算する関数を変えずに、式の複雑さを減らす作業である。目的は、回路におけるゲート数の削減、段数の短縮、あるいは読みやすさの向上などにある。評価指標としては、演算の総数、積項や和項の数、必要な反転数などが用いられる。
簡約により、同じ論理仕様でも実装コストが下がるため、設計プロセスで重要な位置を占める。
カルノー図による簡約
まとめ方の基本手順
カルノー図は、真理値表の情報を二次元配置として視覚化し、隣接関係を利用して項をまとめる簡約手法である。手順としては、入力組に対応するマスを出力が真（または偽）になる場合にマーキングし、隣り合うマスのグループを作る。
グループの大きさに応じて項の変数数が減るため、必要条件を満たす範囲で最大のまとまりを選ぶのが基本となる。結果として、冗長なリテラル（変数またはその否定）の数が削減され、簡潔な論理式が得られる。
ブール代数による代数的簡約
ド・モルガンの法則の活用
代数的簡約では、恒等式を繰り返し適用して式を整理する。特にド・モルガンの法則は、否定と積・和の関係を結びつけ、否定の位置を移動させるために用いられる。これにより、カルノー図で得た形に近づけたり、演算の対称性を使って項をまとめやすくしたりできる。
また、否定を吸収・冪等・補元と組み合わせることで、同じ入力パターンを直接表す形から冗長な要素を除去する道が開ける。
論理回路への対応
関数とゲートの対応
論理関数は、演算記号の並びとしてゲートのネットワークに対応付けられる。否定は反転ゲート、論理積はANDゲート、論理和はORゲートとして実装される。したがって、論理式の構造は、回路の配線とゲートの種類・接続関係に対応する。
この対応により、式の簡約はゲート数や接続の削減へ直結する。さらに、同値変形を通じて機能を保持したまま回路を改善できるため、代数的手法が実装設計の根拠になる。
回路最適化の考え方
回路最適化では、簡約された論理式を回路に写像したときのコストを評価する。目標は、必要ゲートの総量だけでなく、信号伝搬遅延（段数）、反転の数、配線の複雑さなども含むことが多い。
簡約により項が減ると、自然にゲート削減につながる一方、表現の形によっては反転ゲートが増える場合もある。そのため、代数的な簡潔さだけでなく、実装の制約とバランスを取りながら設計を進めるのが一般的である。