Talk:De Morgan's laws/Archive 1

This is an archive of past discussions about De Morgan's laws. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Computer programming

Quoting from the article:

In the sense of computer science, in several languages (such as Java 1.5) De Morgan's laws can be simplified to:

!(p && q) is the same as !p || !q

!(p || q) is the same as !p && !q

It's interesting to note that in ISO C++, this can be written in a slightly more readable form as:

not (p and q) is the same as not p or not q

not (p or q) is the same as not p and not q

— Loadmaster 02:16, 8 September 2006 (UTC)

Quoting from the article:

In C, Java, and other related programming languages, De Morgan's laws can be written as:

!(p && q) == !p || !q

!(p || q) == !p && !q —Preceding unsigned comment added by 199.246.40.54 (talk) 20:53, 17 September 2007 (UTC)

These equations always return a value of true, regardless of the values of p and q.

This is incorrect. In C/C++ operator precedence, the == operator has greater precedence than either the && or || operators. Thus, a compiler will interpret the commands as:

(!(p && q) == !p) || !q

(!(p || q) == !p) && !q

To correct this, I'd recommend changing the text to:

!(p && q) == (!p || !q)

!(p || q) == (!p && !q) —Preceding unsigned comment added by 199.246.40.54 (talk) 20:51, 17 September 2007 (UTC)

Religion

Since the article on Venial sin states the rules are deduced from De Morgan's laws, I think this article should describe how the negation of Mortal sins is derived. Kitwe 04:45, 9 August 2007 (UTC)

A mortal sin is one that meets

(1) this condition AND

(2) this condition, AND

(3) this condition.

A venial sin is a sin that is not mortal. Thus a venial sin is one that

(1) fails to meet this condition, OR

(2) fails to meet this condition, OR

(3) fails to meet this condition.

De Morgan's law says that if you put "and" between the three conditions, then the negation of the whole thing is the same as if you negate the conditions separately and then put "or" between them. "A or B or C" means at least one of the three is true. Whether that should be in this article I'll leave to others. Michael Hardy 13:34, 9 August 2007 (UTC)

While there might be some logic in using DeMorgan's laws to define a venial sin, venial sins have nothing to do with DeMorgan's laws (any more than any other extremely minor application of them) and thus don't belong in this article. TheWarlock 01:38, 8 October 2007 (UTC)

In code?

I find the code pretty, but why is it there? I'd rather know how (if at all) the laws are used in programming than see a string of code, the math-versions already look like code, it's just another code-- so why is it there? futurebird (talk) 05:33, 29 December 2007 (UTC)

Still no comments on the importance of this section...futurebird (talk) 03:50, 12 January 2008 (UTC)

Page Edits

In a series of edits i restructured this article to (hopefully) make it more accessible to a general audience. I also added a proof of De Morgan's law intended for a more specific audience. Jsorr (talk) 05:29, 13 March 2009 (UTC)

I believe your edits had the opposite effect. They have further complicated the introduction which, in addition to making it less accessible, is contrary to Wikipedia guidelines. —Preceding unsigned comment added by 74.202.89.125 (talk) 20:45, 12 August 2009 (UTC)

Bubble pushing

I redirected the "Bubble pushing" article here, as it appeared to simply describe De Morgan's Theorem. Sagsaw (talk) 01:24, 7 September 2009 (UTC)

Proof by False Table

What the heck's a false table? This doesn't look any different to me than proof by a truth table, and there doesn't seem to be any other reference in Wikipedia to such a thing as a false table. -- Joe Avins (talk) 16:14, 25 May 2011 (UTC)

Just some minor vandalism by an anonymous user, self-reverted by the same anonymous user, and then someone mindlessly reverted the self revert. [1] Fixed now. Hans Adler 16:58, 25 May 2011 (UTC)

Oh goshdarnit!... --Cybercobra (talk) 09:25, 26 May 2011 (UTC)

Renaming the article

I was about to move this to "DeMorgan's Law" -- but I've always seen it as "DeMorgan's Laws", plural. Quick straw poll for the new page name? -- Tarquin 12:37 Jul 23, 2002 (PDT)

