Let us start by reconsidering the definition of the dual $\phi^*$ for a given propositional formula $\phi$. It can be summarised by the correspondences:
\begin{align}
\phi \land \psi &\overset*\iff\phi \lor \psi\\
\mathbf F &\overset*\iff \mathbf T
\end{align}
We reuse a fundamental idea of the earlier exercises in the mentioned chapter, namely that $\phi \leftrightarrow \psi$ precisely when $\phi$ and $\psi$ are satisfied by exactly the same lines in a truth table.
Observation 1: A line of a truth table is nothing more than a function $v$ which assigns to each propositional variable a value $\mathbf T$ or $\mathbf F$ and subsequently evaluates the definitions of the connectives for this assignment.
Such a $v$ is known in the literature as a valuation or a boolean interpretation. Abstracting this notion away from the intuitive use in truth tables is a big asset in proving generic theorems. This is because it allows us to discuss rigorously an "arbitrary line of a truth table".
For example, by considering the two possibilities $v(p)=\mathbf T$ and $v(p)=\mathbf F$, it is not hard to see that $v(p\lor \neg p)= \mathbf T$ for every valuation of $\{p\}$. Similarly one can show that $v(p\to q) = v(\neg p \lor q)$ for each valuation of $\{p,q\}$, thus proving equivalence of these statements.
Observation 2: $\phi$ and $\psi$ are equivalent precisely when $v(\phi) =v(\psi)$ for all valuations $v$.
We need one final ingredient before turning to the main result.
Definition: Given a valuation $v$, the valuation $v^*$ is defined by: $$v^*(p) = \begin{cases}\mathbf T&\text{ if $v(p) = F$}\\\mathbf F&\text{ if $v(p) = T$}\end{cases}$$
The desired result will follow from the following:
Theorem: For any formula $\phi$ and valuation $v$, we have: $$v(\phi^*) = v^*(\neg\phi)$$
By assumption $\phi$ will have one of the following forms:
- $\phi = p$
- $\phi = \mathbf F$
- $\phi = \mathbf T$
- $\phi = \neg \tau$
- $\phi = \tau \lor \tau'$
- $\phi = \tau \land \tau'$
I will only prove the assertion for the last possibility $\tau \land \tau'$; the other options are similar or easier. We assume that the result has been proven for $\tau$ and $\tau'$.
Note that this decomposition of $\phi$ into possible forms is known formally as structural induction; it allows us to reason about an arbitrary formula in a structural manner, similar to proving an implication like $(\phi \lor \psi)\to \tau$: we first assume $\phi$ and show $\tau$ from it, and then do the same for $\psi$.
Now for the proof:
\begin{align}
v(\phi^*) &= v((\tau\land\tau')^*)\\
&= v(\tau^* \lor \tau'^*)\\
&= f^\lor(v(\tau^*),v(\tau'^*))\\
&= f^\lor(~v^*(\neg\tau),v^*(\neg\tau')~)\\
&= v^*(\neg \tau \lor \neg\tau')\\
&= v^*(\neg(\tau\land\tau'))\\
&= v^*(\neg\phi)
\end{align}
where $f^\lor$ denotes the definition of $\lor$ in terms of truth values (so $f^\lor(\mathbf F,\mathbf F) = \mathbf F$, otherwise $f^\lor$ yields $\mathbf T$). In the second-to-last step, a De Morgan equivalence is used.
Intuitively, the above result states that for every line of a truth table for $\phi^*$, we can mechanically construct one with the same value for $\neg\phi$. Because $\neg\phi$ and $\neg\psi$ are also equivalent, this means that the constructed valuations agree on $\neg\phi$ and $\neg\psi$. Additionally, it is not hard to see that every valuation on $\neg\phi$ can be constructed in this way, and we can transform them back to valuations of $\phi^*$ since $v^{**}=v$. These ingredients together establish equivalence of $\phi^*$ and $\psi^*$.
I am assuming that by $=$, you mean logical equivalence, which I will denote by $\equiv$.
One thing that might be helpful is the following: For a compound formula $s$, let $s'$ be the formula you get by replacing every variable by its negation.
Then, you get the theorem that $s^* \equiv \lnot s'$. Unfortunately, you will need induction on $s$ to prove that:
- If $s$ is $T$ or $F$, then $s^*$ will be $F$ or $T$, respectively, as will $\lnot s' = \lnot s$.
- If $s$ is a variable $p$, then we have $s^* = p = s$, and, by the definition of $s'$, we have $s' = \lnot p = \lnot s$. Thus we have $s^* \equiv \lnot s'$.
- If $s = a \lor b$, then we assume that $a^* \equiv \lnot a'$ and $b^* \equiv \lnot b'$. Then we have
$$
s^* = a^* \land b^* \equiv \lnot a' \land \lnot b'
\equiv \lnot (a' \lor b') = \lnot s'
$$
by De Morgan's law.
- If $s = a \land b$, then we assume that $a^* \equiv \lnot a'$ and $b^* \equiv \lnot b'$. Then we have
$$
s^* = a^* \lor b^* \equiv \lnot a' \lor \lnot b'
\equiv \lnot (a' \land b') = \lnot s'
$$
by De Morgan's law as well.
Now, this has one important consequence: You mention that $s$ only contains $T$, $F$, $\land$, $\lor$ and $\lnot$, and no variables. In this case, you have $s' = s$ and thus $s^* \equiv \lnot s$, so you will never have $s^* = s$!
But if your $s$ involves variables anyways, you can find out if $s* \equiv s$ by looking at the truth table for $s$: For every entry, you check the "opposite" entry where all the variables are assigned the opposite truth value (for example the opposite of the entry where $p = T, q = F$ is the one where $p = F, q = T$), and then you check if the two entries are different.
One neat result of this is that if $s^* \equiv s$, then exactly half the ways of assigning truth values to the variables will result in $s$ becoming true!
But because the answer to the question if $s^* \equiv s$ depends on the truth table of $s$, I don't expect there to be a method of checking if $s^* \equiv s$ that is faster than just making the truth table.
Best Answer
I hope this is going to help somebody; I came up with the same solution which is known as idempotent law, plus the others: p ∧ T = p ∨ F (identity law) p∧(p∨q)=p∨(p∧q) (absorption law) (try proving logical equivalences)