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)'?
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
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'$$
-
$\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$ Commented Mar 7, 2013 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$– amWhyCommented Mar 7, 2013 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$ Commented Mar 7, 2013 at 3:31
-
$\begingroup$ @amWhy You weren't targeted here personally. It simply comes as incorrect to say that associativity plays any role here whatsoever, even in the case where you generalize to an arbitrary number of finite operations. The pattern holds for any homomorphism, and if you have two different operations, you can do basically the same thing if have an isomorphism between the respective algebraic systems. $\endgroup$ Commented Mar 7, 2013 at 3:46
-
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$ Commented Dec 1, 2013 at 15:22
$\begingroup$
$\endgroup$
5
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.)
-
$\begingroup$ This looks like the same as the (now deleted) answer by user65277. Just curious why... $\endgroup$ Commented Dec 1, 2013 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$– apnortonCommented Dec 1, 2013 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$ Commented Dec 1, 2013 at 15:18
-
-
1$\begingroup$ Maybe user65277 was "fishing" for free points.. -; $\endgroup$ Commented Dec 1, 2013 at 19:35
$\begingroup$
$\endgroup$
"+" 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.
answered Mar 7, 2013 at 3:56