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

I DeMorgan's Theorem

  1. Nov 8, 2016 #1
    According to DeMorgan’s theorem (break the bar and change the sign), the complement of ܽa⋅b+c⋅d is a'+b'⋅c'+d' Yet both functions are 1 for ܾܽܿ abcd 1110. How can both a function and its complement be 1 for the same input combination? What’s wrong here?

    I honestly have no idea. I mean, shouldn't all complements be the inverse? This is the first question that stated otherwise and it really confuses me.
  2. jcsd
  3. Nov 8, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    What does a+b in terms of sets or logical conjunctions mean? And what is (a+b)'? Is it a'+b'?
  4. Nov 8, 2016 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    The complement of ##(a \cdot b) + (c \cdot d) ## is ## (a'+b') \cdot (c'+d') ##
    It isn't ##a'+(b' \cdot c') + d' ##.
  5. Jan 12, 2017 #4
    De M displays a relationship of material equivalence:

    ~(p ⋅ q) ≡ (~p v ~q)
    ~(p v q) ≡ (~p ⋅ ~q)
  6. Jan 12, 2017 #5
    Last edited: Jan 12, 2017
  7. Mar 5, 2017 #6
    A few observations and illustrations:

    It's not "a function and its complement"; it's an expression and an equivalent expression with the complement of the inputs and the duals of the operators -- changing an operator to its dual while retaining the truth value of a negated expression requires distribution of the negation over the inputs: ~(p V q) = ( ~p Λ ~q) -- negation of both sides of the equivalency expression results in (p V q) = ~(~p Λ ~q) [in identity-extended 1st-order logic "=" is normally reserved for identity -- in the foregoing example it's used to mean "is truth-functionally equivalent to" (technically that's a 2nd-order predication) -- perhaps more perspicuous than ≡ and entails the same thing].

    AND (conjunction -- b'0001') is not the complement of OR (disjunction -- b'0111'); NAND (alternative (disjunctive) denial b'1110') is. AND is the dual of OR, just as NAND is the dual of NOR (joint (conjunctive) denial b'1000') --

    Code (Text):

           AND       OR        NAND       NOR       XOR       IFF(XNOR)
    p q     Λ        V         ~Λ         ~V         ⊗        ≡
    0 0     0        0          1          1         0         1
    1 0     0        1          1          0         1         0
    0 1     0        1          1          0         1         0
    1 1     1        1          0          0         0         1
    Notice that looking at the function columns, you can see that OR is (columnarly) the inversion of the complement (or complement of the inversion) of AND, just as NOR stands similarly with respect to NAND -- columnarly, NOR is inverted AND, and NAND is inverted OR (as normally used the inverse is the same as the complement -- I'm using columnarly inverted in the above table to mean the same thing as is normally meant by complement or inverse of the dual) -- XOR and XNOR are complementary, and also are each self-dual, i.e. negating their inputs is equivalent to negating their functions -- wording somewhat differently: where ["only for" = "if and only if"] and ["unless" = "if and only if not"], true unless neither (OR), and false unless both (AND) are duals of each other, true only for neither (NOR), and false only for both (NAND) are duals of each other, and true only for neither or both (XOR), and false unless neither or both (IFF-XNOR), are complementary and each is self-dual -- negating the inputs negates the function -- "neither" is the complement of "both"; "unless" is the complement of "only for".

    The 16 binary relations (as illustrated in Tractatus Logico-Philosphicus by Ludwig Wittgenstein):
    It may be interesting to consider the symmetry of positions, in the above schematic table, of the pairs of complementary functions, and to ponder their other characteristics -- each of the complements of AND and OR (NAND and NOR) is complete (can in combination with itself produce the function of any of the other 15 functions) -- they are duals occupying the 2nd and 12th (5th row down) rows of the table -- their complements are duals that occupy the the 5th and 15th (2nd row down) -- there are other intrigues there that may be entertaining or useful to muse about ...

    This is correct -- not only that, it's succinct --
    negation of conjunction is equivalent to disjunction of negation;
    negation of disjunction is equivalent to conjunction of negation.
    Last edited: Mar 5, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted