Для этого, сделаем несколько утверждений:
* # Если <tex>(x_{1}^* \ldots x_{k}^*)</tex> - набор значений <tex>x_i</tex>, удовлетворяющий дизъюнкт <tex>(x_1 \vee \ldots \vee x_k)</tex>, то существует такой набор значений <tex>z_{1}^* \ldots z_{k-3}^*</tex>, что каждый из <tex>k-2</tex> новых дизъюнктов также удовлетворен.
* # Среди значений <tex>(x_{1}^* \ldots x_{k}^*)</tex> хотя бы одно должно равняться <tex>true</tex>. Не умаляя общности, пусть для некоторого <tex>r: 1 \le r \le k, x_r = true</tex>. Тогда, пусть <tex>z_{s}^*=true</tex> для <tex>s \le r-2</tex> и <tex>z_{s}^*=false</tex> для <tex>s > r - 2</tex>. Тогда, все новые дизъюнкты также будут удовлетворены. Докажем эти утверждения. Пусть все новые дизъюнкты удовлетворяются некоторым набором значений <tex>x_i</tex> и <tex>z_i</tex>. Покажем, что тогда хотя бы один из <tex>x_i</tex> должен равняться <tex>true</tex>. Предположим, что это не так.
Таким образом, мы свели <tex>CNFSAT</tex> к <tex>3SAT</TEX>, следовательно <tex>3SAT \in NPH</tex>. Теорема доказана.
