Changing conjunction and disjunction in equivalent boolean functions.

Question

I have some difficulties to prove that if two equivalent boolean functions contain only ∧, ∨ and $\neg$ than we can change ∧ to ∨ and vice versa and the result functions will remain equivalent.

There's a hint to solve it with the induction and de Morgan's laws, but I've no idea how to use it.

Thanks in advance!

Answer 1

HINT

First, get some precise definitions going, so you can refer to those in your proof.

So, relative to any expression or function $\phi$ built up from $\neg$, $\lor$, and $\land$, define the expression $\phi^D$ to be the result of changing all $\land$'s into $\lor$'s and vice versa. Formally and recursively:

1. $A^D = A$ if $A$ is an atomic sentence
2. $(\neg \phi)^D = \neg \phi^D$
3. $(\phi \land \psi)^D = \phi^D \lor \psi^D$
4. $(\phi \lor \psi)^D = \phi^D \land \psi^D$

OK, so what you are asked to prove is that for any $\phi$ and $\psi$ built up from $\neg$, $\lor$, and $\land$: If $\phi \Leftrightarrow \psi$ then $\phi^D \Leftrightarrow \psi^D$

Now, how do you prove this? Here is one strategy:

Relative to any expression or function $\phi$ built up from $\neg$, $\lor$, and $\land$, define the expression $\phi’$ to be the sentence that one obtains by putting a negation in front of every atomic sentence occurring in $\phi$. Formally and recursively:

1. $A’ = \neg A$ if $A$ is an atomic sentence
2. $(\neg \phi)’ = \neg \phi’$
3. $(\phi \land \psi)' = \phi' \land \psi'$
4. $(\phi \lor \psi)' = \phi' \lor \psi'$

Use this to prove (using induction) the following Lemma's:

1. For any $\phi$ built up from $\neg$, $\lor$, and $\land$: $\phi^D \Leftrightarrow \neg \phi'$

2. For any $\phi$ and $\psi$ built up from $\neg$, $\lor$, and $\land$: If $\phi \Leftrightarrow \psi$ then $\phi' \Leftrightarrow \psi'$

The result you have to prove follows quickly from these two Lemma's.