Egységterjedést

Egységterjedést, often translated as "unit propagation" or "unit clause propagation" in English, is a fundamental technique used in automated satisfiability (SAT) solvers and constraint satisfaction problem (CSP) solvers. Its primary purpose is to simplify a propositional logic formula or constraint system by deducing the truth values of variables that are forced by the presence of unit clauses.

A unit clause is a disjunction (OR statement) containing exactly one unassigned literal. A literal is either a propositional variable or its negation. If a formula contains a unit clause, say "x" (meaning variable 'x' must be true), then the solver can immediately deduce that 'x' must be true. This deduction has a cascading effect. If the formula also contains clauses like "¬x ∨ y" (meaning 'x' is false OR 'y' is true), and we've deduced 'x' is true, then '¬x' must be false. For the clause "¬x ∨ y" to be satisfied, 'y' must then be true. Similarly, if a clause was "x ∨ z" and 'x' is deduced to be true, this clause is satisfied regardless of 'z', and 'z' remains unassigned for now.

Egységterjedést efficiently propagates these forced assignments throughout the formula. It systematically identifies unit clauses, assigns the corresponding variable values, and simplifies all other clauses affected by these assignments. This process is repeated until no more unit clauses can be found. Egységterjedést is a crucial component of many modern SAT solvers, significantly speeding up the search for a satisfying assignment or a proof of unsatisfiability. It helps prune the search space and can often resolve parts of the problem without requiring backtracking or more complex inference rules.