0
$\begingroup$

I have the formula: $A_n = \bigvee^{n-1}_{i=0}( X_i \oplus X_{i+1} )$ Now I have to transform it to an equivalent formula with only $\neg , \vee$ and $\wedge$. Then I have to prove it with induction. So i transformed it to: $A_n = \bigvee^{n-1}_{i=0}( \neg X_i \wedge X_{i+1} )\vee(X_i \wedge \neg X_{i+1})$. Hope that's ok so far. Then in the induction basis I thought I could prove with solving the value table, (which worked). But is that correct to solve it about that? And in the induction step I don't know how to sum up the formula: (btw. I'll induce over $n-1$ to $n$ not from $n$ to $n+1$).
$(\neg X_{n-1} \wedge X_n) \vee (X_{n-1}\wedge X_n) \bigvee_{i=0}^{n-2}(\neg X_{i} \wedge X_{i+1}) \vee (X_{i}\wedge X_{i+1})$ = by the induction hypothesis: $(\neg X_{n-1} \wedge X_n) \vee (X_{n-1}\wedge X_n)\bigvee_{i=0}^{n-2}X_{i} \oplus X_{i+1}$

...?

Thanks for help!

$\endgroup$
0
$\begingroup$

It's very straightforward. The base case ($n=1$) is just $$ X_0 \oplus X_1 \iff (X_0 \wedge \neg X_1) \vee (\neg X_0 \wedge X_1)\tag{$Eq_1$} $$ You can establish this by any means at your disposal: truth tables, a derivation, definitions and equivalences you already know and can appeal to, etc.

Induction Hypothesis (IH): Assume $$ \bigvee^{n-1}_{i=0}( X_i \oplus X_{i+1} ) \iff \bigvee^{n-1}_{i=0}((X_i \wedge \neg X_{i+1}) \vee (\neg X_i \wedge X_{i+1})) \tag{$Eq_n$} $$ Using the identity $$ X_n \oplus X_{n+1} \iff (X_n \wedge \neg X_{n+1}) \vee (\neg X_n \wedge X_{n+1}) \text{,}\tag{Id} $$ "or"ing the LHS and RHS of (Id) onto the LHS and RHS of ($Eq_n$) respectively, gives the desired result, with the "big vee" index $i$ ranging from $0$ to $n$.

$\endgroup$

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.