A formula $A$ is a tautology if it is true with every assignment.
A formula $A$ is satisfiable if there is at least an assignemnt $v$ such that $A$ is true for $v$.
If $A$ is true for the assignment $v$, then its negation, $¬A$, is false for that assignment.
A formula $A$ is a tautology iff its negation, $¬A$, is not satisfiable.
The complement of a decision problem :
is the decision problem resulting from reversing the yes and no answers.
Thus, in a nutshell, if the answer to the problem "is $A$ in TAUT ?" is NO, then $¬A$ is in SAT.
More precisely, the problem of determining if some formula $A$ is not a tautology is thus equivalent to the problem of determining if the negation of the formula, $¬A$, is satisfiable.
It seems to me that it is only a terminological issue. Compare with :
Now we define some additional complexity classes related to $\text {P}$ and $\text {NP}$.
If $L ⊆ \{ 0, 1 \}^∗$ is a language, then we denote by $\overline L$ the complement of $L$.
We make the following definition: $\text {coNP} = \{ L \mid \overline L ∈ \text {NP} \}$.
$\text {coNP}$ is not the complement of the class $\text {NP}$. The following
is an example of a $\text {coNP}$ language: $\overline {\text {SAT} } = \{ \varphi \mid \varphi \text { is not satisfiable} \}$.
The decision problems (or languages) are complementary : not the corresponding classes of formulae.
There are a few mistakes in your truth table. The third and fourth rows have the same values for $\phi$, $\varphi$ and $\theta$ so you have missed out one combination. And some of your truth values for $\phi\wedge(\varphi\wedge\theta)$ are wrong. It might be easier to work these out if you have a column for $\varphi\wedge\theta$, as you did for $\phi\wedge\varphi$ when working out the values for the first conjunction.
Best Answer
Wikipedia : "two formulae are equisatisfiable if the first formula is satisfiable whenever the second is". In order that $p$ and $\neg p$ to be equisatisfiable a very weak interpretation of whenever must be adopted.
Wikipedia: "Equisatisfiability is generally used in the context of translating formulae," examples "Skolemization" and "translations into conjunctive normal form". In these examples the interpretation of whenever could be asymmetric. In any model that the first sentence is satisfiable the second sentence is satisfiable.
I am no expert and would be delighted to be corrected. But I find it hard to believe that when people say "Skolemization results in equisatisfiable sentences not equivalent sentences" that they are adopting such a weak interpretation of equisatisfiable.
As symmetry is implied in the Wiki description of equisatisfiable we could take a reasonably standard approach (In category theory adjunctions are frequently interpreted as weak equalities) and interpret equisatisfiable to imply the existence of a Galois mapping connecting the two sentences. Then the asymmetry caused by one term containing a superset of non-logical functions can be modeled by requiring the Galois connection be a retract (a Galois connection with one sided inverse) regards david