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.

  • $\begingroup$ Because * is defined inductively (technically one should say recursively) on formulas you can prove things about it by induction on formulas. $\endgroup$ – 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.$$

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.