トップページに戻る
論理代数(ブール代数)の多変数へ の拡張と応用について(荒井公康著)
論理和OR 論理積AND
A B A∨B A B A∧B
1 1 1 1 1 1
1 0 1 1 0 0
0 1 1 0 1 0
0 0 0 0 0 0
排他的論理和
A B A●B
1 1 0
1 0 1
0 1 1
0 0 0
含意→(ならば)
A B A→B
1 1 1
1 0 0
0 1 1
0 0 1
A∨B=a+b-ab A∧B=ab A●B=a+b-2ab
A→B = 1-a+b-(1-a)b = -a+ab+1
次に、変数の数を増やしていく。
A∨B∨C=a+b+c-ab-bc-ca+abc
A∨B∨C∨D=a+b+c+d-ab-ac-ad-bc-bd-cd
+abc+acd+abd+bcd-abcd
・・・・・・・・・
A●B●C=a+b+c-2ab-2ac-2bc+4abc
A●B●C●D=a+b+c+d-2ab-2ac-2ad-2bc-2bd-2cd
+4abc+4acd+4abd+4bcd
-8abcd
・・・・・・・・
A∧B∧C=abc
n=2の時
a b ab a●b
1 1 1 1 a1 0
1 0 0 1 a2 = 1
0 1 0 1 a3 1
0 0 0 1 a4 0
↑ ↑
行列 項の未知係数
a●b=a+b-2ab
a b c d 論理関数F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 → 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1
論理関数Fは、なんと
F=-a-d+ad-bc+bd+cd+abc-abcd+1.0
F = A1a+A2b+A3c+A4d+A5 (A1~A5は定数)
;;;
;;; c:\\program files\\acl62\\kaiki.cl
;;;
(defun read-sentence ()
(let ((input (make-string-input-stream (read-line))))
(unwind-protect
(progn
(do ((word (read input nil) (read input nil))
(sentence nil))
((not word) (return (reverse sentence)))
(push word sentence)))
(close input))))
(defun set-data ()
(setf a (make-array '(16 16) :initial-element nil))
(setf a2 (make-array '(16 17) :initial-element nil))
(setf b (make-array '(16 1) :initial-element nil))
(setf n (make-array '(16 1) :initial-element nil))
(setf (aref n 0 0) 'a)
(setf (aref n 1 0) 'b)
(setf (aref n 2 0) 'c)
(setf (aref n 3 0) 'd)
(setf (aref n 4 0) 'ab)
(setf (aref n 5 0) 'ac)
(setf (aref n 6 0) 'ad)
(setf (aref n 7 0) 'bc)
(setf (aref n 8 0) 'bd)
(setf (aref n 9 0) 'cd)
(setf (aref n 10 0) 'abc)
(setf (aref n 11 0) 'acd)
(setf (aref n 12 0) 'abd)
(setf (aref n 13 0) 'bcd)
(setf (aref n 14 0) 'abcd)
(setf (aref n 15 0) "")
;;;
;;; a:0 b:1 c:2 d:3
;;;
(setf (aref a 0 0) 0) (setf (aref a 0 1) 0)
(setf (aref a 0 2) 0) (setf (aref a 0 3) 0)
(setf (aref a 1 0) 0) (setf (aref a 1 1) 0)
(setf (aref a 1 2) 0) (setf (aref a 1 3) 1)
(setf (aref a 2 0) 0) (setf (aref a 2 1) 0)
(setf (aref a 2 2) 1) (setf (aref a 2 3) 0)
(setf (aref a 3 0) 0) (setf (aref a 3 1) 0)
(setf (aref a 3 2) 1) (setf (aref a 3 3) 1)
(setf (aref a 4 0) 0) (setf (aref a 4 1) 1)
(setf (aref a 4 2) 0) (setf (aref a 4 3) 0)
(setf (aref a 5 0) 0) (setf (aref a 5 1) 1)
(setf (aref a 5 2) 0) (setf (aref a 5 3) 1)
(setf (aref a 6 0) 0) (setf (aref a 6 1) 1)
(setf (aref a 6 2) 1) (setf (aref a 6 3) 0)
(setf (aref a 7 0) 0) (setf (aref a 7 1) 1)
(setf (aref a 7 2) 1) (setf (aref a 7 3) 1)
(setf (aref a 8 0) 1) (setf (aref a 8 1) 0)
(setf (aref a 8 2) 0) (setf (aref a 8 3) 0)
(setf (aref a 9 0) 1) (setf (aref a 9 1) 0)
(setf (aref a 9 2) 0) (setf (aref a 9 3) 1)
(setf (aref a 10 0) 1) (setf (aref a 10 1) 0)
(setf (aref a 10 2) 1) (setf (aref a 10 3) 0)
(setf (aref a 11 0) 1) (setf (aref a 11 1) 0)
(setf (aref a 11 2) 1) (setf (aref a 11 3) 1)
(setf (aref a 12 0) 1) (setf (aref a 12 1) 1)
(setf (aref a 12 2) 0) (setf (aref a 12 3) 0)
(setf (aref a 13 0) 1) (setf (aref a 13 1) 1)
(setf (aref a 13 2) 0) (setf (aref a 13 3) 1)
(setf (aref a 14 0) 1) (setf (aref a 14 1) 1)
(setf (aref a 14 2) 1) (setf (aref a 14 3) 0)
(setf (aref a 15 0) 1) (setf (aref a 15 1) 1)
(setf (aref a 15 2) 1) (setf (aref a 15 3) 1)
;;; 定数項
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 15) 1))
;;; ab
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 4) (* (aref a i 0) (aref a i 1))))
;;; ac
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 5) (* (aref a i 0) (aref a i 2))))
;;; ad
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 6) (* (aref a i 0) (aref a i 3))))
;;; bc
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 7) (* (aref a i 1) (aref a i 2))))
;;; bd
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 8) (* (aref a i 1) (aref a i 3))))
;;; cd
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 9) (* (aref a i 2) (aref a i 3))))
;;; abc
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 10) (* (aref a i 0) (aref a i 1)
(aref a i 2))))
;;; acd
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 11) (* (aref a i 0) (aref a i 2)
(aref a i 3))))
;;; abd
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 12) (* (aref a i 0) (aref a i 1)
(aref a i 3))))
;;; bcd
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 13) (* (aref a i 1) (aref a i 2)
(aref a i 3))))
;;; abcd
(do ((i 0 (1+ i)))
((> i 15))
(setf (aref a i 14) (* (aref a i 0) (aref a i 1)
(aref a i 2) (aref a i 3))))
;;;
;;;
;;;
(do ((j 0 (1+ j)))
((> j 15))
(do ((i 0 (1+ i))
(s 0))
((> i 15) (setf (aref a2 0 j) s))
(setf s (+ s (aref a i j)))))
;;;
;;;
;;;
(do ((l 0 (1+ l)))
((> l 14))
(do ((j 0 (1+ j)))
((> j 15))
(do ((i 0 (1+ i))
(s 0))
((> i 15) (setf (aref a2 (1+ l) j) s))
(setf s (+ s (* (aref a i l)
(aref a i j))))))))
;;;
;;;
;;;
(defun input-1-or-0 ()
(do ((i 0 (1+ i)))
((> i 15))
(format t "~%No.~a~%" (1+ i))
(setf (aref b i 0) (car (read-sentence)))))
(defun solve-aux ()
(input-1-or-0)
(do ((i 0 (1+ i))
(s 0))
((> i 15) (setf (aref a2 0 16) s))
(setf s (+ s (aref b i 0))))
(do ((l 0 (1+ l)))
((> l 14))
(do ((i 0 (1+ i))
(s 0))
((> i 15) (setf (aref a2 (1+ l) 16) s))
(setf s (+ s (* (aref a i l)
(aref b i 0)))))))
(defun convert-l-to-a ()
(prog ()
(set-data)
(solve-aux)
(do ((k 0 (1+ k)))
((> k 15))
(setf w (aref a2 k k))
(setf k1 (1+ k))
(do ((j k1 (1+ j)))
((> j 16))
(setf (aref a2 k j)
(/ (aref a2 k j) w)))
(do ((i 0 (1+ i)))
((> i 15))
(cond ((not (equal i k))
(setf w (aref a2 i k))
(do ((j k1 (1+ j)))
((> j 16))
(setf (aref a2 i j)
(- (aref a2 i j)
(* (aref a2 k j) w)
)))))))
(do ((i 0 (1+ i)))
((> i 15))
(format t "~%No.~a ~a~a"
(1+ i)
(float (aref a2 i 16))
(aref n i 0))))
a b c d e 実験結果No.
0 0 0 0 0 1
0 0 0 1 1 2
0 0 1 0 1 3
0 0 1 1 0 4
0 1 0 0 1 5
0 1 0 1 0 6
0 1 1 0 0 7
0 1 1 1 1 8
1 0 0 0 1 9
1 0 0 1 0 10
1 0 1 0 0 11
1 0 1 1 1 12
1 1 0 0 0 13
1 1 0 1 1 14
1 1 1 0 1 15
1 1 1 1 0 16
実験結果=A1a+A2b+A3c+A4d+A5e
+A6ab+A7ac+A8ad+A9ae
+A10bc+A11bd+A12be
+A13cd+A14ce
+A15de
+A16
10 'The name of this program is L16
20 CLS :SCREEN 4
30 LOCATE 5,5 :INPUT "Enter the name of data." A$
40 N=16
50 M=15
60 DIM B(50),R(50,25),A(50,25),B$(50),C(50,25)
70 X=16
80 '
90 FOR I=1 TO 16 :A(I,16)=1 :NEXT I
100 A(1,1)=0:A(1,2)=0:A(1,3)=0:A(1,4)=0:A(1,5)=0
110 A(2,1)=0:A(2,2)=0:A(2,3)=0:A(2,4)=1:A(2,5)=1
120 A(3,1)=0:A(3,2)=0:A(3,3)=1:A(3,4)=0:A(3,5)=1
130 A(4,1)=0:A(4,2)=0:A(4,3)=1:A(4,4)=1:A(4,5)=0
140 A(5,1)=0:A(5,2)=1:A(5,3)=0:A(5,4)=0:A(5,5)=1
150 A(6,1)=0:A(6,2)=1:A(6,3)=0:A(6,4)=1:A(6,5)=0
160 A(7,1)=0:A(7,2)=1:A(7,3)=1:A(7,4)=0:A(7,5)=0
170 A(8,1)=0:A(8,2)=1:A(8,3)=1:A(8,4)=1:A(8,5)=1
180 A(9,1)=1:A(9,2)=0:A(9,3)=0:A(9,4)=0:A(9,5)=1
190 A(10,1)=1:A(10,2)=0:A(10,3)=0:A(10,4)=1:A(10,5)=0
200 A(11,1)=1:A(11,2)=0:A(11,3)=1:A(11,4)=0:A(11,5)=0
210 A(12,1)=1:A(12,2)=0:A(12,3)=1:A(12,4)=1:A(12,5)=1
220 A(13,1)=1:A(13,2)=1:A(13,3)=0:A(13,4)=0:A(13,5)=0
230 A(14,1)=1:A(14,2)=1:A(14,3)=0:A(14,4)=1:A(14,5)=1
240 A(15,1)=1:A(15,2)=1:A(15,3)=1:A(15,4)=0:A(15,5)=1
250 A(16,1)=1:A(16,2)=1:A(16,3)=1:A(16,4)=1:A(16,5)=0
260 FOR I=1 TO 16
270 A(I,6)=A(I,1)*A(I,2)
280 A(I,7)=A(I,1)*A(I,3)
290 A(I,8)=A(I,1)*A(I,4)
300 A(I,9)=A(I,1)*A(I,5)
310 A(I,10)=A(I,2)*A(I,3)
320 A(I,11)=A(I,2)*A(I,4)
330 A(I,12)=A(I,2)*A(I,5)
340 A(I,13)=A(I,3)*A(I,4)
350 A(I,14)=A(I,3)*A(I,5)
360 A(I,15)=A(I,4)*A(I,5)
370 NEXT I
380 B$(1)=" 1" :B$(2)=" 2" :B$(3)=" 3" :B$(4)=" 4"
390 B$(5)=" 5" :B$(6)=" 6" :B$(7)=" 7" :B$(8)=" 8"
400 B$(9)=" 9" :B$(10)="10" :B$(11)="11" :B$(12)="12"
410 B$(13)="13" :B$(14)="14" :B$(15)="15" :B$(16)="16"
420 FOR I=1 TO 16
430 PRINT "B(";I;")=";:INPUT B(I)
440 NEXT I
450 FOR J=1 TO 16
460 S=0
470 FOR I=1 TO 16 :S=S+A(I,J) :NEXT I
480 R(I,J)=S
490 NEXT J
500 '
510 FOR L=1 TO 15
520 FOR J=1 TO 16
530 S=0
540 FOR I=1 TO 16 :S=S+A(I,L)*A(I,J) :NEXT I
550 K=L+1 :R(K,J)=S
560 NEXT J
570 NEXT L
580 S=0
590 FOR I=1 TO 16 :S=S+B(I) :NEXT I
600 R(1,17)=S
610 FOR L=1 TO 15
620 S=0
630 FOR I=1 TO 16 :S=S+A(I,L)*B(I) :NEXT I
640 K=L+1 :R(K,17)=S
650 NEXT L
660 '
670 FOR K=1 TO 16
680 W=R(K,K)
690 K1=K+1
700 FOR J=K1 TO 17
710 R(K,J)=R(K,J)/W
720 NEXT J
730 FOR I=1 TO 16
740 IF I=K THEN 790
750 W=R(I,K)
760 FOR J=K1 TO 17
770 R(I,J)=R(I,J)-R(K,J)*W
780 NEXT J
790 NEXT I
800 NEXT K
810 CLS
820 PRINT "*****";A$;"*****"
830 PRINT "A(n,1)X(1)+A(n,2)X(2)+ ........ +A(n,m-1)X(m-1)
+A(n,m)X(m)+A(n,m+1)"
840 PRINT " A(1) A(2)
A(m-1) A(m) A(m+1)
850 PRINT "m=";16
860 FOR I=1 TO 16 :PRINT "A(";I;")=";R(I,17) :NEXT I
870 END
Fa=A1+A6b+A7c+A8d+A9e
p q p|q
1 1 0
1 0 1
0 1 1
0 0 1
p|q = ¬(p∧q) = ¬p∨¬q
否定は ¬p = p|p
論理和は p∨q = (p|p)|(q|q)
p|p = ¬p∨¬p = ¬p
(p|p)|(q|q) = (¬p)|(¬q)
= (¬¬p)∨(¬¬q)
= p∨q
(defun rewrite (l)
(cond ((atom l) l)
((equal (first l) 'NAND)
(list 'NAND
(rewrite (second l))
(rewrite (third l))))
((equal (first l) 'NOT)
(rewrite (list 'NAND (second l) t)))
((equal (first l) 'AND)
(rewrite (list 'NOT
(list 'NAND (second l)
(third l)))))
((equal (first l) 'OR)
(rewrite (list 'NAND
(list 'NOT (second l))
(list 'NOT (third l)))))
((equal (first l) 'XOR)
(rewrite (list 'AND
(list 'OR
(second l)
(third l))
(list 'OR
(list 'NOT (second l))
(list 'NOT (third l))))))
(t (list 'error l))))
(defun rewrite (l)
(cond ((atom l) l)
((equal (first l) 'NAND)
`(NAND ,(rewrite (second l))
,(rewrite (third l))))
((equal (first l) 'NOT)
(rewrite `(NAND ,(second l) t)))
((equal (first l) 'AND)
(rewrite `(NOT (NAND ,(second l)
,(third l)))))
((equal (first l) 'OR)
(rewrite `(NAND (NOT ,(second l))
(NOT ,(third l)))))
((equal (first l) 'XOR)
(rewrite `(AND (OR ,(second l)
,(third l))
(OR (NOT ,(second l))
(NOT ,(third l))))))
(t `(error ,l))))
(defun and-or-not (s)
(cond ((atom s) s)
((equal (first s) 'NOT)
`(NOT ,(and-or-not (second s))))
((equal (first s) 'AND)
`(AND ,(and-or-not (second s))
,(and-or-not (third s))))
((equal (first s) 'OR)
`(OR ,(and-or-not (second s))
,(and-or-not (third s))))
((equal (first s) '->)
`(OR (NOT ,(and-or-not (second s)))
,(and-or-not (third s))))))
(defun de-morgan (s)
(cond ((atom s) s)
((equal (first s) 'NOT)
(move-not (second s)))
((equal (first s) 'AND)
`(AND ,(de-morgan (second s))
,(de-morgan (third s))))
((equal (first s) 'OR)
`(OR ,(de-morgan (second s))
,(de-morgan (third s))))))
(defun move-not (s)
(cond ((atom s) `(NOT ,s))
((equal (first s) 'NOT)
(de-morgan (second s)))
((equal (first s) 'AND)
`(OR ,(move-not (second s))
,(move-not (third s))))
((equal (first s) 'OR)
`(AND ,(move-not (second s))
,(move-not (third s))))))
;;;
;;; (prove '(OR a (NOT a)) ===> (OR a (NOT a))
;;;
(prove '(AND (-> a a) (-> b b))) ===>
(AND (OR (NOT a) a) (OR (NOT b) b)))
;;;
(defun prove (s)
(de-morgan (and-or-not s)))
n=2(変数の数が2の場合)の時
{a b ab}
n=3(変数の数が3の場合)の時
{a b c ab ac bc abc}
n=4(変数の数が4の場合)の時
{a b c d ab ac ad bc bd cd abc abd acd bcd abcd}
基底項の線形結合+定数項(1または0)
論理和 A∨B=a+b-ab
論理積 A∧B=ab
排他的論理和 A●B=a+b-2ab
否定論理積 A NAND B=-ab+1
否定論理和 A NOR B=¬(A∨B)
=¬A∧¬B
=(1-a)(1-b)
=-a-b+ab+1
含意 A⇒B=¬A∨B=(1-a)+b-(1-a)b=-a+ab+1
n=3,n=4の場合の例をいくつか挙げると
A∨B∨C=a+b+c-ab-bc-ac+abc
A∨B∨C∨D=a+b+c+d-ab-ac-ad-bc-bd-cd
+abc+acd+abd+bcd
-abcd
A●B●C=a+b+c-2ab-2bc-2ac+4abc
A●B●C●D=a+b+c+d-2ab-2ac-2ad-2bc-2bd-2cd
+4abc+4acd+4abd+4bcd
-8abcd
A∧B∧C=abc
A∧B∧C∧D=abcd
{(a b c d)
(ab ac ad bc bd cd)
(abc acd abd bcd)
(abcd)}
基底項の線形結合+定数項(0または1)
a+b+c-ab-cb-abc
________a__b__c__-ab_ -cb__ -abc_______ a+b+c-ab-cb-abc
________0__0__0___0_____0______0___________________0
________0__0__1___0_____0______0___________________1
________0__1__0___0_____0______0___________________1
________0__1__1___0____-1_____ 0____ ______________1
________1__0__0___0_____0______0___________________1
________1__0__1___0_____0______0___________________2
________1__1__0__-1 ____0______0___________________1
________1__1__1__-1 ___-1 ____-1___________________0
A∧B=ab=(P⇒Q)∧(Q⇒P)=(-p+pq+1)(-q+pq+1)
=pq-pq-p-pq+pq+pq-q+pq+1=-p-q+2pq+1=P⇔Q
「P∧(P⇒Q)⇒Q」=1-p(1-p+pq)+p(1-p+pq)q
=1-(p-p+pq)+(p-p+pq)q
=1-pq+pq=1
男脳パワー = 右脳パワー + 左脳パワー
ー 0.06*(右脳パワー*左脳パワー)
女脳パワー = 右脳パワー + 左脳パワー
+ 8956*(右脳パワー*左脳パワー)