リテラル(一つの変数またはその補元)のみからなる積を基本積と呼ぶ.
例:
基本積が各リテラルを一つずつ含んでいるとき, それを最小項と呼ぶ.
例: X,Y,ZX,Y,ZX,Y,Zのみが与えられた場合;
論理関数が基本積の和で表される時, 積和形をなしているという
積和形の全ての基本積が最小項である場合, その積和形を主加法標準形 という.
例: X,YX,YX,Yのみが与えられた場合;
F=A‾BC‾+AB‾C+A B C F = \overline{A}B\overline{C} + A\overline{B}C+ A\,B\,C F=ABC+ABC+ABC
これらの記号を入れ替えた関係のこと
ここでは論理積と論理和だけを考えればよい.
論理積と論理和には次のような関係が成り立つ.
このことをDe Morganの双対性(De Morganの定理)と呼ぶ
論理関数F(A,B,…,N)F(A, B, \ldots , N)F(A,B,…,N) があるとき, 式中のリテラル(変数とその補元)以外の各記号を双対となる記号に置き換えた関数を双対関数と呼び, F∗(A,B,…,N)F^*(A, B, \ldots , N)F∗(A,B,…,N) と書くことにする.
F1(A,B)=A+B‾F_1(A,B) = A + \overline{B}F1(A,B)=A+B の時, 双対関数は F1∗(A,B)=A⋅B‾F_1^{*}(A,B) = A \cdot\overline{B}F1∗(A,B)=A⋅B
F2(A,B,C)=A⋅B+C‾F_2(A,B,C) = A\cdot\overline{B+C}F2(A,B,C)=A⋅B+C の時, 双対関数は F2∗(A,B,C)=A+B⋅C‾F_2^{*}(A,B,C) = A +\overline{B\cdot C}F2∗(A,B,C)=A+B⋅C
注意: 一般に, 双対関数は元の関数と一致しない.
最大項のみからなる和積形をした論理関数(主加法標準形の双対)
注意: ある主加法標準形の双対関数となる主乗法標準形を作っても, 同値な論理式になるとは限らない.
論理関数FFFが自己双対であるとは,
が成り立つことである.
あるいは次のように言い換えても良い.
F(X,Y,Z)=X Y+Y Z‾+X Z‾F(X,Y,Z) = X\,Y + Y\,\overline{Z}+X\,\overline{Z}F(X,Y,Z)=XY+YZ+XZの双対関数は
F∗(X,Y,Z)=(X+Y)(Y+Z‾)(X+Z‾)F^*(X,Y,Z) = (X+Y)(Y+\overline{Z}) (X+\overline{Z}) F∗(X,Y,Z)=(X+Y)(Y+Z)(X+Z)
これは変形させると
(XY+Y+XZ‾+YZ‾)(X+Z‾)=XY+XZ‾+XYZ‾+YZ‾=X Y+Y Z‾+X Z‾\begin{aligned} (XY+ Y + X\overline{Z} + Y\overline{Z} )(X + \overline{Z}) &= XY + X\overline{Z} + XY\overline{Z} + Y\overline{Z}\\ &= X\,Y + Y\,\overline{Z}+X\,\overline{Z} \end{aligned} (XY+Y+XZ+YZ)(X+Z)=XY+XZ+XYZ+YZ=XY+YZ+XZ
よって, F(X,Y,Z)F(X,Y,Z)F(X,Y,Z)は自己双対関数である.
F(A,B,C,…,N)F(A,B,C,\ldots,N)F(A,B,C,…,N)の双対関数をF∗(A,B,C,…,N)F^*(A,B,C,\ldots,N)F∗(A,B,C,…,N)と書くことにする. この時, 以下が常に成り立つ.
F(A,B,C,…,N)‾=F∗(A‾,B‾,C‾,…,N‾)\overline{F(A,B,C,\ldots,N)} = F^*(\overline{A}, \overline{B}, \overline{C},\ldots,\overline{N}) F(A,B,C,…,N)=F∗(A,B,C,…,N)
この一般化は双対定理とも呼ぶ.