My latest project tying in with our study of events (which are sets) in CMPE 107 is a program for building set membership tables.

Theory

One way to verify that two set expressions are equivalent is to build a set membership table or SMT for each expression and compare them. This approach has the advantage that it is relatively simple to compute such a table, especially with a computer. It does not require any kind of computer algebra based system. On the other hand, such a table has 2ⁿ rows where n is the number of variables. This can easily be prohibitively expensive for expressions with many variables. It is also sometimes difficult to verify two expressions are the same if they have different numbers of variables but some variables are not algebraically relevant.

In this application, I parse a text based representation of a set expression into an abstract syntax tree. I then extract the variables and subexpressions from that tree. Finally, I enumerate the different combinations of Boolean values for each variable and use them to evaluate the subexpressions and final expression in a table.

Examples

Here are some example uses of the generator adapted from this pdf.

Commutative Law

A ∪ B = B ∪ A

A ∩ B = B ∩ A

Associative Laws

(A ∪ B) ∪ C = A ∪ (B ∪ C)

(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Laws

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Identity Laws

A ∪ ∅ = A

A ∩ 𝕌 = A

Complement Laws

A ∪ A^∁ = 𝕌

A ∩ A^∁ = ∅

Double Complement Laws

(A^∁)^∁ = A

Idempotent Laws

A ∪ A = A

A ∩ A = A

Universal Bound Laws

A ∪ 𝕌 = 𝕌

A ∩ ∅ = ∅

De Morgan’s Laws

(A ∪ B)^∁ = A^∁ ∩ B^∁

(A ∩ B)^∁ = A^∁ ∪ B^∁

Absorption Laws

A ∪ (A ∩ B) = A

A ∩ (A ∪ B) = A

Complements of 𝕌 and ∅

𝕌^∁ = ∅

∅^∁ = 𝕌

Set Difference Law

A − B = A ∩ B^∁

Grammar

The parser uses a relatively simple grammar in order to parse set expressions. An expression is first broken down into tokens then run. Anything that cannot be interpreted as a keyword will be interpreted as a variable. Most keywords have several synonymous ways to input them. Unfortunately, the parser currently doesn’t give the user much help if their expression is invalid.

Infix Expressions

These expressions expect a subexpression to be on either side of them. Eg expr *infix* expr

Unary Expressions

These expressions expect a subexpression on the left but none on the right. Eg expr *unary*

Value Expressions

These expressions immediately evaluate to a set without any operands. Eg *value*

Grouping

You can group tokens together using parenthesis or brackets. Either choice will be treated exactly the same. Groups follow the regular algebraic rules. Expressions inside of parenthesis are evaluated before expressions outside of them.