基礎ブール方程式を解く

基礎ブール方程式を解く
未知変数yを
独立変数x1,…,xnの
陽関数の形で求める
定理“０和”
•  A+B=0⇔A=0,B=0…(0和)
←は明らか
→は？
A=A・(A+B)∵　吸収
=A・0=0　∵　零元
Bも同様
補題“XOR”
•  X=Y⇔X’・Y+X・Y’=0…(XOR)
→は明らか
X’・Y+X・Y’=X’・X+X・X’=0∵　補元
←は？
X’・Y+X・Y’=0ならば，定理“０和”より，
X’・Y=X・Y’=0
X=X+0=X+X’・Y=(X+X’)・(X+Y)=1・(X+Y)=X+Y
=(X+Y)・1=(X+Y)・(Y’+Y)=X・Y’+Y=0+Y=Y
１°　任意のブール方程式
をF(y)=0の方程式に
•  yを含む任意のブール等式
L=R…(1)
（L,Rは独立変数x1,…,xnとyを含むブール式、
ただし、y=(yを含まない式)の形ではない）
•  F(y)=(左辺)’(右辺)+(左辺)(右辺)’とおくと、
補題“XOR”より、
F(y)=L’・R+L・R’=0…(☆1)
２°　F(0),F(1)を求める
•  F(0),F(1)を計算する
（独立変数x1,…,xnのみを含む式になる）
•  （参考）☆１は標準方程式に整理できる
F(0)・y’+F(1)・y=0…(☆2)
３°　解の存在確認
•  方程式☆2（☆1）に解があるのは
F(0)・F(1)=0…(☆3)
のとき、かつこのときに限る。
•  これが確認できれば、次に進む。
４°　yの一般解を求める
•  yの一般解は
y=F(0)+α・F(1)’
ただし、αはx1,…,xnの任意の関数
基礎ブール方程式　例１
x+y=x・y
１°　F(y)=0の方程式を作る
•  与式
x+y=x・y…(1)
•  F(y)=(左辺)’(右辺)+(左辺)(右辺)’とおいて、
F(y)=(x+y)’・(x・y)+(x+y)・(x・y)’=0…(☆1)
２°　F(0),F(1)を求める
•  F(0),F(1)を計算する
F(0)=(x+0)’・(x・0)+(x+0)・(x・0)’=x
F(1)=(x+1)’・(x・1)+(x+1)・(x・1)’=x’
３°　解の存在確認
•  解の存在条件
F(0)・F(1)
=x・x’=0…(☆3)
•  式☆3が成立するので、解が存在する
４°　yの一般解を求める
•  yの一般解は
y=F(0)+α・F(1)’
=x+α・x’’
=x+α・x∵　復元
=x∵　吸収

Download Report