f : {T, F}^n -> {T, F}가 있을 때,
0부터 2^n -1 개의 연속된 이진수를 자연수로 표현하는 게 가능하다는 건 알 거임.
가령, n=3일 때,
(0, 0, 0)= 0
(0, 1, 1)=3
(1, 0, 0)=4
(1, 1, 1)=7임.
이렇게해서,
2진법으로 나타낸 n자리 수 (x1, x2, ..., xn)을 자연수로 바꿔줌. 그렇게 자연수로 바꿔주는 함수의 표기를 N(x1, x2, .., xn)이라고 하자.
그 다음에는
일단, _ _ _ _ _ _ _ _ .... _ 이렇게 2^n개의 자리를 표시함. ({T, F}^n이 정의역인 명제 함수들을 injective하게 표현하는데 메모리가 2^n 개 이상 필요하다는 건 이론상 어쩔 수 없을 거임.)
이제, 여기에
f(x1, x2, x3, ..., xn)=k인 경우, N(x1, x2, ..., xn) 번째 자리에 k가 False면 0, k가 True면 1을 적음.
그러면, (0, 1, 0, 0, ... , 1) 이런 식으로 길이가 2^n인 수 혹은 튜플이 될 거임. 이 튜플을 A(f)라고 하겠음.
여기서
~하면 그냥 각 자리에서 0은 1로, 1은 0으로 바꿔주면 됨. A(~f)는 그냥 비트 연산으로 ~A(f) 해주면 됨.
여기서 f1 and f2 해주면 그냥 f1을 저렇게 표현하고, f2를 저렇게 표현한 뒤, 각 자리수별로 비교해서 곱해주면 됨.
A(f1 and f2)는 그냥 비트 연산으로 A(f1)&A(f2)라고 하면 됨.
가령,
f : {T, F}^2 -> {T, F} s.t.
(0, 0, 0)
(0, 1, 1)
(1, 0, 1)
(1, 1, 0)
에 대해,
A(f)는 그냥 0110 으로 표현됨.
A(~f)는 1001 로 표현됨.
근데, 2^n은 길이가 너무 길다? 각 자리를 4진법으로 표현하면 대충 log_4 (2^n) = 2^(2/n)의 길이 정도로 표현 가능하긴 함.
그 다음으로 더 짧은 표기법을 찾고 싶으면 그냥 이진수 _ _ _ ... _ 을 더 짧게 표현하는 방법을 찾아보면 됨. 간단하게는 그냥 이진법으로 나타낸 수를 4진법, 8진법, 16진법 등으로 고쳐주는 방법이 있음. string 관점에서 길이는 짧아짐.
참고로 컴퓨터 관점에서는 단순 +, *보다 저렇게 bit 연산하는 게 더 빠름.
이걸 정말로 자연수로 표현하고 싶으면, 저 n자리 2진수를 자연수로 바꾸고, (가령, 0 1 0 = 2로.)
(1+∑(k=0~n-1) 2^(2^k) + 변환된 자연수 ) 를 해주면 injective하게 자연수로 변환됨.
그리고 Conjunctive normal form 이나 Disjunctive normal form 같은 걸로 표현하는 건,
-> : {T, F}^2 -> {T, F}로 가는 함수 1개랑
not : {T, F} -> {T, F}로 가는 함수 1개를 정의해서
임의의 명제 함수를 이것들의 합성 함수로 표현해 준다는 건데, {~, and, or}을 사용해서 명제 함수를 표현하면,
위의
f : {T, F}^2 -> {T, F}는
(0, 0, 0)
(0, 1, 1)
(1, 0, 1)
(1, 1, 1)
(~x1 and x2) or (x1 and ~x2) or (x1 and x2) 라고 표현 가능함.
혹은 1 대신에 0에 집중해서 ~(x1 and x2) 라고 표현할 수도 있음.
이렇게 되면, f에 대해 min (0이 나오는 input의 수, 1이 나오는 input의 수) 를 취해서 or 이나 and를 그만큼의 개수만큼 사용해서 표현 가능함.
근데, 이것도 결국 명제함수(truth function) f를 특정 조건을 만족하는 "string"으로 표현한다는 거임.
그러면 그게 과연 정말로 짧은가는 생각해 볼 필요가 있음.
and, x1, x2, ~, (, )는 각각 길이 1짜리 string으로 볼 때, ~(x1 and x2)는 길이가 6임. 위의 방법처럼 표현한 길이 4짜리 표현이 더 짧음. 그리고 f의 정의역이 {T, F}^n이라는 점에서 n을 따로 표시해 줘야 함.
그러면 항진 명제의 경우에는 (T, n)으로 모순 명제의 경우는 (F, n)이라고 간단하게 표현할 수 있겠다만,
그러면 위의 경우에도 그냥 0 0 0 1 0 0 1 에서 앞의 0은 다 생략하고, 1 0 0 1이라고 쓰고
(1 0 0 1, n) 이라고도 표현 가능하고,
아니면, 0 0 0 1 0 0 1 에서 1이 4번째, 7번째에 있으므로
((4, 7), 7) 이라고 표현할 수도 있음. (근데, 여기서 명제함수를 string으로 변환했을 때 길이는 2의 거듭제곱 꼴이어야 하긴 함.)
1 1 0 1 1 0 0 0 같은 경우는
((1, 2, 4, 5), 8) 이라고 표현할 수도 있음.
아니면, tuple 개수 한 개 더 추가해서
1이 적으면 1의 위치를 적은 뒤 T를 옆에 적고,
0이 적으면 0의 위치를 적은 뒤 F를 옆에 적어서,
언제나 길이가 2^(n-1)+2 이하가 되게 하는 방법이 있음.
가령, 1 1 0 1 0 1 1은 0이 적으니까
((3, 5), F, 8) 이라고 적고
0 1 1 0 1 0 0 0은 1이 적으니까
((2, 3, 5), T, 8)이라고 적을 수 있음.
그리고 이러면 ,
~((a, b, c, d), F, n) 은 그냥 ((A, B, C), T, n)으로 적을 수 있음.
그리고 ((a, b, c, d), F, n) and ((a, b, c, d), T, n) 은
(A, B, C) - (a, b, c, d) 로 차집합으로 표현한 (x1, x2, .., xk)에 대해, ((x1, x2, ..., xk), T, n)으로 적어주면 됨.
((a, b, c, d), F, n) and ((A, B, C), F, n) 형태로 둘 다 F면
((a, b, c, d)U (A, B, C) , F, n)으로 적으면 됨.
((a, b, c, d), T, n) and ((A, B, C), T, n) 형태로 둘 다 T면
((a, b, c, d)∩(A, B, C) , F, n) 이라고 표현해 주면 됨.
어쨋든 이렇게
((1의 위치들), T, 명제함수의 input의 길이) 또는 ((0의 위치들), F, 명제함수의 input의 길이)로 표현하는 게 일단은 직관적으로 표현/변환하는 것의 내 지능의 한계임.
만족스럽지 않으면 어느 부분이 만족스럽지 않은지 말해주셈.
