ブール代数と論理演算  (2)
Boolean algebra & logical operation

■ ブール代数の基本的な性質

  ブール代数の演算において基本となる公理および法則をまとめたものを次に示す.
A +  1  =  1 A ·  1  =  A ・・・(1) 単位元
A +  0  =  A A ·  0  =  0・・・(2) 零元
A A   =  1 A · A   =  0・・・(3) 補元
A B  =  B A A · B  =  B · A ・・・(4) 交換律
A + ( B · C ) = ( A B ) · ( A C ) A · ( B C ) = ( A · B ) + ( A · C )・・・(5) 分配律
A + ( B C )  =  ( A B ) + C A · ( B · C )  =  ( A · B ) · C ・・・(6) 結合律
A + ( A · B )  =  A A · ( A B )  =  A ・・・(7) 吸収律
A + B  =  A  ·  B A · B  =  A B ・・・(8) ド・モルガンの法則
二重否定
A  =  A

・・・(9) 対合(二重否定)
A A  =  A A · A  =  A ・・・(10) べき等
(   + :論理和 OR ,  ·  :論理積 AND ,     :否定 NOT   )
(1) 単位元ブール代数では 1 が単位元である.命題変数と 1 との論理和(OR)は 1 であり,論理積(AND)はその命題変数と同一である.
(2) 零元ブール代数では 0 が零元である.命題変数と 0 との論理和(OR)はその命題変数と同一であり,論理積(AND)は 0 である.
(3) 補元命題変数とその否定の命題変数は補元の関係にあるという.命題変数とその補元との論理和(OR)は 1 であり,論理積(AND)は 0 である.
(4) 交換律論理和(OR)の演算または論理積(AND)の演算において,それぞれの命題変数を交換しても同じである.
(5) 分配律複数の命題変数の項からなる論理演算の組み合わせにより,項を分配することができる.
(6) 結合律論理和(OR)の演算または論理積(AND)の演算において,それぞれの命題変数の計算の優先順位(結合)を変えても同じである.
(7) 吸収律複数の命題変数の項からなる論理演算の組み合わせにより,項を吸収することができる.
(8) ド・モルガンの法則複数の命題変数の論理積(AND)全体の否定(NOT)は命題変数それぞれの否定(NOT)の論理和(OR)と等しく,複数の命題変数の論理和(OR)全体の否定(NOT)は命題変数それぞれの否定(NOT)の論理積(AND)と等しい.このことは否定(NOT)と組み合わせることで論理和(OR)と論理積(AND)が変換可能であることを示している.
(9) 対合(二重否定)命題変数の否定(NOT)の否定(NOT)は,元に戻ってその命題変数と同一である.
(10) べき等同じ命題変数同士の論理和(OR)あるいは論理積(AND)は,その命題変数と同一である.

■ 基本論理演算と拡張論理演算

  ブール代数では,NOT,OR,AND の3つが基本的な演算であるが, これらを組み合わせて拡張した演算も考えられる. 電子回路上でよく利用される拡張論理演算としては「否定論理積 NAND:not-and 」があり, 論理演算でよく利用される拡張論理演算としては 「排他的論理和 XOR:exclusive-or 」が挙げられる.
否定論理積 NAND:not-and fNAND( A, B ) =   A · B
=   A B
排他的論理和 XOR:exclusive-or fXOR( A, B ) =   ( A · B ) + ( A · B )
=   ( A B ) · ( A B )

  NOT,OR,AND の3つの演算は「NAND」だけを用いて変換することもできる. すなわち,任意の論理関数は NAND のみで表現できることを示している.
  実は電子回路をトランジスタ等の電子部品で設計する場合に AND や OR は 出力を反転(否定)する回路が必要となり複雑なものとなるが,NAND や NOR(not-or) は 否定回路が必要ないため構造がシンプルになり工業的に大量生産しやすい. そのため,実際の電子部品(IC等)では,NOT,OR,AND の回路を NAND の 組み合わせで設計されているものも多い.
否定 NOT fNOT( A ) =   fNAND( A, A ) NANDによるNOT表現
論理和 OR fOR( A, B ) =   fNAND( fNAND( A, A ),   fNAND( B, B ) ) NANDによるOR表現
論理積 AND fAND( A, B ) =   fNAND( fNAND( A, B ),   fNAND( A, B ) ) NANDによるAND表現

  排他的論理和 XOR は,否定 NOT によく似た性質を持っている.ある変数に対して NOT の「する」「しない」を制御したいときには,ある変数 A と 0 との XOR は A のままで変化しないが, A と 1 との XOR は A ( A の否定)となる.
  また,ある変数 A B の XOR の結果に対してさらに B と XOR をすると,その結果は元の A に戻る.すなわち同じ変数で XOR を2回繰り返すと二重否定と同様に元に戻る.

■ 2変数の論理演算一覧表

  ブール代数で基本となる2変数の論理演算を次の表に整理している. 3変数以上の演算は全てこれら2変数の演算の組み合わせで実現できる.

A
B
0  1  0  1
0  0  1  1
論理演算の名称と説明
f0( A, B )0  0  0  00恒偽(常に 0 )
f1( A, B )0  0  0  1 A · B 論理積 A AND B
f2( A, B )0  0  1  0 A · B
f3( A, B )0  0  1  1 B
f4( A, B )0  1  0  0 A · B
f5( A, B )0  1  0  1 A
f6( A, B )0  1  1  0A · B ) + ( A · B  )排他的論理和 (exclusive-or) A XOR B
f7( A, B )0  1  1  1 A + B 論理和 A OR B
f8( A, B )1  0  0  0  A + B  否定論理和 (not-or) A NOR B = NOT(A OR B)
f9( A, B )1  0  0  1( A + B  ) · ( A + B )同値,等価 (equivalence) A EQV B = NOT(A XOR B)
f10( A, B )1  0  1  0  A  否定 NOT A
f11( A, B )1  0  1  1 A B 含意 (implication) A IMP B
f12( A, B )1  1  0  0  B  否定 NOT B
f13( A, B )1  1  0  1 A B 含意 (implication) B IMP A
f14( A, B )1  1  1  0  A · B  否定論理積 (not-and) A NAND B = NOT(A AND B)
f15( A, B )1  1  1  11恒真(常に 1 )

【練習問題】

1. 否定論理和(NOR)は   fNOR( A, B ) = A + B   である.次の論理演算について,NOR のみを用いた式に変換せよ.

(1)  
NOT

(2)  
OR

(3)  
AND

2. 次に示す真理値表と同じ論理演算の関数について,MIL記号による回路図を NAND NANDゲート のみを用いて描画せよ.
A   B f ( A, B )
0   0
0   1
1   0
1   1
1
0
0
1

<前 [  1  |  2  ]

Copyright © NAKAGAWA Masao 2006-2017 All Rights Reserved


[ ビット演算(2進数の論理演算) ]
[ ビット演算(排他的論理和 XOR) ]
[ 複数ビットの加算 ]
[ 複数ビットの減算 ]
[ 2進数とビット操作 (ドットパターンの表現) ] 
[ ブール代数と論理演算 ]
[ 付表:2進数・8進数・16進数 ]
[ 付表:2の補数表現 ]
[ 教材・資料(情報教育用) ]
[ 情報科学・システム工学(中川雅央) ]