論理回路

プログラミング論 I
2008年7月11日
論理回路(and,or,not)を作成.
回路を組み合わせ半/全加算器.
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/
H-1
おまけ:getchar() 1/4
• getchar() とは?
• キーボードから1文字読み込み,その文字
CODEを取得する関数.
• 入力されるのを待つので,人間がキーを叩
くまでプログラムは停止する.
– 正しくは“キーボードから”でなく,“標準入力
から”読み込む.
– “標準入力”は,通常はキーボードだが,パイ
プやリダイレクトにより変えることができる.
H-2
#include <stdio.h>
void main(){
int i;
printf("Hello,World!! ");
printf("(No.0)\n");
getchar() 2/4
printf("Please hit Enter key.");
i = getchar();
printf("Hello,World!! ");
printf("(No.1)\n");
}
ここで
一端停止
する
実行結果
Hello,World!! (No.0)
Please hit Enter key.[人間がEnterを押す]
Hello,World!! (No.1)
H-3
getchar() 3/4
• Windows+VisualStudioでありがちな状況.
– プログラムを実行し,
途中でprintf()などにより文字が出力され,
プログラムが無事終了し
Windowが自動的に閉じてしまう.
– 結果,途中で出力した文字が消えてしまい,
実行(出力)結果を人間が確認できない.
– このような場合は,最後にgetchar()を入れ
る.そうすれば,人間がEnterを押すまでプロ
グラムが止まってくれる.
H-4
getchar() 4/4
#include <stdio.h> キーボードからの入力を待ち,
入力されたキーの文字コード
void main(){
をiに代入.
int i;
do {
i = getchar();
printf("You typed [%c].\n\n", i);
} while ( i != '.' );
}
入力された文字を表示.
%cはchar型(文字型)を
表示する.
H-5
論理回路(and,or,not)
の作成.
回路を組み合わせ
半/全加算器を作成
H-6
BTW... 演算子とは?
• 算数の足し算 + とは?
3 + 4 = 7
3 と 4 の演算結果が,7である.
3 と 4 を入力すると,7が出力される.
H-7
ブール論理
(Boolean logic)
• 0と1(真と偽)を論理体系.
• それを扱う代数が,ブール代数.
– 論理否定(not),論理和(or),論理積
(and)の3演算より構成される.
– 登場する値は“真”と“偽”のみ.
• 0と1と考えてもよい.これはdigitalである.
– 基本は,四則演算(+-*/)より単純
• ただし,多くの場合は大量に登場する
H-8
論理値
• “真”と“偽”の二値
– 通常,真を1,偽を0と表現する.
– つまり,“整数の足し算”よりも単純で簡単?
H-9
演算
• 基本的な演算
– not(論理否定),or(論理和),
and(論理積)
• 応用的な演算
– 基本的な演算を組み合わせることにより表現
可能だが,よく使われる演算.
– xor(排他的論理和),nor(否定論理和),
nand(否定論理積)など
• 例えば,P nand Q = not( P and Q )
H-10
論理否定 (not)
• 論理値を反転する演算.
– 表記は ¬P や not P や P など.
単項演算子.
Pが真のとき,¬Pは偽.
¬真 = 偽
P
¬1 = 0
偽
Pが偽のとき,¬Pは真.
0
¬偽 = 真
真
¬0 = 1
1
注意:0と1以外の値は存在しない.
¬P
真
1
偽
0
H-11
論理和 (or)
• どれが一つでも真なら,演算結果は真.
– 表記は,P∨Q や P or Q
– 多項演算子
– 日本語の“または”に
近い(が少し異なる).
– P+Q+R
=(P+Q)+R=P+(Q+R)
や P+Q など.
P
Q
P∨Q
0
0
0
0
1
1
1
0
1
1
1
1
これは,足し算に近い? H-12
論理積 (and)
• 全てが真のとき限り,演算結果は真.
– 表記は,P∧Q や P and Q
– 多項演算子
– 日本語の“かつ”に
近い.
– P・Q・R
=(P・Q)・R=P・(Q・R)
や P・Q など.
P
Q
P∨Q
0
0
0
0
1
0
1
0
0
1
1
1
これは,まさにかけ算 H-13
排他的論理和 (xor)
• 論理和に近いが,1xor1=0
– 表記は,P xor Q や P  Q など.
– exclusive or
– PとQが異なれば 1
PとQが同じななら 0
– P Q R
=(P  Q)  R
=P  (Q  R)
P
Q
P∨Q
0
0
0
0
1
1
1
0
1
1
1
0
論理和に近いが排他的? H-14
否定論理和 (nor)
• P nor Qは, not(P or Q)
• 本講義では扱わない
P
Q
P∨Q
0
0
1
0
1
0
1
0
0
1
1
0
H-15
否定論理積 (nand)
• P nand Qは, not(P and Q)
– nandを組み合わせれば,
not,and,orなど
P
全てを表現できる.
• 本講義では扱わない
Q
P∨Q
0
0
1
0
1
1
1
0
1
1
1
0
H-16
“or” と 日本語“または”
• 「国語90点以上」または「算数90点以上」
の人は授業料免除です.
– 両方満たした人も含む.“or”と同じ.
– 「少なくとも1個が成り立てば」の意味.
• コーヒーまたは紅茶がつきます.
– 両方つくことはない.これは“xor”と同じ.
• 電車代またはガソリン代を請求します.
– 両方請求することはない.“xor”と同じ.
H-17
Bool代数
• ¬(¬P)=P
2回反転すると,元に戻る.
• ドモルガンの法則
¬(P∧Q) = (¬P)∨(¬Q)
¬(P∨Q) = (¬P)∧(¬Q)
H-18
Bool代数
• P  Qは,(Pに対して,  Qが施されたと考える)
– Qが0ならP. Qが1なら¬P.
つまり, 0は値を保持, 1は値を反転.
– P  Q  R  S  Tは
1が登場するたびに反転するので,
1が偶数個の場合→計算結果は 0
1が奇数個の場合→計算結果は 1
H-19
論理回路
• 0 と 1 の情報の演算を処理する回路.
– 計算機, CPUは基本的にこれら回路の組み合
わせ.これらを組み合わせると計算ができる.
– ディジタル(電子)回路などと呼ばれる
H-20
論理回路
not
and
or
xor
H-21
論理回路
x
z
x
y
not
z
or
入力
x
出力
z
入力
x
入力
y
出力
z
0
1
0
0
0
1
0
0
1
1
1
0
1
1
1
1
左から0を入れると,
右から1が出てくる回路.
H-22
論理回路
x
y
z
x
y
z
xor
and
入力
x
入力
y
出力
z
入力
x
入力
y
出力
z
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
H-23
論理回路の例
• 下の回路に(左から) 1 と 0 を入力すると,
(右から) 1 が出力される.
1
1
or
0
1
1
1
1
0
0
and
0
0 not
and
1
1
H-24
加算器
• not,or,andを組み合わせると“加算処
理装置”を作ることができる.
• 2進数の加算器を考える.
– 例えば,
10進数:
5 +
1 =
6
2進数: 101 + 001 = 110
H-25
半加算器 (half adder)
• 1桁の2進数 A と B を入力し,
その和を出力する回路考える.
– ただし,下の桁からの繰り上がりは考えない.
• 1桁の2進数は,真偽値(0か1)が1個.
• つまり,2個の真偽値を入力すると,
2個の真偽値が出力される回路.
– 注意:桁が繰り上がる事があるので ,
1桁同士の加算結果は,2桁になることがある.
H-26
半加算器 (half adder)




