Results 1 to 11 of 11

Math Help - Induction help me please

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    calgary
    Posts
    6

    Induction help me please

    Consider the following recursive definition of the set of all propositional formulas F

    Base Case: i N pi ∈ F (pi is a propositional variable) 1


    3. We can define sorted lists of integers as follows.



    InductionStep: f∈Ff∈F
    f1,f2 ∈F f1 f2 ∈F
    f1,f2 ∈F f1 f2 ∈F
    And, F contains no other elements than defined above.
    Recall that propositional formulas f1 and f2 are logically equivalent if and only if f1 and f2 evaluate to the same value, no matter how their variables are set.
    The goal is to prove that for all propositional formulas f F, there is an equivalent propositional formula f∈ F such that the only negation symbols () in fare applied to individual propositional variables.
    For example, the formal (p1 p2) p3 is in F and its equivalent formula (p1 p2) p3 has the negation symbols only applied to the individual propositional variables. You are allowed to use propositional logic equalities such as (p q) = p q in your proof.
    (a) Prove the goal using structural induction.
    (b) Prove the goal using complete induction on the number of logical operators (, , and ) that is used in formula f.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    calgary
    Posts
    6

    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∈Ff∈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 ;(
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Induction help me please

    Quote Originally Posted by Manueldodo View Post
    "3. We can define sorted lists of integers as follows. " <- sorry I added it accidentally. I know how to get ∀f∈Ff∈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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2013
    From
    calgary
    Posts
    6

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Induction help me please

    Quote Originally Posted by Manueldodo View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2013
    From
    calgary
    Posts
    6

    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((
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Induction help me please

    Quote Originally Posted by Manueldodo View Post
    I see why P(n) is not enough.
    Then why?

    Quote Originally Posted by Manueldodo View Post
    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 View Post
    even number of operators((
    Why do you think it is even?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2013
    From
    calgary
    Posts
    6

    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(
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jan 2013
    From
    calgary
    Posts
    6

    Re: Induction help me please

    thank you anyway
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction.
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: November 13th 2010, 03:37 PM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 17th 2008, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum