Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas
A literal of a Boolean variable is the variable itself or its negation. A clause is a disjunction (OR) of k literals. A formula is a conjunction (AND) of a finite set of clauses. A k-SAT formula is a formula where each clause is a disjunction of k literals. A legal clause is one in which there are no repeated or complementary literals. Using the terminology, the authors say that a formula is simple if it consists of only legal clauses. A configuration formula is not necessarily legal. A SATisfying (SAT) assignment of a formula is a truth assignment of variables for which the formula evaluates to true, i.e., all the clauses evaluate to true.