Microproject
Write a Clojure program using higher order functions (e.g., map, filter, reduce, some, …) to symbolically simplify non-nested boolean disjunctions of arbitrary length >= 1 represented as unevaluated lists. For example, in each of the below, given a list representation of the item on the left (you should quote the list), the result should be the item on the right.
|
1 2 3 4 5 6 7 8 9 10 11 |
(or false) => false; (or true) => true; (or x) => x; (or x true) => true; (or x false) => x; (or x y) => (or x y); (or x y true) => true; (or x y false) => (or x y); (or x true true) => true; (or x false false) => x; (or x y z) => (or x y z) |
Your program must work for any arbitrary variables used.
Main Project
In this project you will symbolically simplify arbitrary boolean expressions containing the “and”, “or”, and “not” connectives. “not” will be assumed to take one argument, while “and” and “or” will take one or more. You should use false for False and true for True.
Expressions are created as unevaluated lists. For example:
|
1 2 3 |
(def p1 '(and x (or x (and y (not z))))) (def p2 '(and (and z false) (or x true false))) (def p3 '(or true a)) |
Simplification consists of replacing particular forms with equivalent forms or symbols. Some examples are provided below, though you must be sure your project works in general.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
(or true) => true; (or false) => false; (and true) => true; (and false) => false; (or x false) => x; (or false x) => x; (or true x) = true; (or x true) => true; (or x y false) => (or x y); (or x y z false) => (or x y z); (or x true false) => true; (or x y true false) => true; (and x false) => false; (and false x) => false; (and x true) => x; (and true x) => x; (and x y true) => (and x y); (and x y false) => false; (and x y z) => (and x y z); (not false) => true; (not true) => false<br/> |
The main entry point to the program, “evalexp”, calls functions that simplify, bind, and evaluate these expressions.
Binding consists of replacing some or all of the variables in expressions with constants (true or false), and then returning the partially evaluated form.
The evalexp function should take a symbolic expression and a binding map and return the simplest form (that might just be a constant). One way to define this is
|
1 |
(defn evalexp [exp bindings] (simplify (bind-values bindings exp))) |
Example:
|
1 |
(evalexp p1 '{x false, z true}) |
binds x and z (but not y) in p1, leading to (and false (or false (and y (not true)))) and then further simplifies to just false.
Extra Credit
Write a set of Clojure functions that perform symbolic simplification and evaluation of the set-oriented logical connectives “andor” and “thresh” [1]. These connectives generalize all of the standard boolean logic connectives (such as and, or, xor, and not), and allow the use of many more. They are defined as follows (adapted from [1]):
andor
Syntax: (andor (i j) p1 … pn) 0 <= i <= j <= n
Semantics: (andor (i j) p1 …pn) is True if at least min(i, |{p1 … pn}|) and at most min(j, |{p1 … pn}|) of pi ∈ {p1,…,pn} are True; otherwise it is False.
(andor (0 0)) ≡ True.
thresh
Syntax: (thresh (i j) p1 … pn) 0 <= i <= j <= n
Semantics: (thresh (i j) p1 …pn) is True if either fewer than min(i, |{p1 … pn}|) or more than min(j, |{p1 … pn}|) of pi ∈ {p1,…,pn} are True; otherwise it is False.
(thresh (0 0)) ≡ False
Suggested Development Environment
Either:
- IntelliJ IDEA + Cursive
- emacs + cider