十進BASIC 第2掲示板 過去ログ

!論理式の計算

DEF AND3(a,b,c)=AND(AND(a,b),c) !３変数以上の場合
DEF AND4(a,b,c,d)=AND(AND(a,b),AND(c,d))
DEF OR3(a,b,c)=OR(OR(a,b),c)
DEF OR4(a,b,c,d)=OR(OR(a,b),OR(c,d))

LET C1=NT(0) !1　※－１のビットパターン
!------------------------------ ここまでがマクロの定義

LET N=3 !変数の数　※１～５

LET A=BOOL(N,1) !Ｎ個の変数の１番目
LET B=BOOL(N,2)
LET C=BOOL(N,3)
!LET D=BOOL(N,4)
!LET E=BOOL(N,5)

LET nA=NT(A) !A' 補元
LET nB=NT(B)
LET nC=NT(C)
!LET nD=NT(D)
!LET nE=NT(E)


!●論理式の真理値表をつくる

PRINT BitPTN$(N, A); ":A"
PRINT BitPTN$(N, B); ":B"
PRINT BitPTN$(N, C); ":C"

LET f=OR3(AND3(A,B,C), AND3(A,nB,C), AND3(A,B,nC))
PRINT BitPTN$(N, f); ":ABC+AB'C+ABC'"
PRINT


!●論理式を主加法標準展開、主乗法標準展開する

LET f=OR(A,AND(B,C))
!PRINT BitPTN$(N, f); ":A+BC"

CALL PrintPDCF(N,f)
CALL PrintPCCF(N,f)
PRINT


!●クワイン・マクラスキー法（Quine-McCluskey algorithm）で式を簡単化する

!ステップ０　論理式の真理値表をつくる

LET f=OR4(AND3(nA,B,C),AND3(A,nB,C),AND3(A,B,nC),AND3(A,B,C))
!PRINT BitPTN$(N, f); ":A'BC+AB'C+ABC'+ABC"


!ステップ１　論理式を最小項で記述する（主加法標準展開）

DIM Term$(2^N) !最小項のビットパターン
LET CntOfTerm=0 !最小項の数
FOR i=0 TO 2^N-1 !真理値表を２進法の数とみなして小さい順に
   IF Bit(f,i)=1 THEN !最小項なら
      LET CntOfTerm=CntOfTerm+1
      LET Term$(CntOfTerm)=right$(REPEAT$("0",N-1)&BSTR$(i,2),N) !ビットパターンは、…DCBA順
   END IF
NEXT i
!FOR i=1 TO CntOfTerm !debug
!   PRINT Term$(i)
!NEXT i

IF CntOfTerm=0 THEN !すべて０なら、終了！
   PRINT "0"
   STOP
ELSEIF CntOfTerm=2^N THEN !すべての１なら、終了！
   PRINT "1"
   STOP
END IF


!ステップ２　AB+AB'=Aを使って、最小項の変数を減らす

DIM wTerm$(100) !作業用にコピーする
FOR i=1 TO CntOfTerm
   LET wTerm$(i)=Term$(i)
NEXT i
LET wCntOfTerm=CntOfTerm

DIM Term9$(2^N) !主項のビットパターン
LET CntOfTerm9=0 !主項の数

