Negation Normal Form and the length of formulas

512 Views Asked by At

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

There are 1 best solutions below

3
On
  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$