Results 1 to 3 of 3

Math Help - Not functionally complete set of connectives

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    Not functionally complete set of connectives

    Hello,
    the task is to show that the following set of connectives isn't (functionally) complete: \{ \vee, \wedge, \rightarrow, \leftrightarrow, \top \}

    I know that the negation connective can't be expressed with those, but the problem is how to prove that. I tried to roll some truth tables, but that didn't help. I think some kind of inductive proof is needed.

    Any help is appreciated, thank you very much!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765
    From Wikipedia: "Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives: ..." I don't remember if I studied the proof, but I would guess that the hard part is to prove the "if" part, i.e., not being a subset implies completeness. Your set of connectives is one of the five listed in the theorem, and once you know the name of this set, it is easy to see that it is not complete.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39
    Thanks for help. I browsed Wikipedia, but somehow managed to skip part of that article. I think the following (from Wikipedia) definition is enough for my purposes:
    "The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables"

    There seems to be some kind of modernized version of Post's proof about functional completeness:
    http://www.sfu.ca/~jeffpell/papers/PostPellMartin.pdf

    Maybe I study that, if I have enough time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] set of connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 14th 2011, 11:39 AM
  2. [SOLVED] Not Functionally Complete
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2010, 08:33 AM
  3. functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 15th 2010, 11:50 AM
  4. Logic Connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 09:57 PM
  5. Basic Connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 31st 2007, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum