#noindex
## fork할때 새 페이지에 noindex 넣을 것
<<tableofcontents>>
= 대각선논법 간단한 설명 SNU이광근 =
// 대각선논법,diagonal_argument 작성중
From: 컴여세 p41

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

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

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

자연수의 부분집합들이 자연수만큼만 있다면 그 집합들을 자연수로 모두 번호 매길 수 있을 것이다.
N1, N2, N3 등등. 이제 N1부터 차례로 살피면서 자연수 집합 X를 만들 수 있는데, 이 집합이 모든 자연수의 부분집합들과는 다르게 된다!
X는 빈집합([[VG:공집합,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 등을 세로축에 쓰면
대각선의 점들에 해당하기 때문이다.

= 선택: 멀티플렉서 multiplexer mux =
// 컴여세 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
= 응답: 디코더 decoder =
// 컴여세 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 =
[[VG:플립플롭,flip-flop]] [[래치,latch]]
// 컴여세 pp. 73-76