- note that demorgans laws are also a big part in circut design.
In logic, De Morgan's laws (or De Morgan's theorem) are rules in formal logic relating pairs of dual logical operators in a systematic manner expressed in terms of negation. The relationship so induced is called De Morgan duality. Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is most often said to be the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ...
Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ...
In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. ...
Negation, in its most basic sense, changes the truth value of a statement to its opposite. ...
To give some intuition, suppose P is true if and only if it is raining and Q is true if and only if you are wearing a raincoat. If you never go in the rain without a raincoat, then it can't be that P is true and Q is false. Thus, following formula is true:
- not(P and (not Q))
On the other hand, another way of expressing the same statement is that either: - It's not raining, so you don't care whether you're wearing a raincoat or not;
- You're wearing a raincoat, so you don't care whether it's raining.
In symbols, this would be written: - (not P) or Q
One of DeMorgan's laws tells us that these two formulas are equivalent.
History and formulations Augustus De Morgan originally observed that in classical propositional logic the following relationships hold: Augustus De Morgan (June 27, 1806 - March 18, 1871) was an Indian-born British mathematician and logician. ...
A propositional calculus is a formal, deduction system, or proof theory for reasoning with propositional formulas as symbolic logic. ...
- not (P and Q) = (not P) or (not Q)
- not (P or Q) = (not P) and (not Q)
De Morgan's observation influenced the algebraisation of logic undertaken by George Boole, which cemented De Morgan's claim to the find, although a similar observation was made by Aristotle and was known to Greek and Medieval logicians (cf. Bocheński's History of Formal Logic). George Boole [], (November 2, 1815 Lincoln, Lincolnshire, England – December 8, 1864 Ballintemple, County Cork, Ireland) was a mathematician and philosopher. ...
Aristotle, marble copy of bronze by Lysippos. ...
In formal logic the laws are usually written
  and in set theory   In extensions of classical propositional logic, the duality still holds (that is, to any logical operator we can always find its dual), since in the presence of the identities governing negation, one may always introduce an operator that is the De Morgan dual of another. This leads to an important property of logics based on classical logic, namely the existence of negation normal forms: any formula is equivalent to another formula where negations only occur applied to the non-logical atoms of the formula. The existence of negation normal forms drives many applications, for example in digital circuit design, where it is used to manipulate the types of logic gates, and in formal logic, where it is a prerequisite for finding the conjunctive normal form and disjunctive normal form of a formula. Computer programmers use them to change a complicated statement like IF ... AND (... OR ...) THEN ... into its opposite. They are also often useful in computations in elementary probability theory. A logical formula is in negation normal form if negation occurs only immediately above elementary propositions. ...
Digital circuits are electric circuits based on a number of discrete voltage levels. ...
A logic gate is an arrangement of controlled switches used to calculate operations using Boolean logic in digital circuits. ...
In Boolean logic, a formula is in Conjunctive Normal Form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. ...
In Boolean logic, Disjunctive Normal Form (DNF) is a method of standardizing and normalizing logical formulas. ...
Probability theory is the mathematical study of probability. ...
Let us define the dual of any propositional operator P(p, q, ...) depending on elementary propositions p, q, ... to be
 This idea can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals: In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ...
In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ...
  To relate these quantifier dualities to the De Morgan laws, set up a model with some small number of elements in its domain D, such as In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ...
- D = {a, b, c}.
Then  and  . But, using De Morgan's laws,  and  verifying the quantifier dualities in the model.
Then, the quantifier dualities can be extended further to modal logic, relating the box and diamond operators: A modal logic is a logic that deals with sentences that are qualified by modalities such as can, could, might, may, must, possibly, necessarily, eventually, etc. ...
 , . In its application to the alethic modalities of possibility and necessity, Aristotle observed this case, and in the case of normal modal logic, the relationship of these modal operators to the quantification can be understood by setting up models using Kripke semantics. ...
Aristotle, marble copy of bronze by Lysippos. ...
In logic, normal modal logic is a set L of modal formulas such that L contains all propositional tautologies, Kripkes schema: , and L is closed under substitution, detachment rule: from A and A→B infer B, necessitation rule: from A infer . ...
Kripke semantics (also known as possible world semantics, relational semantics, or frame semantics) is a formal semantics for modal logic systems, created in late 1950s and early 1960s by Saul Kripke. ...
Quotes - It should be noted that the contradictory opposite of a disjunctive proposition is a conjunctive proposition composed of the contradictories of the parts of the disjunctive proposition (William of Ockham, Summa Logicae).
Hello, I am Sam, Sam I am. ...
See also Algebra of sets George Boole Boolean algebra Boolean function Boolean logic Boolean homomorphism Boolean Implicant Boolean prime ideal theorem Boolean-valued model Boolean satisfiability problem Booles syllogistic canonical form (Boolean algebra) compactness theorem Complete Boolean algebra connective -- see logical operator de Morgans laws Augustus De Morgan duality (order...
External links |
Feeds |
Contact