Re: Induction help me please

Do you know what structural induction and complete induction are? Have you read example proofs using these methods? Do you understand the recursive definition of formulas? (By the way, what do "sorted lists of integers" have to do with formulas?) In other words, please describe precisely your difficulty.

Re: Induction help me please

"3. We can define sorted lists of integers as follows. " <- sorry I added it accidentally. I know how to get –∀f∈F¬f∈F

– ∀f1,f2 ∈F f1 ∧f2 ∈F

– ∀f1,f2 ∈F f1 ∨f2 ∈F.

By that I mean that I have a base case, Induction Hypothesis. I know how to get to "1 ∧f2 ∈F, f1 ∨f2 ∈F etc". But then I dont know what to do to get the goal that he only negation symbols (“¬”) in f′ are applied to individual propositional variables ;(

Re: Induction help me please

Quote:

Originally Posted by

**Manueldodo** "3. We can define sorted lists of integers as follows. " <- sorry I added it accidentally. I know how to get –∀f∈F¬f∈F

– ∀f1,f2 ∈F f1 ∧f2 ∈F

– ∀f1,f2 ∈F f1 ∨f2 ∈F.

By that I mean that I have a base case, Induction Hypothesis. I know how to get to "1 ∧f2 ∈F, f1 ∨f2 ∈F etc".

What you wrote is a definition, not a proof. As such, it does not have an induction hypothesis. I'll assume that you understand the recursive definition of formulas, but you still have not answered the other questions in post #2. At the moment, I can't find an easy tutorial on structural induction on the Internet. You should check your textbook or lecture notes for example proofs.

If f is a propositional formula, let N(f) mean that negations in f are applied to propositional variables only. Also, let E(f) mean that there exists a formula f' such that f is equivalent to f' and N(f'). You need to prove E(f) for all formulas f.

Structural induction works as follows. First you need to show E(p) for any propositional variable p. Then show that if E(f) and E(g) for some formulas f and g, then E(f \/ g), E(f /\ g) and E(~f).

Re: Induction help me please

thank u! I got it. One more question: how deal with this condition: Prove the goal using complete induction on the number of logical operators (∧, ∨, and ¬) that is used in formula f TO THE SAME PROBLEM?

Re: Induction help me please

Quote:

Originally Posted by

**Manueldodo** One more question: how deal with this condition: Prove the goal using complete induction on the number of logical operators (∧, ∨, and ¬) that is used in formula f TO THE SAME PROBLEM?

This proof uses induction on natural numbers, but where in the induction step you assume not just P(n), but all of P(0), P(1), ..., P(n) to prove P(n + 1). This is often called strong induction.

In this case, P(n) means that for all formulas f, if f has n logical operators, then E(f). For the induction step, assume P(0), ..., P(n) and let some formula f have n + 1 operators. Then f has to have the form f1 /\ f2, f1 \/ f2 or ~f1 for some f1, f2. What can be said about the number of operators in f1 and f2? Do you see why assuming just P(n) is not enough?

Re: Induction help me please

I see why P(n) is not enough. So assuming that P(0)....P(n) is true, then number of operators in f1 and f2 is going to be n+1 operators.....even number of operators((

Re: Induction help me please

Quote:

Originally Posted by

**Manueldodo** I see why P(n) is not enough.

Then why?

Quote:

Originally Posted by

**Manueldodo** So assuming that P(0)....P(n) is true, then number of operators in f1 and f2 is going to be n+1 operators

By the "number of operators in f1 and f2," do you mean the number of operators in f1plus the number of operators in f2? Even so, this number is one less than the number of operators in f1 /\ f2.

Quote:

Originally Posted by

**Manueldodo** even number of operators((

Why do you think it is even?

Re: Induction help me please

They asked us use complete induction....so we cannot apply simple induction here. I dont knwo..I totally lost, sorry(

Re: Induction help me please

I described the proof outline in post #6. I don't think you would be asked to come up with this proof if you have not been exposed to complete (or, strong) induction in the past. I recommend looking at the proofs you have.

Re: Induction help me please