16
$\begingroup$

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'.

I didn't find the answer for my question, therefore I'll ask here:

What is De-Morgan's theorem for (A + B + C)'?

$\endgroup$
  • $\begingroup$ I dont understand this notation. $\endgroup$ – Goldname Jan 14 '17 at 19:43
21
$\begingroup$

DeMorgan's Theorem applied to $(A + B + C)'$ is as follows:

$$(A + B + C)' = A'B'C'{}{}{}{}$$

We have $\;\;$NOT(A or B or C) $\;\equiv\;$ Not(A) and Not(B) and Not(C),

which in boolean-algebra equates to $A'B'C'$

Both these extensions from DeMorgan's defined for two variables can be justified precisely because we can apply DeMorgan's in a nested manner, and in so doing, reapply, etc, in the end, it is equivalent to an immediate extension of it's application to three variables (or more) variables, provided they are connected by the same connective, $\land, \lor$.

For example, we can write $(A+B+C)' \equiv \big(A + (B+C)\big)' \equiv \big(A' \cdot (B+C)'\big) \equiv A'\cdot (B'C') \equiv A'B'C'$.


Indeed, provided we have a negated series of multiple variables all connected by the SAME connective (all and'ed or all or'ed), we can generalize DeMorgan's to even more than three variables, again, due to the associativity of AND and OR connectives. For any arbitrary finite number of connected variables:

So, $$(ABCDEFGHIJ)' = A' + B' + C' + \cdots + H' + I' + J'$$

And $$(A + B + C + \cdots + H + I + J)' = A'B'C'D'E'F'G'H'I'J'$$

$\endgroup$
  • 1
    $\begingroup$ You're very welcome! $\endgroup$ – Namaste Mar 4 '13 at 19:31
  • $\begingroup$ The associativity of AND and OR is irrelevant here. If there exists a homomorphism H from (S, +) to (R, &), with + and & as binary, then H(a+...+z)=(Ha&...&Hz). NOT((A OR B) OR C)=(NOT(A OR B) AND NOT B)) by closure and since NOT(X OR Y)=(NOT X AND NOT Y). (NOT(A OR B) AND NOT B))=((NOT A AND NOT B) AND NOT C). One can similarly justify that NOT(A OR (B OR C))=(NOT A AND (NOT B AND NOT C)). You don't need the associativity property, just the De Morgan laws, which comes as equivalent to saying that ({T, F}, OR) is homomorphic to ({T, F}, AND) by negation. $\endgroup$ – Doug Spoonwood Mar 7 '13 at 3:15
  • 1
    $\begingroup$ @Doug: I'm tempted to flag you and your comments and downvote, as this is one of many occasions in which you've behaved like a crank. If you don't cease and desist and stop targeting my posts for downvotes, and or don't reverse it, I will flag. $\endgroup$ – Namaste Mar 7 '13 at 3:22
  • $\begingroup$ In this case we can apply the idea of changing all operations to the opposite operation without having the same operation throughout. In other words, with & as AND, '(A+B&C+...&Z)=('A&'B+'C&...+'Z), or better put where X indicates a member of {&, +) and Y a member, not necessarily different from Y) of {&, +) '(a X b Y...X z)=('a Y 'b X... Y 'z) . This happens because ' is an isomorphism between ({T, F}, +) and ({T, F}, &). $\endgroup$ – Doug Spoonwood Mar 7 '13 at 3:31
  • 2
    $\begingroup$ One needs associativity in order that an $n$-fold "or" has a meaning. Or at least one needs it in deriving the general DeMorgan from the two variable case. $\endgroup$ – coffeemath Dec 1 '13 at 15:22
9
$\begingroup$

This is one instance where introducing another variable provides some insight. Let $D = B\lor C$.

Then, we have: $$\begin{align} \neg(A\lor B\lor C) &= \neg(A\lor D)\\ &=\neg A \land \neg D \\ &=\neg A \land \neg(B\lor C) \\ &=\neg A \land \neg B \land \neg C \end{align}$$

Thus: $$\neg(A\lor B \lor C) = \neg A \land \neg B \land \neg C$$

The idea is effectively the same for even more terms. Thus we can have: $$\neg(P_1 \lor P_2 \lor \cdots \lor P_n) = \neg P_1 \land \neg P_2 \land \cdots \land \neg P_n$$ ...and... $$\neg(P_1 \land P_2 \land \cdots \land P_n) = \neg P_1 \lor \neg P_2 \lor \cdots \lor \neg P_n$$ (Note: I'm more familiar with this notation for logic, so I'm using it. $\lor$ is or, $\land$ is and, and $\neg$ is not.)

$\endgroup$
  • $\begingroup$ This looks like the same as the (now deleted) answer by user65277. Just curious why... $\endgroup$ – coffeemath Dec 1 '13 at 13:33
  • 1
    $\begingroup$ @coffeemath Perhaps it's because great minds think alike? What is the timestamp on both--I assure you I did not copy his/her answer, if that's what you're implying. $\endgroup$ – apnorton Dec 1 '13 at 15:08
  • $\begingroup$ Yes, I assumed it was the other way around. But it seems like very bad behavior if user65277 just copied your answer and put it up two days after yours! Maybe that's why mixedmath deleted it. Strange goings-on (and +1 for your ans) $\endgroup$ – coffeemath Dec 1 '13 at 15:18
  • $\begingroup$ @coffeemath Ok, cool. Yeah, I seem to recall some other instances (via meta) of people copying answers in the past. According to this lookup, there are no posts by that user that have not been deleted. Something smells fishy. ;) $\endgroup$ – apnorton Dec 1 '13 at 15:22
  • 1
    $\begingroup$ Maybe user65277 was "fishing" for free points.. -; $\endgroup$ – coffeemath Dec 1 '13 at 19:35
0
$\begingroup$

"+" is a closed operation on the truth set {T, F}. This means that for any two truth values "x" and "y", (x+y) can get assigned a truth value. Consequently, we know that for ((a+b)+c)' we can assign a truth value to (a+b) and c. (x+y)'=(x'+y') holds for anything to which we can assign truth values "x" and "y". Thus, ((a+b)+c)'=((a+b)'+c')=((a'+b')+c').

We can generalize this to any negated series of multiple variables connected by conjunction (AND) and disjunction (OR), so long as we switch the operations throughout. In other words, where X is a member of {AND, OR} and Y a member of {AND, OR}, (a X b Y...X c)'=(a' Y b' X...Y c'). This happens because, ' is a particular kind of isomorphism between the set of truth values under conjunction ({T, F}, AND) and the set of truth values under disjunction ({T, F}, OR). In particular we have that (x X y)'=(x' Y y'), and (x Y y)'=(x' X y') where X and Y indicate binary operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.