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 Answer 1

  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$
  • $\begingroup$ I've edited the question to address your counterexample. $\endgroup$
    – ShyPerson
    Jun 20, 2019 at 2:31
  • $\begingroup$ @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'? $\endgroup$
    – Bram28
    Jun 20, 2019 at 11:50
  • $\begingroup$ 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. $\endgroup$
    – ShyPerson
    Jun 21, 2019 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.