新しく発言する EXIT インデックスへ

論理演算や集合演算の計算して、その結果を...

　　論理演算や集合演算の計算して、その結果を真理値表やベン図で表す 山中和義 2008/03/08 14:38:52  (修正1回)
　　├つづき（真理値表、ベン図） 山中和義 2008/03/08 14:41:15 
　　│└つづき（式の評価eval） 山中和義 2008/03/08 14:43:25  (修正1回)
　　│　└つづき 山中和義 2008/03/08 14:44:12  (修正1回)
　　│　　└つづき 山中和義 2008/03/08 14:44:53 
　　│　　　└つづき（メイン） 山中和義 2008/03/08 14:46:11  (修正1回)
　　├真理値表（truthtable）から論理式（論理関... 山中和義 2008/03/10 10:55:33 
　　└!真理値表から多変数多項式をつくる 山中和義 2008/04/08 14:22:27 

　　論理演算や集合演算の計算して、その結果を真理値表やベン図で表す 山中和義 2008/03/08 14:38:52  (修正1回)  ツリーへ
論理演算や集合演算の計算して、その結果を真理値表やベン図で表す 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/08 14:38:52 ** この記事は1回修正されてます

!論理演算や集合演算の式を計算して、その結果を真理値表やベン図で表す

!●論理演算
!<式>::=<項> { + <項> }*
!<項>::=<因子> { * <因子> }*
!<因子>::={ <数> | ( <式> ) } { ' }*
!<数>::={ <変数> | <整数> }
!<変数>::={ A | B | C | D | … | X | Y | Z }　※小文字は大文字として扱う
!<整数>::=<数字>　※0,1

!●集合演算、命題
!<命題>::=<式> { { ⇒ | ⇔ } <式> }*
!<式>::=<項> { { ∪ | - } <項> }*　※∨,|も可能
!<項>::=<因子> { ∩ <因子> }*　//∧,&も可能
!<因子>::={ ¬ }* { <数> | ( <命題> ) }　※〜,!も可能
!<数>::={ <関数> | <変数> }
!<関数>::={
!　　　　　φ |　//空集合
!　　　　　Ω　　//普遍集合
!　　　　 }
!<変数>::={ A | B | C | D | … | X | Y | Z }　※小文字は大文字として扱う


LET N=3 !変数の数

DIM vTBL(26) !変数A〜Z　※真理値表ビットパターン（2^N 桁）
LET vTBL(1)=BVAL("00001111",2) !A
LET vTBL(2)=BVAL("00110011",2) !B
LET vTBL(3)=BVAL("01010101",2) !C
LET vTBL(21)=BVAL("11111111",2) !U=Ω

DIM cTBL(0 TO 1) !定数
LET cTBL(0)=BVAL("00000000",2) !0,φ
LET cTBL(1)=BVAL("11111111",2) !1,Ω

DIM stack_Eval(50) !式の計算用のスタック
LET sp_Eval=0 !スタックポインタ


!ビット単位の論理演算
DEF AND(x,y)=MIN(x,y) !論理積
DEF OR(x,y)=MAX(x,y) !論理和
DEF NT(x)=1-x !否定　※２値論理

!ビット演算
FUNCTION BitAND(v1,v2) !ビットAND　f=v1&v2
LET vv=0
FOR i=2^N-1 TO 0 STEP -1
LET vv=vv*2+AND(Bit(v1,i),Bit(v2,i))
NEXT i
LET BitAND=vv
END FUNCTION
FUNCTION BitOR(v1,v2) !ビットOR　f=v1|v2
LET vv=0
FOR i=2^N-1 TO 0 STEP -1
LET vv=vv*2+OR(Bit(v1,i),Bit(v2,i))
NEXT i
LET BitOR=vv
END FUNCTION
FUNCTION BitNOT(v) !ビット反転　f=!v
LET vv=0
FOR i=2^N-1 TO 0 STEP -1
LET vv=vv*2+NT(Bit(v,i))
NEXT i
LET BitNOT=vv
END FUNCTION
 
　　├つづき（真理値表、ベン図） 山中和義 2008/03/08 14:41:15   ツリーへ
Re: 論理演算や集合演算の計算して、その結果を真理値表やベン図で表す 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/08 14:41:15
つづき（真理値表、ベン図）


DEF Bit(x,m)=MOD(INT(x/2^m),2) !mビット目を得る　0,1

SUB TruthTable(m$, N,T()) !真理値表ビットパターン（m$）から真理値表へ
MAT T=ZER

FOR j=0 TO N-1
PRINT " ";CHR$(j+ORD("A"));
NEXT j
PRINT " | f"
PRINT "-------+----"
FOR i=1 TO 2^N
FOR j=0 TO N-1 !ビットパターン
PRINT " ";STR$(Bit(i-1,N-j-1));
NEXT j
PRINT " | ";
LET T(i)=VAL(m$(i:i)) !値
PRINT T(i)
NEXT i
END SUB




DEF co(t)=r*COS(RAD(t)) !配置位置
DEF si(t)=r*SIN(RAD(t))

SUB Venn(m$) !真理値表ビットパターンからベン図へ（Venn's Diagram）　※３変数
SET WINDOW -1.5,1.5,-1.5,1.5 !表示領域

SET LINE width 2
PLOT LINES: -1,-1; 1,-1; 1,1; -1,1; -1,-1 !U
LET r=0.35
DRAW circle WITH SHIFT(co(90),si(90)) !A
DRAW circle WITH SHIFT(co(210),si(210)) !B
DRAW circle WITH SHIFT(co(330),si(330)) !C


DATA 0.9, 0.9 !A'B'C'の位置
DATA 0.35,-0.2 !A'B'C
DATA -0.35,-0.2 !A'B C'
DATA 0,-0.35 !A'B C
DATA 0, 0.35 !A B'C'
DATA 0.25, 0.15 !A B'C
DATA -0.25, 0.15 !A B C'
DATA 0, 0 !A B C
SET AREA COLOR 4
FOR i=1 TO 2^N
READ x,y
IF VAL(m$(i:i))=1 THEN flood x,y !塗りつぶし
NEXT i


SET TEXT HEIGHT 0.2 !記号を書く
SET TEXT JUSTIFY "center","half"
SET TEXT background "opaque"

PLOT TEXT ,AT -0.8,1: "Ｕ"
LET r=0.85
PLOT TEXT ,AT co(90),si(90): "Ａ"
PLOT TEXT ,AT co(210),si(210): "Ｂ"
PLOT TEXT ,AT co(330),si(330): "Ｃ"
END SUB
PICTURE circle !半径1/2の円
FOR i=0 TO 360
PLOT LINES: COS(RAD(i))/2,SIN(RAD(i))/2;
NEXT i
PLOT LINES
END PICTURE
 
　　│└つづき（式の評価eval） 山中和義 2008/03/08 14:43:25  (修正1回)  ツリーへ
Re: つづき（真理値表、ベン図） 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/08 14:43:25 ** この記事は1回修正されてます
つづき（式の評価　eval）

!論理式の計算
FUNCTION propositional_expression(s$) !命題
LET v1=boolean_expression(s$)

LET t$=token$(s$)
DO WHILE t$="⇒" OR t$="⇔" !包含、同値
LET p=p+1 !eat it

CALL push(stack_Eval,sp_Eval, v1)

IF t$="⇒" THEN !計算する　※term$()でt$が破壊されるため
LET v2=boolean_expression(s$)

CALL pop(stack_Eval,sp_Eval, v1)

LET v1=BitOR(BitNOT(v1),v2) !A⇒B=¬A∪B=A'+B
ELSE
LET v2=boolean_expression(s$)

CALL pop(stack_Eval,sp_Eval, v1)

LET vv1=BitAND(BitNOT(v1),BitNOT(v2)) !v1=!(v1 xor v2)
LET vv2=BitAND(v1,v2)
LET v1=BitOR(vv1,vv2)
END IF

LET t$=token$(s$) !次へ
LOOP

LET propositional_expression=v1
END FUNCTION

FUNCTION boolean_expression(s$) !式
LET v1=term(s$)

LET t$=token$(s$)
DO WHILE t$="+" OR t$="∪" OR t$="∨" OR t$="-" OR t$="|" !和、差なら
LET p=p+1 !eat it

CALL push(stack_Eval,sp_Eval, v1)

IF t$="-" THEN !計算する　※term$()でt$が破壊されるため
LET v2=term(s$)

CALL pop(stack_Eval,sp_Eval, v1)

LET v2=BitNOT(v2) !A-B=A∩¬B=A*B'
LET v1=BitAND(v1,v2)
ELSE
LET v2=term(s$)

CALL pop(stack_Eval,sp_Eval, v1)

LET v1=BitOR(v1,v2) !v1=v1|v2
END IF

LET t$=token$(s$) !次へ
LOOP

LET boolean_expression=v1
END FUNCTION

FUNCTION term(s$) !項
LET v1=factor(s$)

LET t$=token$(s$)
DO WHILE t$="*" OR t$="・" OR t$="・" OR t$="∩" OR t$="∧" OR t$="&" !積なら
LET p=p+1 !eat it

CALL push(stack_Eval,sp_Eval, v1)

LET v2=factor(s$)

CALL pop(stack_Eval,sp_Eval, v1)

LET v1=BitAND(v1,v2) !v1=v1&v2

LET t$=token$(s$) !次へ
LOOP

LET term=v1
END FUNCTION
 
　　│　└つづき 山中和義 2008/03/08 14:44:12  (修正1回)  ツリーへ
Re: つづき（式の評価eval） 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/08 14:44:12 ** この記事は1回修正されてます
つづき


FUNCTION factor(s$) !因子
LET CntOfNOT=0 !補演算子の数

LET t$=token$(s$)
IF t$="¬" OR t$="〜" OR t$="!" THEN !補演算なら
LET p=p+1 !eat it

LET CntOfNOT=1

LET t$=token$(s$)
DO WHILE t$="¬" OR t$="〜" OR t$="!" !補演算が続けば
LET p=p+1 !eat it

LET CntOfNOT=CntOfNOT+1

LET t$=token$(s$) !次へ
LOOP
END IF
CALL push(stack_Eval,sp_Eval, CntOfNOT) !save it


LET t$=token$(s$)
IF t$="(" THEN !括弧なら
LET p=p+1 !eat it

LET v=propositional_expression(s$) !命題
!LET v=boolean_expression(s$) !式

CALL CheckToken(s$,")") !閉じ括弧か確認する

ELSE
LET v=num(s$) !数を得る
END IF


CALL pop(stack_Eval,sp_Eval, CntOfNOT) !restore it
LET t$=token$(s$)
IF t$="'" THEN !補演算なら
LET p=p+1 !eat it

LET CntOfNOT=CntOfNOT+1

LET t$=token$(s$)
DO WHILE t$="'" !補演算が続けば
LET p=p+1 !eat it

LET CntOfNOT=CntOfNOT+1

LET t$=token$(s$) !次へ
LOOP
END IF

IF MOD(CntOfNOT,2)=1 THEN LET v=BitNOT(v) !v=!v


LET factor=v
END FUNCTION

FUNCTION num(s$) !数
LET c=func(s$)
IF c>=0 THEN !組込み関数なら
LET v=cTBL(c)

ELSE
LET c=var(s$)
IF c>0 THEN !変数なら
LET v=vTBL(c) !1=A,2=B,…,26=Z

ELSE
LET c=digit(s$)
IF c>=0 THEN !数値なら
LET v=cTBL(c)
ELSE
CALL Error("不正な文字です。")
END IF

END IF

END IF

LET num=v
END FUNCTION

FUNCTION func(s$) !組込み関数
LET t$=token$(s$)
IF t$="φ" THEN !空集合
LET p=p+1 !eat it
LET func=0
ELSEIF t$="Ω" THEN !普遍集合
LET p=p+1 !eat it
LET func=1
ELSE
LET func=-1
END IF
END FUNCTION

FUNCTION var(s$) !変数
LET t$=UCASE$(token$(s$)) !大文字へ
IF "A"<=t$ AND t$<="Z" THEN
LET p=p+1 !eat it
LET var=ORD(t$)-ORD("@") !オフセット　@=0,A=1,B=2,…,Z=26
ELSE
LET var=-1
END IF
END FUNCTION

FUNCTION digit(s$) !１文字の数字（２進法）
LET t$=token$(s$)
IF "0"<=t$ AND t$<="1" THEN
LET p=p+1 !eat it
LET digit=VAL(t$) !値
ELSE
LET digit=-1
END IF
END FUNCTION
 
　　│　　└つづき 山中和義 2008/03/08 14:44:53   ツリーへ
Re: つづき 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/08 14:44:53
つづき


!下位の共通ルーチン
FUNCTION token$(s$) !１文字読み込む
CALL EatSpace(s$)

LET token$=""
IF p<=LEN(s$) THEN LET token$=s$(p:p)
END FUNCTION

SUB EatSpace(s$) !空白を読み飛ばす
DO WHILE s$(p:p)=" " AND p<=LEN(s$)
LET p=p+1
LOOP
END SUB

SUB CheckToken(s$,L$) !文字を確認する
CALL EatSpace(s$)
IF UCASE$(s$(p:p+LEN(L$)-1))<>L$ THEN CALL Error(L$&" がありません。")
LET p=p+LEN(L$) !eat it
END SUB

SUB Error(x$) !エラーメッセージを表示する
PRINT
PRINT x$,p

STOP
END SUB


!スタック関連
SUB push(stack(),sp, v) !スタックに保存する
IF sp<UBOUND(stack) THEN
LET sp=sp+1
LET stack(sp)=v
ELSE
CALL Error("スタックがオーバーフローです。")
END IF
END SUB
SUB pop(stack(),sp, v) !スタックから取り出す
IF sp<1 THEN
CALL Error("スタックが空です。")
ELSE
LET v=stack(sp)
LET sp=sp-1
END IF
END SUB
!------------------------------ ここまでがサブルーチン

 
　　│　　　└つづき（メイン） 山中和義 2008/03/08 14:46:11  (修正1回)  ツリーへ
Re: つづき 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/08 14:46:11 ** この記事は1回修正されてます
つづき（メイン）



DEF ToBin$(x,m)=right$(REPEAT$("0",m-1)&BSTR$(x,2),m) !mビットの２進数に変換する
!DEF ToBin$(x,m)=right$(REPEAT$("0",m-1)&BSTR$(MOD(x,2^m),2),m) !mビットの２進数に変換する


LET p=1 !文字位置　※１〜LEN(s$)

LET s$="(A+B)*(A'+C)" !論理演算（論理式）
!LET s$="A*C+A'*B"
!LET s$="A'*B'*C'+A'*B*C'+A*B'*C'+A*B*C'" !C
!LET s$="!A+!B" !!A*B

!LET s$="¬(A∪B)" !集合演算
!LET s$="A-A∩B∩C"
!LET s$="A∩¬φ" !A
!LET s$="¬¬(¬A∩B)"

!LET s$="A⇒B" !命題
!LET s$="¬A⇒¬B" !裏
!LET s$="B ⇒ A" !逆
!LET s$="¬B ⇒ ¬A" !対偶

!LET s$="¬(A⇔B)" !XOR
!LET s$="A⇒(B⇒A)"
!LET s$="A⇒A∨B"


LET eval=propositional_expression(s$) !式の評価

IF p<=LEN(s$) THEN PRINT p;"文字目が誤りです。"

LET m$=ToBin$(eval,2^N) !2進数へ
PRINT "eval=(";m$;")2" !結果
PRINT


DIM T(2^N) !真理値表
CALL TruthTable(m$, N,T) !表示
PRINT


CALL Venn(m$) !ベン図を描く


END
 
　　├真理値表（truthtable）から論理式（論理関... 山中和義 2008/03/10 10:55:33   ツリーへ
Re: 論理演算や集合演算の計算して、その結果を真理値表やベン図で表す 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/10 10:55:33
真理値表（truth table）から論理式（論理関数f）をつくる

!※論理式を真理値表で表現する

LET N=3 !変数の数

!真理値表
! f A,B,C
DATA 0 !0,0,0=0　※２進法とみなす順
DATA 0 !0,0,1=1
DATA 0 !0,1,0=2
DATA 1 !0,1,1=3
DATA 0 !1,0,0=4
DATA 1 !1,0,1=5
DATA 1 !1,1,0=6
DATA 1 !1,1,1=7

!f(A,B,C)=A'BC+AB'C+ABC'+ABC=AB+BC+CA



!主加法標準形に直す（シャノンの展開定理）

DIM T(2^N) !論理関数f
MAT READ T !f=T(abc)

CALL BooleanDisplayExpression(N,T) !f=Σm(3,5,6,7)
CALL BooleanDisplayExpression2(N,T) !f=ΠM(0,1,2,4)



!補助ルーチン
DEF Bit(x,m)=MOD(INT(x/2^m),2) !mビット目を得る　※正の整数


!表示ルーチン
SUB BooleanDisplayExpression(N,T()) !論理式の表示（主加法標準形）
FOR i=0 TO 2^N-1
IF T(i+1)=1 THEN
CALL BooleanDisplayTerm(N,i,"") !その他の記号 *・・∩∧&
IF i<2^N-1 THEN PRINT " + ";
END IF
NEXT i
PRINT
END SUB
SUB BooleanDisplayTerm(n,v, op$) !項の表示
FOR j=1 TO N !A,B,C,…の文字をそれぞれ１回ずつ含む　※'は否定
!!!IF Bit(v,N-j)=0 THEN PRINT "¬"; !その他の記号 〜￣!
PRINT CHR$(j+ORD("A")-1);
IF Bit(v,N-j)=0 THEN PRINT "'";
IF j<N THEN PRINT op$; !演算子
NEXT j
END SUB

SUB BooleanDisplayExpression2(N,T()) !論理式の表示（主乗法標準形）
FOR i=0 TO 2^N-1
IF T(i+1)=0 THEN
PRINT "( ";
CALL BooleanDisplayTerm(N,i,"+") !∪∨|
PRINT " )";
END IF
NEXT i
PRINT
END SUB

END
 
　　└!真理値表から多変数多項式をつくる 山中和義 2008/04/08 14:22:27   ツリーへ
Re: 論理演算や集合演算の計算して、その結果を真理値表やベン図で表す 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/04/08 14:22:27
!真理値表から多変数多項式をつくる

!n変数a,b,c,…の論理関数f(a,b,c,…)を、n変数の多項式で表す

!１変数の場合、項a,1を使った多項式で表現する。
!係数x1,x2とすると、a op b=x1*a+x2*1となる。
!　否定　NOT a = -a+1
!
!２変数の場合、項a,b,ab,1を使った多項式で表現する。
!係数x1,x2,x3,x4とすると、a op b=x1*a+x2*b+x3*ab+x4*1となる。
!
!　論理積　a AND b = ab
!　論理和　a OR b = a+b-ab
!　排他的論理和　a XOR b = a+b-2ab
!　包含　a → b = -a+ab-1
!
!※n変数では2^n個の項がある


LET N=3 !変数の数

DIM T(2^N,2^N) !項 a b c ab bc ca abc 1
DEF idx(a,b,c)=(a*2+b)*2+c+1 !※真理値表から機械的に生成する
FOR a=0 TO 1
FOR b=0 TO 1
FOR c=0 TO 1
LET T(idx(a,b,c),1)=a
LET T(idx(a,b,c),2)=b
LET T(idx(a,b,c),3)=c
LET T(idx(a,b,c),4)=a*b
LET T(idx(a,b,c),5)=b*c
LET T(idx(a,b,c),6)=c*a
LET T(idx(a,b,c),7)=a*b*c
LET T(idx(a,b,c),8)=1
NEXT c
NEXT b
NEXT a

! f　論理関数 a OR b OR c
DATA 0 !0,0,0
DATA 1 !0,0,1
DATA 1 !0,1,0
DATA 1 !0,1,1
DATA 1 !1,0,0
DATA 1 !1,0,1
DATA 1 !1,1,0
DATA 1 !1,1,1
DIM f(2^N)
MAT READ f

DIM x(2^N) !連立方程式Tx=f

DIM iT(2^N,2^N) !逆行列を求める
MAT iT=INV(T)

MAT x=iT*f !xを求める
MAT PRINT x !係数列　※a+b+c-ab-bc-ca+abc


END

インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。