Logic laws
In this article we will see a list of the most important logical laws used in propositional logic.
Table of Contents
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*
Other articles that may interest you