結論：上がトートロジー、下が矛盾です。
Wikipediaの真理値表を眺めていると入力にかかわらず常に真、常に偽である項目があることに気づきました。
これがトートロジーと矛盾です。
Nand2TetrisによるとNAND素子で全ての演算ができるということだったので、トートロジーと矛盾もNANDから導出できないか考えてみました。
で、できたのが冒頭の図です。
NOT、OR、ANDしか使っていないので、これはやはりNANDから導けるということですね。
この回路に使用価値があるのかといわれると微妙ですが（VDD、GNDの方がシンプル）、NANDの完全性を確かめられた気がします。