論理式
論理演算:真と偽の二つの元(真理値)だけを持つ集合における演算。
真理値表:変数の全ての組み合わせについてどのような論理値になるか示した表。
論理式:論理変数と論理記号をある規則に従って並べた記号の列。
ブール代数(論理代数):二つの値(0と1)と三つの基本演算(AND OR NOT)で論理式を表す。
0…偽、1…真。NAD…論理積,・、OR…論理和,+、NOT…否定,A
真理値表
A | B | AND | OR | NAND | NOR | XNOR |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 0 | 0 | 0 |
A・0=1、A+1=1、A・1=A、A+0=A、A・A=A、A+A=A。
A=A、A・A=A・A=0、A+A=A+A=1。
交換則:A・B=B・A、A+B=B+A。
分配則:A+B・C=(A+B)・(A+C)、A・(B+C)=A・B+A・C。
ド・モルガンの定理:A+B=A・B、A・B=A+B。
標準展開
論理関数を論理積の論理和(加法標準形)や論理和の論理積(乗法標準形)の形に展開することを標準展開という。
この時各項は変数かその否定があらわれるのみで、論理和や論理積の否定などは含まれない。
標準展開によって最小項の論理和で表された形を主加法標準形とよび、最大項の論理積で表された形を主乗法標準形と呼ぶ。
f(A,B,C)=AB+C(論理積・省略)
=(AB+C)(A+A)(B+B)(C+C)
=ABC+ABC+AB C+ABC+A B C(主加法標準形)
f(A,B,C)=(A+B+C)(A+B+C)(A+B+C)(主乗法標準形)
カルノー図
カルノー図は下記のような論理式を簡略化するための図(表)。ブール代数の公式を使って数式で簡略化するよりも、感覚的にできるので広く使われている。マス目の隣同士の真偽値が1つだけ違うように配置する。
例:AB+C
カルノー図
AB+C=ABC+ABC+AB C+ABC+A B C
真理値表
ABC | AB+C |
---|---|
000 | 1 |
001 | 0 |
010 | 1 |
011 | 0 |
100 | 1 |
101 | 0 |
110 | 1 |
111 | 1 |
主加法標準形ABC+ABC+AB C+AB C+A B C
関数値が1の最小項の論理和
主乗法標準形(A+B+C)(A+B+C)(A+B+C)
関数値が0の最小項の論理積
ABC+ABC+AB C+ABC+A B Cについてカルノー図を書く(各項目の場所に1を入れる)と容易に簡略型AB+Cを得る。