- Page ID
The final piece of algebra in Boolean algebra is the observation that we can chain logical equivalences together. That is, from P ≡ Q and Q ≡ R, it follows that P ≡ R. This is really just a consequence of the Second Substitution Law: The equivalence Q ≡ R allows us to substitute R for Q in the statement P ≡ Q, giving P ≡ R. (Remember that, by Definition 2.5, logical equivalence is defined in terms of a proposition.) This means that we can show that two compound propositions are logically equivalent by finding a chain of logical equivalences that lead from one to the other. For example:
p ∧ (p → q) ≡ p ∧ (¬p ∨ q) definition of p → q, Theorem 2.2
≡ (p ∧ ¬p) ∨ (p ∧ q) Distributive Law
≡ F ∨ (p ∧ q) Law of Contradiction, Theorem 2.2
≡ (p ∧ q) Identity Law
Each step in the chain has its own justification. In several cases, a substitution law is used without stating as much. In the first line, for example, the definition of p → q is that p → q ≡ ¬p ∨ q. The Second Substitution Law allows us to substitute (¬p ∨ q) for(p → q). In the last line, we implicitly applied the First Substitution Law to the Identity Law, F ∨ p ≡ p, to obtain F ∨ (p ∧ q) ≡ (p ∧ q).
The chain of equivalences in the above example allows us to conclude that p ∧ (p → q)is logically equivalent to p ∧ q. This means that if you were to make a truth table for these two expressions, the truth values in the column for p ∧ (p → q) would be identical to those in the column for p ∧ q. We know this without actually making the table. In this case, the table would only be four lines long and easy enough to make. But Boolean algebra can be applied in cases where the number of propositional variables is too large for a truth table to be practical.
Let’s do another example. Recall that a compound proposition is a tautology if it is true for all possible combinations of truth values of the propositional variables that it contains. But another way of saying the same thing is that P is a tautology if P ≡ T. So, we can prove that a compound proposition, P, is a tautology by finding a chain of logical equivalences leading from P to T. For example:
((p∨q)∧¬p) → q
≡ (¬((p∨q)∧¬p))∨q definition of
≡ (¬(p∨q)∨¬(¬p))∨q DeMorgan’s Law, Theorem 2.2
≡ (¬(p ∨ q) ∨ p) ∨ q Double Negation, Theorem 2.2
≡ (¬(p∨q))∨(p∨q) Associative Law for ∨
≡T Law of Excluded Middle
From this chain of equivalences, we can conclude that ((p ∨ q) ∧ ¬p) → q is a tautology.
Now, it takes some practice to look at an expression and see which rules can be ap- plied to it; to see (¬(p ∨ q)) ∨ (p ∨ q) as an application of the law of the excluded middle for example, you need to mentally substitute (p ∨ q) for p in the law as it is stated in Figure 2.2. Often, there are several rules that apply, and there are no definite guidelines about which one you should try. This is what makes algebra something of an art.