DO
   DIM CHK(100) !圧縮の有無
   MAT CHK=ZER

   LET CntOfCompTRM=0 !圧縮された項の数

   FOR i=1 TO wCntOfTerm-1 !すべての組合せで考慮する
      FOR j=i+1 TO wCntOfTerm

         LET CntOf1=0 !「１」の数
         FOR k=1 TO N !ビット単位の排他的論理和を求める
            LET t1$=wTerm$(i)(k:k)
            LET t2$=wTerm$(j)(k:k)
            IF (t1$="1" AND t2$="0") OR (t1$="0" AND t2$="1") THEN !「１」とする
               LET CntOf1=CntOf1+1
               LET PosOf1=k !消去される変数の位置
            ELSEIF (t1$="0" AND t2$="0") OR (t1$="1" AND t2$="1") THEN !「０」とする
            !skip it
            ELSEIF (t1$="-" AND t2$="-") THEN !マスク・ビットなら
            !skip it
            ELSE !片方がマスク・ビットなら、候補ではない！
               LET CntOf1=N
               EXIT FOR
            END IF
         NEXT k

         IF CntOf1=1 THEN !AB+AB'=A（ハミング距離が１）より、消去する
            LET t$=wTerm$(i) !ビットパターン
            LET t$(PosOf1:PosOf1)="-" !その変数を消去する

            LET CHK(i)=1 !圧縮あり
            LET CHK(j)=1

            DIM CompTRM$(100)
            FOR k=1 TO CntOfCompTRM !同じ項があるか確認する
               IF t$=CompTRM$(k) THEN EXIT FOR
            NEXT k
            IF k>CntOfCompTRM THEN !なけらば、新規に登録する
               LET CntOfCompTRM=CntOfCompTRM+1
               LET CompTRM$(CntOfCompTRM)=t$

               !PRINT i;j; t$ !debug
            END IF
         END IF

      NEXT j
   NEXT i

   LET Cnt=0 !今回圧縮できなかった項の数
   FOR i=1 TO wCntOfTerm !圧縮されないものは、主項となる
      IF CHK(i)=0 THEN
         LET Cnt=Cnt+1

         LET CntOfTerm9=CntOfTerm9+1 !主項として記録する
         LET Term9$(CntOfTerm9)=wTerm$(i)
      END IF
   NEXT i

   IF Cnt=wCntOfTerm THEN EXIT DO !すべて圧縮できなければ、終了！


   FOR i=1 TO CntOfCompTRM !次へ
      LET wTerm$(i)=CompTRM$(i) !copy it
   NEXT i
   LET wCntOfTerm=CntOfCompTRM

LOOP


!ステップ３　主項表を使って冗長な主項を削除する

!ステップ３－１　主項表をつくる

DIM TT(CntOfTerm9,CntOfTerm) !主項表（図）　※TT(主項,最小項)
MAT TT=ZER

FOR i=1 TO CntOfTerm9 !最小項を包含する主項にチェックを入れる
   FOR j=1 TO CntOfTerm
      FOR k=1 TO N
         LET t$=Term9$(i)(k:k)
         IF t$<>"-" THEN !マスク・ビット以外が不一致なら、終了！
            IF t$<>Term$(j)(k:k) THEN EXIT FOR
         END IF
      NEXT k
      IF k>N THEN LET TT(i,j)=1 !すべてのビットが一致すれば、包含する
   NEXT j
NEXT i
!MAT PRINT TT; !debug


!ステップ３－２　主項表から必須項を探す

DIM CHK2(CntOfTerm9) !必須項としてチェックする
MAT CHK2=ZER

MAT CHK=ZER
FOR j=1 TO CntOfTerm !主項表から必須項を探す
   LET Cnt=0
   FOR i=1 TO CntOfTerm9 !列で走査して、「１」が１つの列を見つける
      IF TT(i,j)=1 THEN
         LET Cnt=Cnt+1
         LET PosOf1=i !行位置
      END IF
   NEXT i
   IF Cnt=1 THEN !１つのものは、必須項とする
      LET CHK2(PosOf1)=1
      FOR k=1 TO CntOfTerm !必須項だけで最小項を包含するか（冗長性）
         LET CHK(k)=OR(CHK(k),TT(PosOf1,k))
      NEXT k
   END IF
NEXT j
!MAT PRINT CHK; !debug
!MAT PRINT CHK2;

!ステップ３－３　必須項と選択項の組み合わせで過不足なく項を選ぶ

