I'm asked to prove that every propositional assertion in Fuzzy Logic, expressed using the standard propositional connectives $\{\land, \lor,\lnot, \rightarrow, \leftrightarrow\} $ can be expressed in Disjunctive Normal Form (DNF).

I want to prove by induction on formulas, using 'if $\phi$ and $\psi$ are propositional variables, then they are already in DNF' as a base case, and showing that applying either $\lnot$ or $\lor$ preserves DNF, taking $\{\lnot, \lor \}$ to be a complete set of connectives in this case. (Alternatively, I could take the set of $\{\lnot, \rightarrow\}$, or $\{\lnot, \land\}$)

First, eliminate $\leftrightarrow$ by $\phi \leftrightarrow \psi \equiv (\phi \rightarrow \psi) \land (\psi \rightarrow \phi)$, eliminate $\rightarrow$ by $(\phi\rightarrow\psi)\equiv \lnot\phi \lor \psi$, and eliminate $\land$ by $\phi\land\psi \equiv\lnot(\lnot\phi\lor\lnot\psi)$. We then have $\lnot$ and $\lor$.

This seems to be the right track, since these are the connectives used in DNF, but where do I go from here?

NOTE: An earlier version of this question simply asked how to eliminate $\land$.


1 Answer 1


$\phi \land \psi \equiv \lnot (\lnot \phi \lor \lnot \psi) \equiv \lnot (\phi \implies \lnot \psi)$

  • $\begingroup$ Oh man.. De Morgan, of course! Thanks! $\endgroup$
    – J.R.CD
    Feb 23, 2016 at 16:57

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.