Задача булевой выполнимости — задача определения, существует ли присваивание значений true или false переменным, при котором булева формула принимает значение true. Она также известна как SAT и является фундаментальной задачей в логике, решении ограничений и вычислительной сложности.
(Also propositional satisfiability problem; abbreviated SATISFIABILITY or SAT.) The problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, th