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:

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

Yes. There is one matching rule:

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

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

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

Yes. There is one matching rule:

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

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:

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

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