Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to prove a set of propositional connectives is NOT adequate?

  1. Jun 9, 2010 #1
    I know how to prove if a set is adequate (all the main conncectives can be made from the set), but how would you prove that it is impossible to make all the connectives using this set?
    For instance how would you prove if a set of connectives {and, or} is NOT adequate?

    This is a question I thought of for preperation for a exam.

    Any answer is appreciated.

    Thanks
     
  2. jcsd
  3. Jun 11, 2010 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

  4. Jun 12, 2010 #3

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Note that on the site I posted, K = "NOT 2nd" and M = "NOT 1st."

    Also from http://en.wikipedia.org/wiki/Functional_completeness#Informal I surmise that {and, or} is not adequate because the "NOT" operator, which is excluded from the set, is necessary for generating the "--->" (if/then; implies) relationship.
     
    Last edited: Jun 13, 2010
  5. Jun 13, 2010 #4

    Math Is Hard

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Note: moved this thread from Philosophy. This will likely be a better place to get help with this type of question.
     
  6. Jun 13, 2010 #5

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    I agree; I guess there is a difference between propositional logic and "philosophical" logic, and sometimes it gets ignored.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to prove a set of propositional connectives is NOT adequate?
Loading...