I do know there are generally used boolean satisfiability problem-solving strategies (comparable to DPLL and so forth.). So far as I do know, such strategies principally rely upon changing boolean expression into the CNF or DNF type. Nevertheless, I am attempting to resolve the given expressions “as-is”, with out conversion to different kinds. So, for boolean expression, I am constructing a tree, consisting of many logical gates (AND, OR, NOT, XOR, VAR, CONST) and attempting to propagate the precise values by making use of boolean legal guidelines.
step 1 – Frequent boolean legal guidelines
In such an method there are some trivial steps like if AND has a price of 1 then the inputs should be each 1 and 1, or if XOR has a price of 1, and one enter is 0, then the second enter should be 1, and so forth. This step I name “propagation of values”, and it’s carried out till there aren’t any values to resolve.
step 2 – Decision by battle
The second step is to assign worth to the random gate, with no worth assigned/resolved but, identify it X quickly, then do “propagation of values”, and observe if within the expression tree some conflicts occurred. By battle, I imply unlawful state of the gate like AND(1,1)->0. So if the battle occurred, this tells us that worth assigned to the X gate is illegitimate, so I can assign the alternative worth, and get again to step one. This step I name “decision by battle”.
step 3 – Decision by commons
The third step is to assign a price of Zero to the random gate, with no worth assigned/resolved but. Carry out “propagation of values”, gather outcomes (the assigned values of gates from the tree), in different phrases, do a “snapshot” of the tree after task. Then again to the unique state earlier than this step, assign a price of 1 to the identical gate, carry out propagation of values, then gather the second “snapshot”, then again to the unique state once more. Now, if the snapshots are each conflict-free, we might take a look at values which might be each the identical within the first and the second snapshot. These values are unbiased of the preliminary gate task and legitimate, so we are able to safely assign them to their gates. This step I name “decision by commons”.
These steps had been examined by me (program in C++) and labored fairly properly.
So, the query is, what different kinds of steps can apply for this type of decision / BSAT fixing? I am asking as a result of there are nonetheless some issues that with these steps I am unable to go additional (algorithm with these steps “see” that’s nothing to do extra).
If one thing is unclear, please let me know within the feedback. Additionally if such an method is thought I am going to be grateful for references or hyperlinks to assets concerning the matter.