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:
- \(\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.