數位邏輯學-第三章



3.3布林代數的基本定理與假設


  布林代數是處理數位邏輯的代數運算式,布林定理(Boolean Theorems)就是根據邏輯運算原理整理而得的布林恆等式。我們可利用這些布林恆等式來化簡複雜的布林代數運算式,而得到簡化的邏輯關係。表3.3.1是單變數的布林恆等是,表3.3.2則是多變數的布林恆等式。

表3.3.1 布林代數基本定理(單變數定理)

基本定理 加法運算 乘法運算
對偶定理 A+0=A A.1=A
吸收定理 A+1=1 A.0=0
全等定理 A+A=A A.A=A
補數定理 A+A1.gif (144 bytes) =1 A. A1.gif (144 bytes) =0
自補定理 A2.gif (148 bytes)=A

 

  1. 對偶定理( Duality Theorem):加法對偶定理是一變數(A)與0執行邏輯加法(OR)運算,其運算結果都等於原來值(A)。乘法對偶定理是一變數(A)與1執行邏輯乘法(AND)運算,其運算結果都等於原來值(A)。

     

    加法對偶定理:A+0=A
    乘法對偶定理:A.1=A

    例3.1 利用真值表證明加法與乘法對偶定理,並畫出等效邏輯閘。

    真值表

    加法對偶定理真值表

    A 0 A+0
    0 0 0
    1 0 1
    乘法對偶定理真值表
    A 1 A.1
    0 1 0
    1 1 1
    等效閘
    1-1.gif (601 bytes)
    加法對偶定理等效閘
    1-2.gif (550 bytes)
    乘法對偶定理等效閘
     

     

  2. 吸收定理(Absorbtive Theorem):加法吸收定理是一變數(A)與1執行邏輯加法(OR)運算其運算結果都等於1。乘法吸收定理是一變數(A)與0執行邏輯乘法(AND)運算,其運算結果都等於0。

    加法吸收定理:A+1=1
    乘法吸收定理:A.0=0

    例3.2 利用真值表證明加法與乘法吸收定理,並畫出等效邏輯閘。

    真值表
    加法吸收定理真值表
    A 1 A+1
    0 1 1
    1 1 1
    乘法吸收定理真值表
    A 0 A.0
    0 0 0
    1 0 0
    等效閘 2-1.gif (559 bytes) 2-2.gif (578 bytes)
    加法吸收定理等效閘 乘法吸收定理等效閘

     

  3. 全等定理(Equal Theorem):加法全等定理是一變數(A)與其本身執行邏輯加法(OR)運算,其運算結果都等於原來值(A)。同理,乘法全等定理是一變數(A)與其本身執行邏輯乘法(AND)運算,其運算結果都等於原來值(A)。
    加法全等定理:A+A=A
    乘法全等定理:A.A=A

    例3.3 利用真值表證明加法與乘法全等定理,並畫出等效邏輯閘。

    真值表
    加法全等定理真值表
    A A A+A
    0 0 0
    1 1 1
    乘法全等定理真值表
    A A A.A
    0 0 0
    1 1 1
    等效閘 3-1.gif (588 bytes) 3-2.gif (559 bytes)
    加法全等定理等效閘 乘法全等定理等效閘
     

     

  4. 補數定理(Complementary Theorem):加法補數定理是一變數(A)與反函數(A1.gif (144 bytes))執行邏輯加法(OR)運算,其運算結果都等於1。同理,乘法補數定理是一變數(A)與反函數(A1.gif (144 bytes))執行邏輯乘法(AND)運算,其運算結果都等於0。
    加法補數定理:A+A1.gif (144 bytes)=1
    乘法補數定理:A.A1.gif (144 bytes)=0

    例3.4 利用真值表證明加法與乘法補數定理,並畫出等效邏輯閘。

    真值表
    加法補數定理真值表
    A A1.gif (144 bytes) A+A1.gif (144 bytes)
    0 1 1
    1 0 1
    乘法補數定理真值表
    A A1.gif (144 bytes) A.A1.gif (144 bytes)
    0 1 0
    1 0 0
    等效閘 4-1.gif (586 bytes) 4-2.gif (592 bytes)
    加法補數定理等效閘 乘法補數定理等效閘
     

     

  5. 自補定理(Involution Theorem):自補定理是一變數(A)經二次邏輯補數運算(NOT)後,其運算結果等於原來值(A)。
    自補定理:A1.gif (144 bytes)=A

    例3.5 利用真值表證明自補定理,並畫出此定理的等效邏輯閘。

    真值表
    自補定理真值表
    A A1.gif (144 bytes) A2.gif (148 bytes)
    0 1 0
    1 0 1
    等效閘 5-1-1.gif (791 bytes)
    自補定理等效閘
