Simplification

During the simplification step, what simplifications are possible? Each logical operator is fully defined by the rules below. We can use these rules as a look-up table to simplify an expression:

Not

  • \(\lnot 0 = 1\)
  • \(\lnot 1 = 0\)

Or

  • \(0 \lor 0 = 0\)
  • \(0 \lor 1 = 1\)
  • \(1 \lor 0 = 1\)
  • \(1 \lor 1 = 1\)

And

  • \(0 \land 0 = 0\)
  • \(0 \land 1 = 0\)
  • \(1 \land 0 = 0\)
  • \(1 \land 1 = 1\)

Implies

  • \(0 \supset 0 = 1\)
  • \(0 \supset 1 = 1\)
  • \(1 \supset 0 = 0\)
  • \(1 \supset 1 = 1\)

Example 1. Can \(\lnot 0\) be simplified?

Yes. There is one matching rule:

So we can replace \(\lnot 0\) by \(1\).

Example 2. Can \(x \land y = 1\) be simplified?

Yes. There is one matching rule:

So we can infer that \(x = 1\) and \(y = 1\).

Example 3. Can \(x \lor y = 1\) be simplified?

No. There are three matching rules:

Neither variable can be pinned down to a single value, so we cannot simplify \(x \lor y = 1\) any further.