論理和標準形と論理積標準形の定義・性質・例題について
1. 論理和標準形とは
論理和標準形は、論理式を「論理積の論理和」の形で表したものです。具体的には、いくつかの「リテラル（変数やその否定）」の論理積をとり、それらの論理積の論理和をとった形式です。
\[ (\text{リテラル}_1 \land \text{リテラル}_2 \land \ldots) \lor (\text{リテラル}_3 \land \text{リテラル}_4 \land \ldots) \lor \ldots \]
論理和標準形は選言標準形とも呼ばれます。
1.1. 論理和標準形の例
\[ (A \land B) \lor (\neg C \land D) \] これは論理和標準形の一例です。各括弧内の式が論理積で、それらの論理積を論理和で結んでいます。
2. 論理積標準形とは
論理積標準形は、論理式を「論理和の論理積」の形で表したものです。具体的には、いくつかの「リテラル（変数やその否定）」の論理和をとり、それらの論理和の論理積をとった形式です。
\[ (\text{リテラル}_1 \lor \text{リテラル}_2 \lor \ldots) \land (\text{リテラル}_3 \lor \text{リテラル}_4 \lor \ldots) \land \ldots \]
論理積標準形は連言標準形とも呼ばれます。
2.1. 論理積標準形の例
次は論理積標準形の一例です。各括弧内の式が論理和で、それらの論理和を論理積で結んでいます。
\[ (A \lor \neg B) \land (C \lor D) \]
3. 標準形に変換する例題
3.1. 例題1
含意の変換を行う。
\[ (A \rightarrow B) \equiv (\neg A \lor B) \] したがって、元の式は以下のように変換されます。\[ (\neg A \lor B) \land (C \lor \neg D) \]
3.2. 例題2
\[A \rightarrow (B \lor C)\]
\[\equiv \neg A \lor (B \lor C) \]
\[\equiv \neg A \lor B \lor C \]
よって、論理和標準形を求めることができました。
3.3. 例題3
含意の規則の変換を行います。
\[ (A \land B) \rightarrow (C \lor D) \equiv \neg (A \land B) \lor (C \lor D) \]
\(\neg (A \land B)\) はド・モルガンの法則を使って分解できます。
\[ \equiv (\neg A \lor \neg B) \lor (C \lor D) \]
さらに、論理和を整理すると、次の形になります。
\[ \equiv (\neg A \lor \neg B \lor C \lor D) \]
3.4. 例題4
\[ \neg(A \rightarrow B) \rightarrow C \]
\[ \equiv \neg(\neg A \lor B) \rightarrow C \]
\[ \equiv (A \land \neg B) \rightarrow C \]
\[ \equiv \neg (A \land \neg B) \lor C \]
\[ \equiv (\neg A \lor B) \lor C \]
\[ \equiv \neg A \lor B \lor C \]
論理和標準形、論理積標準形となります。
3.5. 例題5
\[ (A \rightarrow \neg B) \land (C \rightarrow D)\]
\[ \equiv (\neg A \lor \neg B) \land (C \rightarrow D) \]
\[ \equiv (\neg A \lor \neg B) \land (\neg C \lor D) \]
この論理式は論理積標準形に変換されました。
