Talk:De Morgan's laws

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Foundations, logic, and set theory
One of the 500 most frequently viewed mathematics articles.

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)

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)

Contents

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

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

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

This article may be too technical for a general audience.
Please help improve this article by providing more context and better explanations of technical details to make it more accessible, without removing technical details.

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)

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

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