expected$-$output.txt logic.h testing.cpp testlogic.cpp

logic.cpp Makefile testing.h

Now you're ready to start working.

Part $2$: SAT solve like there's no tomorrow

Make sure to watch the introduction video that explains everything! You won't need to write more than $50$ lines of code for this lab, but you'll have to think hard about every line.

SAT solving is the process of taking a Boolean formula and determining whether or not it is satisfiable $-$ that is$,$ whether it is possible to set the variables just right to make the formula be true. For example, the formula $pvv(q^{{?}^{?}}$notr$)$ is satisfiable because you could set $p=T,q=F,$ and $r=F$ and the formula would evaluate to $T.$

In this lab we want to find all the ways to make a formula satisfiable.

Take a look at logic.h and testLogic.cpp$,$ and notice how we're using subclasses of Formula to represent logical formulae. In particular, notice how I build the formula from above in testEval.

Part $2\mathrm{.}1$: Implement evaluate for each Formula subclass

Each logical formula is represented as a tree. The tree in blue below is essentially what $pvv(q^{{?}^{?}}$notr$)$ looks like:

To evaluate any non$-$Var Formula to true or false, you can recursively evaluate its children and combine their result$($s$).$ For example, suppose you're evaluating $Or(x,y),$ where $x$ and $y$ are any Formula. To evaluate the entire $Or(x,y),$ you can evaluate $x$ and $y$ individually first $-$ then you can combine them together using II$,$ since that's what Or means!

To evaluate any non$-$Var Formula to true or false, you can recursively evaluate its children and combine their result$($s$).$ For example, suppose you'r$$ evaluating $Or(x,x),$ where $x$ and $y$ are any Formula. To evaluate the entire $Or(x,y),$ you can evaluate $x$ and $y$ individually first $-$ then you can combine them together using I I, since that's what Or means!

The leaves in Formula trees are always Vars. A Var could stand for anything, so that is why we pass along the var $2$Val map $($shown in green$)$ when we call evaluate $-$ the user must pick ahead of time what each variable's value is$.$ You never change var $2$Val yourself during evaluation, and you keep passing the same var $2$Val map in each recursive call. Evaluating a Var is as simple as looking up its value in the map!

Implement the proper overridden evaluate method for each subclass of Formula.

Part $2\mathrm{.}2$: Implement satSolve and satSolveHelper

These two functions do the actual satisfiability checking, and they'll take the most work to get right. The goal of satSolve is to take a Formula, try every possible combination of values for every variable, and remember each combination that evaluated to true. A solution to a Formula is an assignment of variables that makes the Formula evaluate to true.

The easiest way to do all this is with a recursive helper function.

satSolveHelper takes four parameters:

The Formula you're trying to SAT solve.

The variables you haven't make choices for yet.

The variables you have made choices for $($and the values you're currently trying for them$).$

A reference to the set that contains all the satisfying solutions. Every time you find a new solution, you'll add it to this set.

Read the comments for an in$-$depth explanation of how the recursion needs to work. Here's a quick summary of what happens in each case:

In the base case, you've made choices for each variable in the Formula f$,$ and you're ready to try them qut. If $f$ evaluates to true with your current choices for variables, then you should add the solution to your set of solutions.

In the recursive case, you're still guessing values for each variable. You'll take out a variable $v$ that hasn't been assigned to yet, and make two different recursive calls $-$ you do this because you need to try setting $v$ to true and to false.

Each time you make a recursive call, the number of variables left to choose shrinks by one. That guarantees that you'll never get stuck in an infinite loop!

When you make your initial call to satSolveHelper from inside satSolve, no decisions have been made yet. So$,$ you'll start with a full set of remainingVars and an empty map of choicesForVars.

You can compile with make testLogic and run with $./$testLogic$.$ Compare your output with expected$-$output.txt to know if you're on the right track.

$$

$$