문제 : {~, ↔}이 adequate set인가?


{~, and}가 adequate set이라는 것에서부터 이 문제는 


~과 ↔ 만을 사용하여 (P1 and P2)와 동치인 명제를 만들 수 있냐는 질문으로 바뀔 수 있습니다. 



어떤 명제 Q가 (P1 and P2) 와 동치라는 건, 


P1, P2의 가능한 모든 진리값에 대해, Q와 P1 and P2의 진리값이 서로 같다는 의미죠. 


(P1, P2)의 가능한 값으로는 


(T, T)

(T, F)

(F, T)

(F, F)로 총 4개가 있죠. 


다만, ~과 ↔로만 이루어진 명제 Q가 반드시 P1, P2의 단순명제들로만 이루어지리라는 보장은 없습니다. 


가령, ~(P1↔ P2) 는 ((P1↔ P2) ↔ ~(P3↔ P3) )와 동치입니다. 



그러니 n개의 단순명제, P1, P2, P3, .., Pn와 {~, ↔}만으로 구성된 명제 Q에 대해 생각해 줍시다. 


이러한 임의의 명제 Q에 대해, Q에 대응하는 다음의 진리 함수 f_Q : {T, F}^n ->{T, F} 를 생각해 줄 수 있습니다. 


f_Q( A1, A2,...., An)={  T  (1~n까지 모든 k에 대해, Pk가 Ak 일 때, Q가 참)

                                    {  F  (1~n까지 모든 k에 대해, Pk가 Ak일 때, Q가 거짓)



그러면, ~, ↔만으로 이루어진 명제 Q에 대해, f_Q로 어떤 것들이 올 수 있는지를 확인해 봅시다. 


참고로, f_Q의 정의역의 원소의 개수는 2^n 개, 공역의 원소의 개수는 2개입니다. 


그러면 증명해주고자 하는 것은,


f_Q(A1, A2,..., An)=T가 되는 순서쌍 (A1, A2,..., An) 의 개수는 0, 2^(n-1), 2^n 중 하나라는 것입니다. 



이제 수학적 귀납법으로 증명을 해 보죠. 


임의의 명제에 대해, 


i) n=1인 경우.


그러면, f_Q : {T, F}->{T, F}이니


정의역의 원소의 개수가 2개라서, 정의역의 부분집합의 원소의 개수는 0개, 1개, 2개이므로 위 성질을 만족한다. 



ii) 0에서 m까지의 모든 정수 k에 대해 위 성질이 성립한다고 하자.

(즉, k개의 명제 P1, P2, ..., Pk와 {~, ↔}로 이루어진 임의의 명제 P에 대해, f_P(A1, A2,..., Ak)=T가 되는 순서쌍 (A1, A2,..., Ak) 의 개수는 0, 2^(k-1), 2^k 중 하나이다.) 


n=m+1이라고 하자. 


Q에서 P(m+1)을 전부 (P1 ↔ P1)으로 치환한 명제를 A라고 하고,

Q에서 P(m+1)을 전부 ~(P1 ↔ P1)으로 치환한 명제를 B라고 하자. 


그리고 이때, 

~(P↔Q)와 (~P↔ Q)와 (P↔ ~Q)가 서로 동치, 즉, ~을 괄호 밖으로 빼내 줘도 동치라는 것과

~~P와 P가 서로 동치라는 것을 활용해서, 


가령,  

((~P1↔~~P2)↔ (P3↔~~P4)),

(~~~(P1↔P2)↔ ~~(P3↔P4)),

~~~~~((P1↔P2)↔ (P3↔P4)) 들은 서로 동치이다. 



그러면, A에서 괄호 안에 있는 모든 ~들을 연쇄적으로 밖으로 빼내줄 수 있고, 이렇게 빼내주면, A와 동치인 ~~~..~A'꼴로 만들어 줄 수 있고, 


마찬가지로 B에서 괄호 안에 있는 모든 ~들을 연쇄적으로 밖으로 빼내줄 수 있고, 이렇게 빼내주면, B와 동치인 ~~...~B'꼴로 만들어 줄 수 있으며,


