Results 1 to 2 of 2

Math Help - set of connectives

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    set of connectives

    How do we show that the set of connectives \{ \to \} is not complete?

    I'm not sure how to prove it is or it is not complete. But I know how to test for adequacy. And I know the set of standard connectives is adequate \{\neg, \wedge, \vee, \to, \leftrightarrow \}, so a set of connectives is adequate if we can express all the standard connectives in terms of this set. There is a test for adequacy of connctives. But if prove that the set is not adequate, how do we know if it failed completeness?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: set of connectives

    Implication is true if both arguments are true, so by induction any function built from -> returns true when all arguments are true. Therefore, negation is not expressible.

    For a characterization of completeness, see Post's theorem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Not functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 17th 2010, 04:15 AM
  2. functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 15th 2010, 11:50 AM
  3. Logic Connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 09:57 PM
  4. Disproving the completeness of a set of connectives
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 18th 2008, 12:09 PM
  5. Basic Connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 31st 2007, 04:34 AM

/mathhelpforum @mathhelpforum