두 명제 P, Q에 대해, 

P가 참일 때, Q가 참이고, 

P가 거짓일 때, Q가 거짓이면, 

P와 Q를 서로 동치라고 한다. 

임의의 명제 (좀 더 엄밀히는 0차 술어 논리의 명제)에 대해, 그 명제랑 동치이고 논리적 연결사가 {and, not, or}만으로 이루어진 명제가 존재한다는 것이 알려져 있다. 

가령, ((P Q) -> ~R) 는 ((~P or ~Q) and (P or Q)) or ~R 이랑 동치이다.   (~은 not이라는 의미이다.)

(P, Q, R에 참/거짓 값을 아무렇게나 부여해도 두 명제는 서로 참이다.)

이런 식으로 논리적 연결사들의 집합 S에 대해,

임의의 명제 (좀 더 엄밀히는 0차 술어 논리의 명제)에 대해, 그 명제랑 동치이고 연결사가 S의 원소들만으로 이루어진 명제가 존재한다면, 그 S를 adequate set이라고 부른다. 

즉, {and, or, not}은 adequate set이다. 

그러면, {and, or}은 adequate set일까? 

아니다. 왜냐하면, 연결사가 모두 {and, or} 만으로 이루어진 명제는 절대 모순 명제가 될 수 없기 때문이다. 

즉, {and, or} 만으로는 (P and ~P)와 동치인 명제를 만들 수 없다. 

그러면, {→, ~}은 어떨까?

이건 adequate set이다. 왜냐하면, A or B는 (~A->B) 와 동치이고, (A and B) 는 ~(~A->B)와 동치이다. 따라서 

임의의 명제에 대해 {and, or, ~}으로만 연결된 동치인 명제가 존재하고, 그 동치인 명제에 대해 다시 {→, or}만을 이용해서 동치인 명제를 찾을 수 있기 때문이다. 

심지어 원소가 한 개인 adequate set도 있다. 

nand라는 논리적 연결사가 있는데, 이는 (A nand B)는  A와 B 둘 다 참이면 거짓, 그 외에는 참이 되게 하는 연결사이다. 

이 {nand}는 adequate set임이 알려져 있다. 

(~A는 (A nand A) 와 동치이고,  

(A and B)는 ((A nand B) nand (A nand B)) 와 동치이다.)

그러면,  과연 {~, }은 adequate set일까? (즉, 임의의 명제에 대해,  그 명제랑 동치이고 모든 연결사가 ~ 나 인 명제가 존재할까?)