이때, A'과 B'은 각각 P1, P2, ..., Pm과  {↔}만으로 이루어진 서로 같은 모양의 명제이다. 


그러면, 

A와 B, A'과 B'은 각각 P1, P2, ..., Pm과  {~, ↔} 으로 구성된 명제들이고, 

이들을 각각 진리 함수로 치환한 

g_A : {T, F}^m ->{T, F},

g_A' : {T, F}^m ->{T, F}

g_B : {T, F}^m ->{T, F},

g_B' : {T, F}^m ->{T, F}  를 살펴보면, 


g_A' = g_B'이고, 


-T=F, -F=T, a는 명제 A 안의 ~ 개수, b는 명제 B 안의 ~ 개수라고 했을 때,


g_A = (-1)^a *g_A'    

g_B = (-1)^b * g_B' , 


즉, g_A=(-1)^(b-a) *g_B 이다. 


또한, 

g_A(A1, A2,..., Am) =f_Q(A1, A2,..., Am, T)

g_B(A1, A2,..., Am) =f_Q(A1, A2,..., Am, F)  가 모든 (A1, A2, ..., Am)∈{T, F}^m에 대해 성립한다. 


g_A(A1, A2,..., Am) =f_Q(A1, A2,..., Am, T)= T를 만족하는 (A1, A2,..., Am)의 개수를 A_Q라고 하고, 

g_B(A1, A2,..., Am) =f_Q(A1, A2,..., Am, F)=T를 만족하는 (A1, A2,..., Am)의 개수를 B_Q라고 하자. 


그러면, A_Q와 B_Q는 귀납법 가정에 의해 0, 2^(m-1), 2^m개여야 한다. 


만약 g_A= g_B이면, 당연히 A_Q=B_Q여야 하므로, A_Q+B_Q∈{0, 2^m, 2^(m+1)}이 성립한다. 


만약 g_A=-g_B 이면, 

g_A(A1, A2,..., Am) =T이면 g_B(A1, A2,..., Am) =F 이므로 A_Q≤2^m -B_Q 가 성립,  (2^m-B_Q는 g_B =F인 경우의 수이다.)

g_A(A1, A2,..., Am) =F이면 g_A(A1, A2,..., Am) =T이므로  2^m-A_Q≤B_Q 가 성립.   

2^m≤ A_Q+B_Q≤2^m , A_Q+B_Q=2^m이다. 



따라서 A_Q+B_Q∈{0, 2^m, 2^(m+1)} 이고, 

f_Q(A1, A2,..., Am, A(m+1))=T를 만족하는  (A1, A2,..., Am, A(m+1))의 개수는 0, 2^m, 2^(m+1) 중 하나이다. 






따라서, f_Q(A1, A2,..., An)=T가 되는 순서쌍 (A1, A2,..., An) 의 개수는 0, 2^(n-1), 2^n 중 하나입니다. 



그러면 여기서 귀류법으로 


~과 ↔ 만을 사용하여 (P1 and P2)와 동치인 명제 Q가 존재한다고 해봅시다. 

이 명제 Q는 P1, P2, ..., Pn의 단순명제로 이루어져 있고, 


f_Q 와 f_(P1 and P2)는 서로 같아야 합니다. 


하지만, f_(P1 and P2) (A1, A2, ..., An)=T를 만족하는 (A1, A2, ..., An) 의 경우는, A1과 A2가 T인 경우로 총 2^(n-2)개여야 하고, 

2^(n-2)는 {0, 2^(n-1), 2^n}의 원소가 아닙니다. 즉,  f_(P1 and P2) (A1, A2, ..., An)≠f_Q (A1, A2, ..., An) 인 (A1, A2, ..., An)이 존재하며, 이는 Q와 (P1 and P2)가 서로 동치라는 것에 모순입니다. 



따라서, 

아무리 많은 단순 명제를 사용하더라도 ~과 ↔ 만을 유한 번 사용해서는 절대로 (P1 and P2)와 동치인 명제를 만들 수 없습니다.


따라서 {~, ↔}는 adequate set이 아닙니다.