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

Showing that the following isn't complete

  1. May 26, 2007 #1
    Let's have a look at [tex]\left\{ \neg,\equiv\right\}[/tex]. How could one show that this isn't complete?

    I've tried finding some sort of invariance that propositions built with these might have, but I couldn't find anything... I'm going crazy! :smile:
  2. jcsd
  3. May 27, 2007 #2
    The set {~,<->} is inadequate.

    Proof? You might try to prove that operator -> can't be expressed by any combination of the operators ~ and <->.

    A start would be to show that the truth table for any proposition that is made up of 2 or more propositional
    symbols and only the operators ~ and <-> must have an even number of ones and an even number of zeros in its last column (call it the even property). I think it's pretty clear this would have to be done by induction.

    Then argue that since -> has the odd property it can't be expressed using only ~ and <->.

    (The operator -> could be replaced by either V or &.)
    Last edited: May 27, 2007
  4. Jun 1, 2007 #3
    Thanks, I did do this eventually, and just came back here now to thank anyone that might have answered.

    So thanks!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Showing that the following isn't complete
  1. Completeness theorem (Replies: 3)

  2. Does it follow? (Replies: 2)

  3. Following ordinal (Replies: 1)