3
$\begingroup$

I'm not really used to inductive proofs at all but I have to proof the associative property in logic inductively, a general description is as followed:

Is $A_l$ a left associative and $A_r$ a right associative form in $B = \bigvee_{i=1}^{n} p_i$ then: $A_l \equiv A_r$ or $((p \vee q) \vee r) \equiv (p \vee (q \vee r))$.

Or discribed more formal: $\bigvee_{i=1}^{n-1} p_i \equiv \bigvee_{i=1}^{n-1} p_{i+1}$

If someone knows how to solve it, it would be nice if I could get a description how to do induction in general with this as an example.

  • 0
    I've added an "example", thank you2011-05-09

1 Answers 1

2

Supposing you mean

$A_l = (((p_1\lor p_2) \lor p_3) ... \lor p_{n-1}) \lor p_n$

and

$A_r = p_1\lor(p_2 \lor (p_3 \lor ... (p_{n-1} \lor p_n)))$

to do the induction, assume that associativity holds for where you don't have $p_n$ involved, then see if you can use that to manipulate $A_l$, preserving equality, to $A_r$.

The next step is to assume that $A_l(n-1) = A_r(n-1)$ where

$A_l(n-1) = ((p_1\lor p_2) \lor p_3) ... \lor p_{n-1}$

and

$A_r(n-1) = p_1\lor(p_2 \lor (p_3 \lor ... p_{n-1}))$

The crux of the matter is to, using the latter as a fact, to show that you can do it for $n$, that is show that $A_l = A_r$. You know that $A_l = A_l(n-1) \lor p_n$. You can't do that directly to $A_r$, but oyou can replace $p_{n-1}$ with $p_{n-1} \lor p_n$ to get $A_r$. With those manipulations, how do you know that $A_l$ is equal to $A_r$?

Of course you still need to do a base case.

  • 0
    Ok, this finally did it, thanks for your efford2011-05-10