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
    Should the "Is" in the second paragraph be "If"?2011-05-09
  • 0
    I'm not sure what $A_l$ and $A_r$ supposed to be.2011-05-09
  • 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
    Oh this helps, thank you!2011-05-10
  • 0
    but I'm not really know how to go from here, it would be helpful if you could be more detailed2011-05-10
  • 1
    @beyeran: to apply a proof technique to a proof in some domain you have to know something about the technique apart from the domain. You probably studied in your class the technique of induction proofs in general and with specific examples but not for propositional logic, and separately you probably studied propositional logic. So I mentioned in my answer what looks to me like the first step in setting up the induction step of the proof. The next step is 'use _that_ to manipulate' where _that_ is the inductive hypothesis (that is, in terms of $n-1$). I will add a further hint.2011-05-10
  • 0
    Ok, this finally did it, thanks for your efford2011-05-10