Morgan’s Laws

The l eyes of Morgan are inference rules used in propositional logic, which establish what the result of denying a disjunction and a conjunction of propositions or propositional variables. These laws were defined by the mathematician Augustus De Morgan.

Morgan’s laws represent a very useful tool to demonstrate the validity of mathematical reasoning. Later they were generalized within the concept of sets by the mathematician George Boole.

Morgan's Laws

This generalization made by Boole is completely equivalent to initial Morgan’s laws, but it is developed specifically for sets rather than for propositions. This generalization is also known as Morgan’s laws.

Review of propositional logic

Before looking at what specifically Morgan’s laws are and how they are used, it is helpful to remember some basic notions of propositional logic. (For more details see article on propositional logic).

In the realm of mathematical (or propositional) logic, an inference is a conclusion that is issued from a set of premises or hypotheses. This conclusion, together with the aforementioned premises, gives rise to what is known as mathematical reasoning.

Such reasoning must be demonstrable or denied; that is, not all inferences or conclusions in mathematical reasoning are valid.

Fallacy

A false inference made from certain hypotheses that are assumed to be true is known as a fallacy. The fallacies have the peculiarity of being arguments that seem correct, but mathematically they are not.

Propositional logic is precisely responsible for developing and providing methods by means of which one can, without any ambiguity, validate or refute a mathematical reasoning; that is, infer a valid conclusion from premises. These methods are known as inference rules, of which Morgan’s laws are part.

Propositions

The essential elements of propositional logic are propositions. Propositions are statements that can be said to be valid or not, but cannot be true or false at the same time. There should be no ambiguity in this matter.

Just as numbers can be combined through the operations of addition, subtraction, multiplication and division, propositions can be operated by means of the well-known logical connectives (or connectors): negation (¬, “not”), disjunction (V , “Or”), conjunction (Ʌ, “and”), conditional (→, “if…, then…”) and biconditional (↔, “if, and only if”).

To work more generally, instead of considering specific propositions, propositional variables that represent any propositions are considered, and they are usually denoted with lowercase letters p, q, r, s, etc.

A propositional formula is a combination of propositional variables by means of some of the logical connectives. In other words, it is a composition of propositional variables. They are usually denoted with Greek letters.

It is said that a propositional formula logically implies another when the latter is true each time the former is true. This is denoted by:

When the logical implication between two propositional formulas is reciprocal —that is, when the previous implication is also valid in the opposite sense— the formulas are said to be logically equivalent, and is denoted by

Morgan's Laws

Logical equivalence is a kind of equality between propositional formulas and allows one to be replaced by the other when necessary.

Morgan’s Laws

Morgan’s laws consist of two logical equivalences between two propositional forms, namely:

Morgan's Laws

These laws allow separating the negation of a disjunction or conjunction, as negations of the variables involved.

The first can be read as follows: the negation of a disjunction is equal to the conjunction of the negations. And the second reads like this: the negation of a conjunction is the disjunction of negations.

In other words, denying the disjunction of two propositional variables is equivalent to the conjunction of the negations of both variables. Likewise, denying the conjunction of two propositional variables is equivalent to the disjunction of the negations of both variables.

As mentioned earlier, substituting this logical equivalence helps to prove important results, along with the other existing inference rules. With these you can simplify many propositional formulas, so that they are more useful to work with.

The following is an example of a mathematical proof using inference rules, including Morgan’s laws. Specifically, it is shown that the formula:

Morgan's Laws

It is equivalent to:

Morgan's Laws

The latter is simpler to understand and develop.

Demonstration

Morgan's Laws

It is worth mentioning that the validity of Morgan’s laws can be demonstrated mathematically. One way is by comparing your truth tables.

Sets

The same rules of inference and the notions of logic applied to propositions can also be developed considering sets. This is what is known as Boolean algebra, after the mathematician George Boole.

To differentiate the cases, it is necessary to change the notation and transfer to sets, all the already seen notions of propositional logic.

A set is a collection of objects. Sets are denoted by capital letters A, B, C, X, … and the elements of a set are denoted by lower case letters a, b, c, x, etc. When an element a belongs to a set X, it is denoted by:

Morgan's Laws

When it does not belong to X, the notation is:

Morgan's Laws

The way to represent sets is by placing their elements inside braces. For example, the set of natural numbers is represented by:

Morgan's Laws

Sets can also be represented without writing an explicit list of their elements. They can be expressed in the form {:}. The colon is read “such that”. To the left of the two points a variable is placed that represents the elements of the set, and to the right side is placed the property or condition that they satisfy. This is:

Morgan's Laws

For example, the set of whole numbers greater than -4 can be expressed as:

Morgan's Laws

Or equivalently, and more abbreviated, as:

Morgan's Laws

Similarly, the following expressions represent the sets of odd and even numbers, respectively:

Morgan's Laws

Union, intersection, and complements of sets

Next we will see the analogs of logical connectives in the case of sets, which are part of the basic operations between sets.

Union and intersection

The union and the intersection of sets are defined, respectively, as follows:

Morgan's Laws

For example, consider the sets:

Morgan's Laws

So, you have to:

Morgan's Laws

Complement

The complement of a set is formed by the elements that do not belong to said set (of the same type that the original represents). The complement of a set A, is denoted by:

Morgan's Laws

For example, within natural numbers, the complement of the set of even numbers is that of odd numbers, and vice versa.

To determine the complement of a set, the universal or principal set of the elements under consideration must be clear from the beginning. For example, it is not the same to consider the complement of a set on the natural numbers as on the rational ones.

The following table shows the relationship or analogy that exists between the operations on sets previously defined, and the connectives of propositional logic:

Morgan's Laws

Morgan’s Laws for Sets

Finally, Morgan’s laws on sets are:

Morgan's Laws

In words: the complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements.

A mathematical proof of the first equality would be the following:

Morgan's Laws

The proof of the second is analogous.

References

  1. Almaguer, G. (2002). Mathematics 1. Editorial Limusa.
  2. Aylwin, CU (2011). Logic, Sets and Numbers. Mérida – Venezuela: Publications Council, Universidad de Los Andes.
  3. Barrantes, H., Díaz, P., Murillo, M., & Soto, A. (1998). Introduction to Number Theory. EUNED.
  4. Castañeda, S. (2016). Basic course of number theory. Northern University.
  5. Cofré, A., & Tapia, L. (1995). How to Develop Mathematical Logical Reasoning. University Publishing House.
  6. Guevara, MH (sf). Theory of Numbers. EUNED.
  7. Zaragoza, AC (sf). Number theory Editorial Vision Libros.

Add a Comment

Your email address will not be published. Required fields are marked *