この記事は，ブール代数と論理関数について自分が知らなかったことをまとめたメモです．
Turning Completeをプレイしているうちに自分の知識が足りないと感じ，勉強しました．
この記事は，自分用のメモなので勉強したいならうさぎ先生ととり先生の計算機工学の動画を見るとよいと思います．
ブール代数の公理と定理と性質
ブール代数
ブール代数は以下の公理と定理が成り立つ．
線が引かれている式は忘れがちな式．
- 交換則 x・y = y ・x，x+y = y+x
- 補元則 x・(not x) = 0，x+(not x) =1
- 対合則 not(not x) = x
- べき等則 x・x = x，x+x = x
- 単位原則 x・1 = x，x+0 = x
- 零原則 x・0 = 0，x+1 = 1
- 吸収則 x+x・y = x，x・(x+y) = x
- 名前はないがよく使う式 x+(not x)・y = x+y，x((not x)+y) = xy
- 結合則 (x・y)・z = x・(y・z)，(x+y)+z = x+(y+z)
- 分配則 x・(y+z) = xy+xz，x+(y・z) = (x+y)・(x+z)
- ド・モルガン (not x)・(not y) = x+y，(not x)+(not y) = x・y
演算順序は算術演算と同じ．()→論理積→論理和
双対性
上の公理と定理で双対性が成立する．
ここで双対性について説明する．
双対性
ブール代数では，一般にある公理・定理の論理式と論理和，0と1を置き換えて得られる公理・定理は必ず成立する性質．
逆元の有無
算術演算の積和には，逆元は存在した．(必ずx・1/x=1，x+(-x)=0)
しかし，論理積と論理和には逆元は存在しない．
すべてのxに対し，x・y = 1となるyは存在せず，すべてのxに対し，x+y = 0となるyも存在しない．
つまり，これらの逆元は存在しない．
そして重要なのが，「逆元がないので論理積，論理和は移行できない．」ということだ．
もっというと，逆元がないということは，式の項を打ち消すことができないので移行はできないということだ．
当たり前かと思うかもしれないが，実はこれから後で出てくるEORには逆元が存在するため，移行することができるのだ．そのためここで触れておいた．
逆元
演算をすると必ずその演算の単位元になる元のこと．
例．x+(-x) = 0，x・1/x = 1 (x≠0)
充足可能性
充足可能性
論理関数f(x1,x2,…xn)についてf(x1,x2,…xn) = 1となる変数値x1,x2,…xnの組が存在するとき関数fは充足可能であるという．逆に存在しないとき関数fは充足不能であるという．
(真理値表ですべての行が0のとき，充足不能)
変数の数が増えると充足可能性を確認するのは難しくなる．
論理関数の性質
双対関数
前でやった双対性に関して，式で表すと下のようにあらわされる．
双対関数
次式を満たす論理関数gを論理関数fの双対関数いう．
g(x1,x2,…xn) = not(f(not(x1),not(x2),…not(xn)))
つまり，入力と出力のどちらにもNOTをとった関数を双対関数という．
例．x・yとx+yは互いに双対関数
ド・モルガン則より
x・y = not(not(x)+not(y))
x+y = not(not(x)・not(y))
双対関数かどうかは真理値表から簡単に調べることができる．
以下の性質を利用する．
ある関数の真理値表を上から順に，その双対関数の表を下から順に読んだとき，同じ番目に必ずお互いに反転した値が出現する．
これを使えば，双対関数かどうか判断することができる．
例．x・yとx+y
下はANDとORの真理値表である．
ANDは上から読むと 0001
ORは下から読むと 1110
よって，x・yとx+yは互いに双対関数であることが分かった．
自己双対関数
自己双対関数
論理関数fの双対関数がfであるとき，fを自己双対関数という．
f(x1,x2,…xn) = not(f(not(x1),not(x2),…not(xn)))
つまり，双対関数が自身である関数のこと．
自己双対関数の例：多数決関数
出力を上から読むと00010111
出力を下から読むと11101000
よって自己双対関数である．
自己反双対関数
自己反双対関数
次式を満たす論理関数fを自己反双対関数という．
f(x1,x2,…xn) = f(not(x1),not(x2),…not(xn)) ・・・(＊)
（右辺全体の否定がない）
自己反双対関数の真理値表は上から読んでも下から読んでも同じになる．
つまり，真理値表の真ん中から対称的になるのが自己反双対関数である．
また，自己反双対関数の双対関数は以下の式のようになる．
(＊)より
not(f(not(x1),not(x2),…not(xn))) = not(f(x1,x2,…xn))
つまり，自己反双対関数の双対関数は自身の否定である．
例．下の真理値表
下の真理値表を
上から読んでも，下から読んでも10011001
また，真ん中で対称である．1001｜1001
対称関数
論理関数f(x1,…,xi,…,xj,…,xn)についてすべての変数値x1,x2,…xnに対して，f(x1,…,xi,…,xj,…,xn)=f(x1,…,xj,…,xi,…,xn)であるならfは”変数xi,xjにおいて対称である”という．
対称関数
論理関数fがすべての変数の組おいて対称であるときfを対称関数と呼ぶ．
多数決関数や論理積，論理和も対称関数である．(論理積，論理和は交換則が成り立つため自明)
対称関数の値は1である入力の数だけによって決まる．
下は多数決関数を1である入力数に着目した真理値表である．
しきい値関数
対称関数の例としてしきい値関数がある．
しきい値関数
1の入力数がある値（しきい値）以上なら1となる関数をしきい値関数とよぶ．
実は，論理積と論理和，多数決関数もしきい値である．
論理積は，しきい値2のしきい値関数
論理和は，しきい値1のしきい値関数
多数決関数は，しきい値が過半数以上のしきい値関数
NPN同値
ある関数に関する定理を証明 → 双対関数についても同様の定理が成立する
NPN同値
一部または全部の変数値，あるいは関数全体に否定を付けたり，変数を入れ替えることで同じになる関数の集合
論理式の大小関係
論理関数f,gを考えるすべての変数値についてf(・・・) = g(・・・)またはf(・・・) < g(・・・)ならばgはfをカバーすると呼びf≦gとあらわす．
すべての論理式に大小関係があるわけではない．
論理関数fはf自身をカバーする．f≦f
以下の3式は同値である．
f ≦ g⇔f+g = g ⇔ f・g = f
論理関数f(x1,…,xi,…,xn)について
f(x1,…,0,…,xn) ≦ f(x1,…,1,…,xn)であるならfは”変数xiにおいて単調増加である”という
f(x1,…,1,…,xn) ≦ f(x1,…,0,…,xn)であるならfは”変数xiにおいて単調減少である”という
fが変数xiにおいて単調増加または単調減少であるならfは”変数xiにおいてユネイトである”という
すべての変数において論理関数f(x1,…,xn)が単調増加のとき，fを単調増加関数であるという
すべての変数において論理関数f(x1,…,xn)が単調減少のとき，fを単調減少であるという
単調増加関数の例：多数決関数，しきい値関数
「反対者が賛成回ったら可決が否決になった」なんてことはない．
主加法標準形と主乗法標準形
最小項
すべての変数またはその否定を用いた積項を最小項とよぶ．
すべての最小項について真理値表中，1となる行は1行しかない
上の下線部の性質とORを用いることで，あらゆる論理関数を最小項の和(積和)で表せる．
そのような表し方を主加法標準形という．
最大項
すべての変数またはその否定を用いた和項を最大項とよぶ．
すべての最大項について真理値表中，0となる行は1行しかない
上の下線部の性質とANDを用いることで，あらゆる論理関数を最大項の積(和積)で表せる．
そのような表し方を主乗法標準形という．
排他的論理和 XOR
XORの公理と定理
公理や定理は少し覚えにくいかもしれないが，XORを「繰り上がりがある論理和」「同じものを入力されたら0を返す」と考えたら，覚えやすいかも．
- 交換則 x⊕y = y⊕x
- 単位原則 x⊕0 = x
零原則 x⊕1 = not xは成り立つべき等則 x⊕x = 0は成り立つ- 結合則 (x⊕y)⊕z = x⊕(y⊕z)
- 分配則 x(y⊕z) = (xy)⊕(xz)
ANDとORの双対性
逆元の有無
そして，前でも言った通り排他的論理和では逆元が存在するため，移行が可能である．
排他的論理和ではxの逆元はx自身である．
x⊕a = b ⇔ x = b⊕a
XORの性質
2変数の排他的論理和は自己反双対関数
2変数の排他的論理和は自己反双対関数
双対関数は自身の否定：(not x) ⊕ (not y)
排他的論理和は対称関数
XORは交換則が成立するため対称関数である．
排他的論理和をAND，OR，NOTで表す
x⊕y = x(not y) + (not x)y (積和)
x⊕y = ((not x)+(not y))・(x+y) (和積)
上の式はカルノー図を用いれば変形できる．
ブログを書く上で参考にしたもの
コメント