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

And - Or - Not in terms of one another

  1. Dec 22, 2015 #1
    It is possible to express the boolean AND in terms of boolean OR and boolean NOT:
    a AND b <=> NOT (NOT a OR NOT b)
    Similarly,
    a OR b <=> NOT (NOT a AND NOT b)

    Why can't we express NOT in terms of OR and AND?
     
  2. jcsd
  3. Dec 22, 2015 #2

    jedishrfu

    Staff: Mentor

  4. Dec 22, 2015 #3

    Erland

    User Avatar
    Science Advisor

    Suppose we have a boolean expression ##\phi(A,B,C,\dots...)## built up by the atomic sentences ##A,B,C,\dots##and the connectives ##\land## and ##\lor## only, such that ##\phi(A,B,C\dots)\equiv\neg A##.
    Since the truth value of ##\neg A## is independent of the truth values of ##B,C,\dots##, the equivalence will still hold if we replace ##B,C,\dots## with any sentences, in particular, if we replace them all with ##A##, so ##\phi(A,B,C,\dots)\equiv
    \phi(A,A,A,\dots)##, the latter being built up from ##A##, ##\land##, and ##\lor## only. But since ##A\land A\equiv A## and ##A\lor A \equiv A##, ##\phi(A,A,A,\dots)## can be successively reduced to ##A##, so, ##\phi(A,A,A,\dots)\equiv A##.
    Thus, ##A\equiv\neg A##, which clearly is a contradiction.
     
  5. Dec 22, 2015 #4
    Clever! I am almost ready to buy it.
    What do you mean by atomic sentences? Are B, C etc propositions or are they literals? Not sure yet if it matters, but if A, B, C are themselves composed of other "variables" X, Y, Z then their truth values may not be independent.
    But then again, they are independent in the general case.
    For example: NOT A = B U C if the universal set is {A, B, C}.
    Apologies for the lack of rigor in the language used to express these ideas, I am not a mathematician.
     
  6. Dec 22, 2015 #5

    Erland

    User Avatar
    Science Advisor

    I mean that ##A,B,C, \dots## are atomic sentences or propostions, i.e. that they are not built up from simpler propositions by connectives. But as you say, it doesn't really matter, everything I wrote still holds whether ##A,B,C,\dots## are atomic or not, independent or not, etc...

    Edit: ##\equiv## means logical equivalence, which means that e.g. ##\neg(A\land B)\equiv \neg A \lor \neg B## means that ##\neg(A\land B)## and ##\neg A \lor \neg B## either are both true or both false, no matter which truth values we assign to ##A## and ##B##. We can have an interpretation where ##\neg A\leftrightarrow (B\lor C)## is true, but this is not true for all interpretations.
     
    Last edited: Dec 22, 2015
  7. Dec 26, 2015 #6

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    OP: Have you considered using the Sheffer stroke?
     
  8. Dec 29, 2015 #7
    WWGD - that is not my question. I know that AND, OR, NOT can be expressed in terms of NAND (Sheffer stroke.) Also, just using NOR.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: And - Or - Not in terms of one another
  1. Terms of a language (Replies: 1)

  2. Another question! (Replies: 4)

  3. One to one function (Replies: 1)

Loading...