Logical Equivalence: The Laws of Logic
In mathematics, it is important to know whether the entities being studied are equal or whether they are essentially the same.
For example, in arithmetic and algebra, two nonzero real numbers are equal when they have the same magnitude and algebraic sign. Therefore, for two nonzero real numbers x, y, then x = y if |x| = |y| and xy > 0. Conversely, if x = y, then |x| = |y| and xy > 0. In geometry, triangle ABC and triangle DEF are congruent if they have equal corresponding sides.
The study of logic is often referred to as the algebra of propositions instead of the algebra of real numbers. The algebra of propositions uses truth tables of the statements to develop the idea of when two entities are essentially the same.
Example For the primitive statements p and q, the following provides the truth table for the compound statements ¬p ᴠ q and p → q.
It is shown from the truth table that the two statements ¬p ᴠ q and p → q are exactly the same.
Logical Equivalence Two statements s₁, s₂ are logically equivalent when either the statement s₁ is true if and only if s₂ is true, or the statement s₁ is false if and only if s₂ is false. Logically equivalent statements s₁, s₂ are denoted as s₁ <=> s₂.
Note that if s₁ <=> s₂, the statements s₁ and s₂ have the same truth value assignments on their truth tables, because the statements s₁, s₂ have the same truth values for all truth value assignment cases of their primitive components.
Using this concept, it can be shown that the implication of primitive statements p → q is logically equivalent to the negation and disjunction of its primitive statements, denoted as ¬p ᴠ q, where (p → q) <=> (¬p ᴠ q). Therefore, each compound statement can be rewritten in terms of one another.
Similarly, the following truth table shows that (p ↔ q) <=> (p → q) ᴧ (q → p), which helps validate the use of biconditional:
The following truth table demonstrates that using negation with the conjunction and disjunction connectives creates a compound statement that is logically equivalent to the simple exclusive "or" connective ⊻:
Notice how p ⊻ q <=> (p ᴠ q) ᴧ ¬(p ᴧ q).
The Laws of Logic Using the concepts of logical equivalence, tautology, and contradiction, the following are the laws of logic:
For any primitive statements p, q, r, any tautology T₀, and any contradiction F₀:
1. Law of Double Negation ¬¬p <=> p
2. DeMorgan's Laws ¬(p ᴠ q) <=> ¬p ᴧ ¬q ¬(p ᴧ q) <=> ¬p ᴠ ¬q
Note that DeMorgan's Laws does not change the connectives inside inner parentheses of complex compound statements.
3. Commutative Laws p ᴠ q <=> q ᴠ p p ᴧ q <=> q ᴧ p
4. Associative Laws p ᴠ (q ᴠ r) <=> (p ᴠ q) ᴠ r p ᴧ (q ᴧ r) <=> (p ᴧ q) ᴧ r
Note that, parentheses are then optional.
5. Distributive Laws p ᴠ (q ᴧ r) <=> (p ᴠ q) ᴧ (p ᴠ r) p ᴧ (q ᴠ r) <=> (p ᴧ q) ᴠ (p ᴧ r)
6. Idempotent Laws p ᴠ p <=> p p ᴧ p <=> p
7. Identity Laws p ᴠ F₀ <=> p p ᴧ T₀ <=> p
8. Domination Laws p ᴠ T₀ <=> T₀ p ᴧ F₀ <=> F₀
9. Inverse Laws p ᴠ ¬p <=> T₀ p ᴧ ¬p <=> F₀
10. Absorption Laws p ᴠ (p ᴧ q) <=> p p ᴧ (p ᴠ q) <=> p
Other Important Tautologies The following biconditional statements are tautologies and therefore logically equivalent individually:
(p ↔ q) ↔ [(p → q) ᴧ (q → p)]
p ⊻ q ↔ (p ᴠ q) ᴧ ¬(p ᴧ q)
(p → q) ↔ (¬p ᴠ q) ¬(p → q) ↔ (p ᴧ ¬q)
¬p ↔ (p ↑ p) (p ↑ q) ↔ ¬(p ᴧ q)
Note that, if s₁, s₂, s₃ are statements such that s₁ <=> s₂ and s₂ <=> s₃, then s₁ <=> s₃.
To designate the situation that two statements s₁, s₂ are not logically equivalent, it is denoted as s₁ <≠> s₂.
The Principle of Duality Notice that the laws of logic, from the second law to the tenth law, have a pairing. This pairing idea will help logical problem solving.
Let s be a statement where it contains no logical connectives except for the conjunction connective ᴧ and the disjunction connective ᴠ. Additionally, s can contain either a tautology T₀ or a contradiction F₀. Then the dual of s, denoted as sd, is the statement obtained from s by replacing each conjunction connective ᴧ with the disjunction connective ᴠ and each disjunction connective ᴠ with the conjunction connective ᴧ. If there contains a tautology T₀, it is replaced with F₀. If there contains a contradiction F₀, it is replaced with T₀.
In general, if there are no conjunction connectives or disjunction connectives or tautologies and contradictions, let p be a primitive statement, then the dual of a primitive statement pd is simply the same as its original primitive statement p. Therefore (¬p)d is the same as ¬p. However, whenever p is primitive, then p ᴠ ¬p and p ᴧ ¬p are duals of each other.
Example Given the primitive statements p, q ,r, and the following compound statement: s: (p ᴧ ¬q) ᴠ (r ᴧ T₀) The dual of s is then the following: sd: (p ᴠ ¬q) ᴧ (r ᴠ F₀) Notice that ¬q is unchanged.
Duality and Logical Equivalence Let s and t be statements that contain no logical connectives other than ᴧ and ᴠ. Then, if s <=> t, then sd <=> td.
As a result, this can prove the laws of logic from the second law to the tenth law. Additionally, other logical equivalences can be derived.
Example If q, r, s are primitive statements, then the following truth table is made:
The truth table shows that (r ᴧ s) → q <=> ¬(r ᴧ s) ᴠ q, and so [(r ᴧ s) → q] ↔ [¬(r ᴧ s) ᴠ q] is a tautology. Instead of always constructing large truth tables, recall that the following compound statement is a tautology: (p → q) ↔ (¬p ᴠ q) If the primitive statement p was replaced with the compound statement r ᴧ s, then the earlier tautology is obtained.
Substitution Rules The following two substitution rules help simplify statements:
1. Tautologies. Let P be a compound statement that is a tautology. If a primitive statement p appears in P, and each primitive statement p is replaced by some statement q, then the resulting compound statement P₁ is also a tautology.
2. Logical Equivalence. Let P be a compound statement, where p is an arbitrary statement that appears in P. Let q be a statement such that q <=> p. If one or more occurrences of p in P are replaced by q, then this replacement yields the compound statement P₁, where P₁ <=> P.
The following example applies the first substitution rule:
Example The following P denotes the compound statement of the first DeMorgan's law, where p, q are primitive statements: P: ¬(p ᴠ q) ↔ (¬p ᴧ ¬q) Since it is the first DeMorgan's law, this compound statement is a tautology. Therefore, any compound statement can replace all occurrences of the primitive statement p. Let this compound statement be r ᴧ s. Then: P: ¬(p ᴠ q) ↔ (¬p ᴧ ¬q) P₁: ¬[(r ᴧ s) ᴠ q] ↔ [¬(r ᴧ s) ᴧ ¬q] P₁ is therefore also a tautology. Additionally, another compound statement can replace all the occurrences of the primitive statement q. Let that compound statement be t → u. Then: P₁: ¬[(r ᴧ s) ᴠ q] ↔ [¬(r ᴧ s) ᴧ ¬q] P₂: ¬[(r ᴧ s) ᴠ (t → u)] ↔ [¬(r ᴧ s) ᴧ ¬(t → u)] P₂ is therefore also a tautology. Then the biconditional statement P₂ can demonstrate logical equivalence: P₂: ¬[(r ᴧ s) ᴠ (t → u)] <=> [¬(r ᴧ s) ᴧ ¬(t → u)]
The following examples apply the second substitution rule:
Example Let P denote the compound statement (p → q) → r. Since (p → q) <=> ¬p ᴠ q, then P₁ <=> P if P₁ denotes the compound statement (¬p ᴠ q) → r. Therefore, [(p → q) → r] ↔ [(¬p ᴠ q) → r] is a tautology.
Example Let P denote the tautology compound statement p → (p ᴠ q). Since ¬¬p <=> p, the compound statements P₁: p → (¬¬p ᴠ q) and P₂: ¬¬p → (¬¬p ᴠ q) can be formed by replacing one or more of the primitive statement p by its logically equivalent form ¬¬p. P₁ and P₂ are still tautologies, and they are both logically equivalent to P.
The following examples use the ideas of logical equivalence, the laws of logic, and the two substitution rules:
Example To negate and simplify the compound statement (p ᴠ q) → r, recall that (s → t) ↔ (¬s ᴠ t) is a tautology, so by the first rule of substitution: (p ᴠ q) → r <=> ¬(p ᴠ q) ᴠ r Negating both sides of the logical equation: ¬[(p ᴠ q) → r] <=> ¬[¬(p ᴠ q) ᴠ r] Using DeMorgan's law on the right side of the logical equation: ¬[¬(p ᴠ q) ᴠ r] <=> ¬¬(p ᴠ q) ᴧ ¬r Using the double negation law on the right side of the logical equation: ¬¬(p ᴠ q) ᴧ ¬r <=> (p ᴠ q) ᴧ ¬r Therefore, ¬[(p ᴠ q) → r] <=> (p ᴠ q) ᴧ ¬r
Example Let p,q denote the following primitive statements: p: Joan goes to Lake George. q: Mary pays for Joan's shopping spree. Consider the following implication: p → q: If Joan goes to Lake George, then Mary will pay for Joan's shopping spree. To negate and simplify this implication without it producing the following result: ¬(p → q): It is not the case that if Joan goes to Lake George, then Mary will pay for Joan's shopping spree. Instead, the wanted result is: ¬(p → q): Joan goes to Lake George, but Mary does not pay for Joan's shopping spree. This negation and simplification of p → q to yield the above wanted outcome can be done using the logically equivalent statement p → q <=> ¬p ᴠ q. Negating both sides of the logical equation: p → q <=> ¬p ᴠ q ¬(p → q) <=> ¬(¬p ᴠ q) Using DeMorgan's law on the right side of the logical equation: ¬(¬p ᴠ q) <=> ¬¬p ᴧ ¬q Using the double negation law on the right side of the logical equation: ¬¬p ᴧ ¬q <=> p ᴧ ¬q By the second substitution rule, ¬(p → q) <=> p ᴧ ¬q. The statement p ᴧ ¬q satisfies the words of the wanted outcome.
Note that the negation of an implication does not begin with the word "if" when written in words. It is not another implication. Therefore, when writing out the compound statement ¬(p → q), use the tautology (p → q) ↔ (p ᴧ ¬q).
Example Above the dual sd of a statement s was defined only for statements involving the negation and connectives ᴧ and ᴠ. To find the dual statement sd for an implication statement s: p → q, where p, q are primitive, consider the following logical equivalence: p → q <=> ¬p ᴠ q Let t denote the compound statement ¬p ᴠ q. Therefore, s <=> t. By the definition of duality, then sd <=> td. Therefore, td <=> (¬p ᴠ q)d, which is ¬p ᴧ q.
Implications, Contrapositives, Converses, and Inverses The following truth table demonstrates that p → q <=> ¬q → ¬p and that q → p <=> ¬p → ¬q:
The compound statement ¬q → ¬p is logically equivalent to p → q is called the contrapositive of p → q.
The statement q → p is called the converse of p → q.
The compound statement ¬p → ¬q that is logically equivalent to the converse of p → q, which is q → p, is called the inverse of p → q, or the contrapositive of q → p.
Note that the implication p → q is not logically equivalent to q → p, where p → q <≠> q → p. Additionally, the inverse of p → q is not logically equivalent to the contrapositive of p → q, where ¬q → ¬p <≠> ¬p → ¬q.
Therefore, if a certain implication p → q is true, it does not require that the converse q → q is also true. However, if a certain implication p → q is true, then the contrapositive ¬q → ¬p must also be true.
Consider the following statements p,q:
p: Jeff is concerned about his cholesterol levels. q: Jeff walks at least two miles three times a week.
The implication of p,q is p → q: If Jeff is concerned about his cholesterol levels, then he will walk at least two miles three times a week.
The contrapositive of p → q is ¬q → ¬p: If Jeff does not walk at least two miles three times a week, then he is not concerned about his cholesterol levels.
The converse of p → q is q → p: If Jeff walks at least two miles three times a week, then he is concerned about his cholesterol levels.
The inverse of p → q is ¬p → ¬q: If Jeff is not concerned about his cholesterol levels, then he does not walk at least two miles three times a week.
If the statement p is true and the statement q is false, then the implication p → q and the contrapositive ¬q → ¬p are both false, while the converse q → p and the inverse ¬p → ¬q are both true. Similarly, if the statement p is false and the statement q is true, then the implication p → q and the contrapositive ¬q → ¬p are both true, while the converse q → p and the inverse ¬p → ¬q are both false.
If both the statements p,q are true, or if both the statements p,q are false, then the implication, contrapositive, converse, and inverse are all true.
Example Let p,q,r be primitive statements. Simplifying (p ᴠ q) ᴧ ¬(¬p ᴧ q): (p ᴠ q) ᴧ ¬(¬p ᴧ q) <=> (p ᴠ q) ᴧ (¬¬p ᴠ ¬q) (DeMorgan's law) <=> (p ᴠ q) ᴧ (p ᴠ ¬q) (Double negation law) <=> p ᴠ (q ᴧ ¬q) (Distributive law) <=> p ᴠ F₀ (Inverse law) <=> p ᴠ (p ᴧ ¬p) (Inverse law) <=> (p ᴠ p) ᴧ (p ᴠ ¬p) (Distributive law) <=> p ᴧ T₀ (Idempotent law and Inverse Law) <=> p (Identity law) Therefore, (p ᴠ q) ᴧ ¬(¬p ᴧ q) <=> p.
Example Let p,q,r be primitive statements. Simplifying ¬[¬[(p ᴠ q) ᴧ r] ᴠ ¬q]: ¬[¬[(p ᴠ q) ᴧ r] ᴠ ¬q] <=> ¬¬[(p ᴠ q) ᴧ r] ᴧ ¬¬q (DeMorgan's law) <=> [(p ᴠ q) ᴧ r] ᴧ q (Double negation law) <=> [(p ᴠ q) ᴧ q] ᴧ (q ᴧ r) (Distributive law) <=> q ᴧ (q ᴧ r) (Absorption law) <=> (q ᴧ q) ᴧ r (Associative law) <=> q ᴧ r (Idempotent law) Therefore, ¬[¬[(p ᴠ q) ᴧ r] ᴠ ¬q] <=> q ᴧ r.
PDF reference: 87
a.i)
Therefore, p → (q ᴧ r) <=> (p → q) ᴧ (p → r).
a.iii)
Therefore, p → (q ᴠ r) <=> ¬r → (p → q).
b)
Using the left side:
Therefore, p → (q ᴠ r) <=> (p ᴧ ¬q) → r.
a)
p: Kelsey will get a good education. q: Kelsey puts her studies before her interest in cheerleading. q → p: If Kelsey puts her studies before her interest in cheerleading, then she will get a good education. Tautology: ¬(q → p) ↔ (q ᴧ ¬p) ¬(q → p): Kelsey puts her studies before her interest in cheerleading, but she still didn't get a good education.
b)
p: Norma is doing her homework. q: Karen is practicing her piano lessons. p ᴧ q: Norma is doing her homework, and Karen is practicing her piano lessons. Tautology: ¬(p ᴧ q) ↔ (¬p ᴠ ¬q) ¬(p ᴧ q): Norma is not doing her homework, or Karen is not practicing her piano lessons.
c)
p: Harold passes his C++ course. q: Harold finishes his data structures project. r: Harold will graduate at the end of the semester. (p ᴧ q) → r: If Harold passes his C++ course and finishes his data structures project, he will graduate at the end of the semester. Tautology: ¬(q → p) ↔ (q ᴧ ¬p) ¬[(p ᴧ q) → r]: Harold passed his C++ course and finished his data structures project, but he still didn't graduate at the end of the semester.
a)
Implication: If 0 + 0 = 0, then 1 + 1 = 1. (false) Contrapositive: If 1 + 1 ≠ 1, then 0 + 0 ≠ 0. (false) Converse: If 1 + 1 = 1, then 0 + 0 = 0. (true) Inverse: If 0 + 0 ≠ 0, then 1 + 1 ≠ 1. (true)
b)
Implication: If -1 < 3 and 3 + 7 = 10, then sin(3π/2) = -1. (true) Contrapositive: If sin(3π/2) ≠ -1, then -1 ≥ 3 and 3 + 7 ≠ 10. (true). Converse: If sin(3π/2) = -1, then -1 < 3 and 3 + 7 = 10. (true) Inverse: If -1 ≥ 3 and 3 + 7 ≠ 10, then sin(3π/2) ≠ -1. (true)
a)
b)
c)
d)
a)
b)
c)