論理代数を学ぼう


  1. 論理代数とは


    論理代数は、0と1のみを定数とし、論理積(AND), 論理和(OR), 論理否定(not) を演算とする代数系です。
     この代数系の特徴は論理式を用いて計算機の回路(ディジタル回路)の基本となる論理回路の動作を表現できることです。2進数で足し算や大小比較をする論理回路を合成することができます。また、論理式をそのまま計算するスイッチ回路を作成することができます。

  2. 論理演算を理解しよう


    1. 論理演算

      論理代数は値として0,1の二つの値のみをとる代数系で、・(AND:論理積)、+(OR:論理和)、^(NOT:論理否定)の三種の演算を持ちます。 ・ と +は二項演算、^ は単項演算であり、下表のように定義されます。演算子の優先順序は ^、・、+ の順とします。 表の先頭の行と列が演算される値で、表の中が演算した値です。
      論理和は A または B どちらか一方(A or B)が1のとき、1となりますから OR 演算、論理積は A と B (A and B)どちらも1なら結果は1となりますから AND 演算とよばれます。また、論理否定は逆(not)の値をとりますから NOT 演算とよばれます。
      論理和 論理積 否定
       0  1
      0  0  1
      1  1  1
       0  1
      0  0  0
      1  0  1
       0  1
       1  0

       
    2. 論理演算の例

      演算は論理否定、論理積、論理和の順に行います。(..)があれば、その計算を優先します。
      0 + 0 = 0,  0 + 1 = 1,  1 + 1 = 1
      0・0 = 0,  0 ・ 1 = 0,  1 ・ 1 = 1
      ^0 = 1,  ^1 = 0
      これを組み合わせると、
      1・0 + ^0・1 = 0 + 1・1 = 0 + 1 = 1
      ^(1・0 + 1) = ^1= 0

    3. 問題

      次の計算をしなさい。( ) がある場合、その値を先に計算します。
       1 ・ ( ^0 + 0) =
      ^(0 + 1) ・ (0 + ^1) =

  3. 論理変数と論理式


    1. 論理変数とは

      A,B,C..を0または1を表す論理変数とします。0との論理積は相手が0でも 1 でも 0 となりますから
           A ・ 0 = 0 
      となります。同様に 0 と論理和しても値は変化しませんから
           A + 0 = A 
      となります。

    2. 論理式

      論理変数を演算すると論理式ができます。括弧がない場合、演算の順序は、否定、論理積、論理和の順とします。
      論理積は論理和に優先して演算されますから、
        (A・B) + ((^C)・D) = A・B + ^C・D
      と書くことができます。

    3. 問題2

      各変数がとりうるすべての値の組に対し、次の論理式の値を求めなさい。2変数の場合4通りあります。
       ^A・B + A・^B
       A・B + ^A・^B

    4. 論理式のパラドックス(逆理)

      1. パラドックス
        結果はおかしいのだが、なぜおかしいのか、簡単には説明できない問題のことです。

      2. 問題
         1 + 0 = 1 + 1
        ですね。で、両辺から、同じ数1をとります。すると、
         0 = 1 !!
        どこが、おかしいのかな?

      3. 両辺から同じ数が削除できるのは
         A + B = A + C
        普通の代数で、両辺から同じ数が削除できるのは、両辺に -A を加えて、0にできるからです。
         -A + A + B =-A + A + C
        0 + B = 0 + C
        論理式で、1 を削除するには、 1 + X = 0 となる X が必要です。このような数がなければ、1 を削除できないのです。論理和、論理積、否定演算と{0,1} から構成される論理式は、これまでの数学の手法は通用しません。

      4. 排他的論理和と代数系

        和の演算には、排他的論理和 ◎ があります。これは、1 ◎ 1 = 0 とする以外、論理和と同じです。この演算を用いると、通常の計算ができ、論理積を積演算として、連列方程式を解くこともできます。
        (この話を拡張すると、「群」や「体」の話になります)。
        論理和、論理積を用いた代数系は、「体」ではなく「束」になります。

  4. 基本公式


    1. 定数と変数

      論理式では定数と変数の間に次の性質があります
      零元   A・0 = 0 A+0 = A 
      単位元 A・1 = A A+1 = 1
      べき等律 A・A = A A+A = A
      補元律  A・^A=0 A +(^A)=1

    2. 基本的性質

      論理式では次の公式が成立します。
      交換律 A・B = B・A A+B = B+A
      結合律 A・(B・C) = (A・B)・C A+(B+C) = (A+B)+C 
      分配律 A・(B+C) = A・B+A・C A+(B・C) = (A+B)・(A+C)

    3. 分配律の証明(しらみつぶし法で証明できる)

      A・(B+C)=A・B+A・C を証明します。論理代数では、変数の取る値が限られていますからすべての場合を調べることで証明ができます。

      1. 完全しらみつぶし法による証明
        A,B,Cはそれぞれ0と1しか値をとりませんから、すべての場合(8通り)を尽くせば証明になります。

      2. 部分的なしらみつぶしによる証明
        各変数は0または1しか値をとりません。
        A=0 の場合、左辺は0、右辺も0ですから成立します。
        A=1 の場合、左辺は(B+C)で右辺もB+Cですから、この場合も成立します。
        Aは0と1しか値をとりませんから、これで証明できたことになります。

      3. 問題
        しらみつぶし法で次の式を証明しなさい。
         A+(B・C) = (A+B)・(A+C)

    4. 演習 C言語の論理演算

      すべてのA,B,Cの値に対し、以下の式を計算する C言語プログラムの式を書きなさい。
       X = A・B + ^A・^B
       Y = A・B・C + A・^B・C +  A・B・^C

      ヒント C言語では、論理和は | 、論理積は & 、論理否定は ! 記号で表現します。
        X=A・B + ^A・^B は X = A & B  |  !A  &  !B
      です。

  5. ド・モルガンの定理を理解しよう


    1. 括弧式の否定は

      いよいよ、論理代数最大のハイライトである ド・モルガン の定理を紹介します。
      ^(A + B)のように、括弧のついた式の否定を含む式の括弧をはずす方法を考えます。直感的には
       ^(A + B) = ^A + ^B ------(これは誤り)
      と考えがちですが、これは誤りです。例えば、Aを1、Bを0としたとき左辺は
       ^( 1 + 0 ) = 0
      ですが、右辺は
       ^1 + ^0 = 0 + 1 = 1
      となります。
      論理式の最も重要な性質として、次のド・モルガン(De Morgan:人名)の定理を紹介します。否定のついた括弧をはずすには、このド・モルガンの定理を使います。

    2. これがド・モルガンの定理

      括弧付の ^ の括弧をはずすと、論理和と論理積が入れ替わるという、一見とんでもないことがおこります。
        ^(A ・ B) = ^ A + ^B  
        ^(A + B) = ^A ・ ^B

      1. [証明1]
         ^(A・B) = ^ A+^B を証明します。
        補元律より X・Y = 0 なら ^X = Y となります。X = A・B、Y =^ A + ^B として
          (A・B) ・ (^A + ^B) = ( A・B・^A) + (A・B・^B) = 0
        ですから、^(A・B) = (^A+^B) となります。

      2. [証明2:代入法]
        A=1 なら 左辺は ^B、右辺は 0 + ^B ですから成立します。
        A=0 の場合、左辺は ^0 = 1、右辺は 1 + ^B = 1 となり、やはり、成立します。
        この証明の方法を代入法と呼びます。

    3. ド・モルガンの定理の他の解釈

      ド・モルガンの定理は、論理積と論理和は両者を独立な演算と考えると、一見奇妙に見えるかも知れませんが、次のように考えると納得できるでしょう。論理和、論理積の表を見なおして下さい。論理積は 1 に注目すると、”各項が共に 1 のときのみ結果が 1”です。
      しかし、見方を逆にして 0 に注目しますと、”少なくとも一つの項が 0 であれば結果は 0 である”とも読めます。すなわち、論理積は 0 に注目すれば”論理和”を意味しています。論理否定は 1 と 0の逆転をしていますから、”少なくとも一つの項が 1 でなければ出力は 1 でない”となります。この二つの表現はドモルガンの公式に対応します。

    4. 論理和と論理積は表と裏の関係

       ド・モルガンの定理は論理和と論理積が独立ではなく、論理和は論理否定と論理積から計算できることを意味します。すなわち、ド・モルガンの公式の両辺の 論理否定 をとると
        ^(^(A・B)) = A ・ B = ^(^A + ^B) 
      となります。したがって、各項の論理否定をとってから論理和し、その結果を論理否定をすれば、結果は論理積と同じになります。

    5. ド・モルガンの定理を用いて括弧をはずします。

        ^(A・B +B・^C) = ^(A・B)・^(B・^C) = (^A + ^B)・(^B + C)
       = ^A .^B + ^A .C + ^B + ^B .C

  6. 課題


    1. ド・モルガン

      次の式の( )をはずして、展開しなさい。
      ^(A + B + C)=
       ヒント:x = A+B として、x + C を展開し、その後、x を展開します。

      ^(A + B・^C) =
       注意:演算子の優先順位に注意して下さい。x = B・^C として、まず、A + x を展開します。

      ^((A +B ) ・ ^(A + C))=
      ^( C + D ・ ^E + F)=

      計算過程を含めて、答えをA4用紙に記入し、次回の講義の開始前に講義の教卓に提出して下さい。

    2. アンケート

      1:正しくない等式はどれか
      1:A + ^A = 1 2:A・B + A*^B = A  3:^( A ・ B) = ^A * ^B

      2:^((A + B) ・ C) と等しいのは
      1:^A・ ^B + ^C 2:^(A + B) ・ ^C  3:~A・^B + ^C  4:わからん

      3:論理代数は
      1:あもしろい 2:おもしろそー 3:なんだろう  4:わからん

      4:論理(スイッチ)回路の実験
      1:やってみたい  2:できるかな  3:話がよい 4:実験嫌い

トップに戻る