ああ、分かった。

S1'とS2'から共通する部分集合を取り除けば、
S1''=S(1,0,0,0)+S(0,1,1,1)
S2''=S(1,1,1,0)+S(0,0,0,1)

A△B=C△D⇔S1=S2⇒S1'=S2'⇒S1''=S2''なので、S(1,0,0,0)+S(0,1,1,1)=S(1,1,1,0)+S(0,0,0,1)
この両辺をS1=S2の両辺から取り除けば、 S(1,0,1,1)+S(0,1,0,0)=S(0,0,1,0)+S(1,1,0,1)

以上より、S3=S(1,0,0,0)+S(1,1,0,1)+S(0,0,1,0)+S(0,1,1,1)
の右辺にこれらの等式の右辺を代入すれば、S3=S(1,1,1,0)+S(1,0,1,1)+S(0,1,0,0)+S(0,0,0,1)=S4
となるので、S3=S4⇔A△C=B△D

で、証明終了。