表3.3.2 布林代數定律與多變數定理

定律 加法運算 乘法運算
交換律 A+B=B+A AB=BA
結合律 A+(B+C)=(A+B)+C=A+B+C A(BC)=(AB)C=ABC
分配律 A+(BC)=(A+B)(A+C) A(B+C)=AB+AC
消去律 A+AB=A A(A+B)=A
狄摩根定理 E5.gif (365 bytes) E6.gif (357 bytes)
  1. 交換律(Commutative laws):交換律是指二個變數(AB)在執行邏輯加法(OR)運算或邏輯乘法(AND)運算時,這二個變數(AB)的先後順序並不影響執行的結果。
    加法交換律:A+B=B+A
    乘法交換律:AB=BA

    例3.6 利用真值表證明加法與乘法交換律,並畫出等效邏輯閘。

    真值表
    輸入 加法交換律 乘法交換律
    A B A+B B+A AB BA
    0 0 0 0 0 0
    0 1 1 1 0 0
    1 0 1 1 0 0
    1 1 1 1 1 1
    等效閘 E7.gif (1096 bytes)

    加法交換律等效閘

    E8.gif (1038 bytes)

    乘法交換律等效閘

     

     

  2. 結合律(Associative laws):是指三個變數(ABC)在執行三變數邏輯加法或乘法運算時,可先執行其中二變數的邏輯加法(A+BB+CA+C)或乘法(ABBCAC)後,其結果在與另一變數(CAB)執行邏輯加法或乘法運算,且執行結果與直接執行三變數的邏輯加法或乘法運算相同。
    加法結合律:A+(B+C)=(A+B)+C=A+B+C
    乘法結合律:A(BC)=(AB)C=ABC

    例3.7 利用真值表證明加法與乘法結合律,並畫出等效邏輯閘。



    輸入 加法結合律
    A B C A+B (A+B)+C B+C A+(B+C)
    0 0 0 0 0 0 0
    0 0 1 0 1 1 1
    0 1 0 1 1 1 1
    0 1 1 1 1 1 1
    1 0 0 1 1 0 1
    1 0 1 1 1 1 1
    1 1 0 1 1 1 1
    1 1 1 1 1 1 1
    輸入 乘法結合律
    A B C AB (AB)C BC A(BC)
    0 0 0 0 0 0 0
    0 0 1 0 0 0 0
    0 1 0 0 0 0 0
    0 1 1 0 0 1 0
    1 0 0 0 0 0 0
    1 0 1 0 0 0 0
    1 1 0 1 0 0 0
    1 1 1 1 1 1 1



    E9.gif (1854 bytes)

    加法結合律等效閘

    E10.gif (1703 bytes)

    乘法結合律等效閘

     

     

  3. 分配律(Distributive laws):加法分配律是指一變數(A)與多變數的積項(BC)之和(A+BC),可以被展開為和項之積((A+B)(A+C))。乘法分配律是指一個變數(A)與多個變數和項(B+C)之積(A(B+C)),可以被展開為積項之和(AB+AC)。一般代數具有乘法分配律,而布林代數則具有加法分配律與乘法分配律。
    加法分配律:A+(BC)=(A+B)(A+C)
    乘法分配律:A(B+C)=AB+AC

    例3.8利用真值表證明加法與乘法分配律,並畫出等效邏輯閘。



    輸入 加法對乘法分配律
    A B C BC A+(BC) A+B A+C (A+B)(A+C)
    0 0 0 0 0 0 0 0
    0 0 1 0 0 0 1 0
    0 1 0 0 0 1 0 0
    0 1 1 1 1 1 1 1
    1 0 0 0 1 1 1 1
    1 0 1 0 1 1 1 1
    1 1 0 0 1 1 1 1
    1 1 1 1 1 1 1 1
    輸入 乘法對加法分配律
    A B C B+C A(B+C) AB AC AB+AC
    0 0 0 0 0 0 0 0
    0 0 1 1 0 0 0 0
    0 1 0 1 0 0 0 0
    0 1 1 1 0 0 0 0
    1 0 0 0 0 0 0 0
    1 0 1 1 1 0 1 1
    1 1 0 1 1 1 0 1
    1 1 1 1 1 1 1 1


    E11.gif (2351 bytes)

    加法對乘法分配律等效閘

    E12.gif (2203 bytes)

    乘法對加法分配律等效閘

     

     

  4. 消去律(Elimination laws):加法消去律是指一變數(A)與含有該變數的多項變數積項(AB)之和(A+AB)等於該變數值(A)。乘法消去律是指一個變數(A)與含有該變數的多變數和項(A+B)之積A(A+B)等於該變數值(A)
    加法消去律:A+AB=A
    乘法消去律:A(A+B)=A

    例3.9利用真值表與前述定理證明加法消去律與乘法消去律。

    真值表
    輸入 加法消去律 乘法消去律
    A B AB A+AB=A A+B A(A+B)=A
    0 0 0 0 0 0
    0 1 0 0 1 0
    1 0 0 1 1 1
    1 1 1 1 1 1
    證明一 A+AB =A.1+AB 利用乘法對偶定理
    =A(1+B) 利用乘法對加法分配律
    =A(B+1) 利用加法交換律
    =A.1 利用加法吸收定理
    =A 利用乘法對偶定理
    證明二 A(A+B) =(A+1)(A+B) 利用加法對偶定理
    =A+(1.B) 利用加法對乘法分配律
    =A+(B.1) 利用乘法交換律
    =A+1 利用乘法吸收定理
    =A 利用加法對偶定理
     

     

  5. 狄摩根定理(Demorgan’s Theorems):狄摩根是偉大的邏輯學家和數學家,他提出布林代數中二個重要的定理;第一定理是和的補數(E2.gif (232 bytes))等於補數的積(E13.gif (247 bytes)),第二定理是積(E14.gif (213 bytes))的補數等於補數的和(E15.gif (230 bytes))。狄摩根定理不只適用於二變數,同時它也適用於多變數。
    狄摩根第一定理:E5.gif (365 bytes)
    狄摩根第二定理:E6.gif (357 bytes)

    例3.10利用真值表證明狄摩根第一定理與狄摩根第二定理。



    狄摩根第一定理
    A B E2.gif (232 bytes) A.gif (148 bytes) B.gif (158 bytes) E13.gif (247 bytes)
    0 0 1 1 1 1
    0 1 0 1 0 0
    1 0 0 0 1 0
    1 1 0 0 0 0
    狄摩根第二定理
    A B E14.gif (213 bytes) A.gif (148 bytes) B.gif (158 bytes) E15.gif (230 bytes)
    0 0 1 1 1 1
    0 1 1 1 0 1
    1 0 1 0 1 1
    1 1 0 0 0 0
    等效閘 E16.gif (2127 bytes)

    狄摩根第一定理

    E17.gif (2155 bytes)

    狄摩根第二定理


到上一頁 回章節首頁