por We explain what De Morgan’s laws are, demonstrate them and give examples
What are De Morgan’s laws?
De Morgan’s laws are two logical laws belonging to propositional logic that were formulated by the English mathematician Augustus De Morgan (1806-1871). They establish the following, with respect to a compound logical proposition:
The opposite of a conjunction is equivalent to the disjunction that is formed with the opposites or negations of the propositions that make up the conjunction.
The negation of the disjunction can be expressed as a conjunction made up of the opposites or negations of the propositions involved in the disjunction.
In propositional logic notation, De Morgan’s laws are expressed in a compact and more formal form as follows:
∼(p ∧ q) ⇔ ∼p ∨ ∼q
∼(p ∨ q) ⇔ ∼p ∧ ∼q
What these laws express is that, whether in the negation of the conjunction or of the disjunction, the result is equivalent to negating each of the participating propositions separately and inverting the connector that links them.
For a better understanding of De Morgan’s laws, it is necessary to review the meaning of the propositions and symbols used in propositional logic, to see how to properly apply these laws.
logical notation
The basic tool of propositional logic is propositions. A logical proposition is a statement that admits a truth value, either this is true or false, but not both at the same time. In this no ambiguity is allowed, that is, there can be no doubts.
A proposition is denoted by a lowercase letter, as in the following examples:
p: Mexico City is the capital of Mexico (true).
q: Adding 2 and 3 yields 4 (false).
A: All mammals are land animals (false).
There are also more complex propositions, which are structured by using simple propositions, like these:
Q: Carlos will go to the movies if it doesn’t rain.
q: Ana is a chemist or marine biologist.
A: Juan is going to have dinner or Pedro will watch the game on television.
Logical connectors
Logical connectors are symbols used to link simple propositions together to build more complex propositions. In propositional logic each of them has a particular meaning.
The most used connectors are conjunction, disjunction, exclusive disjunction, negation, conditionality, and bi-conditionality.
Conjunction
The conjunction is denoted by an inverted letter “v”. A compound proposition through a conjunction is symbolized p ∧ q, as follows:
p ∧ q: Mexico City is the capital of Mexico and is in North America.
It is easy to identify here that p is “Mexico City is the capital of Mexico” and q is “It is in North America”.
Disjunction
Two types of disjunction are distinguished: the weak and the exclusive. A weak disjunction it is symbolized by ∨ and in logical notation it would be p ∨ q. An example of this class of disjunction is:
p ∨ q: Juan is a soccer player or Juan is a tennis player.
Instead, the exclusive disjunction it is symbolized by the sign ⊻ and implies that one of the propositions must be discarded, for example:
p ⊻ q: Alice is 20 years old or Alice is 22 years old.
The difference between both types is clear, in the exclusive disjunction, one of the propositions is discarded, since if Alicia is 20 years old, she cannot be 22 and vice versa. On the other hand, in the weak disjunction, Juan may be a soccer player and a tennis player at the same time.
Denial
By placing the symbol ∼ before a statement, the statement is negated, as in:
p: ∼(Veracruz is the capital of Mexico).
Which reads as “Veracruz is not the capital of Mexico”. Other ways of expressing a denial, apart from «no», is through phrases such as «it is false», «it is a lie that» and «it is not true that».
conditionality
They are compound propositions that usually use the words «if» and «then…» to link two propositions in which there is conditionality or implication. The part of the proposition that is written immediately after the «if» is the antecedent wave hypothesis of the proposition and what is after the term «then» is the conclusion either consequent.
The symbol used for conditionality is the arrow from left to right “→”, therefore a conditionality between two propositions is represented as p → q, which can be read as “If p, then q”. For example:
p → q: If it rains during the afternoon then I won’t play tennis.
Bi-conditionality
In this type of proposition the phrase «if, and only if» is used to connect two propositions, called the first and second members of the biconditional. The symbol used is the bidirectional arrow “↔”.
The two propositions connected by «if, and only if» are respectively called first and second member and the bi-conditionality of two propositions p and q remains as p ↔ q. For example:
p ↔ q : Maria likes to ride a bike if and only if the day is sunny.
Demonstration of De Morgan’s laws
De Morgan’s laws are part of logical equivalences and can be demonstrated through truth tables, which are used to determine the truth value (true or false) of a proposition.
Since the conjunction is only true when p and q are true, its truth table is:
On the other hand, in the disjunction, the proposition is true if p and q are true or if at least one of them is true, but it is false if both are true:
Now, negation transforms what is true into false and vice versa. In such a case, the truth values of ∼(p ∧ q) and ∼(p ∨ q) are the inverse of the truth values of (p ∧ q) and (p ∨ q):
And we must verify that these results are obtained by carrying out the respective truth tables of (∼ p ˅ ∼ q) and (∼ p ˄ ∼ q):
And indeed, when comparing the respective truth tables, it is observed that De Morgan’s laws are fulfilled. Now we will see two examples of its application.
Worked example 1
Apply De Morgan’s laws to find the equivalent expression of: ∼ (∼p ˅ ∼q)
The given expression ∼ (∼p ˅ ∼q) is compared with Morgan’s law:
∼(p ∨ q) ⇔ ∼p ∧ ∼q
And it is observed that the negation is already outside the parentheses in both cases, therefore the instructions of the law are followed: negate ∼p, negate ∼q, and change the connector:
∼ (∼p ˅ ∼q) ⇔ ∼ (∼p) ∧ ∼ (∼q) ⇔ p ∧ q
Worked example 2
Determine the equivalent expression of ∼ [∼p ˄ ∼ (∼q)] ≡
First, the negation of ∼q is simplified:
∼ [∼p ˄ ∼ (∼q)] ⇔ ∼ [∼p ˄ q]
Since there is already a negation outside the bracket, the resulting expression is compared with Morgan’s law: ∼(p ∧ q) ⇔ ∼p ∨ ∼q
To solve ∼ [∼p ˄ q] negate ∼p, negate q, and change the connector:
∼ [∼p ˄ q] ⇔∼(∼p) ∨ ∼q ⇔ p ˅ ∼q
References
Becerra, JM Notes on logic from the UNAM.
brilliant. From Morgan’s Laws. Retrieved from: brilliant.org.
Electronics Tutorials. From Morgan’s Theorem. Retrieved from: electronics-tutorials.ws.
López, F. Introduction to mathematical logic. Retrieved from: youtube.com
Muñoz, C. Introduction to logic. Retrieved from: webs.ucm.es.