Talk:De Morgan's laws

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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)[reply]

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)[reply]

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)

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]