Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. We have two well-formed formulas $\varphi$ and $\sigma$ which are equivalent: $\varphi \leftrightarrow \sigma$. The formula $\sigma$ has no occurrences of the negation symbol ($\lnot$). Now let's push negation inward to reduce $\varphi$ to Negation Normal Form and call that normal form $\varphi'$. We note that $\varphi' \leftrightarrow \sigma$.
EDIT: We further stipulate that neither $\varphi$ nor $\sigma$ contain tautologies or contradictions.
Two questions:
- Can we conclude that $\varphi'$ has no occurrences of the negation symbol ($\lnot$)? If we convert both $\varphi'$ and $\sigma$ to disjunctive normal form for instance, neither should have negation symbols since we're given that $\sigma$ doesn't.
- Can we conclude that the length of $\varphi'$ is bounded above by some polynomial function of the length of $\varphi$? That is, the length of $\varphi'$ won't be exponentially larger than the length of $\varphi$? If not, please provide a counterexample.