Understanding DeMorgan's Theorem: Complements and Input Confusion Explained

[JohnGaltis]

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.

 

[fresh_42]

What does a+b in terms of sets or logical conjunctions mean? And what is (a+b)'? Is it a'+b'?

 

[Stephen Tashi]

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.

The complement of $(a \cdot b) + (c \cdot d)$ is $(a'+b') \cdot (c'+d')$
It isn't $a'+(b' \cdot c') + d'$.

 

[David Pass]

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.

De M displays a relationship of material equivalence:

~(p ⋅ q) ≡ (~p v ~q)
~(p v q) ≡ (~p ⋅ ~q)

 

[Logical Dog]

 

[sysprog]

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.

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') --

       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):

"The truth-functions of every number of elementary propositions can be written in a schema of the following kind:

(TTTT)(p,q) Tautology (if p then p, and if q then q) [p ⊃ p . q ⊃ q]
(FTTT)(p,q) in words: Not both p and q. [∼(p . q)]
(TFTT)(p,q)  „   „    If q then p. [q ⊃ p]
(TTFT)(p,q)  „   „    If p then q. [p ⊃ q]
(TTTF)(p,q)  „   „    p or q. [p ∨ q]
(FFTT)(p,q)  „   „    Not q. [∼q]
(FTFT)(p,q)  „   „    Not p. [∼p]
(FTTF)(p,q)  „   „    p or q, but not both. [p . ∼q : ∨ : q . ∼p]
(TFFT)(p,q)  „   „    If p, then q; and if q, then p. [p ≡ q]
(TFTF)(p,q)  „   „    p
(TTFF)(p,q)  „   „    q
(FFFT)(p,q)  „   „    Neither p nor q. [∼p . ∼q or p | q]
(FFTF)(p,q)  „   „    p and not q. [p . ∼q]
(FTFF)(p,q)  „   „    q and not p. [q . ∼p]
(TFFF)(p,q)  „   „    p and q. [p . q]
(FFFF)(p,q) Contradiction (p and not p; and q and not q.) [p . ∼p . q . ∼q]

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 ...

De M displays a relationship of material equivalence:

~(p ⋅ q) ≡ (~p v ~q)
~(p v q) ≡ (~p ⋅ ~q)

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.