DO
   FOR j=1 TO CntOfTerm !包含されていない箇所を探す
      IF CHK(j)=0 THEN EXIT FOR
   NEXT j
   IF j>CntOfTerm THEN EXIT DO !必須項＋選択項で最小項を包含するなら、終了！

   FOR i=1 TO CntOfTerm9 !その箇所を選択項で埋める
      IF TT(i,j)=1 THEN !行位置
         LET CHK(j)=2
         LET CHK2(i)=2 !選択項に加える
         EXIT FOR
      END IF
   NEXT i
   !MAT PRINT CHK; !debug
   !MAT PRINT CHK2;
LOOP



!結果を表示する

FOR i=1 TO CntOfTerm9
   IF CHK2(i)>0 THEN !必須項または選択項なら
      PRINT "+";
      FOR k=0 TO N-1 !変数へ
         SELECT CASE Term9$(i)(N-k:N-k) !ビットパターンを得る　※…DCBA順
         CASE "0"
            PRINT CHR$(k+ORD("A"));"'"; !否定
         CASE "1"
            PRINT CHR$(k+ORD("A"));
         CASE ELSE !"-"
         END SELECT
      NEXT k
   END IF
NEXT i
PRINT


END


EXTERNAL FUNCTION BOOL(N,i) !真理値表での変数A～Zのビットパターン（2^N 桁）を求める
LET t$=REPEAT$("1",2^(i-1))&REPEAT$("0",2^(i-1)) !11…100…0
LET BOOL=BVAL(REPEAT$(t$,2^(N-i)),2) !A,B,C,…
END FUNCTION


!出力関連
EXTERNAL SUB PrintPDCF(N,f) !真理値表を主加法標準形（選言標準形）で出力する
FOR i=0 TO 2^N-1
   IF Bit(f,i)=1 THEN !最小項
      PRINT "+";
      FOR x=0 TO N-1
         PRINT CHR$(x+ORD("A")); !変数名
         IF Bit(i,x)=0 THEN PRINT "'"; !否定記号
      NEXT x
   END IF
NEXT i
PRINT
END SUB

EXTERNAL SUB PrintPCCF(N,f) !真理値表を主乗法標準形（連言標準形）で出力する
FOR i=0 TO 2^N-1
   IF Bit(f,i)=0 THEN !最大項
      PRINT "(";
      FOR x=0 TO N-1
         PRINT "+";
         PRINT CHR$(x+ORD("A")); !変数名
         IF Bit(i,x)=1 THEN PRINT "'"; !否定記号
      NEXT x
      PRINT ")";
   END IF
NEXT i
PRINT
END SUB


!補助ルーチン
EXTERNAL FUNCTION Bit(x,m) !mビット目を得る　0,1
LET Bit=MOD(INT(x/2^m),2)
END FUNCTION

EXTERNAL FUNCTION BitPTN$(N,a) !ビットパターン（2^N 桁）を求める
IF a>=0 THEN
   LET a$=REPEAT$("0",2^N-1)&BSTR$(a,2)
ELSE
   LET a$=BSTR$(a+2^32,2)
END IF
LET BitPTN$=right$(a$,2^N)
END FUNCTION


!論理演算
EXTERNAL FUNCTION AND(a,b) !整数a,bのビット単位での論理積を求める
LET c=0
FOR i=0 TO 31
   LET aa=MOD(a,2)
   LET a=(a-aa)/2
   LET bb=MOD(b,2)
   LET b=(b-bb)/2
   LET c=c+MIN(aa,bb)*2^i
NEXT i
IF c>=2^31 THEN LET c=c-2^32
LET AND=c
END FUNCTION

EXTERNAL FUNCTION OR(a,b) !整数a,bのビット単位での論理和を求める
LET c=0
FOR i=0 TO 31
   LET aa=MOD(a,2)
   LET a=(a-aa)/2
   LET bb=MOD(b,2)
   LET b=(b-bb)/2
   LET c=c+MAX(aa,bb)*2^i
NEXT i
IF c>=2^31 THEN LET c=c-2^32
LET OR=c
END FUNCTION

EXTERNAL FUNCTION NT(a) !整数aのビット単位での論理否定を求める　※NOTは予約語のため
LET NT=-1-a
END FUNCTION