<문제>전체집합[eqn: U]의 모든 부분집합 [eqn: A,`B,`C]에 대하여

[eqn: n(A SMALLINTER B SMALLINTER C)=n(A)+n(B)+n(C)-n(A CUP B)-n(B CUP C)-n(C CUP A)+n(A CUP B CUP C)] 가 성립함을 보여라

(단, [eqn: U] : 유한집합).

<증명>[eqn: n(A CUP B CUP C)=n(A)+n(B)+n(C)-n(A SMALLINTER B)-n(B SMALLINTER C)-n(C SMALLINTER A)+n(A SMALLINTER B SMALLINTER C)]은 전체집합[eqn: U]의

모든 부분집합A, B, C에 대하여 성립하므로,

[eqn: A=X ^{c} ,```B=Y ^{c} ,``C=Z ^{c}]일 때도 성립하여야 한다.

[eqn: n(X ^{c} CUP Y ^{c} CUP Z ^{c} )=n(X ^{c} )+n(Y ^{c} )+n(Z ^{c} )-n(X ^{c} SMALLINTER Y ^{c} )-n(Y ^{c} SMALLINTER Z ^{c} )+n(X ^{c} SMALLINTER Y ^{c} SMALLINTER Z ^{c} )]…①

따라서, [드 모르간의 법칙]에 의하여

① : [eqn: n(X SMALLINTER Y SMALLINTER Z) ^{c} =n(X ^{c} )+n(Y ^{c} )+n(Z ^{c} )-n(X CUP Y) ^{c} -n(Y CUP Z) ^{c} -n(Z CUP X) ^{c} +n(X CUP Y CUP Z) ^{c}]…②

한편, 임의의 [eqn: X]에 대하여, [eqn: n(X ^{c} )=n(U)-n(X)]이므로,

[eqn: n(X SMALLINTER Y SMALLINTER Z) ^{c} =n(U)-n(X SMALLINTER Y SMALLINTER Z)], [eqn: n(X ^{c} )=n(U)-n(X)], [eqn: n(Y ^{c} )=n(U)-n(Y)],[eqn: n(Z ^{c} )=n(U)-n(Z)],

[eqn: n(X CUP Y) ^{c} =n(U)-n(X CUP Y)], [eqn: n(Y CUP Z) ^{c} =n(U)-n(Y CUP Z)],[eqn: n(Z CUP X) ^{c} =n(U)-n(Z CUP X)],

[eqn: n(X CUP Y CUP Z) ^{c} =n(U)-n(X CUP Y CUP Z)]이다.

이를 ②식에 대입하여 정리하면,

② : [eqn: n(X SMALLINTER Y SMALLINTER Z)=n(X)+n(Y)+n(Z)-n(X CUP Y)-n(Y CUP Z)-n(Z CUP X)+n(X CUP Y CUP Z)]

즉, [eqn: n(A SMALLINTER B SMALLINTER C)=n(A)+n(B)+n(C)-n(A CUP B)-n(B CUP C)-n(C CUP A)+n(A CUP B CUP C)] -q.e.d