# Negation Normal Form and the length of formulas

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:

1. 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.
2. 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.

1. No. Consider $$\sigma = P$$, and $$\varphi = P \lor (P \land \neg P)$$. These are equivalent, and since $$\varphi$$ is already in NNF, $$\varphi'=\varphi$$
• @ShyPerson Hmm, how exactly is 'contains a tautology or contradiction' defined? For example, does $(P \land Q) \lor (P \land \neg Q)$ (which is equivalent to $P$) 'contain a tautology or contradiction'? Jun 20, 2019 at 11:50
• Let's try this: it 'contains a tautology or contradiction' if valid propositional rules of inference can reduce it to a shorter logically equivalent formula. So your example $(P \land Q) \lor (P \land \lnot Q)$ satisfies this definition. Jun 21, 2019 at 4:14