My latest project tying in with our study of events (which are sets) in CMPE 107 is a program for building set membership tables.
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 2n 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.
Here are some example uses of the generator adapted from this pdf.
Double Complement Laws
Universal Bound Laws
De Morgan’s Laws
Complements of 𝕌 and ∅
Set Difference Law
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.
These expressions expect a subexpression to be on either side of them. Eg
expr *infix* expr
|Union||union, or, ∪|
|Intersection||intersection, and, &, ∩|
|Difference||difference, -, \|
These expressions expect a subexpression on the left but none on the right. Eg
|Complement||complement, ^C, !, ^∁, ∁|
These expressions immediately evaluate to a set without any operands. Eg
|Universal Set||universal, 𝕌, Ω|
|Empty Set||empty, ∅|
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.