選言標準形

選言標準形（Disjunctive Normal Form, DNF）とは、数理論理学において、ブール論理における論理式を特定の形式に標準化する手法の一つです。具体的には、一つ以上のリテラルの論理積（AND）を、一つ以上の論理和（OR）で結合した形式で論理式を表します。別名として、加法標準形、主加法標準形、積和標準形とも呼ばれます。

DNFの概要

DNFの論理式は、複数の「連言節」と呼ばれる論理積のグループを、論理和で結合した構造を持ちます。ここで、連言節は一つ以上のリテラル（変数またはその否定）から構成されます。DNFでは、使用できる論理演算子は、論理積（AND）、論理和（OR）、そして否定（NOT）のみです。

以下に、DNFの例を示します。

`A ∨ B` （AまたはB）
`A` （A）
`(A ∧ B) ∨ C` （AかつB、またはC）
`(A ∧ ¬B ∧ ¬C) ∨ (¬D ∧ E ∧ F)` （AかつBでなくCでない、またはDでなくEかつF）

これらの例のように、DNFでは否定演算子（¬）はリテラルにのみ適用され、論理式の最も外側の演算子がNOTになることはありません。また、OR演算子がAND演算子よりも内側に来ることもありません。

リテラルと標準項

リテラルとは、変数（命題）またはその否定を指します。DNFでは、否定演算子はこの形式でのみ使用されます。全ての変数（またはその否定）を含む論理式を標準項と呼び、特に、全ての変数（またはその否定）の論理積の形になっている項を最小項と呼びます。

最小項の論理和で表される論理式は、DNFの形式に合致します。この形式は、真理値表において出力が「真」となる行を、それぞれ最小項として取り出し、それらを論理和で結合したものです。これにより、真理値表で表現される全ての論理関数を、選言標準形で表現できることが保証されます。この特性から、組み合わせ回路などの設計にも応用されています。

DNFへの変換

任意の論理式をDNFに変換するには、以下の法則を適用します。

1. 二重否定の除去: `¬¬A`を`A`に変換
2. ド・モルガンの法則: `¬(A ∨ B)`を`¬A ∧ ¬B`に、`¬(A ∧ B)`を`¬A ∨ ¬B`に変換
3. 分配法則: `A ∧ (B ∨ C)`を`(A ∧ B) ∨ (A ∧ C)`に変換

これらの変換を用いることで、全ての論理式はDNFに変換できます。ただし、変換後の論理式が元の論理式よりも非常に長大になる場合もあります。例えば、以下の論理式をDNFに変換すると、2n個の項が必要になります。

`(X1 ∨ Y1) ∧ (X2 ∨ Y2) ∧ ... ∧ (Xn ∨ Yn)`

DNFの形式文法

DNFの形式文法は以下のように定義できます。

`` → `∨`
`` → `∧`
`` → `¬`
`` → ``
`` → `` `` ``
`` → ``
`` → `(` `` ``)`
`` → ``
`` → ``

ここで、``は任意の変数です。

関連事項

リード-マラー標準形
ブール関数
ブール値関数
連言標準形 (CNF)
ホーン節
クワイン・マクラスキー法
真理値表

選言標準形は、論理式の構造を明確にする上で重要な概念であり、様々な分野で応用されています。

もう一度検索