2
$\begingroup$

Here is a theorem in my notes:

If $\phi$ is any wff such that $\neg \phi$ is not a tautology, then $\phi$ is tautologically equivalent to a conjunction of clauses.

My question is that...can this theorem hold if $\phi$ is not a tautology and so $\neg \phi$ is tautologically equivalent to a conjunction of clauses?

$\endgroup$
  • $\begingroup$ How would you write a tautology as a conjunction of clauses? Does your definition allow $x \vee \neg x$ as a clause? $\endgroup$ – Fabio Somenzi Oct 15 '18 at 5:41
  • 1
    $\begingroup$ Apply the theorem to $\lnot \phi$ : "If $\lnot \phi$ is any wff such that $¬¬ \phi$ (i.e. $\phi$) is not a tautology, then $\lnot \phi$ is tautologically equivalent to a conjunction of clauses." $\endgroup$ – Mauro ALLEGRANZA Oct 15 '18 at 12:51
  • $\begingroup$ @MauroALLEGRANZA - Sorry, I wrote the answer while you were writing your comment. If you rewrite your comment as an answer, I can delete my answer. $\endgroup$ – Taroccoesbrocco Oct 15 '18 at 13:03
1
$\begingroup$

Short answer. Yes, it does.

Long answer. The statement:

If $\varphi$ is any wff such that $\varphi$ is not a tautology, then $\lnot \varphi$ is tautologically equivalent to a conjunction of clauses.

is a corollary of the theorem stated in your question. Indeed, if $\varphi$ is any wff such that $\varphi$ is not a tautology, then $\lnot \varphi$ is a wff and $\lnot \lnot \varphi$ (which is equivalent to $\varphi$) is not a tautology. According to the theorem stated in your question (applied to $\lnot \varphi$), $\lnot \varphi$ is tautologically equivalent to a conjunction of clauses.

$\endgroup$
  • $\begingroup$ In the theorem from the notes, the "such that $\neg \phi$ is not a tautology" part is redundant. There are plenty of ways to write $\phi$ as a conjunction of clauses if $\neg \phi$ is a tautology. If clauses like $x \vee \neg x$ are not allowed, then if $\phi$ is a tautology (as opposed to $\neg \phi$) then $\phi$ has no equivalent conjunction of clauses. $\endgroup$ – Fabio Somenzi Oct 15 '18 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.