# equivalent formulas

Let $\alpha$ be a formula of the sentential logic with $\wedge, \vee$ and $-$ as its only connectives. Let $\alpha^{*}$ be the formula obtained from $\alpha$ changing each letter $A_i$ in $\alpha$ by $-A_i$, $\wedge$ by $\vee$ and $\vee$ by $\wedge$. Show that $-\alpha\Leftrightarrow\alpha^{*}$

(Hint: define $*$ inductively)

as an example: $(A_1\vee A_2)^{*}=(-A_1\wedge -A_2)$

basically what I need to prove is that $\alpha^{*}=-(\alpha)$ but I don't know how to do that formally.

• Because * is defined inductively (technically one should say recursively) on formulas you can prove things about it by induction on formulas. – Trevor Wilson Oct 10 '13 at 5:54

We have - as the hint suggests - inductively

1. $p^* = \neg p$ for each variable $p$
2. $(\neg\alpha)^* = \neg \alpha^*$
3. $(\alpha \lor \beta)^* = \alpha^* \land \beta^*$
4. $(\alpha \land \beta)^* = \alpha^* \lor \beta^*$

Now we will prove by induction, that $\alpha^* \equiv \neg \alpha$:

1. If $\alpha = p$, then $\alpha^* = \neg p$, and $\neg\alpha = \neg p$, so even $\alpha^*= \neg\alpha$.
2. If $\alpha = \neg \beta$, then by 2. above $\alpha^* = \neg \beta^*$, by induction $\beta^*\equiv \neg \beta$, hence $$\alpha^* = \neg\beta^* \equiv \neg\neg \beta = \neg \alpha$$
3. If $\alpha = \beta \lor \gamma$, then as by induciton $\beta^*\equiv \neg \beta$ and $\gamma^*\equiv \neg\gamma$, we have $$\alpha^* = \beta^* \land \gamma^* \equiv \neg\beta \land \neg \gamma \equiv \neg (\beta \lor \gamma) = \neg \alpha.$$
4. If $\alpha = \beta \land \gamma$, then as by induciton $\beta^*\equiv \neg \beta$ and $\gamma^*\equiv \neg\gamma$, we have $$\alpha^* = \beta^* \lor \gamma^* \equiv \neg\beta \lor \neg \gamma \equiv \neg (\beta \land \gamma) = \neg \alpha.$$