You are here

Reasoning with Equivalences

23 July, 2015 - 12:53
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

Exercise 2.5.25

Using Propositional equivalences, and the defnition or nor (mnemonic: "not or"), written ↓, φψ ≡¬ (φψ), express the function ∧ in terms of ↓ only. That is, give a formula which doesn't use ∧, ∨, ¬, but instead only uses ↓ and which has the same truth table as φψ.

Exercise 2.5.26

Similar to the previous exercise, express each of the following using nand (Example ) only, and prove correctness using the algebraic identities (Propositional equivalences).

This operation is particularly interesting, since making a NAND gate in hardware requires only two transistors.

  1. ¬

Exercise 2.5.27

Using algebraic identities (Propositional equivalences), show that (ac) ∧ (bc) ∧ (ca) is equivalent to (bc) ∧ a.

This is an algebraic hand-evaluation: a series of formulas joined by ≡. Don't write just portions of previous formulas and mysteriously re-introduce the dropped parts later. For each step, mention which identity you used. It is also helpful if you underline the formula you are rewriting in the next step. You can use commutativity and associativity without using a separate line, but mention when you use it.

Exercise 2.5.28

In two exercises, you've shown the same equivalence by truth tables (Exercise 2.5.22) and by algebraic identities (Exercise 2.5.27).

  1. What is an advantage of using truth tables? What is an advantage of using identities?
  2. In that truth table exercise (Exercise 2.5.22), you also showed two formulas φ and ψ non-equivalent. It is also possible to do so with Boolean algebra rather than truth tables. How?
  3. Describe a hybrid approach, combining truth tables and Boolean algebra, to prove the equivalence and non-equivalence of formulas.
  4. To ponder on your own without turning it in: Which approach appeals more to you?

Exercise 2.5.29

Using Propositional equivalences, rewrite the formula (abc) ∧¬b to one with fewer connectives.