Bio

Adela Deng is a sophomore in college and she started her exploration in tech not very long ago. She enjoys theoretical computer science as much as applied math.

Computational Essay: Don’t Compel Machines to Compute like a Human: Calculate the Dimension of Snowflake Curve

Project: Shortest Step-by-Step Reduction of Boolean Expressions

Goal

I aim to implement an algorithm that produces a step-by-step reduction of Boolean expressions. Currently, the automated proof-generating framework in the Wolfram Language is unable to give proof of Boolean reductions that are readable by human logicians. My algorithm will be useful for educational purposes.

Summary of Results

1. By recursively pattern matching and applying heuristic logic equivalence rules, I can reduce any Boolean expression to disjunctive or conjunctive normal forms with step-by-step explanation. 2. By a dynamic implementation of Dijkstra’s algorithm, I manage to find the shortest heuristic route of reduction between any two equivalent Boolean expressions. Modifications of Dijkstra’s algorithm: (1) generate new vertices in every iteration (2) start from both end points instead of just one

Future Work

1. Potential improvements in the current algorithm (reduce the runtime of list parsing with other data structures) 2. Assist the exploration of multilevel logic reduction (testing algorithms to minimize the number of operators) 3. Checking the correctness of human proofs (check if a “trivial” step is indeed trivial)