I say keep it singular since most everything around here alreay is that way. One can always write [[DeMorgan's Law]]s to link here. If you like you can even make the plural redirect to the singular. --mav

I think Tarquin has a point here. These are actually two laws, but they're a pair, and they're always given together. As far as I know, DeMorgan hasn't come up with other laws known as such, so I'd go for Tarquin's proposal. Jheijmans 12:54 Jul 23, 2002 (PDT)

It's true that they are two laws, but I've rarely heard of them referred to in that way. I'm an EE, so my education included both digital logic and formal logic, and in both contexts the singular was always used. The article should follow the norm, even if plural would be "better" as the norm. -- Joe Avins (talk) 15:44, 25 May 2011 (UTC)

But there's clearly only a single law, apply the first one to itself gives the supposed 'other': ¬(¬(A∧B))=¬(¬A∨¬B)=A∧B Linket (talk) 03:22, 12 December 2011 (UTC)

I would like to see references to logics in which some/all of the De Morgan laws are valid and to logics in which some/all of them are invalid. (anon, March 31, 2006)

Constructivism

It seems to me that the conclusion $\neg (a\land b)\Rightarrow (\neg a\lor \neg b)$ does not hold in constructivist logic. Am I right? Shall we mention it in the article? HenningThielemann (talk) 15:04, 19 November 2011 (UTC)

You are right. Whether it should be mentioned or not, I'm not sure. But what would speak against it? --Daniel5Ko (talk) 00:56, 18 December 2011 (UTC)

This is mentioned both at Intuitionism#Truth and proof and Classical logic#Non-classical logics. I think it's appropriate to mention it here as well, as it is quite à propos here. I prefer the term "intuitionistic logic". --Lambiam 20:19, 1 February 2012 (UTC)

Requested move

The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the move request was: not moved. Favonian (talk) 21:29, 22 May 2012 (UTC)

De Morgan's laws → De Morgan's law – There's only one independent law so the name should just be "De Morgan's law", which follows the convention of most high level Math/ECE textbooks. Linket (talk) 21:27, 15 May 2012 (UTC)

Oppose Wolfram and Google (91.6K for singular vs. 156K for plural) say it's plural. What textbooks specifically? --Cybercobra (talk) 22:07, 15 May 2012 (UTC)
Oppose The same name refers to negation of disjuncton and negation of conjuncton.Greg Bard (talk) 01:35, 16 May 2012 (UTC)

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

This article may need to be clarified to make it more accessible to a general audience.

The explanation in Loadmaster's talk comment above seems much easier to understand than the article itself. Can the article be rewritten to make it more accessible to a general audience lacking advanced mathematical training? 69.140.164.142 15:29, 22 April 2007 (UTC)

I agree. How about some real-life examples? —Preceding unsigned comment added by 65.192.31.130 (talk) 21:38, 18 January 2008 (UTC)

At this moment, the explanation in the article doesn't seem any more complicated than Loadmaster's explanation. so I've removed the tag. --C S (talk) 23:37, 31 July 2008 (UTC)

The introduction of this article was filled with confusing nonsense.

It's either a law or a theorem, not both, removed theorem as it has one quarter of the google search results.
Removed 'de morgans duality' as it has one twentieth the results
Moved History to new history section
Simplified summary to coincide with Wikipedia guidelines to appeal to the largest possible audience —Preceding unsigned comment added by 74.202.89.125 (talk) 19:26, 25 February 2009 (UTC)

I don't think the general public will be looking up DeMorgan's Law. Most of the general public doesn't even know what a bit is in it's simplist meaning (they've probably only heard of bytes and megabytes for hard drive and RAM sizes).

I don't agree that the current introduction is nonsense. It uses correct professional terminology. But it is needlessly confusing about something that many lay people will be able to understand with a few moments thought if stated in the right way. This includes students who turn to Wikipedia for their entry level information. The first of the two laws is simply "If NOT (A AND B) then (not A) OR (not B)" or "If A and B are not both true then either A is not true or B is not true". For me, the first one is better than the second one. But both leave even poor students slapping their foreheads "Well, obviously!" Something along these lines right up front will make the article much more friendly. Kudos76 (talk) 03:02, 7 June 2012 (UTC)

Engineering - needs expansion

As soon as you use multiple inversions on top op each other it gets more complicated, I think it would be good to add a few more comlicated examples. 82.171.57.121 (talk) 20:45, 25 September 2013 (UTC)

Venn Diagram Confusing

https://en.wikipedia.org/wiki/De_Morgan%27s_laws#mediaviewer/File:Demorganlaws.svg is currently the first picture seen on the De Morgan's Laws Wikipedia page. I think it is a bad example of De Morgan's Laws for the following reasons.

The first half of the picture - captioned with $\neg (A\lor B)$ = $(\neg A)\wedge (\neg B)$ - shows a Venn Diagram of two circles shaded in green with the overlapping area shaded in a slightly different tone. This is all set against a blue background representing U, the universal set. It would seem logically that the picture means A OR B (or A union B), the opposite of the intended meaning.

The second half of the picture is captioned $\neg (A\wedge B)$ = $(\neg A)\lor (\neg B)$ but the picture appears to indicate A AND B (or A intersect B) as the intersection is shaded green and the remainders of A and B are shaded in a dark blue just off the color of U.

I suggest that this picture be removed in favor of a picture or animation that clearly and accurately reflects the meaning of De Morgan's Laws. I am willing to do this but as this is one of my first edits I would rather seek the counsel of the community before taking action on my own.

Remicks (talk) 05:14, 7 March 2015 (UTC)

Union is not logical OR and set intersection is not logical AND

The article incorrectly equates union to logical OR as well as set intersection to logical AND. The two behave similar but are not the same thing. The sections which claim to have correctly written the form of De Morgans law; in set theory and Boolean algebra, in one expression, need to be rewritten, as what is currently there is illegal syntax for Boolean algebra. -- User:Whole Oats (talk) 02:33, 10 June 2019 (UTC)

De Morgan's laws/Archive 1#Formal notation

For this,

\neg (P\land Q)\vdash (\neg P\lor \neg Q)

why its reverse direction,

(\neg P\lor \neg Q)\vdash \neg (P\land Q)

is not included? --Ans (talk) 09:55, 11 December 2019 (UTC)

also see Wikipedia:Reference desk/Mathematics#De Morgan's laws#Formal_notation --Ans (talk) 05:55, 18 December 2019 (UTC)

Circular reasoning?

In the formal proof section, because it says "Because $A\cap B=\{y|y\in A\land y\in B\}$ , it must be the case that $x\not \in A$ or $x\not \in B$ .", doesn't that itself call upon De Morgan's theorem implicitly? It says, "it must be the case that $x\not \in A$ or $x\not \in B$ ", but the only reason I could think of why this otherwise unexplained conclusion must be true, is that $x\in (A\cap B)^{\complement }$ is equivalent to saying $\{x|\neg (x\in A\land x\in B)\}$ . But to then equate $\neg (x\in A\land x\in B)$ to $x\not \in A\lor x\not \in B$ requires the logical form of De Morgan's theorem, which the set form is supposed to prove. Am I wrong about this? --Ipatrol (talk) 20:39, 22 September 2018 (UTC)

I came here to make the same comment, and I see someone has already pointed this out nearly three years ago. As Ipatrol pointed out, the second line of the Boolean algebra proof relies on the propositional logic form of De Morgan's laws. The propositional logic form is a tautology and could easily be proved by a truth table first. After that, the Boolean algebra form could be proved.

However it's done, this example of circular reasoning needs to be fixed. Otherwise, the "formal" proof given here is no better than the "informal" proof. --seberle (talk) 12:05, 5 August 2021 (UTC)

Proof of DeMorgan's Theorem, excluded middle, Fuzzy Logic

I can't provide a reference, since this is something I figured out myself (although I'm sure others have figured out the same), so I won't add it directly to the article. But as I recall, part of the proof of the theorem relies on the law of the excluded middle. Since the excluded middle doesn't exist in Fuzzy Logic, the proof is no longer valid. But you still need DeMorgan's, so it must be adopted implicitly as an axiom. I've never seen anyone else mention this, however.

I have recently had to scour the web for a good proof to DeMorgan's law - it would have been really good to see one here if someone can provide a rigorous one. Squarris 04:29, 8 December 2005 (UTC)

De Morgan's laws are essentially a triviality, it thus does not make much sense to ask for a rigorous proof unless you specify exactly what statement you want to prove, and what are your axioms and proof system.

"Fuzzy logic" is also a fuzzy description, but at least in BL, de Morgan's laws (for ∧ and ∨) are provable, despite that they are not taken as axioms (explicitly or implicitly, whatever that may mean), so something is wrong with the reasoning above. -- EJ 04:30, 16 December 2005 (UTC)

I disagree. De Morgan's laws are not a triviality---in the sense that you can't ask for a rigorous proof. They follow from the axioms of a boolean algebra. It is simply that we are so familiar with them that we believe they are "trivial". ---15 January 2005

De Morgan laws for Boolean algebras follow from the axioms of a Boolean algebra. De Morgan laws for sets follow from definition of the set operations, axiom of extensionality, and laws of the underlying propositional logic. De Morgan laws for connectives in propositional logic follow from the definition of their truth-tables if you define the logic semantically, or by an ad hoc derivation in the calculus if you define the logic as a calculus. Etc.

Each of these proofs is completely different, thus it does not make sense to ask for a rigorous proof until you rigorously pose the question. All of these proofs are quite simple; whether this means "trivial" or only "almost trivial" is just a matter of subjective opinion. And just in case: yes, all the contexts I mentioned above are ultimately related (e.g., all of them involve some Boolean algebra), but showing this relationship is actually harder than proving the De Morgan laws directly. -- EJ 04:51, 16 January 2006 (UTC)

Ok, I understand what you were/are saying now. A proof would be better seen on a Boolean algebra page, for example, rather than on a general page describing De Morgan's law in various contexts. Before your clarification, I thought you had meant that one would need to provide a specific logical statement. Rather, you were saying that we need to provide the proper context. -anon 07:03, 16 January 2006 (UTC)

It seems rather easy to show this with a truth table:

p	q	¬p and ¬q	¬(p or q)
F	F	T	T
F	T	F	F
T	F	F	F
T	T	F	F

— Loadmaster 02:23, 8 September 2006 (UTC)

I think truth tables are on topic here. futurebird (talk) 05:35, 29 December 2007 (UTC)

I think the third line of this proof just uses De Morgan's law to prove De Morgan's law. It basically changes it from proving De Morgan's law on sets to using De Morgan's law on boolean algebra.

x ∈ A ∩ B

x ∉ A ∩ B

x ∉ A or x ∉ B

x ∈ A or x ∈ B

x ∈ A ∪ B

I don't know another proof of De Morgan's law. Could anyone confirm whether or not my observation is right? --Dbmikus (talk) 01:58, 28 January 2011 (UTC)

I'd say the 2nd line seems to be the possibly circular one. --Cybercobra (talk) 07:21, 28 January 2011 (UTC)

I have to agree with Dbmikus. Taking lines 2 and three together gives (x ∉ A ∩ B) ≡ (x ∉ A or x ∉ B) which _is_ DeMorgan's Law. So there's the circularity. (As an aside, I've long thought that these things ought to be called "DeMorgan's Axioms.") -- Joe Avins (talk) 16:01, 25 May 2011 (UTC)

You can use the definition of complements: A and B are complementing each other if A∩B is empty and A∪B is the full set. That way one can avoid the use of deMorgan's law from logic. Syngola (talk) 16:40, 23 March 2022 (UTC)

De Morgan's laws as described here appear to apply to conventional 2-valued logic only

Or at least there's an unwritten assumption. Perhaps clarify they *might* not apply to all other logics? 92.7.34.11 (talk) 20:33, 2 April 2022 (UTC)

Substitution form paragraph

GrkCan's paragraph from July 2020 on the Substitution form really does not make a lot of sense. What is it trying to say? — Preceding unsigned comment added by 125.235.239.193 (talk) 11:08, 21 May 2022 (UTC)

Discussion

The proposition "The complement of the union of two sets is the same as the intersection of their complements " is False. Boutarfa1 (talk) 12:03, 24 September 2023 (UTC)

Discussion

In the proposition "the complement of the intersection of two sets is the union of the complements of the given sets " some conditions should be precised like that the complements of the given sets can be from the same set as well as the complement of the intersection(some other conditions are possible like when the complement of the intersection is taken from a set that is included in the set that the complements of the given sets are taken from). Boutarfa1 (talk) 12:24, 24 September 2023 (UTC)