0
0
1
1
と
と
と
と
0
1
0
1
の加算→ 0
の加算→ 1
の加算→ 1
の加算→10
入力
A
入力
B
出力
C
出力
S
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
0
(上桁
(上桁
(上桁
(上桁
0,
0,
0,
1,
下桁
下桁
下桁
下桁
0)
1)
1)
0)
上の桁の出力結果をC,
下の桁の出力結果をS
とるす.
上の桁は繰り上がり
(Carry Out)と呼ばれる.
H-27
半加算器 (上の桁)
入A 入B 出C
0
0
1
• A と B の両方が 1 のときのみ, 1
C が 1 となる.
A
B
and
0
1
0
1
0
0
0
1
C
H-28
半加算器 (下の桁)
入A 入B
0
0
1
• (A と B の少なくとも片方が 1 ) 1
かつ (“A と B の両方が 1”でない)
が成り立つとき,S が 1 と考える.
A
0
1
1
0
or
and
B
0
1
0
1
出S
and
S
not
H-29
半加算器
• 2入力の加算器が完成
A
or
入A 入B 出C 出S
0
0
1
1
and
0
1
0
1
0
0
0
1
0
1
1
0
S
not
B
and
C
H-30
全加算器 (full adder)
• 1桁の加算器を桁数分組み合わせれば,
n桁の2進数同士の加算器が作成可能.
• ただし,一番下の桁以外は,
下の桁からの繰り上がりを
1 Carry
考慮するする必要がある.
繰り上がりも考慮し,
結局この3個を
足す必要がある.
1
+) 0
1
0
0
1
1
1
0
H-31
全加算器 (full adder)
• 1桁の2進数3個 A と B と c を入力し,
その和を出力する回路考える.
出力は,繰り上がり と その桁 の2個.
入力
A
入力
B
入力
C0
出力
C1
出力
S
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
H-32
全加算器 (full adder)
A
or
and
S
not
B
and
C
先ほど作成した上の回路を,
“Half Adder”という一つの回路と定義する.
Half
Adder
S
C
“Half Adder”は, 2入力2出力の回路.
内部構成は忘れて良い.
原理が分からなくても使えればよい.
入出力の関係さえ理解していればよい.
Black Boxという.
H-33
全加算器 (full adder)
A
B
Half S
Adder
C
Half S
Adder
C
S
C
or
C
H-34
4桁2進数同士の加算回路
• 4桁2進数 A3A2A1A0 と B3B2B1B0 を
入力し,その加算結果,
S4S3S2S1S0を出力する回路を考える.
• ただし,A3A2A1A0 は
A3*8 + A2*4 + A1*2 + A0
H-35
4桁2進数同士の加算回路
• 先ほど作成した下の回路を,“Full
Adder”という一つの回路と定義する.
A
B
C
Half S
Adder
C
Half S
Adder
C
or
S
A Full
B Adder
C
C
S
C
入力のA,B,Cは
省略する.
入れ替えても
結果は同一
H-36
4桁2進数同士の加算回路
A0B0
A1B1
A2B2
A3B3
FA
FA
FA
HA
C
C
C
C
S
S
S
S
S0
S1
S2
S3
S4
H-37
C言語で回路を模倣
• not回路
– 1入力1出力の関数で模倣できる.
入力値を反転した物を返す.
char not(char a){
if( a == 1 ){
return 0;
} else {
return 1;
}
}
H-38
C言語で回路を模倣
• or回路
– 2入力1出力の関数で模倣できる.
2個の入力の論理和演算結果を返す.
char or(char a, char b){
if( a == 1 || b == 1 ){
return 1;
} else {
return 0;
}
}
H-39
C言語で回路を模倣
• and回路
– 2入力1出力の関数で模倣できる.
2個の入力の論理積演算結果を返す.
char and(char a, char b){
if( a == 1 && b == 1 ){
return 1;
} else {
return 0;
}
}
H-40
A
or
B
and
C
char lc00(char a, char b, char, c){
return and(or(a,b),c);
}
H-41
A
B
or
and
Y
X
not
and
S
Z
char ha_s(char a, char b){
char x, y, z;
x = or(a,b);
y = and(a,b);
z = not(y);
return and(x,z);
}
H-42
A
B
or
and
Y
X
not
and
S
Z
char ha_s(char a, char b){
return
and(
or(a,b), not(and(a,b))
);
}
1文で書くと.
H-43
A
B
and
C
char ha_c(char a, char b){
return and(a,b);
}
H-44
A
B
Half S
Adder
C
X
Ci
Half S
Adder
C
or
S
Z
Co
Y
char fa_s(char a, char b, char ci){
char x;
x = ha_s(a,b);
return ha_s(x,c);
}
H-45
A
B
Half S
Adder
C
X
Ci
Half S
Adder
C
or
S
Z
Co
Y
char fa_c(char a, char b, char ci){
char x, y, z;
x = ha_s(a,b);
y = ha_c(a,b);
z = ha_c(x,c);
return or(z,y);
}
H-46
4桁2進数同士の加算回路
A0B0
A1B1
A2B2
A3B3
FA
FA
FA
HA
C X
C
Y
C
Z
C
S
S
S
S
S0
S1
S2
S3
S4
H-47
void adder( char a3, char a2, char a1, char a0,
char b3, char b2, char b1, char b0){
char s4, s3, s2, s1, s0;
char x, y, z;
s0 = ha_s(a0,b0);
x = ha_c(a0,b0);
4桁2進数同士の
加算回路
s1 = fa_s( a1, b1, x);
y = fa_c( a1, b1, x);
s2 = fa_s( a2, b2, y);
z = fa_c( a2, b2, y);
注意:
本関数は,
演算結果を返すのではなく
演算結果を表示する.
s3 = fa_s( a3, b3, z);
s4 = fa_c( a3, b3, z);
printf("%d%d%d%d + ", a3, a2, a1, a0);
printf("%d%d%d%d = ", b3, b2, b1, b0);
printf("%d%d%d%d%d\n", s4, s3, s2, s1, s0);
}
H-48
練習 0
#include <stdio.h>
void f0(){
printf("f0 S!\n");
printf("f0 E!\n");
}
実行結果は
どのようになるか?
void main(){
printf("main S!\n");
f0();
printf("main E!\n");
}
H-49
解答 0
main S!
f0 S!
f0 E!
main E!
H-50
#include <stdio.h>
void f0(){
printf("f0
printf("f0
}
void f1(){
printf("f1
f0();
printf("f1
}
練習 1
S!\n");
E!\n");
実行結果は
どのようになるか?
S!\n");
E!\n");
void main(){
printf("main S!\n");
f1();
printf("main E!\n");
}
H-51
解答 1
main S!
f1 S!
f0 S!
f0 E!
f1 E!
main E!
H-52
#include <stdio.h>
void f0(){
printf("f0
printf("f0
}
void f1(){
printf("f1
f0();
printf("f1
}
void f2(){
printf("f2
f0();
f1();
printf("f2
}
練習 2
S!\n");
E!\n");
実行結果は
どのようになるか?
S!\n");
E!\n");
S!\n");
E!\n");
void main(){
printf("main S!\n");
f2();
printf("main E!\n");
}
H-53
解答 2
main S!
f2 S!
f0 S!
f0 E!
f1 S!
f0 S!
f0 E!
f1 E!
f2 E!
main E!
H-54
練習 3
• 下記の回路に左から0と1を入力すると,
右から0と1のどちらが出力されるか?
0
not
or
or
1
S
and
H-55
解答 3
0
0
or
1
1 not
1
0
0
1
0
1
and
0
0
or
0
S
H-56