Sunday, January 1, 2017

2016 year in review

The methods of propositional logic can be applied to situations that arise from boolean algebra. Boolean formulas are applicable to any boolean algebra structure rather it is booleans themselves or sets, classes, and other predicate like structures. Set theoretic operations like union, intersection, difference, and symmetric difference can be expressed in terms of boolean formulas. These set theoretic operations are not unlike the logical connectives defined by these same boolean formulas.

At the same time, a wide variety of constraint satisfaction problems like sudoku can be expressed in terms of boolean formulas. Boolean formulas defined by clauses that have no more then two elements are equivalent to implication graphs. Backtracking search methods can be used to solve constraint satisfaction problems like sudoku and implications can be used to narrow down the search space for any partial candidate solution in the backtracking search.

The exact solutions to constraint satisfaction problems can therefore be deduced. In the vast majority of cases exact constraint satisfaction methods are not applicable and we need to use heuristics and statistics instead to get approximate solutions to optimization problems.