Logic laws

In this article we will see a list of the most important logical laws used in propositional logic.

What is a logical law?

In discrete mathematics we know a logical law or tautology as a compound proposition that is always true regardless of the truth value of the component propositions. To demonstrate a logical law it is sufficient to draw up the corresponding truth table where the above will be evidenced. We will see the most important ones below.

Basic logic laws

The basic laws of logic are those with which we usually work in propositional logic. We will see them all below

Involution

The negation of a proposition is equivalent to the proposition itself:

*¬(¬p) ↔ p*

Example: "It is not true that it is not raining" is equivalent to "It is raining."

De Morgan's Laws

The negation of a conjunction is equivalent to the disjunction of the negations:

*¬(p∧q) ↔ ¬p ∨ ¬q*

The negation of a disjunction is equivalent to the conjunction of the negations:

*¬(p∨q) ↔ ¬p ∧ ¬q*

Commutativity

We can permute the order of propositions in a conjunction or a disjunction.

*p ∨ q ↔ q ∨ p*
*p ∧ q ↔ q ∧ p*

Associativity

It is allowed to associate propositions in a chain of conjunctions or disjunctions:

*p ∨ (q ∨ r) ↔ (p ∨ q) ∨ r*
*p ∧ (q ∧ r) ↔ (p ∧ q) ∧ r*

Distributivity

Conjunction is distributive with respect to disjunction:

*(p ∨ q) ∧ r ↔ (p∧r) ∨ (q∧r)*

Disjunction is distributive with respect to conjunction:

*(p ∧ q) ∨ r ↔ (p∨r) ∧ (q∨r)*

Law of the Excluded Middle

We know that in logic, a proposition can be true or false, with no possibility of a third option. Symbolically, we write this as follows:

*p ∨ ¬p*

Example: "That animal is either a dog or not a dog."

Law of Non-Contradiction

It cannot happen that a proposition is both true and false at the same time:

*¬ (p ∧ ¬p)*

Idempotence

*p ∧ p ↔ p*
*p ∨ p ↔ p*

Identity Laws

*p →p*
*p ↔p*

Transposition Laws

*(p → q) ↔ (¬q ↔¬p)* (law of contrapositive implication)
*(p ↔ q) ↔ (¬q↔¬p)*

Definitions

The conditional and the biconditional can be expressed in terms of conjunctions or disjunctions. These are known as the definitions of both connectives.

Definition of conditional: *p→q ↔ ¬p ∨ q*

Definition of biconditional or equivalence:
*(p ↔ q) ↔ [(p → q) ∧ (q → p)]*
*(p ↔ q) ↔ [(p ∧ q) ∨ (¬p ∧ ¬q)]*

Inference rules

Modus Ponens: *[(p → q) ∧ p] → q*

Modus Tollens: *[(p → q) ∧ ¬q] → ¬p*

Syllogism: *(p→q)→[(q→r)→( p→r)]*

Disjunctive Syllogism:
*[(p ∨ q) ∧ ¬p] → q*
*[(p ∨ q) ∧ ¬q] → p*

Transitivity or Hypothetical Syllogism:
*[(p → q) ∧ (q → r)] → (p → r)*
*[(p ↔ q) ∧ (q ↔ r)] → (p ↔ r)*

Simplification:
*p∧q → p*
*p∧q → q*

Addition:
*p → p∨q*
*q → p∨q*

Constructive Dilemma: *[( p ∨ q) ∧ ( p→r) ∧ (q→r)]→r*

Second Law of Constructive Dilemma: *[(p→q)∧(r→s)∧(p∨r)]→(q∨s)*

Destructive Dilemma: *[(p → q) ∧ (r → s) ∧ (¬q ∨ ¬s) ] → (¬p ∨ ¬r)*

Law of Contrapositive: *[(p → q) ∧ (¬p → ¬q)] → q*

Exportation: *[(p ∧ q) → r] ↔ [p → (q ∧ r)]*

Other Laws

Negation of the conditional: *¬(p→q) ↔ p ∧ ¬q*

Absorption Laws:
*p ∨ (p ∧ q) ↔ p*
*p ∧ (p ∨ q) ↔ p*

Permutation Law: *[p→(q→r)]↔[q→(p→r)]*

Expansion Laws:
*(p → q) ↔ [(p ∨ q) ↔ q]*
*(p → q) ↔ [(p ∧ q) ↔ p]*

When it is known that a proposition is true (T) or false (F):
*T∨p ↔ T*
*F∨p ↔ p*
*T∧p ↔ p*
*F∧p ↔ F*
*p∧¬p ↔ F*
*p∨¬p ↔ T*

+ See infographics