Surf Wiki
Save to docs
general/boolean-algebra

From Surf Wiki (app.surf) — the open knowledge base

Implication graph

Directed graph representing a Boolean expression

Directed graph representing a Boolean expression

In mathematical logic and graph theory, an implication graph is a skew-symmetric, directed graph composed of vertex set V and directed edge set E. Each vertex in V represents the truth status of a Boolean literal, and each directed edge from vertex u to vertex v represents the material implication "If the literal u is true then the literal v is also true". Implication graphs were originally used for analyzing complex Boolean expressions.

Applications

A 2-satisfiability instance in conjunctive normal form can be transformed into an implication graph by replacing each of its disjunctions by a pair of implications. For example, the statement (x_0\lor x_1) can be rewritten as the pair (\neg x_0 \rightarrow x_1), (\neg x_1 \rightarrow x_0). An instance is satisfiable if and only if no literal and its negation belong to the same strongly connected component of its implication graph; this characterization can be used to solve 2-satisfiability instances in linear time.

In CDCL SAT-solvers, unit propagation can be naturally associated with an implication graph that captures all possible ways of deriving all implied literals from decision literals, which is then used for clause learning.

References

References

  1. (1979). "A linear-time algorithm for testing the truth of certain quantified boolean formulas". Information Processing Letters.
  2. (2003). "Understanding the Power of Clause Learning".
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

boolean-algebra application-specific-graphs directed-graphs graph-families
Want to explore this topic further?

Ask Mako anything about Implication graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report