// 대각선논법,diagonal_argument 작성중
From: 컴여세 p41

무한이 다 같은 무한이 아니고 자연수,natural_number의 개수보다 실수,real_number의 개수가 훨씬 크다.
또, 자연수의 개수보다 자연수의 부분집합,subset의 개수가 훨씬 더 크다. Georg_Cantor가 처음으로 확인해 준 사실이다.

에 대한 각주:

다음과 같이 확인할 수 있다. 대각선 논법diagonalization 이라고 불린다.

자연수의 부분집합들의 개수가 자연수 개수만큼만 있다면 모순이 된다.
자연수의 부분집합을 자연수로 번호 붙이기에는 늘 부족하게 된다. 다음과 같은 이유 때문이다.

자연수의 부분집합들이 자연수만큼만 있다면 그 집합들을 자연수로 모두 번호 매길 수 있을 것이다.
N1, N2, N3 등등. 이제 N1부터 차례로 살피면서 자연수 집합 X를 만들 수 있는데, 이 집합이 모든 자연수의 부분집합들과는 다르게 된다!
X는 빈집합(공집합,empty_set)에서 시작해서,
N1에 1이 없으면 X에 1을 넣고, 있으면 X에 넣지 않는다. 다음으로
N2에 2가 없으면 X에 2를 넣고, 있으면 X에 넣지 않는다.
이 과정을 N3, N4 등 모두에 대해서 한다.
그러면, X는 자연수의 부분집합이 분명하지만 N1, N2 등등 모두와 다르다.
자연수로 번호 매긴 것이 다인 줄 알았는데(N1, N2 등등) 그 외에 또 있는 것이다(X).

이런 논법을 대각선 논법이라고 부르는 이유는 X를 만들 때 따지는 (N1, 1), (N2, 2), … 들이
N1, N2 등을 가로축에 쓰고
1, 2 등을 세로축에 쓰면
대각선의 점들에 해당하기 때문이다.

// 컴여세 pp. 72-73
둘 중 하나를 조건에 따라 결정하는 회로를 만들 수 있다. 즉,
들어오는 입력 x, y 중에서
선택자 z가 0이면 x를, 1이면 y를 선택하는 회로다. '''멀티플렉서multiplexer''라고 한다.
이러한 회로 역시 마찬가지로 입력과 출력을 표로 그리고 원하는 출력이 나오도록 회로를 만들어 주면 된다.

x	y	z	결과
0	0	0	0
0	1	0	0
1	0	0	1
1	1	0	1
0	0	1	0
0	1	1	1
1	0	1	0
1	1	1	1

결과가 1이 되는 xyz의 4가지 경우는 100 110 011 111 이다. 따라서 위의 작동을 하는 디지털 논리회로는 다음과 같다.

x(-y)(-z)+xy(-z)+(-x)yz+xyz

같은 일을 하는 더 간단한 회로로 다시 쓰면 아래와 같이 된다.

x(-z)+yz

// 컴여세 pp. 73-74
번호를 부르면 응답하는 디코더decoder도 회로로 만들 수 있다.

출력이 두 개의 선 x, y이다. 선택자(입력) c의 값에 따라 x나 y 중 하나만 1이 되는 회로다.

c	x	y
0	1	0
1	0	1

따라서 논리회로는 x=-c이고 y=c이다.

출력이 네 개의 선 x, y, z, w라고 하자. 이 경우 선택자(입력)는 두 개가 필요하다. 선 c와 d에 따라, 네 개의 출력 선 중에서 하나만 1이 된다.

c	d	x	y	z	w
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

따라서 논리회로는 다음과 같다.

x=(-c)(-d)
y=(-c)d
z=c(-d)
w=cd

플립플롭,flip-flop 래치,latch
// 컴여세 pp. 73-76

그리고 기억장치도 '그리고', '또는', '아닌'으로 조립할 수 있다.