Microproject
Write a Clojure program using at least one higher order function (e.g., map, filter, reduce, some, …) to symbolically simplify non-nested boolean nand relations 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. Some example rules for simplification are provided below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
(nand false) =: true (nand true) =: false (nand (nand x)) =: x (nand x (nand x)) =: true (nand x x) =: (nand x) (nand x y) =: (nand x y) (nand x true) =: (nand x) (nand x false) =: true (nand true true) =: false (nand x y true) =: (nand x y) (nand x true true) =: (nand x) (nand true true true) =: false) (nand x y false) =: true (nand x y z) =: (nand x y z) |
You should generalize for any length expression based on these patterns. Your program must work for any arbitrary variables used.
Main Project
In this project you will convert logical expressions which consist of “and”, “or”, and “not” connectives to ones which only use the “nand” connective. “not” will be assumed to take one argument, while “and” and “or” will take one or more. Then, you will symbolically simplify the resulting expression.
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)) |
Conversion from and/or/not logic to nand logic is done using the following patterns:
|
1 2 3 4 5 6 7 |
(not x) =: (nand x) (and x y) =: (nand (nand x y)) (and x y z) =: (nand (nand x y z)) (and w x y z) =: (nand (nand w x y z)) (or x y) =: (nand (nand x) (nand y)) (or x y z) =: (nand (nand x) (nand y) (nand z)) (or w x y z) =: (nand (nand w) (nand x) (nand y) (nand z)) |
You should generalize for any number of arguments based on the patterns.
Simplification consists of replacing particular forms with equivalent forms or symbols. Use the patterns from the microproject, but here the simplification must be recursive.
The main entry point to the program, “evalexp”, calls functions that simplify, nand-convert, and bind 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 2 |
(defn evalexp [exp bindings] (simplify (nand-convert (bind-values bindings exp)))) |
Example:
|
1 |
(evalexp p1 '{x false, z true}) |
binds x and z (but not y) in p1, leading to
|
1 |
(and false (or false (and y (not true)))) |
Then the conversion to nand occurs resulting in:
|
1 |
(nand (nand false (nand (nand false) (nand (nand (nand y (nand true))))))) |
and then further simplifies to just false.
Suggested Development Environment
Either:
- IntelliJ IDEA + Cursive
- emacs + cider