Skip to main content

Subsection 3.3.9 Simplification

As we work with logical expressions, we often end up with ones that are longer and messier than they need to be. Before we go farther, it can help a lot to attempt to simplify them. In other words, given an expression E , we look for an alternative expression that:

  • is logically equivalent to E , and

  • is simpler in some way, and thus easier to work with, than E is.

We have two bags of tools that we can use to do this:

  • the Boolean identities that we’ve just described (plus any others that you want badly enough to prove the correctness of), and

  • computation.

So how do we know what tools to use and how to use them? There’s no magic answer. Often what we try to do is to transform subexpressions so that we’re able to use computation.

In the examples that follow, we’ll underline, in each expression, the subexpression that will be changed to create the next line. That should make the process a bit easier to follow.

Suppose that we have: \((p \wedge s) \wedge ((p \vee \neg p) \rightarrow (\neg p \wedge r))\)

We can simplify as follows:

  1. \(\displaystyle (p  s)  ((p  p)  (p  r))\)

  2. \((p  s)  (T  (p  r))\) Computation

  3. \((p  s)  (p  r) \) Computation

  4. \((s  p)  (p  r) \) Commutativity of and

  5. \(((s  p)  p)  r \) Associativity of and

  6. \((s  (p  p))  r \) Associativity of and

  7. \((s  F)  r \) Computation

  8. \(F  r \) Computation

  9. \(F \) Computation

Sometimes, it can take just a few steps to do a really significant simplification.

Suppose that we have: ((p  q)  (p  q))  (p  r).

The trick in this example is to use De Morgan’s laws backwards from the way we usually use them. Why? Because, in this case, doing so will create a subexpression of the form P  P that can be simplified to T. (More precisely, we’ll end up with (p  q)  (p  q), but, letting P stand for (p  q), we have P  P.)

So we can simplify as follows:

  1. \(\displaystyle ((p  q)  (p  q))  (p  r) \)

  2. \(((p  q)  (p  q))  (p  r) \) De Morgan

  3. \(T  (p  r) \) Computation

  4. \(p  r \) Computation

When we simplify an expression, we’re actually doing a special kind of proof. We’re proving that the expression that we started with and the one that we ended up with are, in fact, equivalent. We do that using the identities and computational rules that we’ve just described.

In the next couple of learning modules, we’ll add to our Boolean logic proof arsenal a collection of inference rules. Then we’ll see how to exploit combinations of identities, computational rules and inference rules to produce useful proofs.