# indexing boolean algebra

Boolean algebra can be encoded by indexing, for example, a venn diagram for two sets: $$A$$ and $$B$$ divide diagram to four parts: $$1, 2, 3, 4$$. Thus

1. $$A = \{1, 2\}$$
2. $$B = \{1, 3\}$$
3. $$A \cup B = \{1, 2, 3\}$$
4. $$A \cap B = \{1\}$$
5. $$(A \cup B)' = \{4\}$$

The benefit of the encoding is the encoding let any sets can be treated as finite sets operation. So for any set check a boolean algebra is valid, indexing helps you check them by computer.

## 1. Encoding to program

(define I (set 1 2 3 4))
(define A (set 1 2))
(define B (set 1 3))
(define ∅ (set))
(define ∩ set-intersect)
(define ∪ set-union)
(define (not S)
(set-subtract I S))
(define (→ A B)
(∪ (not A) B))
(define (- A B)
(∩ A (not B)))
(define (≡ A B)
(∪ (∩ A B) (∩ (not A) (not B))))


## 2. Checking based on encoding

Now, you can check $$A \to B = (A - B)'$$ by the following program.

(equal? (→ A B) (not (- A B)))


And you will know $$(A \cap (A - B)') = \emptyset$$ is invalid since the following program returns false.

(equal? (∩ A (not (- A B))) ∅)


## 3. Futher

You can even extend this method for $$A, B, C$$, for $$A, B, C, D$$ and so on, but then that's too far for this article.

Date: 2022-02-16 Wed 00:00