# 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.