I'm having trouble proving this:
Let $\alpha$ be a wff such that the only possible connectives in it are $\lnot, \land, \lor$. Let $\alpha^{\ast}$ be the result of changing every $\land$ in $\alpha$ to $\lor$, every $\lor$ in $\alpha$ to $\land$, and every sentence symbol in $\alpha$ with its negation.
Prove: $\lnot(\alpha^{\ast})\vDash(\lnot\alpha)^{\ast}$ and $(\lnot\alpha)^{\ast}\vDash\lnot(\alpha^{\ast})$
I tried proving this in two way, one is Mathematical Induction on the length of the wff, and the other is with the Induction Principle (as described in Enderton's). In both ways I got stuck in the Step.
This is my attempt with Mathematical Induction:
Let $n$ be the length of $\alpha$. if $n=1$ then $\alpha$ can only be a symbol sentence and: $(\lnot\alpha)^{\ast}\overset{\alpha^{\ast}\;def}{=}(\lnot(\lnot\alpha))=\lnot(\lnot\alpha)=\lnot(\alpha^{\ast})$
Assume that every wff $\delta$ of length $1\leq j<n$ satisfies $\lnot(\delta^{\ast})\vDash(\lnot\delta)^{\ast}$ and $(\lnot\delta)^{\ast}\vDash\lnot(\delta^{\ast})$
Now we show for $n$,
Case 1: There's a wff $\beta$ such that $\alpha=\lnot \beta$ and we get that $\alpha^{\ast}=(\lnot \beta)^{\ast}$. Let $v$ be a truth assignment for the set of all sentence symbols in $\lnot(\alpha^{\ast}),(\lnot\alpha)^{\ast}$. Then:
$\overline{v}(\lnot(\alpha^{\ast}))=\overline{v}(\lnot((\lnot \beta)^{\ast}))=T\; \Leftrightarrow\;\overline{v}((\lnot \beta)^{\ast})=F \; \Leftrightarrow\; \overline{v}((\lnot(\beta^{\ast}))=F \; \Leftrightarrow\; ???? \; \Leftrightarrow\; \overline{v}((\lnot(\lnot \beta))^{\ast})=\overline{v}((\lnot\alpha)^{\ast})=T$
And that is how far i got. I thought maybe I haven't used the assumption the right way, or maybe I haven't assume the right thing.
Also I was trying to prove that $\lnot(\alpha^{\ast})=(\lnot\alpha)^{\ast}$ which I thought might also be true, but had problems there too.
Thanks for any help
First, point out that for any $\alpha$ and $\beta$:
Lemma 1. $(\alpha \land \beta)^* = \alpha ^* \lor \beta ^*$ , because doing all replacements for $(\alpha \land \beta)$ amounts to replacing the $\land$ with a $\lor$, and otherwise replacing everything in $\alpha$ and $\beta$
Lemma 2. $(\alpha \lor \beta)^* = \alpha ^* \land \beta ^*$ (same idea)
Now use structural induction to show that for any $\alpha$: $\neg (\alpha)^* \Leftrightarrow (\neg \alpha )^*$ (from which it immediately follows that both $\neg (\alpha)^* \vDash (\neg \alpha )^*$ and $(\neg \alpha )^* \vDash \neg (\alpha)^* $
Base: $\alpha = A$ for some atomic statement $A$
Then:
$\neg (\alpha)^* \Leftrightarrow \neg (A)^* \Leftrightarrow \neg \neg A \Leftrightarrow (\neg A )^* \Leftrightarrow (\neg \alpha )^*$
Step: (assuming $\neg$, $\land$ and $\lor$ are the only operators ... but the proof can easily be extended to any other operators)
Case 1: $\alpha = \neg \beta$ with inductive hypothesis: $\neg (\beta)^* \Leftrightarrow (\neg \beta )^*$
Then: $\neg (\alpha)^* \Leftrightarrow \neg (\neg \beta)^* \Leftrightarrow $ (Inductive Hypothesis) $\neg \neg (\beta)^* \Leftrightarrow ( \beta )^* \Leftrightarrow \Leftrightarrow ( \neg \neg \beta )^* \Leftrightarrow (\neg \alpha) ^*$
Case 2: $\alpha = \beta \land \gamma $ with inductive hypothesis: $\neg (\beta)^* \Leftrightarrow (\neg \beta )^*$ and $\neg (\gamma)^* \Leftrightarrow (\neg \gamma )^*$
Then: $\neg (\alpha)^* \Leftrightarrow \neg (\beta \land \gamma )^* =$ (Lemma 1) $\neg (\beta^* \lor \gamma^*) \Leftrightarrow$ (DeMorgan) $ \neg \beta^* \land \neg \gamma^* $ (Inductive Hypothesis) $ (\neg \beta)^* \land (\neg \gamma)^* =$ (Lemma 2) $ (\neg \beta \lor \neg \gamma)^* \Leftrightarrow$ (DeMorgan) $(\neg (\beta \land \gamma))^* \Leftrightarrow (\neg \alpha) ^*$
Case 3: $\alpha = \beta \lor \gamma $ ... similar to case 2