Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Structural Induction

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    hk
    Posts
    1

    Structural Induction

    Hi everyone

    Im studying boolean algebra and one question is about checking functionally complete
    Ive search a lot on the internet but still cant figure out how to do this.

    Show { AND , <=> } is functionally incomplete

    Can anyone give me some hints?

    My idea is if we have a proposition which value is True

    P | NOT P | P AND P | P<=> P
    T F T T T T

    we cant build a false using these operations, so it is not a functionally complete set

    But how to do this in induction? Thank you
    Last edited by jackchan100; August 26th 2012 at 02:49 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Structural Induction

    You have the right idea: all four connectives in the set are truth-preserving. See also Post's characterization of functional completeness.

    Do you know the inductive definition of propositional formulas? The induction principle for formulas is the flip side of the definition. The definitions says that strings of symbols built using certain rules are well-formed formulas. The induction principle says that if a certain property is true for strings of symbols built using those rules, then the property holds for all well-formed formulas. Essentially, the first part (the definition) approximates the set of formulas from below by saying which strings are considered formulas. The second part (the induction principle) limits the set of formulas by saying that only strings built using those rules are formulas.

    Formally, the induction principle for formulas built from AND, OR, => and <=> is the following. Let P be a property. If P holds of atoms and if the fact that P holds of x and y implies that P holds of x AND y, x OR y, x => y, x <=> y, then P holds of all formulas built from AND, OR, => and <=>.
    Thanks from jackchan100
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Structural Induction problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 17th 2012, 09:47 PM
  2. Please check my work: Structural Induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 17th 2012, 11:16 AM
  3. help with structural induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 1st 2011, 04:09 PM
  4. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  5. structural induction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 19th 2009, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum